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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> pipii;
typedef pair<pii, int> piipi;
typedef pair<pii, pii> piipii;

#define mp make_pair
#define fi first
#define se second
#define all(a) (a).begin(), (a).end()
#define sz(a) (int)(a).size()
#define eb emplace_back
const int mod = 1e9+7;

ll dp[100005];
ll pow2(ll a, ll b){
    ll ans = 1;
    while(b){
        if(b%2 == 1) ans = ans*a%mod;
        a = a*a%mod;
        b/=2;
    }
    return ans;
}
int main(){
    int n, k;
    scanf("%d%d", &n, &k);

    vector<int> f;
    for(int i=1;i*i<=n;i++){
        if(n%i == 0){
            f.eb(i);
            if(n/i != i) f.eb(n/i);
        }
    }   
    sort(all(f));
    ll ans = 0;
    for(int i=0;i<sz(f);i++){
        dp[i] = pow2(k, (f[i]+1)/2);
        for(int j=0;j<i;j++){
            if(f[i]%f[j] == 0){
                dp[i] = (dp[i] - dp[j] + mod)%mod;
            }
        }
        if(f[i]%2 == 0) ans = (ans + dp[i]*1ll*f[i]/2)%mod;
        else ans = (ans + dp[i]*1ll*f[i])%mod;
    }
    printf("%lld\n", ans);
}