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 int mod=1e9+7,N=1e5+99;
int n,m,phi[N][2],cnt,d[N];
ll ans;
map<int,int>f;
ll qpow(ll a,int b)
{
	ll ret=1;
	while(b){if(b%2)ret=ret*a%mod;a=a*a%mod;b/=2;}
	return ret;
}
int calc(int p,int q,int e)
{
	if(p>q)return f[e];
	int ans=calc(p+1,q,e);
	for(int i=1;i<=d[p];i++)ans=(ans+calc(p+1,q,e*=phi[p][0]))%mod;
	return ans;
}
void work(int p,int e)
{
	if(p>cnt)
	{
		ll tmp=(((n/e)%2?qpow(m,(e+1)/2):qpow(m,e))-calc(1,p,1)+mod)%mod;
		f[e]=tmp;
		ans=(ans+tmp*e)%mod;
		return;
	}
	d[p]=0;
	work(p+1,e);
	for(int i=1;i<=phi[p][1];i++)d[p]=i,work(p+1,(e*=phi[p][0]));
}
int main()
{
	cin>>n>>m;
	if(n==1){cout<<m;return 0;}
	int q=n;
	for(int i=2;i*i<=q;i++)
	if(q%i==0)
	{
		phi[++cnt][0]=i;
		while(q%i==0)q/=i,phi[cnt][1]++;
	}
	if(q>1)phi[++cnt][0]=q,phi[cnt][1]=1;
	work(1,1);
	cout<<(ans+mod)%mod;
}