問題文

N 個のブロックが横一列に並んでおり、左から順に 1 から N までの番号が付けられています。

これらのブロックそれぞれを、K 種類の色のうちいずれか一色で塗ることを考えます。ここで、次の条件を満たすように塗らなければなりません。

• 1 \leq |i-j| \leq 2 ならば、ブロック i とブロック j に塗られている色は異なる。
• ただし、使わない色があってもよい。

このようなブロックの塗り方が何通りあるかを、10^9 + 7 で割った余りを出力してください。ただし、2 つのブロックの列の塗り方が異なるとは、ある 1 以上 N 以下の整数 i が存在して、ブロック i について異なる色で塗られていることとします。

制約

• 1 \leq N \leq 10^{18}
• 1 \leq K \leq 10^9
• 入力は全て整数である

入力例 1

2 3

出力例 1

6

条件を満たすためには、2 つのブロックは互いに異なる色で塗らなくてはなりません。K=3 であることから、条件を満たす塗り方は 6 通りです。

入力例 2

10 2

出力例 2

0

2 色のみで 10 個のブロックを条件を満たすように塗ることはできません。

入力例 3

2021 617

出力例 3

53731843

答えを 10^9+7 で割った余りを出力することに注意してください。