#include <cstdio>
#include <cmath>
#include <vector>
using namespace std;
const int MOD = 1000000007ll;
int modpow(int r, int n) {
int ret = 1;
while (n > 0) {
if (n % 2 > 0) {
ret = ((long long)ret * r) % MOD;
}
r = ((long long)r * r) % MOD;
n /= 2;
}
return ret;
}
int modinv(int n) {
return modpow(n, MOD - 2);
}
int modprod(int a, int b) {
a = a % MOD;
b = b % MOD;
return ((long long)a * b) % MOD;
}
int modprod(int a, int b, int c) {
c = c % MOD;
return (modprod(a, b) * (long long)c) % MOD;
}
int moddiv(int a, int b) {
return ((long long)a * modinv(b)) % MOD;
}
const int N = 1000000;
int lp[N + 1];
int phi[N + 1];
vector<int> pr;
void sieve() {
phi[1] = 1;
for (int i = 2; i <= N; ++i) {
if (lp[i] == 0) {
lp[i] = i;
phi[i] = i - 1;
pr.push_back(i);
}
else {
if (lp[i] == lp[i / lp[i]]) {
phi[i] = phi[i / lp[i]] * lp[i];
}
else {
phi[i] = phi[i / lp[i]] * (lp[i] - 1);
}
}
for (int j = 0; j < (int)pr.size() && pr[j] <= lp[i] && i * pr[j] <= N; ++j) {
lp[i * pr[j]] = pr[j];
}
}
}
int geoseries(int k, int cnt) {
if (k == 1) {
return cnt;
}
int ret = (modpow(k, cnt) - 1 + MOD) % MOD;
ret = modprod(ret, k);
return moddiv(ret, k - 1);
}
int mpow[N + 1];
void proc() {
sieve();
int n, k;
scanf("%d %d", &n, &k);
for (int i = 1; i <= n; ++i) {
mpow[i] = modpow(k, i);
}
int ssum = 0;
for (int i = 1; i <= n; ++i) {
int t = 0;
int lmt = (int)(sqrt(i) + 0.00001);
for (int p = 1; p <= lmt; ++p) {
if (i % p != 0) {
continue;
}
int q = i / p;
t = (t + modprod(mpow[q], phi[p])) % MOD;
if (p != q) {
t = (t + modprod(mpow[p], phi[q])) % MOD;
}
}
t = moddiv(t, i);
ssum = (ssum + t) % MOD;
}
int ans = moddiv(ssum, 2);
int x = moddiv(modprod(k + 1, geoseries(k, n / 2)), 4);
int y = moddiv(geoseries(k, (n + 1) / 2), 2);
printf("%d", (ans + 1 + x + y) % MOD);
}
int main() {
//freopen("input.txt", "r", stdin);
proc();
return 0;
}
