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;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
typedef long long ll;
#define pu push
#define pb push_back
#define mp make_pair
#define rep(i,x) for(int i=0;i<x;i++)
#define mod 1000000007
ll n,k;
vector<ll>num,cnt;
ll modpow(ll x,ll n)
{
	ll res=1;
	while(n>0)
	{
		if(n&1) res=res*x%mod;
		x=x*x%mod;
		n>>=1;
	}
	return res;
}
int main(){
	cin >> n >> k;
	for(ll i=1;i*i<=n;i++){
		if(n%i == 0) num.pb(i);
		if(n%i == 0 && i*i != n) num.pb(n/i);
	}
	sort(num.begin(),num.end()); 
	ll ret = 0;
	for(int i=0;i<num.size();i++){
		cnt.pb(1);
		int q = (num[i]+1)/2;
		cnt[i] = modpow(k,q); //cout << cnt[i] << endl;
		for(int j=0;j<i;j++){
			if(num[i]%num[j] == 0){
				cnt[i] = cnt[i]+mod-cnt[j]*(num[j]%2==0?2:1);
				cnt[i] %= mod;
			}
		}
		if(num[i]%2 == 0) cnt[i] = cnt[i]*(500000004LL)%mod;
		//cnt[i] = cnt[i] * num[i] % mod;
		ret += cnt[i] * num[i] % mod; //cout << cnt[i] << endl;
	}
	cout << ret%mod << endl;
}