对于 $a_0  \times a_1  \times a_2  \times \dots a_{n-1}  \times a_n$,可以通过添加改变运算顺序。

问有多少种不同的运算顺序?
如 $n=3$ 时，用 $1,2,3$ 表示一开始从左到右出现的乘号的编号，通过添加括号有以下 $5$ 种运算顺序
1 2 3 : $a_0 \times a_1 \times a_2 \times a_3 $    先算第一个乘号，再算第二个，其次第三个
1 3 2 : $a_0 \times a_1 \times (a_2 \times a_3)$   先算第一个乘号，再算第三个，其次第二个
2 1 3 : $a_0 \times (a_1 \times a_2) \times a_3$   先算第二个乘号，再算第一个，其次第三个
2 3 1 : $a_0 \times (a_1 \times a_2 \times a_3) $  先算第二个乘号，再算第三个，其次第一个
3 2 1 : $a_0 \times (a_1 \times (a_2 \times a_3))$ 先算第三个乘号，再算第二个，其次第一个

输入格式

输入 $n$ 表示 $n$ 个乘号，即 $n+1$ 个数连乘。

输出格式

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

数据范围

$0 < n < 31$

样例输入

3

样例输出

5

提示