#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
using namespace std;
typedef long long ll;
typedef pair<int, int> Pi;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) (int)x.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
const ll MOD = 1e9 + 7;
ll pw(ll x, ll y){
ll res = 1;
while(y){
if(y & 1)res = res * x % MOD;
x = x * x % MOD;
y >>= 1;
}
return res;
}
ll pwk[1000010];
int phi[1000010];
int isp[1000010];
ll sum[1000010];
int main(){
int N, K;
scanf("%d%d", &N, &K);
//N = K = 1000000;
pwk[0] = 1;
for(int i=1;i<1000010;i++)pwk[i] = K * pwk[i-1] % MOD;
phi[1] = 1;
for(int i=2;i<1000010;i++)phi[i] = i, isp[i] = 1;
for(int i=2;i<1000010;i++){
if(isp[i]){
phi[i] = i-1;
for(int j=i+i;j<1000010;j+=i){
isp[j] = 0;
phi[j] /= i;
phi[j] *= (i-1);
}
}
}
ll ans = 1;
ll p2 = pw(2, MOD-2);
ll p4 = pw(4, MOD-2);
for(int i=1;i<=N;i++){
for(int j=i,t=1;j<=N;j+=i,t++){
sum[j] += phi[i] * pwk[t];
sum[j] %= MOD;
}
}
for(int i=1;i<=N;i++){
//printf("%d %lld\n", i, sum);
ans += sum[i] * pw(2*i, MOD-2);
if(i & 1)ans += p2 * pwk[(i+1)/2];
else ans += p4 * (K+1) % MOD * pwk[i/2];
ans %= MOD;
}
printf("%lld", ans);
//printf("\n%d", clock());
return 0;
}
