#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 500+5;
const int B = 8;
int n,ha;

inline void add(int &x,int y){
	x += y;if(x >= ha) x -= ha;
}

bool p[MAXN];
int prime[MAXN],cnt;

inline void prework(){
	FOR(i,2,MAXN-1){
		if(!p[i]) prime[++cnt] = i;
		for(int j = 1;j <= cnt && i*prime[j] < MAXN;++j){
			p[i*prime[j]] = 1;
			if(!(i%prime[j])) break;
		}
	}
}

int g[MAXN][(1<<B)+3],f[2][(1<<B)+3][(1<<B)+3];
int h[2][(1<<B)+3];
bool del[MAXN];
int zt[MAXN];

int main(){
	prework();
	scanf("%d%d",&n,&ha);
	FOR(i,1,B){
		for(int j = prime[i];j <= n;j += prime[i]) zt[j] |= (1<<(i-1));
	}
	FOR(i,B+1,cnt){
		if(prime[i] > n) break;
		// printf("%d\n",prime[i]);
		std::vector<int> S;
		for(int j = prime[i];j <= n;j += prime[i]) S.pb(j),del[j] = 1;
		// for(auto x:S) printf("%d ",x);puts("");
		int now = 0;CLR(h[now],0);
		h[now][0] = 1;
		for(auto x:S){
			CLR(h[now^1],0);
			FOR(S,0,(1<<B)-1){
				if(!h[now][S]) continue;
				add(h[now^1][S],h[now][S]);
				add(h[now^1][S|zt[x]],h[now][S]);
			}
			now ^= 1;
		}
		// DEBUG(h[now][1]);
		// exit(0);
		FOR(S,0,(1<<B)-1) g[i][S] = h[now][S];
	}
	int now = 0;f[now][0][0] = 1;
	FOR(i,2,n){
		if(del[i]) continue;
		CLR(f[now^1],0);
		FOR(S1,0,(1<<B)-1){
			FOR(S2,0,(1<<B)-1){
				if(S1&S2) continue;
				if(!(S2&zt[i])) add(f[now^1][S1|zt[i]][S2],f[now][S1][S2]);
				if(!(S1&zt[i])) add(f[now^1][S1][S2|zt[i]],f[now][S1][S2]);
				add(f[now^1][S1][S2],f[now][S1][S2]);
			}
		}
		now ^= 1;
	}
	FOR(i,B+1,cnt){
		if(prime[i] > n) break;
		CLR(f[now^1],0);
		FOR(S1,0,(1<<B)-1){
			FOR(S2,0,(1<<B)-1){
				if(S1&S2) continue;
				if(!f[now][S1][S2]) continue;
				int S = ((1<<B)-1)^S1;
				for(int T = S;;T=(T-1)&S){
					// assert((T&S1)==0);
					add(f[now^1][S1][S2|T],1ll*f[now][S1][S2]*g[i][T]%ha);
					if(!T) break;
				}
				S = ((1<<B)-1)^S2;
				for(int T = S;;T=(T-1)&S){
					// assert((T&S2)==0);
					add(f[now^1][S1|T][S2],1ll*f[now][S1][S2]*g[i][T]%ha);
					if(!T) break;
				}
				add(f[now^1][S1][S2],ha-f[now][S1][S2]);
			}
		}
		now ^= 1;
	}
	int ans = 0;
	FOR(S1,0,(1<<B)-1) FOR(S2,0,(1<<B)-1) if(!(S1&S2)) add(ans,f[now][S1][S2]);
	printf("%d\n",ans);
	return 0;
}