AT_arc064_d [ARC064F] Rotated Palindromes

高桥君和青木君决定合作构造一个数列。 首先，高桥君需要准备一个满足以下所有条件的数列 $a$： - $a$ 的长度为 $N$。 - $a$ 的每个元素都是 $1$ 到 $K$ 之间的整数。 - $a$ 是回文数列。也就是说，将 $a$ 逆序后得到的数列与原数列相同。 接下来，青木君可以任意多次重复以下操作： - 将 $a$ 的第一个元素移动到末尾。 经过上述过程后，最终会得到一个数列 $a$。 请问，最终可能得到多少种不同的数列 $a$？请输出答案对 $10^9+7$ 取模后的结果。

输入从标准输入读取，格式如下： > $N$ $K$

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

### 数据范围 - $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 翻译