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;

const int mod = 1e9 + 7;
long long n, k, cnt = 1, dp[1500], ans = 0;
vector<long long> divisors;

long long power(long long a, long long n) {
    if(n == 0) return 1;
    if(n == 1) return a;
    long long b = power(a, n/2);
    b = (b*b) % mod;
    if(n&1) b = (b*a) % mod;
    return b;
}

int main() {
    scanf("%lld%lld", &n, &k);
    long long p = sqrt(n);
    for(int i = 1; i <= p; i++) {
        if(n % i == 0) {
            divisors.push_back(i);
            long long q = n/i;
            if(q > i) divisors.push_back(q);
        }
    }
    sort(divisors.begin(), divisors.end());
    for(int i = 0; i < divisors.size(); i++) {
        dp[i] = power(k, (divisors[i] + 1)/2) % mod;
        for(int j = 0; j < i; j++) {
            if(divisors[i] % divisors[j] == 0) dp[i] = (dp[i] - dp[j] + mod) % mod;
        }
        ans = ((divisors[i]&1 ? divisors[i] : divisors[i]>>1) * dp[i] + ans) % mod;
    }
    printf("%lld", ans);
}
