TopCoder

Thumb 1
羽瀨川小鷹
我是布丁

User's AC Ratio

100.0% (41/41)

Submission's AC Ratio

69.3% (79/114)

Tags

Description


在寬度為n的照片中,總共有多少種不同的山稜線呢 ?

為了簡化問題,一段長度為n的山稜線將由許多寬度為1的片段構成。
同時在每個片段當中,山稜線不是45度斜向上就是45度斜向下。
當然,相鄰兩個片段的山稜線必須連續,而且山稜線的兩端必須貼齊地平線。
此外,山稜線的任何一部分都不能低於地平線(即照片底端)。

舉例來說,以下就是一個合法的山稜線:

        /\          /\
 /\    /  \/\  /\/\/  \
/  \/\/      \/        \
因為答案可能很大,所以你只要輸出山稜線數量除以1,000,000,007的餘數即可。

Input Format

輸入的第一行是一個正整數T ( 1≦T≦100,000 ),代表接下來有T筆測資,
接下來的T行,每行會有一個正整數 n ( 1≦n≦1,000,000 ),代表照片的寬度。
你可以假設n一定會是偶數。

Output Format

對於每筆測資輸出一行,代表寬度n的照片中,山稜線的數量除以1,000,000,007的餘數。

Sample Input

Sample Input #1
1
6

Sample Input #2
3
2
16
40

Sample Output

Sample Output #1
5

Sample Output #2
1
1430
564120378

Hints

其實有 60% 的測試資料 n≦10,000

Problem Source

原TIOJ1607 / Problem Setter: suhorng

Subtasks

No. Testdata Range Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 10
8 7 10
9 8 10
10 9 10

Testdata and Limits

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