[AGC022F] Checkers

令 $x=10^{100}$, 数轴上有 $n$ 个点, 第 $i$ 个点的坐标为 $x^i$. 进行 $n-1$ 次操作, 每次操作选择两点 $A$ 和 $B$, 将 $A$ 移动到 $A$ 关于 $B$ 的对称的位置并删去 $B$. 求最后剩下的一个数有多少种可能的取值. $n\leqslant 50$

[problemUrl]: https://atcoder.jp/contests/agc022/tasks/agc022_f $ X\ =\ 10^{100} $ とします。イナバは $ N $ 個の駒を数直線上に置いていて、$ i $ 個目の駒は座標 $ X^{i} $ にあります。 $ 1 $ 秒ごとに、イナバは $ 2 $ 個の駒 $ A $、$ B $ を選び、$ A $ を $ B $ に関して対称な点に動かし、その後 $ B $ を取り除きます（$ A $、$ B $ が同じ位置にあっても構わず、$ A $ が移動後に他の駒と同じ位置にあっても構いません）。 $ N\ -\ 1 $ 秒後には、駒が $ 1 $ 個だけ残ります。その駒の位置としてありうるものは何通りあるか、その数を $ 10^{9}\ +\ 7 $ で割った余りを求めてください。

入力は標準入力から以下の形式で与えられる。 > $ N $

最後に残る駒の位置としてありうるものの数を $ 10^{9}\ +\ 7 $ で割った余りを出力せよ。

3

12

4

84

22

487772376

### 制約 - $ 1\ \leq\ N\ \leq\ 50 $ - $ N $ は整数である。 ### Sample Explanation 1 駒が $ 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 $ 通りあり、そのすべてで最後の駒は異なる位置に残ります。 ### Sample Explanation 3 答えを $ 10^{9}\ +\ 7 $ で割った余りを出力することを忘れずに。