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 <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
int gi() {
	int w;bool q=1;char c;
	while (((c=getchar())<'0'||'9'<c)&&c!='-');
	if (c=='-') q=0,c=getchar();
	w=c-'0';
	while ('0'<=(c=getchar())&&c<='9') w=w*10+c-'0';
	return q?w:-w;
}
const int mod=1e9+7;
inline int qpow(int x,int y) {
	int ans=1;
	while (y) {
		if (y&1) ans=1LL*ans*x%mod;
		x=1LL*x*x%mod;y>>=1;
	}
	return ans;
}
const int N=1e5;
int p[N],c[N],f[N];
int main()
{
	int n=gi(),m=gi(),i,j,ans=0,sq=sqrt(n),len=0;
	const int inv2=(mod+1)>>1;
	for (i=1;i<=sq;i++) if (!(n%i)) p[++len]=i;
	for (i=sq*sq==n?sq-1:sq;i;i--) if (!(n%i)) p[++len]=n/i;
	for (i=1;i<=len;i++) {
		f[i]=qpow(m,(p[i]+1)>>1);
		for (j=1;j<i;j++)
			if (!(p[i]%p[j]))
				(f[i]-=f[j])%=mod;
	}
	for (i=1;i<=len;i++) ans=(ans+1LL*f[i]*p[i]%mod*(p[i]&1?1:inv2))%mod;
	printf("%d\n",(ans+mod)%mod);
	return 0;
}
