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<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#define MN 50005
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
map<int,ll> f;
int n,k,num[10000005],a[MN],sum[MN],tot,tt;ll ans;
ll pow(int x,int y){
	ll tmp=1;
	while(y){
		if(y&1)tmp=tmp*x%mod;
		y>>=1,x=1ll*x*x%mod;
	}return tmp;
}
void add(ll &x,int y){(x+=y)>=mod?x-=mod:0;}
void dec(ll &x,int y){(x-=y)<0?x+=mod:0;}
void dfs(int u,int now){
	if(u==tot+1){num[++tt]=now;return ;}
	for(int i=0;i<=sum[u];i++)dfs(u+1,now*pow(a[u],i));
}
int main(){
	scanf("%d%d",&n,&k);int tmp=(int)sqrt(n);f[1]=k;
	int now=n;
	for(int i=2;i<=tmp;i++)if(now%i==0){
		a[++tot]=i;
		while(now%i==0)now/=i,sum[tot]++;
	}if(now!=1)a[++tot]=now,sum[tot]=1;dfs(1,1);
	sort(num+1,num+tt+1);
	for(int i=2;i<=tt;i++){
		f[num[i]]=pow(k,(num[i]+1)/2);
		for(int j=2;j<sqrt(num[i]);j++)if(num[i]%j==0){
			dec(f[num[i]],f[j]),dec(f[num[i]],f[num[i]/j]);
		}dec(f[num[i]],f[1]);
		if((int)sqrt(num[i])*(int)sqrt(num[i])==num[i])dec(f[num[i]],f[(int)sqrt(num[i])]);
	}for(int i=1;i<=tt;i++)if(num[i]%2==1)add(ans,f[num[i]]*num[i]%mod);else add(ans,f[num[i]]*num[i]/2%mod);
	printf("%lld\n",ans);
}