#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; ++i)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
const int Mod = 998244353;
const int inf = 0x3f3f3f3f;
const int inv2 = (Mod+1) / 2;
inline void uadd(int &a, int b){ a += b-Mod; a += (a>>31) & Mod; }
inline void usub(int &a, int b){ a -= b, a += (a>>31) & Mod; }
inline void umul(int &a, int b){ a = (int)(1ll * a * b % Mod); }
inline int add(int a, int b){ a += b-Mod; a += (a>>31) & Mod; return a; }
inline int sub(int a, int b){ a -= b, a += (a>>31) & Mod; return a; }
inline int mul(int a, int b){ return (int)(1ll * a * b % Mod); }
inline int qpow(int b, ll p){ int ret = 1; while(p){ if(p & 1) umul(ret, b); umul(b, b), p >>= 1; } return ret; }

ll N;
const int M = 6e6;
int m;

int g[M+100], h[M+100], Sg[M+100], Sh[M+100], mpw[M+100], inv1_m;
int get_h(int n){
	if(n % 2 == 1) return mul(n, mpw[(n+1) / 2]);
	else return mul(n/2, add(mpw[n/2], mpw[n/2+1]));
}
int p[M/6 + 100], cp = 0, isp[M+100], mu[M+100];
void sieve(int n){
	mpw[0] = 1; rep(i, n) mpw[i+1] = mul(mpw[i], m);
	rep(i, n+1) isp[i] = (i >= 2);
	mu[1] = 1;
	for(int i = 2; i <= n; ++i){
		if(isp[i]) p[cp++] = i, mu[i] = Mod-1;
		for(int j = 0; j < cp && i * p[j] <= n; ++j){
			mu[i * p[j]] = mul(mu[i], mu[p[j]]);
			isp[i * p[j]] = 0;
			if(i % p[j] == 0){
				mu[i * p[j]] = 0;
				break;
			}
		}
	}
	rep(i, n+1) umul(mu[i], i);
	rep(i, n+1) h[i] = get_h(i);
	for(int i = 1; i <= n; ++i){
		for(int j = 1; i*j <= n; ++j)
			uadd(g[i*j], mul(h[i], mu[j]));
	}
	for(int i = 1; i <= n; ++i)
		Sg[i] = add(g[i], Sg[i-1]), Sh[i] = add(h[i], Sh[i-1]);
}

int bSg[2020], bSh[2020];
inline int S1(ll n){
	return mul(sub(1, qpow(m, n+1)), inv1_m);
}
inline int S2(ll n){
	return mul(sub(S1(n), mul((int)((n+1) % Mod), qpow(m, n+1))), inv1_m);
}
int get_bSh(ll d){
	if(bSh[d]) return bSh[d];
	ll n = N / d;
	bSh[d] = add(mul(m, sub(mul(2, S2((n-1)/2)), S1((n-1)/2))), mul(m+1, sub(S2(n/2), S1(n/2))));
	//cout << d << " " << n << ": " << bSh[d] << "\n";
	return bSh[d];
}
int get_Sid(ll l, ll r){
	return (int)((l + r) % Mod * (r - l + 1) % Mod * inv2 % Mod);
}
int get_bSg(ll d){
	ll n = N / d;
	//cout << d << ": " << n << " " << Sg[n] << "\n";
	if(n <= M) return Sg[n];
	if(bSg[d]) return bSg[d];
	int ret = get_bSh(d);
	for(ll l = 2; l <= n; ){
		ll x = n / l, r = n / x;
		usub(ret, mul(get_bSg(d * l), get_Sid(l, r)));
		l = r + 1;
	}
	return bSg[d] = ret;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> N >> m;

	if(m == 1){
		cout << N % Mod << "\n";
		return 0;
	}

	inv1_m = qpow(sub(1, m), Mod-2);
	sieve(M);

	//ll tmp;
	//while(cin >> tmp) cout << S1(tmp) << " " << S2(tmp) << endl;

	int ans = 0;
	for(ll l = 1; l <= N; ){
		ll x = N/l, r = N/x;
		uadd(ans, mul(sub(get_bSg(x), (l == 1 ? 0 : get_bSg(N/(l-1)))), (int)(x % Mod)));
		//cout << " * " << x << "\n";
		l = r+1;
	}

	cout << ans << "\n";

	return 0;
}