#include<bits/stdc++.h>
using namespace std;

const int mod = 1e9 + 7;

int exp(int x, int n) {
    int ret = 1;
    while(n) {
        if(n & 1) ret = 1LL * ret * x % mod;
        x = 1LL * x * x % mod;
        n >>= 1;
    }
    return ret;
}

int N, K, ans;
vector<int> Dv;
int add[100000];

int main() {
    scanf("%d %d", &N, &K);

    ans = 0;
    ans += 1LL * exp(K, (N + 1) / 2) * (N % 2 == 0? N / 2 : N) % mod;
    ans %= mod;

    for(int i = 1; i <= sqrt(N); i++) {
        if(N % i == 0) {
            Dv.push_back(i);
            Dv.push_back(N / i);
        }
    }
    sort(Dv.begin(), Dv.end());

    for(int i = 0; i < Dv.size(); i++) {
        int d = Dv[i];
        if(d == N) break;

        add[i] += exp(K, (d + 1) / 2);

        for(int j = 0; j < i; j++) {
            if(Dv[i] % Dv[j] == 0) {
                add[i] += mod - add[j];
                add[i] %= mod;
            }
        }

        ans += mod - 1LL * add[i] * ((N % 2 == 0? N / 2 : N) - (d % 2 == 0? d / 2 : d)) % mod;
        ans %= mod;
    }

    cout << ans;
}
