问题描述

高桥和青木一起构造了一个整数序列。

首先，高桥会提供一个整数序列 $a$，满足以下所有条件：

• $a$ 的长度为 $N$。
• $a$ 中的每个元素都是介于 $1$ 和 $K$ 之间的整数（包括 $1$ 和 $K$）。
• $a$ 是一个 回文序列，即将 $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

以下六个序列可以获得：

• $(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