分数: 1000 点
问题陈述
Takahashi 和 Aoki 将一起构造一个整数序列。
首先,Takahashi 将提供一个整数序列 a,满足以下所有条件:
- 的长度 a is N.
- 中的每个元素 a 是介于 1 和 K,包括在内。
- a 是 回文,即反转其中元素的顺序 a 将产生与原始序列相同的序列。
然后,Aoki 将执行任意次数的以下操作:
- 将第一个元素移入 a 到结束 a.
有多少个序列 a 可以在这个过程之后获得,模 10^9+7?
约束
- 1≤N≤10^9
- 1≤K≤10^9
输入
输入由标准输入按以下格式给出:
N K
输出
打印序列号 a 可以在程序之后获得,模 10^9+7.
示例输入 1
4 2
示例输出 1
6
可以得到以下6个序列:
- (1, 1, 1, 1)
- (1, 1, 2, 2)
- (1, 2, 2, 1)
- (2, 2, 1, 1)
- (2, 1, 1, 2)
- (2, 2, 2, 2)
示例输入 2
1 10
示例输出 2
10
示例输入 3
6 3
示例输出 3
75
示例输入 4
1000000000 1000000000
示例输出 4
875699961