output_description: Print the number of the sequences a that can be obtained after the procedure,
  modulo 10^9+7.
  
  * * *
input_description: The input is given from Standard Input in the following format:
  
      
      
      N K
attempt: #include <bits/stdc++.h>
  
  using namespace std;
  typedef long long ll;
  typedef pair<ll, ll> p_ll;
  
  template<class T>
  void debug(T itr1, T itr2) { auto now = itr1; while(now<itr2) { cout << *now << " "; now++; } cout << endl; }
  #define repr(i,from,to) for (ll i=(ll)from; i<(ll)to; i++)
  #define all(vec) vec.begin(), vec.end()
  #define rep(i,N) repr(i,0,N)
  #define per(i,N) for (int i=(int)N-1; i>=0; i--)
  
  const ll MOD = pow(10,9)+7;
  const ll LLINF = pow(2,61)-1;
  const int INF = pow(2,30)-1;
  
  vector<ll> fac;
  void c_fac(int x=pow(10,6)+10) { fac.resize(x,true); rep(i,x) fac[i] = i ? (fac[i-1]*i)%MOD : 1; }
  ll inv(ll a, ll m=MOD) { ll b = m, x = 1, y = 0; while (b!=0) { int d = a/b; a -= b*d; swap(a,b); x -= y*d; swap(x,y); } return (x+m)%m; }
  ll nck(ll n, ll k) { return fac[n]*inv(fac[k]*fac[n-k]%MOD)%MOD; }
  ll gcd(ll a, ll b) { if (a<b) swap(a,b); return b==0 ? a : gcd(b, a%b); }
  ll lcm(ll a, ll b) { return a/gcd(a,b)*b; }
  
  // ----------------------------------------------------------------------
  // ----------------------------------------------------------------------
  
  vector<bool> isp;
  
  void sieve(int x=pow(10,6)+10) {
    isp.resize(x,true); 
    isp[0] = false;
    isp[1] = false;
    for (int i=2; pow(i,2)<=x; i++) {
      if (isp[i]) for(int j=2; i*j<=x; j++) isp[i*j] = false;
    }
  }
  
  // ----------------------------------------------------------------------
  // ----------------------------------------------------------------------
  
  ll pnk(ll n, ll k) {
    ll pn = n, now = 0, result = 1;
    while (k>=1ll<<now) {
      if (k&1ll<<now) result = result * pn % MOD;
      pn = pn * pn % MOD;
      now++;
    }
    return result;
  }
  
  int main() {
    ll N, K; cin >> N >> K;
  
    // map<string, ll> m;
    // rep(i,1<<N/2) {
    //   string S; rep(j,N/2) S += i&1<<j ? '1' : '0';
    //   rep(j,N/2) S += S[N/2-1-j];
    //   rep(j,N) {
    //     m[S]++;
    //     S = S.substr(1) + S[0];
    //   }
    // }
    // cout << m.size() << endl;
  
    sieve();
    vector<ll> yaku;
    for (ll i=1; i*i<=N; i++) {
      if (N%i==0) {
        yaku.push_back(i);
        if (i*i!=N) yaku.push_back(N/i);
      }
    }
    sort(all(yaku));
    // debug(all(yaku));
  
    ll l = yaku.size();
    vector<ll> count(l,0);
  
    rep(i,l) {
      count[i] = pnk(K,(yaku[i]+1)/2);
      rep(j,i) if (yaku[i]%yaku[j]==0) count[i] = (count[i]-count[j]+MOD) % MOD;
    }
    // debug(all(count));
  
    ll result = 0; rep(i,l) result = (result+(yaku[i]%2 ? yaku[i] : yaku[i]/2)*count[i]) % MOD;
    cout << result << endl;
  
    return 0;
  }
problem_description: Statement
  
  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?
samples: [{"input": "4 2", "output": "6\n    \n\nThe following six sequences can be obtained:\n\n  * (1, 1, 1, 1)\n  * (1, 1, 2, 2)\n  * (1, 2, 2, 1)\n  * (2, 2, 1, 1)\n  * (2, 1, 1, 2)\n  * (2, 2, 2, 2)\n\n* * *"}, {"input": "1 10", "output": "10\n    \n\n* * *"}, {"input": "6 3", "output": "75\n    \n\n* * *"}, {"input": "1000000000 1000000000", "output": "875699961"}]