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>
#include<algorithm>
#define rep(a,b,c) for (int a=b;a<=c;a++)
#define per(a,b,c) for (int a=b;a>=c;a--)
#define go(u) for (int o=ft[u],v;v=E[o].t;o=E[o].n)
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef double dob;
typedef pair<int,int> par;
const int P=1000000007,inv2=500000004;
LL ans,n,k,a[233],p[233],cnt;
LL pw(LL x,int k){
	LL y=1;
	while (k){
		if (k&1) y=y*x%P;
		x=x*x%P;
		k>>=1;
	}
	return y;
}
#define g(n) pw(k,(n+1)>>1)
void dfs(LL dep,LL fn,LL gn,LL hn){
	if (dep>cnt){
		LL dlt=g(gn)*hn%P;
		if (fn%2==0) dlt=dlt*inv2%P;
		ans=(ans+dlt*fn)%P;
		return;
	}
	LL ff=fn;
	rep(i,0,a[dep]){
		LL gg=gn;
		rep(j,0,i){
			dfs(dep+1,ff,gg,hn*(i-j>1?0:i-j==1?-1:1));
			gg*=p[dep];
		}
		ff*=p[dep];
	}
}
int main(){
	scanf("%lld%lld",&n,&k);
//	if (n%2==1){
//		printf("%lld\n",g(n)*n%P);
//		return 0;
//	}
	rep(i,2,1e6){
		if (n%i!=0) continue;
		p[++cnt]=i;
		while (n%i==0){
			++a[cnt];
			n/=i;
		}
	}
	if (n!=1) a[++cnt]=1,p[cnt]=n;
	dfs(1,1,1,1);
	ans=(ans+P)%P;
	printf("%lld\n",ans);
	return 0;
}
