文理学院程序设计在线练习


多重幂计数问题

Time Limit: 1 Second(s)    Memory Limit: 32 MB

Total Submission(s): 94   Accepted Submission(s): 40
Problem Description

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

编程任务:对n个变量计算出有多少个不同的n重幂。

Input

每组测试数据只有一个数n(1<=n<=30)。

Output

输出n个变量的不同的n重幂的个数,每个答案一行。

Sample Input
4
Sample Output
5
Hint

使用64位Int型变量