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 で割った余りを出力することに注意してください。