TREEII - Yet-Yet Another Counting Problem

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

Added by:Fudan University Problem Setters
Date:2012-11-21
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU
Resource:ACM/ICPC Regional Contest, Chengdu 2012

hide comments
2016-09-03 15:40:22
Nice problem to solve
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.