#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define eps 1e-8
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
ll n,P;
#define N 5000000
#define M 10000000000000LL
int vis[N+5],p[N+5],cnt=0;
ll pn[N+N];
int h[N+N];
vector<int>hp[N];
int tot=0,inv2;
int G(ll x){
	x%=P;
	// printf("G[%lld]=%lld\n",x,x*(x+1)%P*inv2%P);
	return x*(x+1)%P*inv2%P;
}
void dfs(int x,ll val,int hn){
	if(x>cnt || (ll)p[x]*p[x]>n/val)return;
	dfs(x+1,val,hn);
	if(n/val<(ll)p[x]*p[x])return;
	val=val*p[x]*p[x];
	int qwerty=2;
	while(val<=n){
		pn[++tot]=val;
		h[tot]=(ll)hn*hp[x][qwerty++]%P;
		// printf("h[%d]=%d\n",tot,h[tot]);
		dfs(x+1,val,h[tot]);
		if(n/val<p[x])break;
		val*=p[x];
	}
}
int main(){
	for(int i=2;i<=N;i++){
		if(!vis[i])p[++cnt]=i;
		for(int j=1;j<=cnt&&i*p[j]<=N;j++){
			vis[i*p[j]]=1;
			if(i%p[j]==0)break;
		}
	}
	cin>>n>>P;
	for(int i=1;i<=cnt;i++){
		hp[i].push_back(1);
		hp[i].push_back(0);
		ll prod=(ll)p[i]*p[i];
		int vf=(ll)p[i]*(p[i]-1)%P;
		while(prod<=n){
			int val=vf;
			ll pd=prod;
			for(auto vh:hp[i]){
				val=(val-vh*(pd%P)%P+P)%P;
				pd/=p[i];
			}
			// printf("hp[%d][%d]=%d\n",i,hp[i].size(),val);
			hp[i].push_back(val);
			if(n/p[i]<prod)break;
			prod*=p[i];
			vf=(ll)vf*(p[i]-1)%P;
		}
	}
	inv2=(P+1)/2;
	pn[++tot]=1;
	h[tot]=1;
	dfs(1,1,1);
	// printf("%d\n",tot);
	// for(int i=1;i<=tot;i++)printf("%lld ",pn[i]);
	// printf("\n");
	int ans=0;
	for(int i=1;i<=tot;i++)ans=(ans+(ll)h[i]*G(n/pn[i])%P)%P;
	printf("%d",ans);
	return 0;
}
// quod erat demonstrandum