题意

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