問題文

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

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

• $a$ は長さ $N$ である。
• $a$ の各要素は $1$ 以上 $K$ 以下の整数である。
• $a$ は回文である。 すなわち、$a$ を逆順にした数列は元の $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

次の $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