(Solution:)
卡在最后没解出来的感觉难受啊……大概只会 (50 o 70)
首先一眼看到的就是维护质因数了对吧，但是我们发现对于 (100) 以上的数，尤其是到了 (500) 质因数的数目就达到了 (100) 个了，完全就不是能状压的范畴了。
一开始的想法：首先可以砍掉大于 (frac{n}{2}) 的质数；因为这些质数只出现了一次。
其次，尽力去压缩质数的个数，最后发现无论如何也压不到能状压的地步。
观察到性质：对于一个大于 (sqrt{n}) 的数，它作为因子只会出现一次，而且影响的数的数目不超过根号级别。
于是就自然想到了只状压前几个质数。然而我就卡到这里不会了……
我们发现一个数最多有一个大质数因子对吧。我们考虑对它分类。（这一步也想到了的……害）
排序之后序列被我们划分成了若干段。对于最开始的那些因数小的段，设计 (dp[S][T]) 表示第一个人选择的因子集合是 (S) 第二个人是 (T) 的方案数，那么转移条件就是它们没有交集。
（写代码太激动了连这个都忘写了我丢）
于是可以直接大力 (dp) 出第一段。考虑计算后面的：
对于一个大质数，它显然有两种选择：部分被 (S) 选择或不选；部分被 (T) 选择或不选。于是我们可考虑分别 (dp) 两个集合对应的方案数：
(f[S][T],g[S][T]) 分别对应集合 (A,B) 选择该质数的方案数。剩下的问题在于合并：
[dp[S][T]=f[S][T]+g[S][T]-dp[S][T]
]
这里的细节在于，上一次的 (dp) 定义是并没有选择这个大质数的，而这里在两个数组中我们都计算了一次两个集合不选择该质数的方案数，所以需要被减去。
观察到空间限制很小，于是滚动数组即可。注意枚举顺序是逆序。
总结：题目很妙，我在技巧与问题处理方面还是差了点东西……（至少不至于一点思路没有了对吧）
#include<bits/stdc++.h>
using namespace std;
#define int long long
int mod,pr[8]={2,3,5,7,11,13,17,19};
inline int Min(int x,int y){return x<y?x:y;}
inline int Max(int x,int y){return x>y?x:y;}
inline int Mod(int x){return (x>=mod)?(x-mod):(x<0?(x+mod):x);}
inline int Add(int x,int y){return Mod(Mod(x+y));}
inline int Mul(int x,int y){return 1ll*x*y%mod;}
inline int read(){
int s=0,w=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-')w=-1;
ch=getchar();
}
while(isdigit(ch)){
s=s*10-48+ch;
ch=getchar();
}
return s*w;
}
struct Node{
int v,S;
void Init(int x){
for(int i=0;i<8;++i){
while(x&&x%pr[i]==0){
v|=(1<<i);
x/=pr[i];
}
}
if(x)S=x;
}
bool operator<(const Node&B)const{
return S<B.S;
}
}a[501];
int f[1<<9][1<<9];
int g[1<<9][1<<9];
int dp[1<<9][1<<9];
vector<Node>vec[501];
int cnt=0,n;
void solve(){
n=read();mod=read();
for(int i=1;i<n;++i){
a[i].Init(i+1);
}
sort(a+1,a+n);
vec[++cnt].push_back(a[1]);
for(int i=2;i<n;++i){
if(a[i].S==a[i-1].S)vec[cnt].push_back(a[i]);
else vec[++cnt].push_back(a[i]);
}
dp[0][0]=1;
for(auto i:vec[1]){
for(int S=(1<<8)-1;~S;--S)
for(int T=(1<<8)-1;~T;--T){
if(S&T)continue;
dp[S|i.v][T]=Add(dp[S|i.v][T],dp[S][T]);
dp[S][T|i.v]=Add(dp[S][T|i.v],dp[S][T]);
}
}
for(int i=2;i<=cnt;++i){
memcpy(f,dp,sizeof dp);
memcpy(g,dp,sizeof dp);
for(auto j:vec[i]){
for(int S=(1<<8)-1;~S;--S)
for(int T=(1<<8)-1;~T;--T){
if(S&T)continue;
if(!(j.v&T))f[S|j.v][T]=Add(f[S][T],f[S|j.v][T]);
if(!(j.v&S))g[S][T|j.v]=Add(g[S][T],g[S][T|j.v]);
}
}
for(int S=0;S<(1<<8);++S)
for(int T=0;T<(1<<8);++T)
if(!(S&T))
dp[S][T]=f[S][T]+g[S][T]-dp[S][T],dp[S][T]>mod?dp[S][T]-=mod:dp[S][T];
}
int ans=0;
for(int i=0;i<(1<<8);++i)
for(int j=0;j<(1<<8);++j)
if(!(i&j)&&dp[i][j])ans=Add(ans,dp[i][j]);
cout<<ans<<endl;
}
signed main(){
// freopen("111.txt","r",stdin);
solve();
return 0;
}