题解

题面描述

给定一个正整数 $n$ 表示密码长度，要求密码恰好有 $n$ 位，且密码字符必须来自以下 $4$ 个集合中的至少 $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$ 取模输出

输入

输出

输入

输出