序列计数
测试数据来自 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
- 1947
- 难度
- (无)
- 分类
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 通过率
- ?
- 上传者