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, l, r) for(int i = (l), i##end = (r);i <= i##end;++i)
using std::cin; using std::cout;
const int maxn = 200200;
typedef long long ll;
const int mod = 1e9 + 7;
inline ll pow(ll a,int b,int ans = 1) {
	for(;b;b >>= 1,a = a * a % mod) if(b & 1)
		ans = ans * a % mod;
	return ans;
}
inline ll inverse(int x){ return pow(x, mod - 2); }
std::vector<int> ytx;
int n, k;
int dp[maxn];
inline void reduce(int & x) {
	x += x >> 31 & mod;
}
int main() {
	std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n >> k;
	for(int i = 1;i * i <= n;++i) if(n % i == 0) {
		ytx.push_back(i);
		if(i * i != n) ytx.push_back(n / i);
	}
	sort(ytx.begin(), ytx.end());
	int lol = 0;
	rep(i, 0, ytx.size() - 1) {
		dp[i] = pow(k, ytx[i] + 1 >> 1);
		rep(j, 0, i - 1) if(ytx[i] % ytx[j] == 0) reduce(dp[i] -= dp[j]);
		lol = (lol + dp[i] * (ytx[i] & 1 ? ytx[i] : ytx[i] + 1ll >> 1)) % mod;
	}
	cout << lol << '\n';
}
