10420: #2002. 「SDOI2017」序列计数

内存限制：256 MB 时间限制：2.000 S 提交：0 解决：0
评测方式：文本比较 命题人：

题目描述

Alice 想要得到一个长度为 n n n 的序列，序列中的数都是不超过 m m m 的正整数，而且这 n n n 个数的和是 p p p 的倍数。

Alice 还希望，这 n n n 个数中，至少有一个数是质数。

Alice 想知道，有多少个序列满足她的要求。

输入格式

一行三个数 n n n、m m m 和 p p p。

输出格式

一行一个数，满足 Alice 要求的序列的数量。
由于满足条件的序列可能很多，输出结果对 20170408 20170408 20170408 取模。

样例

样例输入

3 5 3

样例输出

33

数据范围与提示

对于 20% 20\% 20% 的数据，1≤n≤100,1≤m≤100 1 \leq n \leq 100, 1 \leq m \leq 100 1≤n≤100,1≤m≤100；
对于 50% 50\% 50% 的数据，1≤m≤100 1 \leq m \leq 100 1≤m≤100；
对于 80% 80\% 80% 的数据，1≤m≤106 1 \leq m \leq 10 ^ 6 1≤m≤10​6​​；
对于 100% 100\% 100% 的数据，1≤n≤109,1≤m≤2×107,1≤p≤100 1 \leq n \leq 10 ^ 9, 1 \leq m \leq 2 \times 10 ^ 7, 1 \leq p \leq 100 1≤n≤10​9​​,1≤m≤2×10​7​​,1≤p≤100。