[SDOI2017] 序列计数
题目描述
Alice 想要得到一个长度为 $n$ 的序列,序列中的数都是不超过 $m$ 的正整数,而且这 $n$ 个数的和是 $p$ 的倍数。
Alice 还希望,这 $n$ 个数中,至少有一个数是质数。
Alice 想知道,有多少个序列满足她的要求。
输入输出格式
输入格式
一行三个数,$n,m,p$。
输出格式
一行一个数,满足 Alice 的要求的序列数量,答案对 $20170408$ 取模。
输入输出样例
输入样例 #1
3 5 3
输出样例 #1
33
说明
对 $20\%$ 的数据,$1\leq n,m\leq100$。
对 $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$。