TopCoder

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

User's AC Ratio

95.5% (21/22)

Submission's AC Ratio

50.8% (31/61)

Description

抓寶網路公司正在幫和平社區規劃新一代的網路架構,該社區的網路平面架構圖如下,其中有編號的頂點代表網路設備的位置,兩個相鄰頂點之間有一虛線段連接,線段部分代表可以鋪設網路光纖的路線,網路設備可以透過光纖連結起來。

工程師發現只要用5 段光纖就可以將這6 個設備連接起來,下圖為兩種可能的連結方法,事實上還有其他連結的方式。工程師想知道總共會有幾種相異的連結方法,可以用最少的線段把所有的網路設備連結起來。

一般而言可將上述平面架構圖延伸為2N (N ≥ 3)個頂點,上排頂點的編號為1 到N,下一排的頂點編號由N+1 至2N,其中頂點I (1 ≤ I ≤ N)與頂點I+N 相鄰,另外對於頂點I (1 < I < N, N+1 < I < 2N) 分別與頂點I-1 及 I+1 相鄰。請寫一程式,幫工程師計算出總共有幾種相異的連結方法。因答案可能很大,程式輸出的答案為「原始答案」除以$10^ 9+9$的餘數。

Input Format

第一列為一個正整數 T,代表測試資料的個數,T ≤ 10。接下來的 T 列,每一列有一個正整數 N,1 ≤ N ≤ 100。

Output Format

每筆測試資料各有一列輸出,即所有相異連結的總數,因答案可能很大,只要輸出原始答案除以$10^ 9+9$ 的餘數即可。

Sample Input

3
1
2
3

Sample Output

1
4
15

Hints

本題共有二個子題,每一子題可有多筆測試資料:
第一子題的測試資料 T ≤ 5,N ≤ 5,全部解出可獲31 分;
第二子題的測試資料 T ≤ 10,N ≤ 100,全部解出可獲69 分。

Problem Source

105學年度高級中學資訊學科能力競賽決賽 程式設計試題第二題

Subtasks

For Testdata: 0 ~ 0, Score: 31
For Testdata: 1 ~ 1, Score: 69
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 524288 65536
1 1000 524288 65536