Expression Counting

Time Limit: 1000ms
Memory Limit: 32768KB
This problem will be judged on HDU. Original ID: 3204
64-bit integer IO format: %I64d      Java class name: Main

Description

YY is a clever boy. One day, he feels very boring and writes some expressions randomly. Later, he discovers that although some expressions were written in different forms, they are essentially the same, such as a+(b-c), (a+b)-c. After several attempts, he becomes interested in this and wants to know the number of distinct expressions involving n different operands.

To make the problem easier, you can assume that only operators +, -, *, / and parentheses are permitted.

Input

The input consists of multiple test cases.

For each test case, there is one line containing only one integer n. (1<=n<=30)
End of input is indicated by a line containing a zero.

Output

For each test case, output the number of distinct expressions involving n different operands. Since the answer is very large, you only need to output the answer modulo 1,000,000,007.

Sample Input

1
2
3
4
0

Sample Output

1
6
68
1170

Source

Language: 
Theme: 
Share Code? 

Powered by NB231 | Current Style: .