积木画

#include<bits/stdc++.h>
using namespace std;
const int N=1e7+10,P=1000000007;

int n;

int f[N][4];
int g[4][4]={
    {1,1,1,1},
    {0,0,1,1},
    {0,1,0,1},
    {1,0,0,0}
};//二维数组表示状态转移，第一维表示第i列的状态，第二维表示第j列的状态，并且j=i+1。如果第二维的数字表示是1，就表示由第i的状态可以得到第j列的状态
 
int main()
{
    scanf("%d",&n);
    
    f[0][0]=1;//第一列什么都不放
    
    for(int i=1;i<=n;i++)
    for(int j=0;j<4;j++)
    for(int k=0;k<4;k++)
    f[i][j]=(f[i][j]+f[i-1][k]*g[k][j])%P;
    
    printf("%d",f[n][0]);//第n+1列什么都不放
    
    return 0;
}