1244 . 序列問題 Sequences
TopCoder
Tags
Description
有n個正整數排成一列。對於所有大於1的正整數K，如果K出現在這個數列時，K-1也出現在這個數列，並且所有的K-1都會出排在最後一個K的前面，那我們認為這個數列是個不錯的「成長數列」。
給你n的值，請問有多少個長度為n的、不錯的「成長數列」呢？
啊，對了，數量可能有很多，你只要輸出答案除以100000007的餘數就可以了！
Input Format
一個輸入檔只包含一個正整數n。(1<=n<=10,000)
Output Format
請輸出合理的「成長數列」個數除以100000007的餘數。
Sample Input 1
3
Sample Output 1
5
Hints
合理的成長數列有：111,112,122,212,123這五個。
※2008/03/02題目敘述修正：感謝shik。
Problem Source
原TIOJ1244 / Adapted from IMO 2002 shortlist C3。Problem Setter：tmt514。
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 14 |
| 2 | 1 | 14 |
| 3 | 2 | 14 |
| 4 | 3 | 14 |
| 5 | 4 | 14 |
| 6 | 5 | 14 |
| 7 | 6 | 16 |