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.

Examples

Input

4 2


Output

6


Input

1 10


Output

10


Input

6 3


Output

75


Input

1000000000 1000000000


Output

875699961
N, K = map(int, input().split())
S = []; T = []
for x in range(1, int(N**.5)+1):
    if N % x == 0:
        S.append(x)
        if x*x < N:
            T.append(N//x)
T.reverse()
S += T
M = len(S)
U = []

MOD = 10**9 + 7
ans = 0
v = 0
for i in range(M):
    x = S[i]
    v = pow(K, (x+1)//2, MOD)
    for j in range(i):
        y = S[j]
        if x % y == 0:
            v -= U[j]
    U.append(v % MOD)
    ans = (ans + (v * x if x & 1 else v * (x//2))) % MOD
print(ans)