Count the number of rooted trees with n nodes, which satiesfy the following condition:

If the distance between node A and the root equals to the distance between node B and the root, then A and B must have same number of (direct) children.

Two trees are considered identical if and only if there's a bijection of n nodes which transforms one tree into another one.

Since the answer can be very large, output the answer modules 1000000007.

Input

Each test case consists of one line containing one integer n (1<=n<=1000). Process until EOF is reached.

Output

For each test case, output one line. See the example for more format details.

Example

Input:
1
2
3
40
50
600
700
Output:
Case 1: 1
Case 2: 1
Case 3: 2
Case 4: 924
Case 5: 1998
Case 6: 315478277
Case 7: 825219749