题目描述

高桥君和青木君决定合作构造一个数列。

首先，高桥君需要准备一个满足以下所有条件的数列 $a$：

• $a$ 的长度为 $N$。
• $a$ 的每个元素都是 $1$ 到 $K$ 之间的整数。
• $a$ 是回文数列。也就是说，将 $a$ 逆序后得到的数列与原数列相同。

接下来，青木君可以任意多次重复以下操作：

• 将 $a$ 的第一个元素移动到末尾。

经过上述过程后，最终会得到一个数列 $a$。

请问，最终可能得到多少种不同的数列 $a$？请输出答案对 $10^9+7$ 取模后的结果。

输入格式

输入从标准输入读取，格式如下：

$N$ $K$

输出格式

输出最终可能得到的不同数列 $a$ 的种数，对 $10^9+7$ 取模。

样例 1

输入

4 2

输出

6

样例 2

输入

1 10

输出

10

样例 3

输入

6 3

输出

75

样例 4

输入

1000000000 1000000000

输出

875699961

说明/提示

数据范围

• $1 \leq N \leq 10^9$
• $1 \leq K \leq 10^9$

样例解释 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)$

由 ChatGPT 4.1 翻译