You have a piece of iron wire with length of n unit. Now you decide to cut it into several ordered pieces and fold each piece into a triangle satisfying that all triangles are integral and pairwise similar.

count the number of different approaches to form triangles. Two approaches are considered different if they produce different numbers of triangles, and/or there exists i that the i-th (again, pieces are ordered) triangle in one approaches is not congruent to ith triangle in another plan.

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

Solve this problem by at most 0.5 KB of source code.

Input

Each test case consists of one line containing one integer n (1<=n<=5,000,000). 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
4
5
6
8
9
10
11
12
15
19
20
100
1000
Output:
Case 1: 0
Case 2: 0
Case 3: 1
Case 4: 0
Case 5: 1
Case 6: 2
Case 7: 1
Case 8: 6
Case 9: 3
Case 10: 4
Case 11: 10
Case 12: 25
Case 13: 10
Case 14: 16
Case 15: 525236
Case 16: 523080925

Explanation

A triangle is integral when all sides are integer.

Two triangles are congruent when all corresponding sides and interior angles are equal.

Two triangles are similar if they have the same shape.

For n = 9, there are 6 different ways: (1,1,1) * 3; (1,1,1), (2,2,2); (2,2,2),(1,1,1); (1,4,4); (2,3,4); (3,3,3).