問題描述
我們把一個數(shù)稱為有趣的，當(dāng)且僅當(dāng)：
1. 它的數(shù)字只包含0, 1, 2, 3，且這四個數(shù)字都出現(xiàn)過至少一次。
2. 所有的0都出現(xiàn)在所有的1之前，而所有的2都出現(xiàn)在所有的3之前。
3. 最高位數(shù)字不為0。
因此，符合我們定義的最小的有趣的數(shù)是2013。除此以外，4位的有趣的數(shù)還有兩個：2031和2301。
請計(jì)算恰好有n位的有趣的數(shù)的個數(shù)。由于答案可能非常大，只需要輸出答案除以1000000007的余數(shù)。
輸入格式
輸入只有一行，包括恰好一個正整數(shù)n (4 ≤ n ≤ 1000)。
輸出格式
輸出只有一行，包括恰好n 位的整數(shù)中有趣的數(shù)的個數(shù)除以1000000007的余數(shù)。
樣例輸入
4
樣例輸出
3
以上為題目描述，（垃圾的我的）分析思路：由1,2,3條約束不難得到數(shù)的開頭必須是2，剩余的n-1位中至少有1個1，1個0，1個3，由于0，1的順序固定，0必須在1前，所以只要知道0和1的個數(shù)的總和，假設(shè)0，1總共有k個，就可以知道0，1的排列種數(shù)為k-1種，所以現(xiàn)在只需考慮2，3的位置和個數(shù)，一開始我想從2的個數(shù)入手，后來發(fā)現(xiàn)這樣會有重復(fù)的情況難以計(jì)算，然后改用從最后一個2的位置入手，然后確定2，3的個數(shù)以及排列的種數(shù)，乘上0，1的排列種數(shù)，最后各種情況求和。最后得了10分。。。。。。全程覺得這是一道考組合數(shù)學(xué)的題。然而，知道真相的我眼淚掉下來。
然后看了幾篇博客，發(fā)現(xiàn)這個問題的正解是定義狀態(tài)，尋找遞推公式，然后得到答案
