問題文

N 個の M 階建てビルがあります。 忍者の高橋君は、全てのビルの全ての階に侵入することにしました。 最初、高橋君は 1 番目のビルの 1 階にいて、最終的に再び 1 番目のビルの 1 階に戻ってきたいです。

高橋君は以下の 2 種類の移動ができます。

• 同じビルの隣接する階に階段で移動する。
• 異なるビルの同じ階に瞬間移動する。

ビルに滞在する時間が長くなると見つかる恐れがあるので、途中で同じビルの同じ階に 2 回以上入ることなく、 1 番目のビルの 1 階に戻ってきたいです。

移動の仕方が何通りあるか、 10^9+7 で割った余りを求めてください。

制約

• 2 ≤ N ≤ 100
• 2 ≤ M ≤ 10^9
• 入力は全て整数

入力例 1

3 2

出力例 1

6

次の 6 通りがあります。 (i,j) は i 番目のビルの j 階を表します。

• (1,1) → (2,1) → (3,1) → (3,2) → (2,2) → (1,2) → (1,1)
• (1,1) → (3,1) → (2,1) → (2,2) → (3,2) → (1,2) → (1,1)
• (1,1) → (3,1) → (3,2) → (1,2) → (2,2) → (2,1) → (1,1)
• (1,1) → (1,2) → (2,2) → (3,2) → (3,1) → (2,1) → (1,1)
• (1,1) → (1,2) → (3,2) → (2,2) → (2,1) → (3,1) → (1,1)
• (1,1) → (2,1) → (2,2) → (1,2) → (3,2) → (3,1) → (1,1)

入力例 2

98 7654321

出力例 2

257361229