题解

题面描述

给定一个正整数 $n$ 表示密码长度，要求密码恰好有 $n$ 位，且密码字符必须来自以下 $4$ 个集合中的至少 $3$ 个：

• 大写字母：$\{A, B, \dots, Z\}$（共 $26$ 个）
• 小写字母：$\{a, b, \dots, z\}$（共 $26$ 个）
• 数字：$\{0,1,2,3,4,5,6,7,8,9\}$（共 $10$ 个）
• 特殊字符：$\{'.','!','?'\}$（共 $3$ 个）

题目内容

小红正在接受一项密码制作工作。

一个安全的密码要求是：

1.刚好为 $n$ 位。

2.种类应该至少包含以下中的任意 $3$ 个或者 $3$ 以上：

A.大写字母，即'$A$'到'$Z$'

B.小写字母，即'$a$'到'$z$'

C.数字，即 {$0,1,2,3,4,5,6,7,8,9$}。

D.特殊字母，仅包含{$'.','!','?'$}。

现在小红给定一个整数 $n$ ，请你帮助她判断有多少种加密方法使得其是一个安全的密码,由于结果可能很大，对 $10^9+7$ 取模后输出。

输入描述

一个整数 $n(1 ≤ n ≤2 × 10^6)$ ，表示密码长度。

输出描述

一个整数，表示安全的密码的方案总数，结果对 $10^9+7$ 取模输出

样例1

输入

1

输出

0

样例2

输入

3

输出

62088