qwq，状态压缩，就是用了滚动数组而不是倒序枚举。然后样例 3 过不了，麻了。

#include<bits/stdc++.h>
using namespace std;
struct node{
	long long s,bigp,num;
}a[510];
long long n,p,tmp,now,las,ans;
long long pri[20]={2,3,5,7,11,13,17,19};
bool cmp(node n1,node n2){
	return n1.bigp<n2.bigp;
}
long long f[310][310],f1[2][310][310],f2[2][310][310];
void work(long long x){
	tmp=x;
	a[x].num=x;
	for(int i=0;i<8;i++)
		if(tmp%pri[i]==0){
			a[x].s+=(1<<i);
			while(tmp%pri[i]==0)tmp/=pri[i];
		}
	if(tmp==1)a[x].bigp=0;
	else a[x].bigp=tmp;
}
int main(){
	cin>>n>>p;
	for(int i=2;i<=n;i++)work(i);
	sort(a+2,a+1+n,cmp);
	f[0][0]=1;
	for(int i=2;i<=n;i++){
		//cout<<a[i].num<<" "<<a[i].s<<" "<<a[i].bigp<<endl;
		if(a[i].bigp==0||a[i].bigp!=a[i-1].bigp){
			for(int j=0;j<=255;j++)
				for(int k=0;k<=255;k++)
					f1[0][j][k]=f1[1][j][k]=f2[0][j][k]=f2[1][j][k]=f[j][k];
		}
		now=i%2;las=1-now;
		for(int j=0;j<=255;j++)
			for(int k=0;k<=255;k++){
				f1[now][j][k]=f1[las][j][k];
				f2[now][j][k]=f2[las][j][k];
			}	
		for(int j=0;j<=255;j++)
			for(int k=0;k<=255;k++){
				if((j&k)!=0)continue;
				if((a[i].s&k)==0)f1[now][j|a[i].s][k]=(f1[now][j|a[i].s][k]+f1[las][j][k])%p;
				if((j&a[i].s)==0)f2[now][j][k|a[i].s]=(f2[now][j][k|a[i].s]+f2[las][j][k])%p;
			}
		if(a[i].bigp==0||a[i].bigp!=a[i-1].bigp||i==n){
			for(int j=0;j<=255;j++)
				for(int k=0;k<=255;k++){
					if((j&k)!=0)continue;
					f[j][k]=((f1[now][j][k]+f2[now][j][k]-f[j][k])%p+p)%p;
				}
					
		}
	}
	for(int j=0;j<=255;j++)
		for(int k=0;k<=255;k++){
			if((j&k)!=0)continue;
			ans=(ans+f[j][k])%p;
		}
			
	cout<<ans<<endl;
	return 0;
}