分值：$1600$ 分

问题描述

设 $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$ 取模。

3

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$ 种可能的移动序列，并且最终的棋子位置各不相同。

4

84

22

487772376

记得输出结果对 $10^{9} + 7$ 取模。