問題

ぴなさんは、誕生日プレゼントにレベル $K$ のガスケットをもらいました。

ただし、レベル$K$のガスケットとは、以下のように定義される図形です。

• $K = 0$ の時、上向きの正三角形

• $K > 0$ の時、下向きの正三角形の辺に、その正三角形と同じ大きさのレベル($K - 1$)のガスケットを、辺を共有するようにつけたもの

例えば、レベル $1,\, 2$ のガスケットはそれぞれ以下のようになっています。

ぴなさんは、もらったレベル $K$ のガスケットの各正三角形の部分をそれぞれ一色ずつ、$N$色のペンキを使って塗ろうとしています。

ただし見栄えのために、正の長さの線分を共有している正三角形同士は異なる色で塗ることにしました。 また、使わない色があってもよいとします。

このとき、色の塗り方は何種類あるでしょうか。$10^9 + 7$ で割った余りを求めてください。

ただし、回転や裏返しによって同一になる塗り方は、それぞれ異なるものとします。

入力

$K\ N$

$0 \leq K \leq 10^5$

$1 \leq N \leq 10^9$

$K, N$ はどちらも整数

出力

$ans$

色の塗り方の種類数を$10^9+7$で割った余り$ans$を出力し、最後に改行してください。

サンプル

サンプル1

入力

1 3

出力

24

色1を橙、色2を黄緑、色3を水色とすると、レベル$1$の中央の正三角形を色1で塗った場合、塗り方は以下の4タイプになります。

• 一番左の塗り方のタイプ(3つ全て色2で塗る)は1種類

• 左から2番目の塗り方のタイプ(2つ色2で、1つ色3で塗る)では、回転・裏返しによって3種類できます。

同様にして、左から3番目、4番目の塗り方のタイプは、3, 1 種類あります。

よって、中央を色1で塗る塗り方は8種類あります。

これは中央の正三角形を色2, 3で塗った場合にも同じなので、答えは8×3 = 24通りになります。

100 1

0

1000 10

910387022