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 <map>
#define int long long
using namespace std;

int mod = 1000000007;
int n, k;
map<int, int> num;

int power(int a, int n) {
	if (n == 0) return 1;
	if (n % 2 == 0) return power((a * a) % mod, n / 2) % mod;
	return (a * power(a, n - 1)) % mod;
}

void setNum(int d) {
	num[d] = power(k, (d + 1) / 2);
	for (int i = 1; i * i <= d; i++) {
		if (d % i != 0) continue;
		if (i != d) {
			if (num.find(i) == num.end()) setNum(i);
			num[d] = (num[d] + mod - num[i]) % mod;
		}
		if (i != d / i && d / i != d) {
			if (num.find(d / i) == num.end()) setNum(d / i);
			num[d] = (num[d] + mod - num[d / i]) % mod;
		}
	}
}

signed main() {
	int i;
	
	cin >> n >> k;
	
	for (i = 1; i * i <= n; i++) {
		if (n % i != 0) continue;
		setNum(i);
		setNum(n / i);
	}
	
	int ans = 0;
	for (map<int, int>::iterator it = num.begin(); it != num.end(); it++) {
		int d = (*it).first;
		int cnt = (*it).second;

		if (d % 2) {
			ans += d * cnt;
		}
		else {
			ans += (d / 2) * cnt;
		}
		ans %= mod;
	}
	cout << ans << endl;
	return 0;
}