```cpp
//Code by John Alfnov
//Please orz Qingyu
//Hydd txdy
#include<bits/stdc++.h>
#define eps 5
//#define dangerous_test
//#define only_one_test
using namespace std;
const signed UKE[]={5307,4307,128};
const signed ML=512;
signed memory_use=1;
const char inio[]=".in";
const char outio[]=".out";
namespace JohnAlfnov{
int mod,inv_6=0;
bool first_test_memory=false;
const signed N_lim=6000000;
int mu[N_lim+eps];
int d[N_lim/8+eps],s[N_lim+eps];
void print(){
int tot=0;
mu[1]=s[1]=1;
for(int i=2;i<=N_lim;++i){
if(!s[i]){
d[++tot]=i;
mu[i]=-1;
}
for(int j=1;j<=tot&&i*d[j]<=N_lim;++j){
s[i*d[j]]=1;
if(i%d[j]==0){
mu[i*d[j]]=0;
break;
}
mu[i*d[j]]=-mu[i];
}
}
for(int i=1;i<=N_lim;++i){
mu[i]=(mu[i-1]+1ll*i*i*mu[i])%mod;
}
}
namespace basic_math{
int basic_math_mod/*=*/;
int quick_power_mod(int x,int y){
int base_ans=1;
while(y){
if(y&1)base_ans=1ll*base_ans*x%basic_math_mod;
y>>=1;
x=1ll*x*x%basic_math_mod;
}
return base_ans;
}
int inverse_num(signed x){
return quick_power_mod(x,basic_math_mod-2);
}
};
namespace file_read{
namespace input_file_io{
char ib[1<<25],*ip1=ib,*ip2=ib;
inline char gc(){
return getchar();
return (ip1==ip2&&(ip2=(ip1=ib)+fread(ib,1,1<<24,stdin)),ip1==ip2?EOF:*ip1++);
}
inline auto read(){
long long x=0;
char c=gc();
while(c<'0'||c>'9')c=gc();
while(c>='0'&&c<='9'){
x=(x<<3)+(x<<1)+(c-'0');
c=gc();
}
return x;
}
};
namespace output_file_io{
char ob[1<<25],*op=ob;
inline void pc(char c){
*op++=c;
}
void write(int x){
if(x<0){
pc('-');
x=-x;
}
if(x==0)pc('0');
static int number_stack[40];
int total_count=0;
while(x)number_stack[++total_count]=x%10,x/=10;
while(total_count){
pc(number_stack[total_count]+'0');
--total_count;
}
}
inline void final_write(){
fwrite(ob,op-ob,1,stdout);
}
};
using namespace input_file_io;
using namespace output_file_io;
};
namespace test_safe{
signed safe_signed_return(){
return signed(0ll);
}
signed unsafe_signed_return(){
return signed(-1ll);
}
void ml_test_safe(){
if(memory_use>ML-50){
assert(~unsafe_signed_return());
}else{
assert(~safe_signed_return());
}
}
};
void file_io(){
freopen(inio,"r",stdin);
freopen(outio,"w",stdout);
}
void init(){
/**/
}
bool second_test_memory=true;
inline int sq_sum(long long x){
x%=mod;
return x*(x+1)/2%mod;
}
inline int sqr_sum(long long x){
int tt=sq_sum(x);
return 1ll*tt*tt%mod;
}
inline int sq2_sum(long long x){
x%=mod;
return x*(x+1)%mod*(2*x+1)%mod*inv_6%mod;
}
unordered_map<long long,int>mp1;
int getmu(long long n){
if(n<=N_lim)return mu[n];
if(mp1[n])return mp1[n];
long long ans=1;
for(long long l=2;l<=n;){
long long a=n/l,r=n/a;
int tt=sq2_sum(r)-sq2_sum(l-1);
ans-=1ll*getmu(a)*tt%mod;
l=r+1;
}
return mp1[n]=ans%mod;
}
void solve(){
mod=file_read::read();
basic_math::basic_math_mod=mod;
inv_6=basic_math::inverse_num(6);
print();
long long n=file_read::read();
int ans=0;
for(long long l1=1;l1<=n;){
long long a1=n/l1,r1=n/a1;
int sqs=sqr_sum(r1)-sqr_sum(l1-1);
int sna=0;
for(long long l2=1;l2<=a1;){
long long a2=a1/l2,r2=a1/a2;
int mus=getmu(r2)-getmu(l2-1);
sna=(sna+1ll*sqr_sum(a2)*mus)%mod;
l2=r2+1;
}
ans=(ans+1ll*sna*sqs)%mod;
l1=r1+1;
}
ans=(ans+mod)%mod;
file_read::write(ans);
memory_use=((&second_test_memory)-(&first_test_memory))/1024/1024;
#ifdef dangerous_test
memory_use=0;
#endif
test_safe::ml_test_safe();
}
};
signed main(){
// JohnAlfnov::file_io();
JohnAlfnov::init();
JohnAlfnov::solve();
JohnAlfnov::file_read::final_write();
return JohnAlfnov::test_safe::safe_signed_return();
}
```
by lqyc @ 2021-12-12 19:11:28