动态规划

数组表示长度为下标且选了这几个数的数量 我们可发现 _0和_01不合法因为首个数字不为0，在剩下的所有状态中进行转移，只选了2的情况值就是1，不用转移。
选了2、3的情况可以由只选了2的情况后面添一个3或者选了2、3的情况后面添上3转移来。
选了0、2的情况可以由只选了2的情况后面添一个0或者选了0、2的情况后面添上0或2。
选了0、2、1的情况可以由选了0、1的情况后面添一个2或者选了0、2、1的情况后面添一个2或1。
选了0、2、3的情况可以由选了0、2的情况添个3，2、3的情况添个0，0、2、3的情况添个0或3。
选了0，1，2，3的情况可以由选了0、2、1的情况添个3，0、2、3的情况添个1，0，1，2，3的情况添个1或3。

转移说的很清楚了，直接跑一边就行，复杂度o(n)。

#include <bits/stdc++.h>
#define int long long
#define MAXN 500005
using namespace std;
const int MOD=1e9+7;
int _2=1;
int _23[MAXN];
int _02[MAXN];
int _021[MAXN];
int _023[MAXN];
int _0123[MAXN];
signed main()
{
    int n;cin>>n;
    for(int i=2;i<=n;i++)
    {
        _23[i]=_2+_23[i-1],_23[i]%=MOD;
        _02[i]=_2+_02[i-1]*2,_02[i]%=MOD;
        _021[i]=_021[i-1]*2+_02[i-1],_021[i]%=MOD;
        _023[i]=_023[i-1]*2+_02[i-1]+_23[i-1],_023[i]%=MOD;
        _0123[i]=_0123[i-1]*2+_021[i-1]+_023[i-1],_0123[i]%=MOD;
    }
    cout<<_0123[n];
}