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;
const int N = 1e5+100;
const int P = 1e9+7;
#define fr(i,a,b) for(int i = a;i <= b; ++i)
#define nfr(i,a,b) for(int i = a;i >= b; --i)
#define div div1234567891

int n,k;
int val[N];

inline int pow_mod(int x,int k){
   int res = 1,base = x;
   while(k){
      if(k&1)res = 1LL*res*base%P;
      k >>= 1; base = 1LL*base*base%P;
   }
   return res;
}

map<int,int> vis;
vector<int> div;

inline void add(int &x,int y){
   x += y; if(x >= P)x -= P;
}

int main(){
   scanf("%d%d",&n,&k);
   int w = (int)sqrt(n);
   fr(i,1,w){
      if(n%i == 0)div.push_back(i);
   }
   nfr(i,w,1){
      if(i*i != n && n%i == 0)div.push_back(n/i);
   }

   int ans = 0;
   int sz = div.size()-1;
   fr(i,0,sz){
      int cur = div[i];
      val[i] = pow_mod(k,(cur+1)/2);
      fr(j,0,i-1){
         if(div[i]%div[j] == 0)add(val[i],P-val[j]);
      }
      add(ans,1LL*val[i]*(cur%2 == 0 ? cur/2 : cur)%P);
   }
   printf("%d\n",ans);
   return 0;
}
