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;
#define rep(i,a,b) for(int i=a;i<b;i++)




#define MOD 1000000007
typedef long long ll;
ll modpow(ll a, ll n) {
	a %= MOD;
	if (a == 0) return 0;
	ll r = 1;
	while (n) r = r*((n % 2) ? a : 1) % MOD, a = a*a%MOD, n >>= 1;
	return r;
}
vector<ll> enumdiv(ll n) {
	vector<ll> S;
	for (ll i = 1; i*i <= n; i++) if (n%i == 0) { S.push_back(i); if (i*i != n) S.push_back(n / i); }
	sort(S.begin(), S.end());
	return S;
}
//-----------------------------------------------------------------
ll N, K;
map<ll, ll> memo;
ll num(ll d) {
	if (memo.find(d) != memo.end()) return memo[d];

	ll ret = modpow(K, (d + 1) / 2);
	
	auto v = enumdiv(d);
	for (ll dd : v) if (dd != d) {
		ret = (ret - num(dd) + MOD) % MOD;
	}

	return memo[d] = ret;
}
//-----------------------------------------------------------------
int main() {
	cin >> N >> K;

	ll ans = 0;
	auto v = enumdiv(N);
	for (ll d : v) {
		if (d % 2)
			ans = (ans + num(d) * d) % MOD;
		else
			ans = (ans + num(d) * d / 2) % MOD;
	}

	cout << ans << endl;
}