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 long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define FORR(i,a,b) for(int i=(int)(b)-1;i>=(int)(a);i--)

#define CHMIN(a,b) (a)=min((a),(b))
#define CHMAX(a,b) (a)=max((a),(b))

#define DEBUG(x) cout<<#x<<": "<<(x)<<endl

#define MOD 1000000007

int n,k;
vi divisor;
vl vals;

ll modpow(ll a, ll b){
	ll r = 1;
	while(b){
		if(b&1)r=r*a%MOD;
		a=a*a%MOD;
		b>>=1;
	}
	return r;
}

int main(){
	scanf("%d%d",&n,&k);
	for(int x=1;x*x<=n;x++)if(n%x==0){
		divisor.push_back(x);
		if(x*x==n)continue;
		divisor.push_back(n/x);
	}
	sort(divisor.begin(), divisor.end());
	int m = divisor.size();
	ll ans = 0;
	REP(i,m){
		int d = divisor[i];
		ll val = modpow(k,(d+1)/2);
		REP(j,i)if(d % divisor[j] == 0)(val += MOD - vals[j]) %= MOD;
		vals.push_back(val);
		if(d%2==0)d/=2;
		ans += val * d % MOD;
		ans %= MOD;
	}
	printf("%lld\n", ans);
	return 0;
}