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<stdio.h>
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i, x, n) for(int i = x; i < n; ++i)

int md = 1e9 + 7;
map<int, int> p;

int pw(int x, int p) {
	if (!p)return 1;
	int t = pw(x, p >> 1);
	t = (ll)t * t % md;
	if (p & 1)t = (ll)t * x % md;
	return t;
}

int main() {
	int n, k;
	scanf("%d%d", &n, &k);
	for (int i = 1; i * i <= n; ++i)if (n % i == 0)p[i], p[n / i];
	for (map<int, int>::iterator it = p.begin(); it != p.end(); ++it) {
		it->second = pw(k, it->first + 1 >> 1);
		if (it->first == 1)continue;
		for (int i = 1; i * i <= it->first; ++i)if (it->first % i == 0) {
			it->second += md - p[i];
			if (it->second >= md)it->second -= md;
			if (it->first / i != i && i != 1) {
				it->second += md - p[it->first / i];
				if (it->second >= md)it->second -= md;
			}
		}
	}
	int an = 0;
	for (map<int, int>::iterator it = p.begin(); it != p.end(); ++it) {
		an += (ll)it->second * (it->first & 1 ? it->first : it->first >> 1) % md;
		if (an >= md)an -= md;
	}
	printf("%d\n", an);
}