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>
#define ll long long
using namespace std;
const ll fish=1e9+7;
ll dp[1000005];
int N,K;
vector<ll> v;
ll Pow(ll x,ll y){
	x%=fish,y%=fish;
	ll ans=1,b=x;
	for (int qwq=y;qwq!=0;qwq/=2){
		if (qwq%2) ans=(ans*b)%fish;
		b=(b*b)%fish;
	}
	return ans;
}
void Pre(){
	v.clear();
	for (ll i=1;i*i<=N;i++){
		if (N%i==0){
			v.push_back(i);
			if (i*i!=N)
				v.push_back(N/i);
		}
	}
	sort(v.begin(),v.end());
}
int main(){
	//cout<<Pow(3,3)<<endl;
	while (cin>>N>>K){
			Pre();
		ll ans=0;
		for (int i=0;i<v.size();i++){
			dp[i]=Pow(K,(v[i]+1)/2);
			for (int j=0;j<i;j++){
				if (v[i]%v[j]==0)
					dp[i]=(dp[i]-dp[j]+fish)%fish;
			}
			if (v[i]%2==0)
				ans=(ans+(dp[i]*v[i]/2)%fish)%fish;
			else ans=(ans+(dp[i]*v[i])%fish)%fish;
		}
	printf("%lld\n",ans);
	}
}