题意

Alice 想要得到一个长度为 \(n\) 的序列,序列中的数都是不超过 \(m\) 的正整数,而且这 \(n\) 个数的和是 \(p\) 的倍数。Alice 还希望,这 \(n\) 个数中,至少有一个数是质数。Alice 想知道,有多少个序列满足她的要求,答案对 \(20170408\) 取模。

其中,\(1 \leq n \leq 10^9\)\(1 \leq m \leq 2 \times 10^7\)\(1 \leq p \leq 100\)

Read More