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;
const ll MOD = 1000000007;

ll modpow(ll x,ll k){
	if(k == 0)return 1;
	ll ret = modpow(x,k/2);
	ret *= ret; ret %= MOD;
	if(k%2 == 1){
		ret *= x;
		ret %= MOD;
	}
	return ret;
}

vector<ll> divisors(ll n){
	vector<ll> ret;
	ret.push_back(1);
	for(int i = 2 ; n > 1 ; i ++){
		if(i*i > n)i = n;
		if(n%i == 0){
			int cnt = 0;
			while(n%i == 0){
				n /= i;
				cnt ++;
			}
			int m = ret.size();
			ll x = 1;
			for(int j = 0 ; j < cnt ; j ++){
				x *= i;
				for(int i = 0 ; i < m ; i ++){
					ret.push_back(ret[i]*x);
				}
			}
		}
	}
	sort(ret.begin(),ret.end());
	return ret;
}

int main(){
	ll n,k;
	cin >> n >> k;
	
	vector<ll> div = divisors(n);
	ll ret = 0;
	ll cnt[1400];
	for(int i = div.size()-1 ; i >= 0 ; i --){
		ll d = div[i];
		if(d&1)cnt[i] = d;
		else cnt[i] = d/2;
		for(int j = i+1 ; j < div.size() ; j ++){
			if(div[j]%d == 0)cnt[i] += MOD-cnt[j];
		}
		ll sum = cnt[i]%MOD;
		sum *= modpow(k,(d+1)/2);
		ret += sum;
		ret %= MOD;
	}
	cout << ret << endl;
}

