503006 - 棋盘

【题目描述】棋盘(chessboard)

有一个棋盘,从起点(0,0)走到终点(n,n)的最短路径数是C(2n,n),现在如果不穿越对角线(但可接触对角线上的格点),这样的路径数有多少?

Input

每次输入一个数n(1≤n≤35),当n等于-1时结束输入。

Output

对于每个输入数据输出路径数。

Examples

Input

1 
3
12 
-1

Output

1 1 2
2 3 10
3 12 416024
Time Limit 1 second
Memory Limit 128 MB
Stats
上一题 下一题