序列计数 ### 题目描述 Alice想要得到一个长度为$n$的序列，序列中的数都是不超过$m$的正整数，而且这$n$个数的和是$p$的倍数。 Alice还希望，这$n$个数中，至少有一个数是质数。 Alice想知道，有多少个序列满足她的要求。 ### 输入描述 输入一行三个数，$n,m,p$。 其中， $1\leq n \leq 10^9,1\leq m \leq 2\times 10^7,1\leq p\leq 100$。 ### 输出描述 输出一行一个数，满足Alice的要求的序列数量，答案对$20170408$取模。 ### 输入输出样例 #### 示例 1 >输入 ```txt 3 5 3 ``` >输出 ```txt 33 ```