首先，两两互质等价于两个集合的质数集无交集。

那么从质数的方面考虑，不难想到状态压缩 DP。

但是打个表发现 $500$ 以内的质数接近 $100$ 个，显然压缩不了。

考虑一个解决这种问题相当常用的方法：根号分治。

注意到 $22$ 以内的质数只有 $8$ 个，而 $22$ 以上的质数至多会被一个数包含一次，称这些质数为「大质数」。

因为它们至多被包含一次，我们可以直接分类讨论它们在哪个集合。

具体地，我们把前 $8$ 个质数压缩状态，把 $2\sim n$ 除去前 $8$ 个质数的结果升序排序。

依次枚举 $2\sim n$，开三个 DP 数组：

$f(j,k)$：表示当前第一个集合状态为 $j$，第二个集合状态为 $k$ 的方案数。

$F(j,k)$：表示当前第一个集合状态为 $j$，第二个集合状态为 $k$，且当前枚举到的「大质数」都在第一个集合的方案数。

$G(j,k)$：表示当前第一个集合状态为 $j$，第二个集合状态为 $k$，且当前枚举到的「大质数」都在第二个集合的方案数。

注：其实这里本该是 $f(i,j,k)$，不过可以直接滚动数组滚掉第一维的阶段，所以我没有写在式子里。

转移相当简单：$F(j|s,k)=\sum F(j,k),G(j,k|s)=\sum G(j,k)$

而 $f$ 数组较为特殊：$f(j,k)=F(j,k)+G(j,k)-f(j,k)$

原因不难理解：$F(j,k),G(j,k)$ 都经过了一轮转移，但 $f(j,k)$ 还保留着上一轮的结果。

直接 $F(j,k)+G(j,k)$ 会将 $f(j,k)$ 计算两遍，所以要再减回来。

还有一些小细节：比如 $f(j,k)$ 复制到 $F(j,k),G(j,k)$，以及 $f(j,k)$ 的计算条件可以参考代码。

时间复杂度 $\mathcal{O}(n\times 2^{16})$

// Problem: #129. 【NOI2015】寿司晚宴
// Contest: UOJ
// URL: https://uoj.ac/problem/129
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
typedef long long ll;
typedef std::pair<int,int> pii;

const int maxn = 505;
int n,prime[10] = {2 , 3 , 5 , 7 , 11 , 13 , 17 , 19};
pii a[maxn];
ll p,f[maxn][maxn],F[maxn][maxn],G[maxn][maxn];

int main() {
	scanf("%d %lld",&n,&p);
	
	for(int i = 2;i <= n;++ i) {
		auto& [s , res] = a[i];
		res = i;
		for(int k = 0;k < 8;++ k) {
			if(res % prime[k])continue ;
			s |= 1 << k;
			for(;!(res % prime[k]);res /= prime[k]);
		}
	}
	
	std::sort(a + 2 , a + n + 1 , [&](const pii& p,const pii& q) {
		return p.second < q.second;
	});
	
	f[0][0] = 1;
	for(int i = 2;i <= n;++ i) {
		auto& [s , res] = a[i];
		if(res == 1||res != a[i - 1].second) {
			memcpy(F , f , sizeof(f));
			memcpy(G , f , sizeof(f));
		}
		for(int j = 255;~ j;-- j) {
			for(int k = 255;~ k;-- k) {
				if(j & k)continue ;
				if(!(s & k))(F[j | s][k] += F[j][k]) %= p;
				if(!(s & j))(G[j][k | s] += G[j][k]) %= p;
			}
		}
		if(i == n||res == 1||res != a[i + 1].second) {
			for(int j = 0;j < 256;++ j) {
				for(int k = 0;k < 256;++ k) {
					if(j & k)continue ;
					f[j][k] = (F[j][k] + G[j][k] - f[j][k] + p) % p;
				}
			}
		}
	}
	
	ll ans = 0;
	for(int j = 0;j < 256;++ j) {
		for(int k = 0;k < 256;++ k) {
			if(j & k)continue ;
			(ans += f[j][k]) %= p;
		}
	}
	
	printf("%lld",ans);
	return 0;
}