E - クリスマスツリー (Tree Coloring) /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 100

問題文

今日はクリスマス・イブである。PAKEN 君は、平成最後のクリスマスに向けて、以下のようなデコレーションを作りました。

  • デコレーションは、「電球」と「棒」で構成される。デコレーションは、以下のようにして作られる。
  • 電球 (a, b) (0 \leq a \leq D, -a \leq b \leq a) を満たす整数の組) を作る。a を「深さ」と呼び、b を「横座標」と呼ぶ。
  • 電球 (0, 0)(1, -1) を、そして電球 (0, 0)(1, 1) を、直接棒で結ぶ。
  • 同じ深さで横座標が 1 しか違わない電球同士を、直接棒で結ぶ。
  • 電球 (a, -(a-1))(a+1, -(a+1)) を、そして電球 (a, a-1)(a+1, a+1) を、直接棒で結ぶ。

例えば、D = 1, 2, 3 のとき、グラフは以下の図のようになります。

どうやらクリスマスツリーみたいな感じです。

PAKEN 君は、色 1 から X までの X 個の色を使って、全ての電球に色を付けたいです。ただし、棒で直接結ばれた電球は同じ色であってはいけません。
色の付け方は何通りあるか、1 \ 000 \ 000 \ 007 で割った余りを求めてください。

制約

  • D1 以上 10 \ 000 \ 000 以下の整数
  • X1 以上 1 \ 000 \ 000 \ 000 以下の整数

入力

入力は以下の形式で標準入力から与えられます。

D X

出力

色の付け方は何通りあるか、1 \ 000 \ 000 \ 007 で割った余りを一行に出力してください。

小課題

小課題 1 [2 点]

入力は以下の条件を満たす。

  • D = 1
  • X \leq 4

小課題 2 [12 点]

入力は以下の条件を満たす。

  • D \leq 2
  • X \leq 6

小課題 3 [21 点]

入力は以下の条件を満たす。

  • D \leq 4
  • X \leq 7

小課題 4 [31 点]

入力は以下の条件を満たす。

  • D \leq 50
  • X \leq 25

小課題 5 [18 点]

  • D \leq 50 を満たす。

小課題 6 [11 点]

  • D \leq 100 \ 000 を満たす。

小課題 7 [5 点]

  • 追加の制約はない。

入力例 1

1 2

出力例 1

2

以下の 2 通りの塗り方が存在します。


入力例 2

1 3

出力例 2

18

以下の 18 通りの塗り方が存在します。

この入力は、小課題 1 の制約を満たします。


入力例 3

4 5

出力例 3

101969466

この入力は、小課題 2 の制約は満たしませんが、小課題 3 の制約を満たします。