Background

Special for beginners, ^_^

Description

Catalan数列在组合数学中有许多重要的应用，卡塔兰数数满足递归式：

h(n)= h(0)*h(n-1) + h(1)*h(n-2) + ... + h(n-1)h(0) (其中$n\gt2$),这是n阶递推关系;

还可以化简为1阶递推关系: 如h(n)=h(n-1)*(4n-2)/(n+1)(n>1) h(0)=h(1)=1</b>

现在请你计算出这个数列的第n项C(n)的值。

Format

Input

第1行：1个整数n($2\lt n \lt 30$)

Output

第1行：1个整数,表示C(n)的值。答案要用long long存。

Samples

5

5

Limitation

1s, 1024KiB for each test case.