U507153 互质覆盖

蒟蒻 xym 在同一个套路上栽坑两次了……

同 [P7800 \[COCI2015-2016#6\] PAROVI](https://www.luogu.com.cn/problem/P7800)，但模数、数据范围略有不同。 $1 \sim n$ 数轴，你可以使用若干条线段 $[l, r]$ 来覆盖，其中要满足 $\gcd(l, r) = 1$。问你能够完全覆盖数轴的方案数，对 $M$ 取模。

一行两个整数 $n, M$。

一行一个整数，表示对 $M$ 取模后的方案数。

对于 $10\%$ 的数据，同 [P7800 \[COCI2015-2016#6\] PAROVI](https://www.luogu.com.cn/problem/P7800)，$n \leq 20$，$M = 10^9$。 对于 $100\%$ 的数据，$2 \leq n \leq 10^4$，$2 \leq M \leq 10^9+7$。**不保证 $M$ 为质数**。数据有一定梯度。 时空已经开到 std 两倍以上。请确保你算法的时间复杂度不超过 $\mathcal{O}(n^2)$，如果你有更优的解法、水过了这道题，欢迎来嘲讽我。 [标程、Gen、题解](https://www.cnblogs.com/XuYueming/p/18559166)。