题意：
- 你有一个集合 \(S={2,3,\dots,n}\)
- 你要选择两个集合 \(A\) 和 \(B\)，满足：
- \(A \subseteq S\)，\(B \subseteq S\)，且 \(A \cap B=\varnothing\)
- 不存在两个数 \(x \in A\)，\(y \in B\)，且 \(\operatorname{gcd}(x,y)>1\)。
- 求满足条件的集合 \(A,B\) 的数量。
\(n \in [2,500]\)
通过分析题面可以发现，如果两个集合 \(A,B\) 满足条件，那么它们的质因子组成的集合一定不会重复。
先考虑 \(30\) 分的做法。\(30\) 以内的质数只有 \(10\) 个（\(2,3,5,7,11,13,17,19,23,29\)）。
我们分别给这 \(10\) 个质数标号 \(1\) 到 \(10\)。这样我们可以使用一个 \(10\) 位二进制数表示质因子的选择情况。
例如 \((1011001100)_2\) 就表示集合中包含质因子 \(2,5,7,17,19\)。
再将 \(2\) 到 \(n\) 每个数分解质因数。记 \(fac_i\) 为 \(i\) 质因子的集合。
到这里，不少题解都使用了三维状压 \(dp\)。这里我要介绍一个不太一样的方法。
我们开一个数组 \(cnt_{i,j}\)，其中 \(i \in [2,n],j \in [0,2^{10}-1]\)。
表示满足 \(2 \leq x \leq i\)，\(fac_i \subseteq j\) 的 \(x\) 的个数
再设 \(dp_s\) 表示质因子集合为 \(s\) 的集合数量。
显然所有 \(fac_i \subseteq s\) 的 \(i\) 都可以被选，那么总共有 \(cnt_{n,i}\) 个数，每个数都有选与不选两种可能，故 \(dp_s=2^{cnt_{n,i}}\)
最后是统计答案，枚举质因子集合 \(s,t\)（根据条件 2，\(s\&t=0\)），两个集合的选择方法是独立的，因此，根据乘法原理，这一部分对答案的贡献为 \(dp_s \times dp_t\)。
但是这样做还不行。假设有一个集合 \(T={2,4}\)，那么 \(T\) 在 \(dp_1\) 中被计算了一次，在 \(dp_3\) 中又被计算了一次，会被重复计算。
这时不难想到容斥原理。你对 \(dp\) 数组进行一遍容斥原理就可以了。
再考虑正解。\(n\) 从 \(30\) 扩大到了 \(500\)，就不能像 \(30\) 分做法那样将一个质因子集合用二进制表示出来了。
但是注意到 \(\sqrt{500}\) 只有 \(22\)，而 \(22\) 以内的质数只有 \(8\) 个。
那么我们可以用根号分治的思想将质数分成两类，一类是 \(\leq 22\) 的质数（我们称其为“小质数”），另一类是 \(\gt 22\) 的质数（我们称其为“大质数”）。
不难发现，\(1\) 到 \(500\) 中的数最多只有一个大质数因子。任意两个大质数乘起来都会 \(\gt 500\)。
换句话说，大质数的选择方案是独立的（是否选择 \(31\) 这个质因子不会影响 \(37\) 的选择方案）
我们枚举小质数因子的集合 \(s,t\)，然后考虑每个大质数 \(p\) 的选择方法：
- \(p\) 在 \(A\) 中，那么选择的方案数为 \(2^{cnt_{\frac{n}{p},s}+1}\)（你可以看成从 \([1,\frac{n}{p}]\) 选择若干个质因子集合为 \(s\) 的集合然后将每个数乘以 \(p\)）
- \(p\) 在 \(B\) 中，那么选择的方案数为 \(2^{cnt_{\frac{n}{p},t}+1}\)
- \(p\) 既不在 \(A\) 也不在 \(B\) 中，方案数为 \(1\)。
将三者加起来就是选择 \(p\) 的方案数。
将选择每个大质数的方案数乘起来就是选择大质数的方案数。
选择小质数的方案数和 \(30\) 分做法一样用乘法原理将两部分乘起来。
用容斥原理算一下就可以了。
/*
Contest: -
Problem: P2150
Author: tzc_wk
Time: 2020.7.31
*/
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define fz(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define foreach(it,v) for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define all(a) a.begin(),a.end()
#define fill0(a) memset(a,0,sizeof(a))
#define fill1(a) memset(a,-1,sizeof(a))
#define fillbig(a) memset(a,0x3f,sizeof(a))
#define fillsmall(a) memset(a,0xcf,sizeof(a))
#define y1 y1010101010101
#define y0 y0101010101010
#define int long long
typedef pair<int,int> pii;
inline int read(){
int x=0,neg=1;char c=getchar();
while(!isdigit(c)){
if(c=='-') neg=-1;
c=getchar();
}
while(isdigit(c)) x=x*10+c-'0',c=getchar();
return x*neg;
}
int n=read(),m=read();
inline int qpow(int x,int e){
int ans=1;
while(e){
if(e&1) ans=ans*x%m;
x=x*x%m;
e>>=1;
}
return ans;
}
int pr[505],num[505],pcnt=0;
bool vis[505];
inline void sieve(){
for(int i=2;i<=500;i++){
if(!vis[i]){
pr[++pcnt]=i;num[i]=pcnt;
for(int j=i+i;j<=500;j+=i) vis[j]=1;
}
}
}
int sumfac[505][1<<8];
int g[505][1<<8],gg[505][1<<8];
inline int calc_fac(int x){
int tmp=x,flg=0;
for(int i=2;i*i<=x;i++){
if(tmp%i==0){
flg|=(1<<(num[i]-1));
while(tmp%i==0) tmp/=i;
}
}
if(tmp>1){
if(num[tmp]>8) return 256;
else flg|=(1<<(num[tmp]-1));
}
return flg;
}
signed main(){
sieve();
fz(i,2,n){
int f=calc_fac(i);
for(int j=0;j<(1<<8);j++){
if((j&f)!=f) sumfac[i][j]=sumfac[i-1][j];
else sumfac[i][j]=sumfac[i-1][j]+1;
// cout<<i<<" "<<j<<" "<<sumfac[i][j]<<endl;
}
}
for(int i=0;i<(1<<8);i++) for(int j=0;j<(1<<8);j++){
if((i&j)==0){
// if(dp[i][n]==0||dp[j][n]==0) continue;
// cout<<i<<" "<<j<<" "<<dp[i][n]<<" "<<dp[j][n]<<endl;
int ans=1;
ans=ans*qpow(2,sumfac[n][i])%m;
ans=ans*qpow(2,sumfac[n][j])%m;
for(int k=23;k<=n;k++){
if(num[k]){
// if(k==23) cout<<i<<" "<<j<<" "<<qpow(2,sumfac[n/k][i]+1)+qpow(2,sumfac[n/k][j]+1)-1<<endl;
ans=ans*(qpow(2,sumfac[n/k][i]+1)+qpow(2,sumfac[n/k][j]+1)-1+m)%m;
}
}
g[i][j]=ans;
// cout<<i<<" "<<j<<" "<<g[i][j]<<endl;
}
}
for(int i=0;i<(1<<8);i++) for(int j=0;j<(1<<8);j++){
if((i&j)==0){
for(int k=0;k<(1<<8);k++){
if((j&k)!=k) continue;
gg[i][j]=(gg[i][j]+(int)pow(-1,__builtin_popcount(j^k))*g[i][k]+m)%m;
}
// cout<<i<<" "<<j<<" "<<gg[i][j]<<endl;
}
}
int sum=0;
for(int i=0;i<(1<<8);i++) for(int j=0;j<(1<<8);j++){
if((i&j)==0){
int x=0;
for(int k=0;k<(1<<8);k++){
if((i&k)!=k) continue;
x=(x+(int)pow(-1,__builtin_popcount(i^k))*gg[k][j]+m)%m;
}
sum=(sum+x)%m;
// cout<<i<<" "<<j<<" "<<x<<endl;
}
}
cout<<sum<<endl;
return 0;
}