← 返回题目列表

AtCoder · arc064_d

F. 旋转回文

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

分数: 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