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
//Love and Freedom.
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<map>
#define ll long long
#define inf 20021225
#define mdn 1000000007
using namespace std;
int read()
{
	int s=0,t=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')	t=-1; ch=getchar();}
	while(ch>='0' && ch<='9')	s=s*10+ch-'0',ch=getchar();
	return s*t;
}
map<int,int> f; int n,k;
int ksm(int bs,int mi)
{
	int ans=1;
	while(mi)
	{
		if(mi&1)	ans=1ll*ans*bs%mdn;
		bs=1ll*bs*bs%mdn; mi>>=1;
	}
	return ans;
}
void upd(int &x,int y){x+=x+y>=mdn?y-mdn:y;}
int calc(int x)
{
	if(f.find(x)!=f.end())	return f[x];
	int tmp=ksm(k,x+1>>1);
	for(int i=1;i*i<=x;i++)	if(x%i==0)
	{
		if(i!=x)	upd(tmp,mdn-calc(i));
		if(i!=x/i&&x/i!=x)	upd(tmp,mdn-calc(x/i));
	}
	return f[x]=tmp;
}
int odd,even;
int main()
{
	n=read(),k=read();
	for(int i=1;i*i<=n;i++)	if(n%i==0)
	{
		int w=i;
		if(w&1)	upd(odd,1ll*w*calc(w)%mdn); else	upd(even,1ll*w*calc(w)%mdn);
		w=n/i; if(w==i)	continue;
		if(w&1)	upd(odd,1ll*w*calc(w)%mdn); else	upd(even,1ll*w*calc(w)%mdn);
	}
	even=500000004ll*even%mdn;
	printf("%d\n",(odd+even)%mdn);
	return 0;
}