配点 : $1600$ 点

問題文

$X = 10^{100}$ とします。イナバは $N$ 個の駒を数直線上に置いていて、$i$ 個目の駒は座標 $X^{i}$ にあります。

$1$ 秒ごとに、イナバは $2$ 個の駒 $A$、$B$ を選び、$A$ を $B$ に関して対称な点に動かし、その後 $B$ を取り除きます（$A$、$B$ が同じ位置にあっても構わず、$A$ が移動後に他の駒と同じ位置にあっても構いません）。

$N - 1$ 秒後には、駒が $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$ 通り）のうち $2$ つを示します。

• 最初の $1$ 秒で $A$ に $B$ を飛び越えさせ、次の $1$ 秒で $A$ に $C$ を飛び越えさせる。$A$ の最終的な位置は $2 \times 10^{300} - 2 \times 10^{200} + 10^{100}$ となる。
• 最初の $1$ 秒で $C$ に $A$ を飛び越えさせ、次の $1$ 秒で $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$ で割った余りを出力することを忘れずに。