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<cstdio> 
#include<algorithm>
#include<cstring>
#include<cmath>
#include<set>
#include<map>
using namespace std;
#define fo(i,j,k) for(i=j;i<=k;i++)
#define fd(i,j,k) for(i=j;i>=k;i--)
#define cmax(a,b) (a=(a>b)?a:b)
#define cmin(a,b) (a=(a<b)?a:b)
typedef long long ll;
const int N=1e6+5,M=2e6+5,mo=1e9+7;
ll f[N],fac[N],i,n,K,j,ans;
ll ksm(ll x,ll y)
{
	ll ret=1;
	while (y)
	{
		if (y&1) ret=ret*x%mo;
		y>>=1;
		x=x*x%mo;
	}
	return ret;
}
void predo()
{
	fo(i,1,trunc(sqrt(n)))
	if (n%i==0)
	{
		fac[++fac[0]]=i;
		if (i*i!=n) fac[++fac[0]]=n/i;
	}
	sort(fac+1,fac+1+fac[0]);
}
int main()
{
	scanf("%lld %lld",&n,&K);
	predo();
	fo(i,1,fac[0])
	{
		f[i]=ksm(K,(fac[i]+1)/2);
		fo(j,1,i-1)
			if (fac[i]%fac[j]==0)
				(f[i]-=f[j])%=mo;
		if (fac[i]%2)
			(ans+=f[i]*fac[i])%=mo;
		else (ans+=f[i]*fac[i]/2)%=mo;
	}
	printf("%lld\n",(ans+mo)%mo);
}