多重幂计数问题

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

设给定n个变量x1 , x2 ,…, xn 。将这些变量依序作底和各层幂,可得n重幂如下:
 
这里将上述n重幂看作是不确定的,当在其中加入适当的括号后,才能成为一个确定的n重幂。不同的加括号方式导致不同的n重幂。例如,当n=4时,全部4重幂有5个。对n个变量计算出有多少个不同的n重幂。

Input

输入数据只有一行,提供一个数n(n≤50)。

Output

输出数据只有一行,表示找到的序关系数。

Sample Input

4

Sample Output

5

Hint

 

Source