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<cstring>
#include<cmath>
#include<algorithm>
#include<functional>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
using namespace std;
#define MOD 1000000007
#define f(i,n) for(long long i=0;i<(long long)(n);i++)
#define N 200000

long long p[30];
void init(long long k){
p[0]=k;
f(i,29){
p[i+1]=p[i]*p[i];
p[i+1]=p[i+1]%MOD;
}
return;
}

long long po(long long x){
long long re=1;
f(i,30){
if(x%2==1){
re=re*p[i];
re=re%MOD;
}
x=x/2;
}
return re;
}



int main(){
vector<long long>a;
vector<long long>b;
	long long n,k;
	long long x,s, ans;

	scanf("%lld %lld", &n,&k);
init(k);
x=1;
while((x*x)<=n){
if(n%x==0){
a.push_back(x);
a.push_back(n/x);
}
x++;
}
sort(a.begin(),a.end());

f(i,a.size()){
x=(a[i]+1)/2;
s=po(x);
f(j,i){
if(a[i]%a[j]==0){
s+=(MOD-b[j]);
s=s%MOD;
}
}
b.push_back(s);
}
ans=0;
f(i,a.size()){
if(a[i]%2==0){
s=b[i]*(a[i]/2);
s=s%MOD;
ans+=s;
ans=ans%MOD;
}
else{
s=b[i]*a[i];
s=s%MOD;
ans+=s;
ans=ans%MOD;
}
}

	printf("%lld\n", ans);


	return 0;
}