Counting trees P78394

Masao Long-Long, 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:

1. All the subtrees of each node must have the same size.
2. That size must be prime (unless n = 2).
3. All the (sub)trees must be specular.

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.