拙见

#include <iostream>

using namespace std;

const int N = 1e7 + 10, MOD = 1e9 + 7;

int n;
// st[j][k]: 第i列状态j是否可以转移到状态k
bool st[4][4] = {
    {true, true, true, true},
    {false, false, true, true},
    {false, true, false, true},
    {true, false, false, false}};
int f[N][4]; // 前i-1列已摆满，第i列状态为j的所有方案数

int main()
{
    cin >> n;

    f[1][0] = 1;
    for(int i = 1; i <= n; i++)
        // 若第i列状态j能转移到状态k,则第i+1列的合法方案数++
        for(int j = 0; j < 4; j++)
            for(int k = 0; k < 4; k++)
                if(st[j][k])
                    f[i + 1][k] = (f[i + 1][k] + f[i][j]) % MOD;

    cout << f[n + 1][0];

    return 0;
}