题目描述

设 $X = 10^{100}$。Inaba 在数轴上放置了 $N$ 个棋子，第 $i$ 个棋子位于坐标 $X^i$。

每经过 $1$ 秒，Inaba 可以选择两个棋子 $A$ 和 $B$，将 $A$ 移动到关于 $B$ 对称的位置，然后移除 $B$（即使 $A$ 和 $B$ 在同一位置也可以，$A$ 移动后与其他棋子重合也没有关系）。

经过 $N-1$ 秒后，只剩下一个棋子。请问最后剩下的棋子可能出现的位置有多少种？请输出这个数对 $10^9+7$ 取模的结果。

输入格式

输入从标准输入读取，格式如下：

$N$

输出格式

输出最后剩下的棋子可能出现的位置数，对 $10^9+7$ 取模。

样例 1

输入

3

输出

12

样例 2

输入

4

输出

84

样例 3

输入

22

输出

487772376

说明/提示

限制条件

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

样例解释 1

有 $3$ 个棋子，分别位于 $10^{100},\ 10^{200},\ 10^{300}$。我们称它们为 $A$、$B$、$C$。以下是 $12$ 种可能的移动方式中的两种：

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

棋子的移动方式共有 $3 \times 2 \times 2 = 12$ 种，并且每种情况下最后的棋子都在不同的位置。

样例解释 3

不要忘记输出答案对 $10^9+7$ 取模。

由 ChatGPT 4.1 翻译