Count the number of distinct expressions involving n different operands a, b, c, etc. Only operators +, -, *, / and parentheses are permitted. Single minus operator (for example -a*b) is not allowed.

Two expression are distinct if for some valid input values (i.e. You won't divide some number by zero) a, b, c ... the two expressions leads to different results. For example, a/b/c and a/(b*c) are the same expressions, but a/b+c and a/(b+c) are not.

Input

Multiple test cases. For each test case:

A single line - n. (1 ≤ n ≤ 2000).

Input terminates by a single zero.

Output

For each test case:

The number of different expressions, modulo 1000000007.

Example

Input:
3
0

Output:
68

The time limit has been changed to 1 second. If you find it too strict, please submit a pre-computed table to get Accepted :-)