在寬度為n的照片中,總共有多少種不同的山稜線呢 ?
為了簡化問題,一段長度為n的山稜線將由許多寬度為1的片段構成。
同時在每個片段當中,山稜線不是45度斜向上就是45度斜向下。
當然,相鄰兩個片段的山稜線必須連續,而且山稜線的兩端必須貼齊地平線。
此外,山稜線的任何一部分都不能低於地平線(即照片底端)。
舉例來說,以下就是一個合法的山稜線:
/\ /\
/\ / \/\ /\/\/ \
/ \/\/ \/ \
因為答案可能很大,所以你只要輸出山稜線數量除以1,000,000,007的餘數即可。
輸入的第一行是一個正整數T ( 1≦T≦100,000 ),代表接下來有T筆測資,
接下來的T行,每行會有一個正整數 n ( 1≦n≦1,000,000 ),代表照片的寬度。
你可以假設n一定會是偶數。
對於每筆測資輸出一行,代表寬度n的照片中,山稜線的數量除以1,000,000,007的餘數。
其實有 60% 的測試資料 n≦10,000
原TIOJ1607 / Problem Setter: suhorng
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 |