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;
long long read()
{
	char ch=getchar();long long x=0,ff=1;
	while(ch<'0'||ch>'9') {if(ch=='-') ff=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return x*ff;
}
void write(long long aa)
{
	if(aa<0) putchar('-'),aa=-aa;
	if(aa>9) write(aa/10);
	putchar('0'+aa%10);
	return;
}
const long long mod=1e9+7;
long long n,K,cnt,ans;
long long shu[1000005],f[1000005],vis[1000005];
long long ksm(long long aa,long long bb)
{
	long long now=1;
	while(bb)
	{
		if(bb&1) now=now*aa%mod;
		aa=aa*aa%mod;bb>>=1;
	}
	return now;
}
void solve(long long aa)
{
	if(vis[aa]) return;
	vis[aa]=1;
	f[aa]=ksm(K,(shu[aa]+1)/2);
	for(long long i=1;i<aa;++i)
	if(shu[aa]%shu[i]==0) 
	{
		solve(i);
		f[aa]=(f[aa]-f[i]+mod)%mod;
	}
	if(shu[aa]%2==0) (ans+=(shu[aa]/2)*f[aa]%mod)%=mod;
	else (ans+=shu[aa]*f[aa]%mod)%=mod;
	return;
}
int main()
{
	n=read(),K=read();
	for(long long i=1;i*i<=n;++i) if(n%i==0)
	{
		shu[++cnt]=i;
		if(i*i!=n) shu[++cnt]=n/i;
	}
	sort(shu+1,shu+cnt+1);
	solve(cnt);
	write(ans);
	return 0;
}