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
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

n,k = map(int,readline().split())
MOD = 10**9+7

def divisor_list(N): #約数のリスト
    if N == 1: return [1]
    res = []
    for i in range(1,N):
        if i*i >= N: break
        if N%i == 0:
            res.append(i)
            res.append(N//i)
    if i*i == N: res.append(i)
    return sorted(res)



if n&1:
    p = [i for i in divisor_list(n)]
    r = {pi:pow(k,(pi+1)//2,MOD) for pi in p}
    #print(r)
    for pi in p:
        for pj in p:
            if pj >= pi: break
            if pi%pj==0:
                r[pi] -= r[pj]
    #print(r)
    ans = 0
    for pi,v in r.items():
        ans += v*(pi)
    ans %= MOD
    print(ans)
    
    

else:
    p = [1] + [i for i in divisor_list(n) if i%2==0 and i!=2]
    
    r = {pi:pow(k,(pi+1)//2,MOD) for pi in p}
    for pi in p:
        for pj in p:
            if pj >= pi: break
            if pi%pj==0:
                r[pi] -= r[pj]

    #print(r)
    ans = 0
    for pi,v in r.items():
        if pi==1:
            ans += v
        else:
            ans += v*(pi//2)
    ans %= MOD
        
        
    print(ans)        
        
        
    
    
    
    


    
    
    
    
    
    