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 <iostream>
#include <vector>
#include <map>
#include <set>
#include <numeric>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long lli;
typedef vector<lli> vll;
typedef vector<vector<lli> > mat;
const lli MOD = 1000000007;
lli n,k;
vll d;
vll dp;
lli ans = 0;
lli pow(lli a,lli n,lli mod = MOD){
	lli ret = 1;
	for(;n!=0;n=n>>1){
		if(n&1) ret = (ret * a) % mod;
		a = (a * a) % mod;
	}
	return ret;
}
int main(){
    cin >> n >> k;
    lli i;
    for(i = 1;i*i < n;i++) if(n%i == 0) d.push_back(i),d.push_back(n/i);
    if(i*i == n) d.push_back(i);
    sort(d.begin(),d.end());
    dp = vector<lli> (d.size());
    for(lli i = 0;i < d.size();i++){
        dp[i] += pow(k,(d[i]+1)/2);//k*(d[i]+1)/2;
        dp[i] %= MOD;
        for(lli j = i+1;j < d.size();j++){
            if(d[j]%d[i] == 0) dp[j] -= dp[i],dp[j] = (dp[j] + MOD) % MOD;
        }
    }
    for(lli i = 0;i < d.size();i++){
        ans += (dp[i]*(d[i]%2 ? d[i] : d[i]/2)) % MOD;
        ans %= MOD;
    }
    cout << ans << endl;
    return 0;

}