問題文

今日はクリスマス・イブである。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 で割った余りを求めてください。

制約

• D は 1 以上 10 \ 000 \ 000 以下の整数
• X は 1 以上 1 \ 000 \ 000 \ 000 以下の整数

入力

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

D X

入力例 1

1 2

出力例 1

2

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

入力例 2

1 3

出力例 2

18

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

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

入力例 3

4 5

出力例 3

101969466

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