EXPR3 - Counting Expressions

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.


Added by:Fudan University Problem Setters
Date:2009-05-23
Time limit:10s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: C99 ERL GOSU JS-RHINO NODEJS PERL6 VB.NET
Resource:Fudan University Local Contest #1

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.