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;
#define LL long long

const int mo=1e9+7;
const int maxn=23333;

int n,k,m,d[maxn],dp[maxn],Ans;

int power(int x,int k)
{
	int res=1;
	while (k)
	{
		if (k&1) res=(LL)res*x%mo;
		x=(LL)x*x%mo;
		k>>=1;
	}
	return res;
}

int main()
{
#ifdef h10
	freopen("F.in","r",stdin);
	freopen("F.out","w",stdout);
#endif
	int i,j;
	scanf("%d%d",&n,&k);
	for (i=1;i*i<=n;i++)
		if (n%i==0)
		{
			d[++m]=i;
			if (i*i!=n) d[++m]=n/i;
		}
	sort(d+1,d+1+m);
	for (i=1;i<=m;i++)
	{
		dp[i]=power(k,(d[i]+1)/2);
		for (j=1;j<i;j++)
			if (d[i]%d[j]==0)
				(dp[i]+=mo-dp[j])%=mo;
		if (d[i]&1)
			(Ans+=(LL)dp[i]*d[i]%mo)%=mo;
		else
			(Ans+=(LL)dp[i]*(d[i]/2)%mo)%=mo;
	}
	printf("%d\n",Ans);
}
