记录编号	220269	评测结果	AAAAAAAAAA
题目名称	[NOI 2015]寿司晚宴	最终得分	100
用户昵称	stdafx.h	是否通过	通过
代码语言	C++	运行时间	2.040 s
提交时间	2016-01-17 19:35:28	内存使用	2.73 MiB

#define MAXS 2UL
#define MAXN 260UL

#include <stdio.h>
#include <string.h>
#include <algorithm>

struct Pair{int x,y;}p[MAXN<<1];
int n,Ans,mod,f[MAXN][MAXN],g[MAXS][MAXN][MAXN],pri[8]={2,3,5,7,11,13,17,19};

inline bool comp(Pair a,Pair b){
	return a.y==b.y?a.x<b.x:a.y<b.y;
}

int main(){
	freopen("dinner.in","r",stdin);
	freopen("dinner.out","w",stdout);
	scanf("%d%d",&n,&mod);
	for(int i=2,j,t;i<=n;i++){
		for(j=0,t=i;j<8;j++){
			if(t%pri[j]) continue;
			p[i].x|=1<<j;
			while(!(t%pri[j])) t/=pri[j];
		}
		p[i].y=t;
	}
	std::sort(p+2,p+n+1,comp);
	f[0][0]=1;
	for(int i=2;i<=n;i++){
		if(p[i].y==1||p[i].y!=p[i-1].y) memcpy(g[0],f,sizeof(f)),memcpy(g[1],f,sizeof(f));
		for(int j=255;j>=0;j--) for(int k=255;k>=0;k--){
			if(!(j&p[i].x)) (g[0][j][k|p[i].x]+=g[0][j][k])%=mod;
			if(!(k&p[i].x)) (g[1][j|p[i].x][k]+=g[1][j][k])%=mod;
		}
		if(i==n||p[i].y==1||p[i].y!=p[i+1].y){
			for(int j=0;j<256;j++) for(int k=0;k<256;k++){
				f[j][k]=((g[0][j][k]+g[1][j][k]-f[j][k])%mod+mod)%mod;
			}
		}
	}
	for(int i=0;i<256;i++) for(int j=0;j<256;j++) if(!(i&j)) Ans+=f[i][j],Ans%=mod;
	printf("%d\n",Ans);
	return 0;
}