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>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}
typedef long long ll;
ll mod=1e9+7;
ll ex(ll x,ll p){
	ll a=1;
	while(p){
		if(p%2) a=a*x%mod;
		x=x*x%mod;
		p/=2;
	}
	return a;
}
int N,X;
vector<int> ds;
ll dp[10000];
int main(){
	cin>>N>>X;
	for(int i=1;i*i<=N;i++){
		if(N%i==0){
			ds.pb(i);
			if(i*i!=N) ds.pb(N/i);
		}
	}
	sort(all(ds));
	int K=ds.size();
	rep(i,K){
		int L=ds[i];
		ll tmp=ex(X,(L+1)/2);
		rep(j,i) if(ds[i]%ds[j]==0) tmp-=dp[j];
		tmp=(tmp%mod+mod)%mod;
		dp[i]=tmp;
	}
	ll ans=0;
	rep(i,K){
		ll ad=dp[i]*ds[i];
		if(ds[i]%2==0) ad/=2;
		ans=(ans+ad)%mod;
	}
	cout<<ans<<endl;
}
