Masao LongLong, an Asian mathematician, is studying general rooted trees. Below you can see some examples. Every node shows the size (the number of nodes) of the subtree rooted at it.

The number of different trees grows very fast with the number of nodes n. Since Masao has some problems with large numbers, he decides to add three conditions:
These restrictions reduce the number of trees dramatically. For instance, only the last of the four trees above fulfills all the restrictions. The first tree does not fulfill (i), the second tree fulfills (i) but not (ii), and the third tree fulfills (i) and (ii) but not (iii).
Input
Input consists of several numbers n between 1 and 500.
Output
For every given n, print the number of general rooted trees with n nodes that fulfill the three conditions above. You, and Masao in particular, may be happy to know that this number always fits in a C++ long long.
Input
1 4 9 15 22
Output
1 1 1 3 5