User's AC Ratio

100.0% (26/26)

Submission's AC Ratio

68.8% (53/77)

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

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