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;
const int maxn=1500;
const int q=1e9+7;
inline int Plus(int x,int y) {return (x+=y)>=q?x-q:x;}
inline void Pe(int &x,int y) {x=Plus(x,y);}
inline int Sub(int x,int y) {return (x-=y)<0?x+q:x;}
inline void Se(int &x,int y) {x=Sub(x,y);}
inline int Multi(int x,int y) {return 1ll*x*y%q;}
inline void Me(int &x,int y) {x=Multi(x,y);}
inline int mi(int x,int y) {
	int ret=1;
	for (;y;y>>=1,Me(x,x)) if (y&1) Me(ret,x);
	return ret;
}
int d[maxn],s=0,n,k,f[maxn],ans=0;
int main() {
	cin>>n>>k;
	for (int i=1;i*i<=n;++i) if (n%i==0) {
		d[++s]=i;
		if (i*i!=n) d[++s]=n/i;
	}
	sort(d+1,d+s+1);
	for (int i=1;i<=s;++i) {
		int di=d[i],&fi=f[i]=mi(k,(di+1)/2);
		for (int j=1;j<i;++j) if (di%d[j]==0) Se(fi,f[j]);
		Pe(ans,((1ll*fi*di)>>(~di&1))%q);
	}
	cout<<ans<<endl;
}
