F - Rotated Palindromes

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 1000

問題文

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

まず、高橋君が次の条件をすべて満たす数列 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

Score : 1000 points

Problem Statement

Takahashi and Aoki are going to together construct a sequence of integers.

First, Takahashi will provide a sequence of integers a, satisfying all of the following conditions:

  • The length of a is N.
  • Each element in a is an integer between 1 and K, inclusive.
  • a is a palindrome, that is, reversing the order of elements in a will result in the same sequence as the original.

Then, Aoki will perform the following operation an arbitrary number of times:

  • Move the first element in a to the end of a.

How many sequences a can be obtained after this procedure, modulo 10^9+7?

Constraints

  • 1≤N≤10^9
  • 1≤K≤10^9

Input

The input is given from Standard Input in the following format:

N K

Output

Print the number of the sequences a that can be obtained after the procedure, modulo 10^9+7.


Sample Input 1

4 2

Sample Output 1

6

The following six sequences can be obtained:

  • (1, 1, 1, 1)
  • (1, 1, 2, 2)
  • (1, 2, 2, 1)
  • (2, 2, 1, 1)
  • (2, 1, 1, 2)
  • (2, 2, 2, 2)

Sample Input 2

1 10

Sample Output 2

10

Sample Input 3

6 3

Sample Output 3

75

Sample Input 4

1000000000 1000000000

Sample Output 4

875699961