/ Vijos / 题库 /

序列计数

序列计数

描述

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
2015
难度
4
分类
(无)
标签
递交数
23
已通过
15
通过率
65%
上传者

相关

在下列训练计划中:

RP++分类题库