069 - Colorful Blocks 2(★3) Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 3

問題文

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
  • 入力は全て整数である

入力

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

N K

出力

条件を満たすような塗り方の数を 10^9+7 で割った余りを出力せよ。


入力例 1

2 3

出力例 1

6

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


入力例 2

10 2

出力例 2

0

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


入力例 3

2021 617

出力例 3

53731843

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


Source Name

「競プロ典型90問」69日目