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<algorithm>
#include<cstring>
#include<cctype>
#include<cstdio>
#include<cmath>
#define rep(i,x,y) for(int i=x; i<=y; ++i)

using namespace std;
const int N=10005,mod=1000000007;
int n,k,prm[N],c[N],a[N],tot;
typedef long long LL;
LL ret,ans;

LL getmi(LL a,LL x)
{
	LL rt=1;
	while(x)
	{
		if(x&1) rt=rt*a%mod;
		a=a*a%mod,x>>=1;
	}
	return rt;
}

void dfs2(int x,int d,int val)
{
	if(x>tot)
	{
		if(d&1) ret=(ret+d*getmi(k,(d/val+1)/2))%mod;
		else ret=(ret+d/2*getmi(k,(d/val+1)/2))%mod;
		return;
	}
	int nw=a[x]?prm[x]:1;
	rep(i,a[x],c[x]) dfs2(x+1,d*nw,val),nw*=prm[x];
}

void dfs1(int x,int mu,int val)
{
	if(x>tot)
	{
		ret=0,dfs2(1,1,val);
		ans=(ans+mu*ret)%mod;
		return;
	}
	a[x]=0,dfs1(x+1,mu,val);
	a[x]=1,dfs1(x+1,-mu,val*prm[x]);
}

int main()
{
	scanf("%d%d",&n,&k);
	int x=n,lim=sqrt(n);
	rep(i,2,lim) if(x%i==0)
	{
		prm[++tot]=i;
		while(x%i==0) x/=i,++c[tot];
	}
	if(x>1) prm[++tot]=x,c[tot]=1;
	dfs1(1,1,1);
	printf("%lld\n",(ans+mod)%mod);
	return 0;
}