#include <cstdio>
using namespace std;
const long long MOD = 1000000007ll;
long long modpow(long long r, long long n) {
long long ret = 1;
while (n > 0) {
if (n % 2 > 0) {
ret = (ret * r) % MOD;
}
r = (r * r) % MOD;
n /= 2;
}
return ret;
}
long long modinv(long long n) {
return modpow(n, MOD - 2);
}
long long modprod(long long a, long long b) {
a = a % MOD;
b = b % MOD;
return (a * b) % MOD;
}
long long modprod(long long a, long long b, long long c) {
c = c % MOD;
return (modprod(a, b) * c) % MOD;
}
long long moddiv(long long a, long long b) {
return (a * modinv(b)) % MOD;
}
long long gcd(long long a, long long b) {
if (a < b) {
return gcd(b, a);
}
return (b == 0) ? a : gcd(b, a % b);
}
void proc() {
long long n, k;
scanf("%lld %lld", &n, &k);
long long ans = 1;
for (long long i = 1; i <= n; ++i) {
long long t = 0;
for (long long p = 1; p <= i; ++p) {
t = (t + modpow(k, gcd(i, p))) % MOD;
}
t = moddiv(t, i);
long long u = 0;
if (i % 2 == 0) {
u = moddiv(t, 2);
long long v = modprod(k + 1, modpow(k, i / 2));
v = moddiv(v, 4);
u = (u + v) % MOD;
}
else {
u = moddiv(t, 2);
long long v = modpow(k, (i + 1) / 2);
v = moddiv(v, 2);
u = (u + v) % MOD;
}
ans = (ans + u) % MOD;
}
printf("%lld", ans);
}
int main() {
//freopen("input.txt", "r", stdin);
proc();
return 0;
}
