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 <cstdlib>
#include <algorithm>
#include <map>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fod(i,a,b) for(int i=a;i>=b;i--)
#define efo(i,q) for(int i=A[q];i;i=B[i][0])
using namespace std;
typedef long long LL;
const int N=100500,mo=1e9+7;
int m,n;
int fj[N][2],fj0;
int d[N];
LL ans;
map<int,int>f;
LL ksm(LL q,int w) {
	LL ans=1;
	for(; w; w>>=1,q=q*q%mo)if(w&1)ans=ans*q%mo;
	return ans;
}
int ss1(int q,int w,int e) {
	if(q>w)return f[e];
	int ans=ss1(q+1,w,e);
	fo(i,1,d[q])((ans+=ss1(q+1,w,(e=e*fj[q][0])))>=mo?ans-=mo:0);
	return ans;
}
void ss(int q,int e) {
	if(q>fj0) {
		LL t=(((n/e)%2?ksm(m,(e+1)>>1):ksm(m,e))-ss1(1,q,1)+mo)%mo;
		f[e]=t;
		ans=(ans+t*e)%mo;
		return;
	}
	d[q]=0;
	ss(q+1,e);
	fo(i,1,fj[q][1])d[q]=i,ss(q+1,(e*=fj[q][0]));
}
int main() {
	int q,w;
	scanf("%d%d",&n,&m);
	if(n==1)return printf("%d\n",m),0;
	q=n;
	for(int i=2; i*i<=q; ++i)if(q%i==0) {
			for(fj[++fj0][0]=i; !(q%i); ++fj[fj0][1],q/=i);
		}
	if(q>1)fj[++fj0][0]=q,fj[fj0][1]=1;
	ss(1,1);
	printf("%lld\n",(ans+mo)%mo);
	return 0;
}