#2002. 「SDOI2017」序列计数

内存限制:256 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

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

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

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

输入格式

一行三个数 n m p

输出格式

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

样例

样例输入

3 5 3

样例输出

33

数据范围与提示

对于 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