TopCoder

User's AC Ratio

75.0% (3/4)

Submission's AC Ratio

27.3% (3/11)

Description

一座山的山稜線由許多片段的45度斜坡構成,每一個片段不是上坡就是下坡。

          *
   *   *  /\
*  /  /\/  \
/\/  \/      \

在我們眼前的所見的任何寬度為n個單位的山稜形狀,可以輕鬆地觀察到所有山頂的位置。

請問有多少種山稜線的形狀,使得所有山頂的位置由左而右非遞減呢?

所有的山稜線都必須完整,也就是說左右兩端都必須是高度為0的山腳,而且不能有任何山谷的位置隱沒在地平線底下。

Input Format

輸入僅包含一個數字n,n一定會是偶數,因為會有相同片段數量的上坡以及下坡。

Output Format

請輸出山頂位置由左而右非遞減的山稜線形狀總數。
由於答案可能很大,你只要輸出以十進位表示時,它的最後9位數即可。

Sample Input

6

Sample Output

4

Hints

佔總分20%的測試數據中 n<=60
佔總分40%的測試數據中 n<=200
佔總分100%的測試數據中 n<=3000

Problem Source

原TIOJ1471 / CSAPC'08 Problem Setter: Tmt, Seanwu

Subtasks

For Testdata: 0 ~ 0, Score: 9
For Testdata: 1 ~ 1, Score: 9
For Testdata: 2 ~ 2, Score: 9
For Testdata: 3 ~ 3, Score: 9
For Testdata: 4 ~ 4, Score: 9
For Testdata: 5 ~ 5, Score: 9
For Testdata: 6 ~ 6, Score: 9
For Testdata: 7 ~ 7, Score: 9
For Testdata: 8 ~ 8, Score: 9
For Testdata: 9 ~ 9, Score: 9
For Testdata: 10 ~ 10, Score: 10
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 11000 65536 65536
1 11000 65536 65536
2 11000 65536 65536
3 11000 65536 65536
4 11000 65536 65536
5 11000 65536 65536
6 11000 65536 65536
7 11000 65536 65536
8 11000 65536 65536
9 11000 65536 65536
10 11000 65536 65536