分数: 1600 点
问题陈述
让 X = 10^{100}。稻叶有 N 数轴上的棋子,其中 i第一个检查块位于坐标处 X^{i} 对于所有人 1 \leq i \leq N.
稻叶每秒都会选择两个棋子, 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 is 2 \times 10^{300} - 2 \times 10^{200} + 10^{100}.
-
让 C 跳过 A 在第一秒,让 B 跳过 C 在第二秒。最终位置为 B is -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.