设给定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型变量