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 <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
const int mod = 1000000007;
long long modpow(long long n, int k) {
	long long r = 1;
	while (k > 0) {
		if (k & 1) r = (r * n) % mod;
		n = (n * n) % mod;
		k >>= 1;
	}
	return r;
}
int main() {
	int N, K;
	cin >> N >> K;
	vector<int> D;
	for (int i = 1; i*i <= N; ++i) if (N % i == 0) {
		D.push_back(i);
		if (N/i > i) D.push_back(N/i);
	}
	sort(D.begin(), D.end());
	map<int, int> num;
	long long res = 0;
	for (int i = 0; i < D.size(); ++i) {
		int d = D[i];
		long long r = modpow(K, (d + 1) / 2);
		for (int j = 0; j < i; ++j) if (d % D[j] == 0) {
			r = (r - num[D[j]] + mod) % mod;
		}
		num[d] = r;
		if (d % 2) {
			res = (res + r * d) % mod;
		} else {
			res = (res + r * (d / 2)) % mod;
		}
	}
	cout << res << endl;
}
