EXPR4 - Counting Expressions II

no tags 

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

Multiply 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 :-)


hide comments
Ehor Nechiporenko: 2009-12-07 13:17:16

Can we change places of operands.
I mean can we use expressions a/b and b/a and look them as distinct expressions?
And also can use leading minuses like expression -a/b?

Re by [Trichromatic]XilinX: a/b and b/a are distinct exp. Single minus is not allowed.

Last edit: 2009-12-07 15:09:28

Added by:Fudan University Problem Setters
Date:2009-06-06
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: C99 ERL GOSU JS-RHINO NODEJS PERL6 VB.NET
Resource:Solution of problem EXPR3 by Tomek Czajka