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>
#define mod 1000000007
using namespace std;
typedef long long ll;
inline int read()
{
	int x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
	return x*f;
}
inline int qpow(int bas,int pw)
{
	int ret=1; for(;pw;pw>>=1,bas=1ll*bas*bas%mod)
	if(pw&1) ret=1ll*ret*bas%mod; return ret;
}
inline void Add(int &x,int y)
{
	x+=y; if(x>=mod) x-=mod;
	if(x<0) x+=mod;
}
int n,k,di[10010],F[10010];
int main()
{
	n=read(); k=read();
	for(int i=1;i*i<=n;i++) if(n%i==0)
	{
		di[++di[0]]=i; if(i*i!=n)
		di[++di[0]]=n/i;
	}
	sort(di+1,di+1+di[0]);
	for(int i=1;i<=di[0];i++)
	{
		F[i]=qpow(k,(di[i]+1)/2);
		for(int j=1;j<i;j++) if(di[i]%di[j]==0)
			Add(F[i],-F[j]);
	}
	int Ans=0;
	for(int i=1;i<=di[0];i++)
		if(di[i]&1) Add(Ans,1ll*di[i]*F[i]%mod);
		else Add(Ans,1ll*di[i]/2*F[i]%mod);
	cout << Ans << endl;
	return 0 ;
}