TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

96.4% (27/28)

Submission's AC Ratio

69.4% (100/144)

Description

現在有一個$N\times N$的白色棋盤,但其中左上到右下的對角線上所有格子都被塗成黑色,如下圖。

有一個古老的遊戲是,拿著棋子從左上角開始,每次只能往右或往下移動一格,最後移到右下角為止,而你獲得的分數就是經過的黑色格子數量(起、終點都算)。當然,這個遊戲看起來十分的無聊,因此聰明的小明決定試著把所有符合規則的不同路徑全部各玩過一次。

小明很好奇當他玩完所有的可能的路徑之後,他每一局的分數全部加起來會是多少。但是因為路徑實在是太多了,所以他只想知道分數總和$\mod 10^ 9+7$的結果。你可以寫個程式幫他計算嗎?

Input Format

輸入第一行有一個正整數$T$,代表測資筆數。
接下來$T$行,每行包含一個正整數$N$,代表詢問大小為$N$的方陣。

Output Format

對於每筆測資,請輸出一行包含一個正整數,代表分數總和$\mod 10^ 9+7$的結果。

Sample Input

2
2
1

Sample Output

4
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

Testdata and Limits

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