2004 . 棋盤遊戲 (Board)
TopCoder
Tags
Description
現在有一個$N\times N$的白色棋盤，但其中左上到右下的對角線上所有格子都被塗成黑色，如下圖。
有一個古老的遊戲是，拿著棋子從左上角開始，每次只能往右或往下移動一格，最後移到右下角為止，而你獲得的分數就是經過的黑色格子數量（起、終點都算）。當然，這個遊戲看起來十分的無聊，因此聰明的小明決定試著把所有符合規則的不同路徑全部各玩過一次。
小明很好奇當他玩完所有的可能的路徑之後，他每一局的分數全部加起來會是多少。但是因為路徑實在是太多了，所以他只想知道分數總和$\mod 10^ 9+7$的結果。你可以寫個程式幫他計算嗎？
Input Format
輸入第一行有一個正整數$T$，代表測資筆數。
接下來$T$行，每行包含一個正整數$N$，代表詢問大小為$N$的方陣。
Output Format
對於每筆測資，請輸出一行包含一個正整數，代表分數總和$\mod 10^ 9+7$的結果。
Sample Input 1
2
2
1
2
1
Sample Output 1
4
1
1
Hints
請試著只用int完成這題。
Problem Source
Problem by Paupière
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | $T\leq 5$，$N\leq 10$ | 5 |
| 2 | 0~4 | $T\leq 5$，$N\leq 1000$ | 20 |
| 3 | 0~6 | $T\leq 5$，$N\leq 10^ 6$ | 25 |
| 4 | 0~8 | $T\leq 10^ 5$，$N\leq 10^ 9$ | 50 |