$rt$，调疯了，就过两个小样例，思路就是按照质因数排一个序，相同的给它归到一起做背包。

#include <vector>
#include <iostream>
#include <algorithm>
#define int long long
#define For(i, a, b) for (int i = (a); i <= (b); i ++)
using namespace std;
int n, p, ans, cnt;
int ps[8] = {2, 3, 5, 7, 11, 13, 17, 19};
int f[505][1 << 8][1 << 8], t[505][1 << 8][1 << 8];
struct Node {int x, mi, status;} a[505];
bool cmp (Node n1, Node n2) {return n1.mi < n2.mi;}
signed main () {
	cnt = 500;
	cin >> n >> p;
	f[0][0][0] = 1;
	for (int i = 2; i <= n; i ++) {
		int x = i;
		a[i - 1].x = i;
		for (int j = 0; j < 8; j ++) while (x % ps[j] == 0) {
			x /= ps[j];
			a[i - 1].status |= 1 << j;
		}
		if (x > 19) a[i - 1].mi = x;
		else a[i - 1].mi = ++ cnt;
	}
	sort (a + 1, a + n, cmp);
	for (int l = 1, r = 1; l < n; l = r + 1) {
		r = l;
		while (a[r + 1].mi == a[l].mi) ++ r;
		For (j, 0, 255) {
			For (k, 0, 255) t[l - 1][j][k] = f[l - 1][j][k];
		}
		For (j, l, r) {
			For (k, 0, 255) {
				For (l, 0, 255) t[j][k][l] = t[j - 1][k][l];
			}
			For (k, 0, 255) {
				int s = (~ (k | a[j].status) ) & 255;
				for (int l = s; l; l = (l - 1) & s) t[j][k | a[j].status][l] = (t[j][k | a[j].status][l] + t[j - 1][k][l]) % p;
				t[j][k | a[j].status][0] = (t[j][k | a[j].status][0] + t[j - 1][k][0]) % p;
			}
		}
		For (k, 0, (1 << 8) - 1) {
			For (l, 0, (1 << 8) - 1) f[r][k][l] = (f[r][k][l] + t[r][k][l]) % p;
		}
		For (j, 0, 255) {
			For (k, 0, 255) t[l - 1][k][j] = f[l - 1][k][j];
		}
		For (j, l, r) {
			For (k, 0, 255) {
				For (l, 0, 255) t[j][l][k] = t[j - 1][l][k];
			}
			For (k, 0, 255) {
				int s = (~ (k | a[j].status) ) & 255;
				//1 0
				for (int l = s; l; l = (l - 1) & s) t[j][l][k | a[j].status] = (t[j][l][k | a[j].status] + t[j - 1][l][k]) % p;
				if (k | a[j].status) t[j][0][k | a[j].status] = (t[j][0][k | a[j].status] + t[j - 1][0][k]) % p;
			}
		}
		int x = l;
		For (k, 0, (1 << 8) - 1) {
			if (k == 0) For (l, 1, (1 << 8) - 1) f[r][l][k] = (f[r][l][k] + t[r][l][k] - t[r - 1][l][k]) % p;
			else For (l, 0, (1 << 8) - 1) f[r][l][k] = (f[r][l][k] + t[r][l][k] - t[x - 1][l][k]) % p;
		}
	}
	For (j, 0, 3) {
		For (k, 0, 3) {
			ans += f[n - 1][j][k];
			ans %= p;
		}
	}
	cout << ans;
	return 0;
}