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 <cstring>
#define LL long long
#define MAXN 100010

const LL P=1000000007;

LL n,m,lim=100000;
LL f1[MAXN],f2[MAXN];
LL p1[MAXN],p2[MAXN];

void init(){
	p1[0]=1;
	for(int i=1;i<=lim;i++)
		p1[i]=p1[i-1]*m%P;
	p2[0]=1;
	for(int i=1;i<=lim;i++)
		p2[i]=p2[i-1]*p1[lim]%P;
}

LL getP(LL x){ return p2[x/lim]*p1[x%lim]%P; }

LL dp(int x){
	if(x<=lim){
		if(~f1[x]) return f1[x];
	}else{
		if(~f2[n/x]) return f2[n/x];
	}
	LL res=getP((x+1)/2);
	for(int i=1;i*i<=x;i++){
		if(x%i) continue;
		int j=x/i;
		if(i!=x) res=(res-dp(i))%P;
		if(j!=i && j!=x) res=(res-dp(j))%P;
	}
	if(res<0) res+=P;
	if(x<=lim){
		return f1[x]=res;
	}else{
		return f2[n/x]=res;
	}
}

LL g(int x){
	if(x&1) return x;
	else return x>>1;
}

int main(){
#ifdef DEBUG
	freopen("F.in","r",stdin);
#endif
	memset(f1,-1,sizeof f1);
	memset(f2,-1,sizeof f2);
	scanf("%lld%lld",&n,&m);
	init();
	dp(n);
	LL ans=0;
	for(int i=1;i<=lim;i++)
		if(f1[i]!=-1)
			ans=(ans+f1[i]*g(i))%P;
	for(int i=1;i<=lim;i++)
		if(f2[i]!=-1)
			ans=(ans+f2[i]*g(n/i))%P;
	printf("%lld\n",ans);
	return 0;
}
