#include<bits/stdc++.h>
using namespace std;
#define int long long
const int M = 2000000;
int n,mod;
int qp(int p,int q){
	int ans = 1,pro = p;
	while(q){
		if(q&1)ans = ans*pro%mod;
		pro = pro*pro%mod;q>>=1;
	}return ans;
}
int cnt[5][5][5];
unordered_map<int,int>mp;
bool ok[2000005];int phi[2000005],v[2000005];
vector<int>p;
void shy(){
	phi[1] = 1;
	for(int i = 2;i<=M;i++){
		if(!ok[i]){
			p.push_back(i);
			phi[i] = i-1;
		}for(int j =0;j<p.size();j++){
			if(i*p[j]>M)break;
			ok[i*p[j]] = 1;
			if(i%p[j] == 0){
				phi[i*p[j]] = phi[i]*p[j];break;
			}phi[i*p[j]] = phi[i]*phi[p[j]];
		}
	}for(int i = 1;i<=M;i++)mp[i] = (mp[i-1]+phi[i])%mod;
}int calc(int x){
	if(x<=M)return phi[x];
	int pro = 1;
	for(int i = 2;i*i<=x;i++){
		if(x%i == 0){
			x/=i;pro*=(i-1);
			while(x%i == 0)x/=i,pro*=i;
		}
	}if(x>1)pro = pro*(x-1);return pro%mod;
}inline int D(int x){
	if(x == 0)return 0;
	if(mp[x])return mp[x];
	if(mp[x+1]){return mp[x] = (mp[x+1]-calc(x+1)+mod)%mod;}
	if(mp[x-1]){return mp[x] = (mp[x-1]+calc(x)+mod)%mod;}
	//cout << 111 << endl; 
//	cout<< x << endl;
	int res =(x*(x+1)/2)%mod;
	for(int l = 2,r;l<=x;l = r+1){
		r = x/(x/l);
		res = (res-D(x/l)*(r-l+1)%mod+mod)%mod;
	}return mp[x] = res;
}
signed main(){
	cin >> n >> mod;
	shy();;int sum = 0;
	D(n);
	for(int l = 1,r;l<=n;l = r+1){
		r = n/(n/l);
		sum = (sum+(n/l)*(n/l)%mod*(n/l)%mod*(D(r)-D(l-1)+mod))%mod;
	}int summ = 0;
	for(int l = 1,r;l<=n;l = r+1){
		r = n/(n/l);
		summ = (summ+(n/l)*(n/l)%mod*(D(r)-D(l-1)+mod))%mod;
	}int summm = (n*(n+1)/2)%mod;
	summ = (summ-summm+mod)*qp(2,mod-2)%mod;summ = (summ+mod)%mod;
	sum = (sum-6*summ+6*mod)%mod;sum = (sum-n*(n+1)/2);sum%=mod;sum+=mod;sum%=mod;
	sum = sum%mod;sum+=mod;sum%=mod;summ = summ%mod,summ+=mod,summ%=mod,summm = summm%mod,summm+=mod;summm%=mod;
	int ans =0;
	ans+=sum*qp(3,mod-2);ans%=mod;
	ans+=summ*3;ans%=mod;
	ans+=n*(n+1)/2;ans%=mod;
	cout << ans << endl; 
}
/*
euler's 反演。
\sum gcd(i,j,k) = \sum_d \lflorr n/d \rflorr \phi(d)
原式相当于上面这个玩意除以 3 再减去 i = j 的方案数
我们考虑独角筛
具体的，考虑到
1 * phi = I
S(I)_n = \sum_i \sum_d|i phi(d)*1(i/d)
     = \sum_d 1(d)*S_phi(n/d)
S(I)_n	 = \sum_{d = 1} 1(d)*S_phi(n/d) + S_phi(n)*1(1)  
S_phi(n) = S(I)_n - \sum_{d = 2} 1(d)*S_phi(n/d)
递归处理，根据一些原理预处理可以达到 O(n^{2/3}) 
wc你写独脚筛干嘛？
完了。
最纸张的一集。
太弱智了，原来还是要独脚的。 
希望取模没炸。 
*/