```cpp
#include<bits/stdc++.h>
#define A 8
#define Z 255
using namespace std;
int d[505],tot=0;
long long f[2][1<<A][1<<A];
int main(){
for(int i=2;i<=500;++i){
int flag=1;
for(int j=2;j*j<=i;++j){
if(i%j==0){
flag=0;
break;
}
}
if(flag)d[++tot]=i;
}
int n,mod,gs=0;
cin>>n>>mod;
f[gs][0][0]=1;
for(int i=2;i<=n;++i){
int fp=0,sg=0;
for(int j=1;j<=tot;++j)if(i%d[j]==0){
if(j<=A)fp|=1<<(j-1);
else{
sg=1;
break;
}
}
if(sg)continue;
for(int j=0;j<(1<<A);++j){
int S=Z&(~j);
for(int k=S;;k=(k-1)&S){
int fs=f[gs][j][k];
f[gs^1][j][k]+=fs;
if(!(k&fp))f[gs^1][j|fp][k]+=fs;
if(!(j&fp))f[gs^1][j][k|fp]+=fs;
if(!k)break;
}
}
gs^=1;
for(int j=0;j<(1<<A);++j){
int S=Z&(~j);
for(int k=S;;k=(k-1)&S){
f[gs][j][k]%=mod;
f[gs^1][j][k]=0;
if(!k)break;
}
}
}
for(int i=A+1;i<=tot&&d[i]<=n;++i){
int ss=n/d[i];
for(int l=1;l<=ss;++l){
int fp=0;
for(int j=1;j<=A;++j)
if(l%d[j]==0)fp|=1<<(j-1);
for(int j=0;j<(1<<A);++j){
int S=Z&(~j);
for(int k=S;;k=(k-1)&S){
int fs=f[gs][j][k];
if(!(k&fp))f[gs^1][j|fp][k]+=fs;
if(!(j&fp))f[gs^1][j][k|fp]+=fs;
if(!k)break;
}
}
}
gs^=1;
for(int j=0;j<(1<<A);++j){
int S=Z&(~j);
for(int k=S;;k=(k-1)&S){
f[gs][j][k]+=f[gs^1][j][k];
f[gs][j][k]%=mod;
f[gs^1][j][k]=0;
if(!k)break;
}
}
}
long long ans=0;
for(int i=0;i<(1<<A);++i){
int S=Z&(~i);
for(int j=S;;j=(j-1)&S){
ans+=f[gs][i][j];
if(!j)break;
}
}
ans%=mod;
cout<<ans<<endl;
return 0;
}
by lqyc @ 2022-01-24 18:58:07