Count the number of distinct expressions involving n different operands a, b, c, etc. Only operators +, -, *, / and parentheses are permitted. Single minus operator (for ex. -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

Multiply test cases. For each test case:

A single line - n.(1<= n <=50).

Input terminates by a single zero.

Output

For each test case:

The number of different expressions, modulo 499999999999993.

Example

Input:
3
0

Output:
68

If you find the constraints is too small in this problem, try problem EXPR4.