Description

Eddy 是一个对数字特别有兴趣,一天他想知道,如果有一些数,然后从中选择一部分数(或者全部),将选出来的数分成两组进行比较,他想使第一组中的最小的数大于第二组中的最大的数,但是这样的情况会有很多,聪明的你知道这样的情况有多少种吗?特别说明:为了问题的简化,我们这里假设数的总数是 n 个,而且 n 个数都不相等,最后结果在 64 位整数范围内.

Format

Input

输入包含多组数据,每组包含一个整数 n,表示有多少个数。

Output

对于每个实例,输出符合要求的总的方案数,每个输出占一行。

Samples

2

1

Hint