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 <iostream>
#include <cstdio>
#include <cstring>
#include <cassert>
#include <cctype>
using namespace std;
typedef long long lint;
#define cout cerr
#define ni (next_num<int>())
template<class T>inline T next_num(){
	T i=0;char c;
	while(!isdigit(c=getchar())&&c!='-');
	bool flag=c=='-';
	flag?(c=getchar()):0;
	while(i=i*10-'0'+c,isdigit(c=getchar()));
	return flag?-i:i;
}
const int dN=5010,O=1000000007;
inline int fpow(int x,int n){
	lint a=1;
	for(;n;n>>=1,x=(lint)x*x%O){
		if(n&1){
			a=(lint)a*x%O;
		}
	}
	return a;
}
inline int inv(int x){
	return fpow(x,O-2);
}
int fact[dN],fs=0;
lint f[dN];
inline void addfact(int x,int e){
	for(int i=0,j=0;i<e;i++){
		for(int k=fs;j<k;j++){
			fact[fs++]=fact[j]*x;
		}
	}
}
int main(){
	int n=ni,k=ni;
	fact[fs++]=1;
	for(int x=2,e;x*x<=n;x++){
		for(e=0;n%x==0;n/=x,e++);
		addfact(x,e);
	}
	if(n!=1){
		addfact(n,1);
	}
	lint ans=0;
	for(int i=0;i<fs;i++){
		int d=fact[i];
		f[i]=fpow(k,(d+1)>>1);
		for(int j=0;j<i;j++){
			if(d%fact[j]==0){
				f[i]-=f[j];
			}
		}
		f[i]=(f[i]%O+O)%O;
		static int inv2=inv(2);
		ans+=d&1?f[i]*d%O:(f[i]*d%O*inv2%O);
	}
	printf("%lld\n",ans%O);
	return 0;
}