#650. #2002. 「SDOI2017」序列计数

#2002. 「SDOI2017」序列计数

题目描述

Alice 想要得到一个长度为 nn 的序列,序列中的数都是不超过 mm 的正整数,而且这 nn 个数的和是 pp 的倍数。 Alice 还希望,这 nn 个数中,至少有一个数是质数。 Alice 想知道,有多少个序列满足她的要求。

输入格式

一行三个数 nn、mm 和 pp。

输出格式

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

3 5 3
33

数据范围与提示

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