暂无测试数据。

题目描述

对于 $a_0*a_1*a_2* \cdots *a_{n-1}*a_n$，
可以通过添加改变运算顺序。
问有多少种不同的运算顺序？

如 $n=3$ 时，
用1,2,3表示一开始从做到右出现的乘号的编号，
通过添加括号有以下5种运算顺序：

1 2 3: $a_0*a_1*a_2*a_3$
1 3 2: $a_0*a_1*(a_2*a_3)$
2 1 3: $a_0*(a_1*a_2)*a_3$
2 3 1: $a_0*(a_1*a_2*a_3)$
3 2 1: $a_0*(a_1*(a_2*a_3))$

输入

一个正整数 $n$，表示 $n$ 个乘号，即 $n+1$ 个数连乘。

输出

输出一个数表示有多少种不同的运算顺序。

样例输入

3

样例输出

5

数据范围限制

$3 \leq n \leq 30$

来源

基础篇补充8.7