暂无测试数据。

题目描述

对于 \(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