#1847. [HDOJ3204]Expression Counting

题目描述

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.

有一些表达式本质上是相同的，如a+(b-c), (a+b)-c。你的任务是统计出N元的不同表达式有多少个。

为使问题简单些，只有+-*/和括号是允许的。

输入格式

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.

一个整数N，意义如上描述。N<=30。

输出格式

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.

一个整数表示表达式个数。

因为答案可能很大，只需输出对1,000,000,007取模后的值。

样例

样例输入

1  

2  

3  

4  

0  

样例输出

1  

6  

68  

1170  

数据范围与提示

There are 6 distinct expressions involving 2 operands: a+b, a-b, b-a, ab, a/b, b/a. There are 68 distinct expressions involving 3 operands: a+b+c, a+b-c, a-b+c, a-b-c, b-a+c, b-a-c, c-a-b, abc, ab/c, a/bc, a/b/c, b/ac, b/a/c, c/a/b, a+bc, b+ac, c+ab, a+b/c, a+c/b, b+a/c, b+c/a, c+a/b, c+b/a, a-bc, b-ac, c-ab, a-b/c, a-c/b, b-a/c, b-c/a, c-a/b, c-b/a, bc-a, ac-b, ab-c, b/c-a, c/b-a, a/c-b, c/a-b, a/b-c, b/a-c, a(b+c), b*(a+c), c*(a+b), a*(b-c), a*(c-b), b*(a-c), b*(c-a), c*(a-b), c*(b-a), a/(b+c), b/(a+c), c/(a+b), a/(b-c), a/(c-b), b/(a-c), b/(c-a), c/(a-b), c/(b-a), (b+c)/a, (a+c)/b, (a+b)/c, (b-c)/a, (c-b)/a, (a-c)/b, (c-a)/b, (a-b)/c, (b-a)/c. When n=4, note that (a-b)/(c-d) and (b-a)/(d-c) are the same, but a/b-c/d and b/a-d/c are not.

提示： ****

二元的表达式：

a+b, a-b, b-a, a*b, a/b, b/a.

三元的表达式：

a+b+c, a+b-c, a-b+c, a-b-c, b-a+c, b-a-c, c-a-b,

abc, ab/c, a/bc, a/b/c, b/a*c, b/a/c, c/a/b,

a+bc, b+ac, c+a*b,

a+b/c, a+c/b, b+a/c, b+c/a, c+a/b, c+b/a,

a-bc, b-ac, c-a*b,

a-b/c, a-c/b, b-a/c, b-c/a, c-a/b, c-b/a,

bc-a, ac-b, a*b-c,

b/c-a, c/b-a, a/c-b, c/a-b, a/b-c, b/a-c,

a*(b+c), b*(a+c), c*(a+b),

a*(b-c), a*(c-b), b*(a-c), b*(c-a), c*(a-b), c*(b-a),

a/(b+c), b/(a+c), c/(a+b),

a/(b-c), a/(c-b), b/(a-c), b/(c-a), c/(a-b), c/(b-a),

(b+c)/a, (a+c)/b, (a+b)/c,

(b-c)/a, (c-b)/a, (a-c)/b, (c-a)/b, (a-b)/c, (b-a)/c.

注意四元的表达式中(a-b)/(c-d)和(b-a)/(d-c)是相同的，而a/b-c/d和b/a-d/c是不同的。