1 有趣的数：（动态规划，状态转移）
 2 #include<stdio.h>
 3 int dp[6][1001];
 4 int main()
 5 {
 6     int n,i;
 7     for(i=0; i<6; i++)
 8         dp[i][0]=0;
 9     while(~scanf("%d",&n))
10     {
11         for(i=1; i<=n; i++)
12         {
13             dp[0][i]=1;
14             dp[1][i]=dp[0][i-1]+dp[1][i-1];
15             dp[2][i]=dp[0][i-1]+dp[2][i-1]*2;
16             dp[3][i]=dp[1][i-1]+dp[2][i-1]+dp[3][i-1]*2;
17             dp[4][i]=dp[1][i-1]+dp[4][i-1]*2;
18             dp[5][i]=dp[3][i-1]+dp[4][i-1]+dp[5][i-1]*2;
19         }
20         printf("%d\n",dp[5][n]%1000000007);
21     }
22     return 0;
23 }