配点 : $1000$ 点

問題文

高橋君と青木君が協力して数列を作ることになりました。

まず、高橋君が次の条件をすべて満たす数列 $a$ を用意します。

• $a$ は長さ $N$ である。
• $a$ の各要素は $1$ 以上 $K$ 以下の整数である。
• $a$ は回文である。 すなわち、$a$ を逆順にした数列は元の $a$ と一致する。

次に、青木君が次の操作を好きな回数だけ繰り返します。

• $a$ の先頭要素を末尾へ移動する。

以上の手続きにより、最終的な $a$ が得られます。

最終的な $a$ として考えられるものは何通りあるでしょうか？ $10^9+7$ で割った余りを求めてください。

制約

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

入力

入力は以下の形式で標準入力から与えられる。

$N$ $K$

出力

最終的な $a$ として考えられるものは何通りあるか？ $10^9+7$ で割った余りを出力せよ。

4 2

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)$

1 10

10

6 3

75

1000000000 1000000000

875699961