题解：数学无处不在

思路

1. 把每个质数看成一次“覆盖”

固定一个质数 (p=p_i)。模 (p) 意义下，(k) 只能选择一个余数。若 (k\equiv-r\pmod p)，那么区间位置 (r,r+p,r+2p,\ldots) 中的数 (k+i) 会被 (p) 整除。

因此，每个质数恰好选择一个模 (p) 的余数类，用它覆盖若干位置。要求是：

• 标为 1 的位置不能被任何质数覆盖；
• 标为 0 的位置至少被一个质数覆盖。

指数只贡献一个独立乘数。模 (p^\alpha) 中，固定模 (p) 的余数后仍有 (p^{\alpha-1}) 种提升，所以最终答案要乘 [ \prod_i p_i^{\alpha_i-1}. ]

下面只需处理各个不同质数的一次方。

2. 子任务 1：直接枚举 (k)

当 (N\le 200000) 时，枚举 (0\le k<N)，逐个检查所有位置的最大公约数即可。

复杂度为 (O(Nm\log N))。

3. 子任务 2：零位置状压

只给 0 位置编号。对于质数 (p) 的每个余数 (r)，若该余数类碰到任何 1 位置，就不能选择；否则它形成一个“新覆盖零位置”的掩码。

设 (f[M]) 表示已经覆盖的零位置集合。枚举当前质数所有不同掩码及其出现次数，转移到 (M\mathbin{\mathrm{or}}C)。

当 (p>m) 时，一个余数至多碰到一个位置，可以把 (p-m) 个“不碰任何位置”的余数合并。

复杂度上界为 (O(n2^z m))，其中 (z\le m\le18)。

4. 支线子任务：所有质数都大于 (m)

此时每个质数至多覆盖一个位置。只需记录还有多少位置尚未覆盖。

设 one 为 1 的数量，(f_j) 表示当前仍有 (j) 个位置没有被覆盖（其中所有 1 必然都未覆盖）。加入质数 (p) 时：

• 选择不碰任何尚未覆盖位置的余数，有 (p-j) 种；
• 覆盖一个尚未覆盖的零位置，有 (j-\text{one}) 种。

于是得到 (O(nm)) 的计数动态规划。

做法

长度只有 40，但直接维护 (2^{40}) 个状态不可行。按质数大小分段处理。

5.1 小质数的稀疏掩码

对 (p<29)，显式生成所有不碰 1 的余数类，用排序合并相同的“仍未覆盖位置”掩码。小质数很少，而且每次会成片消去位置，实际可达状态受到强约束。

5.2 29、31、37 的边界压缩

当 (29\le p<m\le40) 时，只有字符串两端长度 (m-p) 的位置会与另一个位置处于同一余数类；中间位置各自占一个余数类。

因此状态可以拆成：

• 两端共 (2(m-p)) 位的精确掩码；
• 中间仍未覆盖位置的数量。

处理下一个更大的质数时，原边界的一部分移入中段，只需统计被移入位的个数。这样最大表规模约为 (19\cdot2^{22})，可以稳定覆盖最坏的 40 位输入。

5.3 不小于 (m) 的质数

后续质数全部至多覆盖一个位置，状态只需保留未覆盖位置数，使用第 4 节的 (O(nm)) 转移。

最后取只剩全部 1 位置未覆盖的状态，并乘质数幂提升因子。

正确性

每个 (k\bmod N) 由中国剩余定理唯一对应于所有 (k\bmod p_i^{\alpha_i}) 的选择。对每个 (p_i)，算法枚举且只枚举不覆盖 1 的模 (p_i) 余数，并记录其覆盖的 0 位置；最终状态要求所有 0 均已覆盖，因此与题目条件完全等价。每个模 (p_i) 余数有恰好 (p_i^{\alpha_i-1}) 个模 (p_i^{\alpha_i}) 的提升，乘积因子也不重不漏。

复杂度

小质数阶段按实际可达掩码转移；29、31、37 使用至多 (O(19\cdot2^{22})) 的压缩表；大质数阶段为 (O(nm))。空间上界约为 350 MiB。