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;

int exp(int x, int n) {
    int ret = 1;
    while(n) {
        if(n & 1) ret = 1LL * ret * x % mod;
        x = 1LL * x * x % mod;
        n >>= 1;
    }
    return ret;
}

int N, K, ans;
vector<int> Dv;
int add[100000];

int main() {
    scanf("%d %d", &N, &K);

    ans = 0;
    ans += 1LL * exp(K, (N + 1) / 2) * (N % 2 == 0? N / 2 : N) % mod;
    ans %= mod;

    for(int i = 1; i <= sqrt(N); i++) {
        if(N % i == 0) {
            Dv.push_back(i);
            Dv.push_back(N / i);
        }
    }
    sort(Dv.begin(), Dv.end());

    for(int i = 0; i < Dv.size(); i++) {
        int d = Dv[i];
        if(d == N) break;

        add[i] += exp(K, (d + 1) / 2);

        for(int j = 0; j < i; j++) {
            if(Dv[i] % Dv[j] == 0) {
                add[i] += mod - add[j];
                add[i] %= mod;
            }
        }

        ans += mod - 1LL * add[i] * ((N % 2 == 0? N / 2 : N) - (d % 2 == 0? d / 2 : d)) % mod;
        ans %= mod;
    }

    cout << ans;
}
