← 返回题目列表

AtCoder · typical90_bq

069. 七彩积木2(★3)

中文机器翻译题面 查看原题

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