← 返回题目列表

AtCoder · agc022_f

F. 跳棋

中文机器翻译题面 查看原题

分数: 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.