//ll sig(ll x){
//    int ans = 1;
//    for(ll i = 2; i*i <= x; ++i){
//        if(x%(i*i)==0)
//            return 0;
//        if(x%i == 0){
//            x /= i;
//            ans *= -1;
//        }
//    }
//    if(x > 1)
//        ans *= -1;
//    return ans;
//}
//ll f(ll n, ll k){
//    return ipow(k,n/2+1)*n%MOD;
//}
//void __(){
//    ll n,k;
//    cin >> n >> k;
//            //if(x != n)
//    bool odd = true;
//    if(n%2 == 0){
//        n /= 2;
//        odd = false;
//    }
//    vl divs;
//    for(ll i = 1; i*i <= n; ++i){
//        if(n%i == 0){
//            divs.pb(i);
//            if(i*i < n)
//                divs.pb(n/i);
//        }
//    }
//    sort(rall(divs));
//    ll ans = 0;
//    for(int x : divs){
//        ll ways = 0;
//        for(int y : divs){
//            if(x%y == 0){
//                if(!odd)
//                    ways += sig(x/y)*ipow(k,y);
//                else
//                    ways += sig(x/y)*ipow(k,y/2+1);
//            }
//        }
//        ways %= MOD;
//        ans += ways*x%MOD;
//    }
//    ans = (ans%MOD+MOD)%MOD;
//    print ans;
//}
//
#include <iomanip>
#include <algorithm>
#include <vector>
#include <utility>
#include <iostream>
#include <string>
#define pb push_back
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define sz(v) ll(v.size())
#define T1 template<typename T> static
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
const ll MOD = 1e9 + 7;
T1 ostream& operator<<(ostream& stream, const vector<T>& t);
T1 istream& read(T, T, istream& = cin);
ll ipow(ll x, ll p, ll mod = MOD){
    if(abs(x) >= mod)
        x %= mod;
    if(x < 0)
        x += mod;
    if(p == 0)
        return 1;
    if(p == 1)
        return x;
    return ipow(x * x % mod, p / 2, mod) * ipow(x, p % 2, mod) % mod;
}
struct _print {
    string sep,end;
    bool space;
    ostream &stream;
    _print(string _sep=" ",string _end="\n",
            ostream &_stream = cout) 
        : sep(_sep),end(_end),space(false),
            stream(_stream) {}
    ~_print() { stream << end; }

    template <typename T>
        _print &operator , (const T &t) {
            if (space) stream << sep;
            space = true;
            stream << t;
            return *this;
        }
};
#define print _print(),
ll sig(ll x){
    int ans = 1;
    for(ll i = 2; i*i <= x; ++i){
        if(x%(i*i)==0)
            return 0;
        if(x%i == 0){
            x /= i;
            ans *= -1;
        }
    }
    if(x > 1)
        ans *= -1;
    return ans;
}
ll f(ll n, ll k){
    return ipow(k,n/2+1)*n%MOD;
}
void __(){
    ll n,k;
    cin >> n >> k;
            //if(x != n)
    bool odd = true;
    if(n%2 == 0){
        n /= 2;
        odd = false;
    }
    vl divs;
    for(ll i = 1; i*i <= n; ++i){
        if(n%i == 0){
            divs.pb(i);
            if(i*i < n)
                divs.pb(n/i);
        }
    }
    sort(rall(divs));
    ll ans = 0;
    for(int x : divs){
        ll ways = 0;
        for(int y : divs){
            if(x%y == 0){
                if(!odd)
                    ways += sig(x/y)*ipow(k,y);
                else
                    ways += sig(x/y)*ipow(k,y/2+1);
            }
        }
        ways %= MOD;
        ans += ways*x%MOD;
    }
    ans = (ans%MOD+MOD)%MOD;
    print ans;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
        __();
}



Measured memory_bytes: 256