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<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<bitset>
#include<map>

#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)

using namespace std;

typedef long long LL;
typedef double db;

const int N = 1e+5+5;
const int mo = 1e+9+7;

int a[N],m;
int f[N];

int dec(int x,int y){return x>=y?x-y:x+mo-y;}

int quickmi(LL x,int tim){LL ans=1;for(;tim;tim/=2,x=x*x%mo)if (tim&1)ans=ans*x%mo;return ans;}

int add(int x,int y){return x+y>=mo?x+y-mo:x+y;}

int main(){
	int n,k;
	scanf("%d%d",&n,&k);
	fo(i,1,sqrt(n))
	if (n%i==0){
		a[++m]=i;
		if (n/i!=i)a[++m]=n/i;
	}
	sort(a+1,a+1+m);
	f[1]=k;
	fo(i,2,m){
		f[i]=quickmi(k,(a[i]+1)/2);
		fo(j,1,i-1)
		if (a[i]%a[j]==0)f[i]=dec(f[i],f[j]);
	}
	int ans=0;
	fo(i,1,m)
	if (a[i]&1)ans=add(ans,1ll*f[i]*a[i]%mo);
	else ans=add(ans,1ll*f[i]*a[i]/2%mo);
	printf("%d\n",ans);
	return 0;
}