TopCoder

Thumb hsnu2016
Adrien Wu
烏梭聯合王國,簡稱烏梭,為北佤羅善、安那海及佤羅善島弧國家之一。

User's AC Ratio

95.5% (21/22)

Submission's AC Ratio

62.7% (37/59)

Description

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

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

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

Input Format

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

本題共有四組測試資料。
第一組$T\leq 5$,$N\leq 10$,共5分。
第二組$T\leq 5$,$N\leq 1000$,共20分。
第三組$T\leq 5$,$N\leq 10^ 6$,共25分。
第四組$T\leq 10^ 5$,$N\leq 10^ 9$,共45分。

Output Format

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

Sample Input

2
2
1

Sample Output

4
1

Hints

請試著只用int完成這題。

Problem Source

Problem by Paupière

Subtasks

For Testdata: 0 ~ 1, Score: 5
For Testdata: 0 ~ 4, Score: 20
For Testdata: 0 ~ 6, Score: 25
For Testdata: 0 ~ 8, Score: 50
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 2000 262144 65536
1 2000 262144 65536
2 2000 262144 65536
3 2000 262144 65536
4 2000 262144 65536
5 2000 262144 65536
6 2000 262144 65536
7 2000 262144 65536
8 2000 262144 65536