我们把一个数称为有趣的，当且仅当：
- 它的数字只包含 0,1,2,3且这四个数字都出现过至少一次。
- 所有的 0都出现在所有的 1 之前，而所有的 2 都出现在所有的 3 之前。
- 最高位数字不为 0。
因此，符合我们定义的最小的有趣的数是 2013。
除此以外，4 位的有趣的数还有两个：2031 和 2301。
请计算恰好有 n 位的有趣的数的个数。
由于答案可能非常大，只需要输出答案除以 10^9 7 的余数。
输入格式
输入只有一行，包括恰好一个正整数 n。
输出格式
输出只有一行，包括恰好 n 位的整数中有趣的数的个数除以 10^9 7 的余数。
数据范围
4≤n≤1000
输入样例：
代码语言：javascript复制4输出样例：
代码语言：javascript复制3思路：
考察有限状态机的转移：
我们不难发现只有六种情况：
0：只用了2
1: 只用了2、0
2：只用了2、3
3: 只用了2、0、3
4：只用了2 、0、1
5: 只用了2、0、1、3
可以用线性dp dp[n][i] 1<=i<=5 表示有n位 处于状态i的数目
状态转移我们随便举个例子分析一下，其他也是同样道理
比如dp[i][5]=(dp[i-1][3]%mod dp[i-1][4]%mod dp[i-1][5]*2%mod)%mod; 因为前面2013全有 所以下一位只能放 1 3；也可能是4状态转移过来 那就是填3；也可能是3状态填1转移过来
代码语言：javascript复制#include<bits/stdc .h>
using namespace std;
const int N=1010,mod=1e9 7;
int dp[N][6],n;
int main(){
cin>>n;
dp[1][0]=1;
for(int i=2;i<=n;i ){
dp[i][0]=dp[i-1][0]%mod;
dp[i][1]=(dp[i-1][0]%mod dp[i-1][1]*2%mod)%mod;
dp[i][2]=(dp[i-1][0]%mod dp[i-1][2])%mod;
dp[i][3]=(dp[i-1][1]%mod Xdp[i-1][2]%mod dp[i-1][3]*2%mod)%mod;
dp[i][4]=(dp[i-1][1]%mod dp[i-1][4]*2%mod)%mod;
dp[i][5]=(dp[i-1][3]%mod dp[i-1][4]%mod dp[i-1][5]*2%mod)%mod;
}
cout<<dp[n][5]%mod<<endl;
}
