TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

93.9% (62/66)

Submission's AC Ratio

34.2% (90/263)

Tags

Description

ayu是住在北方小鎮的一個女孩,平時最喜歡在商店街散步,然後去商店街最深處的一家鯛魚燒店買熱騰騰的鯛魚燒吃。

雖然說是小鎮,其實這個小鎮還蠻大的,ayu可以每天換一條不一樣的路線走去鯛魚燒店,走了一個多月還沒重複。走著走著她想到一個問題:這個小鎮有很整齊的棋盤狀街道,如果把ayu的出發點當做座標原點 (0, 0),商店街的位置在 (n, 2n)。如果每天都選不一樣的路,而且走最短路線(只能向北和東走),要幾天才能走完所有的路線呢?

雖然心智年齡只有十歲,聰明的 ayu 馬上就算出有 C(3n, n) 種走法。當 n 很大的時候,就算走一輩子也走不完。所以 ayu 想要對路線再加一點條件限制,讓可以挑的路線少一點:在 (0, 0) 到 (n, 2n) 間連一條直線,ayu 走的路只能在這條線的下方,可以踩到線,但是不能超過。加了限制之後問題突然變的很複雜,超過 ayu 的能力範圍,聰明的你能不能幫他計算呢?

Input Format

輸入檔包含多組測試資料,每一組測試資料一行,每行一個整數n (1 ≦ n ≦ 10000)。讀到 n = 0 的時候代表測試檔案的結尾,不需要對於這個數字作任何輸出。

Output Format

對每組測試資料,輸出ayu到鯛魚燒店可能的路線數。如果答案超過10000,只要輸出最後四位數就好。

Ex: n=2時有3種走法如下圖

Sample Input 1

1
2
3
0

Sample Output 1

1
3
12

Hints

Problem Source

原TIOJ1103 / NPSC2006決賽(prob F)

Subtasks

No. Testdata Range Score
1 0 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 65536 262144 1