TopCoder

Thumb maxresdefault
YenSean
Hello World!

User's AC Ratio

85.7% (6/7)

Submission's AC Ratio

34.6% (9/26)

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

3

Sample Output

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 10000 65536 262144 1
1 10000 65536 262144 2
2 10000 65536 262144 3
3 10000 65536 262144 4
4 10000 65536 262144 5
5 10000 65536 262144 6
6 10000 65536 262144 7