为了完成魔法仪式，还需要建造一个魔法祭坛。魔法祭坛是一个 3∗n3*n3∗n 的建筑，现在 zzj 和 liaoy 手上有无限多的 1∗1,1∗2,2∗11*1, 1*2, 2*11∗1,1∗2,2∗1 三种不同规格的魔法建筑材料。现在需要知道用这三种建筑材料一共有多少种建造出 3∗n3*n3∗n 的祭坛的方法。
输入包含一个整数 nnn。
输出一个整数，表示一共有多少种方法。
答案可能过大，输出答案对 1e9+71e9+71e9+7 取模后的结果。
1
3
4
823
1≤n≤1,000,0001 \leq n \leq 1,000,0001≤n≤1,000,000
对于样例 1 ，一共有三种建造方案，分别是：ABC, AAB, ABB。
对于 n=2n=2n=2 也提供两种方案作为参考：
ABB AAB ACD CCD
其中不同字母代表不同建筑材料。