序列计数

序列计数

测试数据来自 system/2015

描述

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

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

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

格式

输入格式

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

输出格式

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

样例1

样例输入1

3 5 3

样例输出1

33

限制

对于20%的数据,\(1\le n\le 100\),\(1\le m\le 100\)

对于50%的数据,\(1\le m\le 100\)

对于80%的数据,\(1\le m\le 10^6\)

对100%的数据,\(1\le n\le 10^9\),\(1\le m\le 2\times 10^7\),\(1\le p\le 100\)

来源

SDOI 2017 Round1 Day1

信息

ID
1059
难度
(无)
分类
(无)
标签
递交数
0
已通过
0
通过率
?
上传者