题目描述

对于连乘$a_0*a_1*a_2*…*a_n$,加了括号后可改变它的运算顺序。

问:有多少种不同的运算顺序?

输入格式

一个整数n

输出格式

一个整数表示答案

样例

3

5

样例解释

n=3时有如下运算顺序:

$a_0*a_1*a_2*a_3,a_0*(a_1*a_2)*a_3,a_0*a_1*(a_2*a_3),a_0*(a_1*a_2*a_3),a_0*(a_1*(a_2*a_3))$

一共有5种

8

1430

数据范围

$n \le 26$

来源

• 信息学奥赛之数学一本通
• stong9070整理