2013年7月7日 星期日

10843 - Anne's game


Problem D
Anne's game
Time Limit: 2 seconds

一個名為 Anne Spetring 小女孩喜歡玩一個遊戲,她在一張紙上畫圈圈,然後再畫一個圈圈,並且將其與第一個圈圈連線,接著隨後畫的圈圈都將與前次其中一個圈圈連線,直到畫了 n 個圈圈,而每個圈圈、連線不會相交,最後她將把每個圈圈隨機地標上 1 到 n 的採用隨機的順序。

有多少不同的圖片,在她畫出 n 個圈圈的中?兩張圖片不同的定義為兩個有連線的圈圈是不同的。

Input
第一行 將會有一個整數 N 表示接下來將會有幾筆測資,
接下來每行會有一個整數 n (0<n<=100).

Output 
對於每組測資,輸出一行  "Case #x:" 以及 mod 2000000011 之後的結果。

Sample Input Sample Output
3
1
2
3
Case #1: 1
Case #2: 1
Case #3: 3

Problemsetter: Igor Naverniouk