你手上有一份拼图需要完成。
具体地说，有 3×n3\times n3×n 个空格子，初始状态下这些空格子上没有东西。你手上有两种大小为 333 个格子的零片（如下图所示，实际上也就只有这两种），各有无数个，你可以将它们任意旋转后拼到图里。
请问一共有多少种方案能使你填满所有格子。
一行一个正整数 nnn 。
一行一个正整数代表答案。由于答案可能很大，你需要对 109+710^9+7109+7 取模。
2
3
10000
18474502
对于 100%100\%100% 的数据， n≤1018n\le 10^{18}n≤1018
