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



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



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