Description

上次由于你的帮助CX赢了ZJS，他很高兴。但是ZJS就不高兴了。他说CX要是算的出一个整数N的所有拆分数目，他才服输。所以这次他又要麻烦你帮帮他了。

Input

输入N（ 1 <= N <= 400 ）。

Output

对于输入的N，输出它的所有的拆分数目。

Sample Input

1
2
7
400

Sample Output

1
2
15
6727090051741041926

HINT

请使用 __int64

Source