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
from math import gcd

def divisors(M):#Mの約数列 O(n^(0.5+e))
    d=[]
    i=1
    while M>=i**2:
        if M%i==0:
            d.append(i)
            if i**2!=M:
                d.append(M//i)
        i=i+1
    d.sort()
    return d

mod=10**9+7
N,K=map(int,input().split())
div=divisors(N)

res=[0 for i in range(len(div))]
ans=0
if N%2==0:
    for i in range(len(div)):
        d=div[i]
        g=gcd(2*d,N)
        res[i]+=pow(K,g//2,mod)
        res[i]%=mod
        ans+=d*res[i]
        ans%=mod
        for j in range(i+1,len(div)):
            if div[j]%d==0:
                res[j]-=res[i]
                res[j]%=mod

    print(ans%mod)
else:
    for i in range(len(div)):
        d=div[i]
        g=gcd(2*d,N)
        res[i]+=pow(K,(g+1)//2,mod)
        res[i]%=mod
        ans+=d*res[i]
        ans%=mod
        for j in range(i+1,len(div)):
            if div[j]%d==0:
                res[j]-=res[i]
                res[j]%=mod

    print(ans%mod)
