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;
#define ll long long
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
ll ksm (ll a , ll b)
{
    ll ans = 1 , base = a;
    while (b){
        if (b & 1) ans = ans * base % mod;
        b >>= 1;
        base = base * base % mod;
    }
    return ans;
}
ll n , k;
vector<ll> fact;
ll dp[50005];
ll getans (ll x){
    return ksm(k , (x - 1) / 2 + 1);
}
int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> k;
    ll ans = 0;
    for (ll i = 1 ; i * i <= n ; i++){
        if (n % i == 0){
            fact.push_back(i);
            if (i != n / i)
                fact.push_back(n / i);
        }
    }
    sort(fact.begin() , fact.end());
    int m = fact.size();
    for (int i = 0 ; i < m ; i++) dp[i] = getans(fact[i]);
    for (int i = 0 ; i < m ; i++){
        // 容斥掉重复部分
        for (int j = 0 ; j < i ; j++)
            if (fact[i] % fact[j] == 0)
                dp[i] = (dp[i] - dp[j] + mod) % mod;
        if (fact[i] & 1) ans = (ans + dp[i] * fact[i]) % mod;
        else ans = (ans + dp[i] * (fact[i] / 2)) % mod;
    }
    cout << ans << endl;
    return 0;
}
