问题陈述

令 $X = 10^{100}$。Inaba在数轴上有 $N$ 个棋子，其中第 $i$ 个棋子位于坐标 $X^{i}$，对所有 $1 \leq i \leq N$。

每一秒钟，Inaba选择两个棋子 $A$ 和 $B$，将 $A$ 移动到相对于 $B$ 当前位置的对称点。然后，棋子 $B$ 被移除。 （可能发生 $A$ 和 $B$ 占据同一位置的情况，并且在移动后，$A$ 可能与另一个棋子占据同一位置）。

经过 $N-1$ 秒，只剩下一个棋子。计算最终棋子的不同可能位置数，模 $10^{9} + 7$。

约束条件

• $1 \leq N \leq 50$
• $N$ 是一个整数。

输入

输入以以下格式从标准输入给出：

$N$

输出

打印最终棋子的不同可能位置数，模 $10^{9} + 7$。

样例输入 1

3

样例输出 1

12

有 $3$ 个棋子，分别位于 $10^{100}, 10^{200}, 10^{300}$。称它们为 $A, B, C$。

以下是两种（共 $12$ 种）可能的移动序列：

• 第一秒让 $A$ 跳过 $B$，第二秒让 $A$ 跳过 $C$。$A$ 的最终位置是 $2 \times 10^{300} - 2 \times 10^{200} + 10^{100}$。
• 第一秒让 $C$ 跳过 $A$，第二秒让 $B$ 跳过 $C$。$B$ 的最终位置是 $-2 \times 10^{300} - 10^{200} + 4 \times 10^{100}$。

共有 $3 \times 2 \times 2 = 12$ 种可能的移动序列，并且所有序列中最终的棋子位置都不同。

样例输入 2

4

样例输出 2

84

样例输入 3

22

样例输出 3

487772376

记得将答案模 $10^{9} + 7$ 输出。