原題鏈接：有趣的數(shù)。

問題描述：參見上文。

問題分析：這是一個計算問題，關(guān)鍵在于找到一個遞推式。只要找到一個遞推式，問題就解決了。有時候這類問題也用DP（動態(tài)規(guī)劃）來解決。

根據(jù)題意，有趣的數(shù)滿足以下約束條件如下：

1.只包含數(shù)字0、1、2和3

2.0、1、2和3各自至少出現(xiàn)一次

3.所有的0都出現(xiàn)在1之前

4.所有的2都出現(xiàn)在3之前

5.最高位數(shù)字不為0

數(shù)（字符串）可以分為以下六種情況（或稱為狀態(tài)）：

1.只包含數(shù)字2，記為S₁

2.只包含數(shù)字2和0（0開始的數(shù)0個，以此數(shù)為前綴的數(shù)均不是以0開始），記為S₂

3.只包含數(shù)字2和3，記為S₃

4.只包含數(shù)字2、0和1，并且滿足所有0在1之前，記為S₄

5.只包含數(shù)字2、0和3，并且滿足所有2在3之前，記為S₅

6.包含任意數(shù)字（包含0、1、2和3），滿足所有0在1之前，滿足所有2在3之前，記為S₆

考慮遞推式：

1.對于S₁，考慮其長度l，定義f(l,S₁)為長度l的S₁數(shù)的數(shù)量，則f(l,S₁)＝１。也就是說長度為l的只包含2的數(shù)只有1個。

2.對于S₂，考慮其長度l，定義f(l,S₂)為長度l的S₂數(shù)的數(shù)量，當(dāng)l=1則那么f(l,S₂)=0，即f(1,S₂)=0，當(dāng)l>1則f(l,S₂)=f(l-1,S₂)*2+f(l-1,S₁)。這是因為，長度為l的S₂數(shù)可以是由長度為l-1的S₂的數(shù)加上2或0構(gòu)成，例20為長度為2的S₂數(shù)，那么202和200為長度為3的S₂數(shù)；另外，長度為l的S₂數(shù)可以是由長度為l-1的S₁的數(shù)加上0構(gòu)成，例如22為長度為2的S₁數(shù)，那么220為長度為3的S₂數(shù)。

3.對于S₃，考慮其長度l，定義f(l,S₃)為長度l的S₃數(shù)的數(shù)量，當(dāng)l=1則那么f(l,S₃)=0，即那么f(1,S₃)=0，當(dāng)l>1則f(l,S₃)=f(l-1,S₃)*2+f(l-1,S₁)。這是因為，長度為l的S₃數(shù)可以是由長度為l-1的S₃的數(shù)加上2或3構(gòu)成，例23為長度為2的S₃數(shù)，那么232和233為長度為3的S₃數(shù)；另外，長度為l的S₃數(shù)可以是由長度為l-1的S₁的數(shù)加上3構(gòu)成，例如22為長度為2的S₁數(shù)，那么223為長度為3的S₃數(shù)。

4.對于S₄，考慮其長度l，定義f(l,S₄)為長度l的S₄數(shù)的數(shù)量，當(dāng)l=1則那么f(l,S₄)=0，即f(1,S₄)=0，當(dāng)l>1則f(l,S₄)=f(l-1,S₄)*2+f(l-1,S₂)+f(l-1,S₃)。這是因為，長度為l的S₄數(shù)可以是由長度為l-1的S₄的數(shù)加上2或1構(gòu)成（滿足所有0在1之前，不可以加上0），例201為長度為3的S₄數(shù)，那么2012和2011為長度為4的S₄數(shù)；另外，長度為l的S₄數(shù)可以是由長度為l-1的S₂的數(shù)加上1構(gòu)成，例如20為長度為2的S₂數(shù)，那么201為長度為3的S₄數(shù)。

同理，對于S₅和S_{6，可以得到相應(yīng)的遞推公式。詳細(xì)參見以下的源程序。}

_{有了遞推式，程序就可以根據(jù)遞推式，逐步進(jìn)行計算。}

程序說明：（略）。

提交后得100分的C++語言程序如下：

/* CCF201312-4 有趣的數(shù) */#include <iostream>#include <cstring>using namespace std;const long long MOD = 1000000007;const int MAXN = 1000;const int MAXS = 5;long long status[MAXN+1][MAXS+1];int main(){    int n;    cin >> n;    memset(status, 0, sizeof(status));    // DP    status[1][0] = 1;    for(int i=2; i<=n; i++) {        status[i][0] = 1;        status[i][1] = (status[i - 1][1] * 2 + status[i - 1] [0]) % MOD;        status[i][2] = (status[i - 1][2] + status[i - 1][0]) % MOD;        status[i][3] = (status[i - 1][3] * 2 + status[i - 1][1] ) % MOD;        status[i][4] = (status[i - 1][4] * 2 + status[i - 1][1] + status[i - 1][2]) % MOD;        status[i][5] = (status[i - 1][5] * 2 + status[i - 1][3] + status[i - 1][4]) % MOD;    }    cout << status[n][5] << endl;    return 0;}