矩阵快速幂。
一开始的思路是$dfs$出一个矩阵，$k[i][j]$表示这一行是状态$i$，将这一行填满，下一行是$j$状态的方案数。然后就可以矩阵快速幂了，但是矩阵大小是$16*16$的，超时了......
仔细观察后会发现，第$0$行状态为$0$，因此往后填充的过程中，并不会出现16种情况，只会在6种状态之间转移：$0000$，$1111$，$1100$，$0011$，$0110$，$1001$。那么只要构造$6*6$的矩阵就可以了。
#includeusing namespace std;const int mod = 1e9 + 7;int k[6][6];long long n;map ans;struct M { int r; int c; int a[6][6];};M mul(const M &a, const M &b) { M res; res.r = a.r; res.c = b.c; memset(res.a, 0, sizeof res.a); for(int j = 0; j < res.c; j ++) { for(int k = 0; k < a.c ; k ++) { if(b.a[k][j] == 0) continue; for(int i = 0; i < res.r; i ++) { long long u = (long long)a.a[i][k] * (long long)b.a[k][j] % (long long)mod; res.a[i][j] = (res.a[i][j] + (int)u) % mod; } } } return res;}void init() { memset(k, 0, sizeof k); /* 0 | 0000 1 | 1111 2 | 1100 3 | 0011 4 | 0110 5 | 1001 */ k[0][0] ++; k[0][1] ++; k[0][2] ++; k[0][3] ++; k[0][5] ++; k[1][0] ++; k[2][0] ++; k[2][3] ++; k[3][0] ++; k[3][2] ++; k[4][5] ++; k[5][4] ++; k[5][0] ++;}void work(long long p) { M a; memset(a.a, 0, sizeof a.a); a.r = 6; a.c = 6; for(int i = 0; i < 6; i ++) { a.a[i][i] = 1; } M b; b.r = 6; b.c = 6; for(int i = 0; i < 6; i ++) { for(int j = 0; j < 6; j ++) { b.a[i][j] = k[i][j]; } } M c; memset(c.a, 0, sizeof c.a); c.r = 1; c.c = 6; c.a[0][0] = 1; while(p) { if(p & 1) { p --; a = mul(a, b); } p = p >> 1; b = mul(b, b); } c = mul(c, a); ans[p] = c.a[0][0]; printf("%d\n", c.a[0][0]);}int main() { init(); while(~scanf("%lld", &n)) { work(n); } return 0;}