配点: 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 后的余数。