[HDOJ3204]Expression Counting

YY 是个聪明的孩子。某天他觉得很无聊，于是随手写下了一些表达式。后来他发现，虽然有些表达式写法不同，但它们本质上是相同的，比如 a+(b-c) 和 (a+b)-c。

经过几次尝试之后，他对此产生了兴趣，想知道由 $n$ 个不同运算对象组成的本质不同的表达式共有多少个。

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

输入格式

输入包含多组测试数据。每组测试数据只有一行，包含一个整数 $n$ 。

输入以一行一个 $0$ 结束。

输出格式

对每组测试数据输出一行一个整数，表示由 $n$ 个不同运算对象组成的本质不同的表达式的个数。

因为答案可能很大，只需输出对 $10^9+7$ 取模后的值。

样例输入

样例输出

样例解释

二元的表达式共 $6$ 个：

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

三元的表达式共 $68$ 个：

a+b+c, a+b-c, a-b+c, a-b-c, b-a+c, b-a-c, c-a-b,
a*b*c, a*b/c, a/b*c, a/b/c, b/a*c, b/a/c, c/a/b,
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), 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 是不同的。

数据范围

$1\le n\le 30$ 。

来源与许可

本题为 HDOJ 3204 试题「Expression Counting」，题面与测试数据整理自 BZOJ 1847。

样例 1

输入

输出