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 <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL N = 200010;
const LL Mod = 1e9+7;
inline LL read()
{
  LL p=0; LL f=1; char ch=getchar();
  while(ch<'0' || ch>'9'){if(ch=='-') f=-1; ch=getchar();}
  while(ch>='0' && ch<='9'){p=p*10+(ch-'0'); ch=getchar();}
  return p*f;
}

vector<LL> V;

LL qpow(LL x,LL k,LL mo){LL s=1; while(k){if(k&1) s=(s*x)%mo; x=(x*x)%mo; k>>=1;} return s;}

LL f[N]; LL n,k;

int main()
{


  n=read(); k=read(); V.clear();
  for(LL i=1;i*i<=n;i++) if(n%i==0)
  {
    V.push_back(i);
    if(i*i!=n) V.push_back(n/i);
  }
  
  sort(V.begin(),V.end());

  LL ans=0; LL ny2=qpow(2,Mod-2,Mod);
  for(LL i=0;i<V.size();i++)
  {
  	LL x=V[i]; f[i]=qpow(k,x/2,Mod);
  	if(x&1) f[i]=f[i]*k%Mod;
  	for(LL j=0;j<i;j++) if(x % V[j] == 0)
  	  f[i] = (f[i] - f[j] + Mod) % Mod;

  	if(x&1) ans = (ans + f[i] * V[i] % Mod ) % Mod;
  	else ans = (ans + f[i] * V[i] % Mod * ny2 % Mod) % Mod;
  	// printf("%lld\n",f[i]);
  }


  return printf("%lld\n",ans),0;
}