1258: #2002. 「SDOI2017」序列计数
[Creator : ]
Description
Alice 想要得到一个长度为 $n$ 的序列，序列中的数都是不超过 $m$ 的正整数，而且这 $n$ 个数的和是 $p$ 的倍数。
Alice 还希望，这 $n$ 个数中，至少有一个数是质数。
Alice 想知道，有多少个序列满足她的要求。
Alice 还希望，这 $n$ 个数中，至少有一个数是质数。
Alice 想知道，有多少个序列满足她的要求。
Input
一行三个数 $n,m,p$。
Output
一行一个数，满足 Alice 要求的序列的数量。
由于满足条件的序列可能很多，输出结果对 $20170408$ 取模。
由于满足条件的序列可能很多，输出结果对 $20170408$ 取模。
Constraints
对于 $20\%$ 的数据，$1 \leq n \leq 100,\ 1 \leq m \leq 100$；
对于 $50\%$ 的数据，$1 \leq m \leq 100$；
对于 $80\%$ 的数据，$1 \leq m \leq 10 ^ 6$；
对于 $100\%$ 的数据，$1 \leq n \leq 10 ^ 9, 1 \leq m \leq 2 \times 10 ^ 7, 1 \leq p \leq 100$。
对于 $50\%$ 的数据，$1 \leq m \leq 100$；
对于 $80\%$ 的数据，$1 \leq m \leq 10 ^ 6$；
对于 $100\%$ 的数据，$1 \leq n \leq 10 ^ 9, 1 \leq m \leq 2 \times 10 ^ 7, 1 \leq p \leq 100$。
Sample 1 Input
3 5 3
Sample 1 Output
33