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;
using Int = long long;
//INSERT ABOVE HERE
signed main(){
  Int n,k;
  cin>>n>>k;
  vector<Int> v;
  for(Int i=1;i*i<=n;i++){
    if(n%i) continue;
    v.emplace_back(i);
    v.emplace_back(n/i);
  }
  sort(v.begin(),v.end());
  v.erase(unique(v.begin(),v.end()),v.end());
  Int m=v.size();

  const Int MOD = 1e9+7;
  auto mod_pow=[&](Int b,Int x){
    Int res=1;
    while(x){
      if(x&1) res=res*b%MOD;
      b=b*b%MOD;
      x>>=1;
    }
    return res;
  };
  //Int inv=mod_pow(2,MOD-2);
  
  Int ans=0;
  vector<Int> dp(m);
  for(Int i=0;i<m;i++){
    dp[i]=mod_pow(k,(v[i]+1)/2);
    for(Int j=0;j<i;j++)
      if(v[i]%v[j]==0) dp[i]+=MOD-dp[j];
    dp[i]%=MOD;
    if(v[i]&1) ans+=dp[i]*v[i]%MOD;
    else ans+=dp[i]*(v[i]/2)%MOD;
    ans%=MOD;
    //cout<<v[i]<<":"<<dp[i]<<endl;
  }
  
  cout<<ans<<endl;
  return 0;
}
