F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister
Problem 4818. -- [Sdoi2017]序列计数

4818: [Sdoi2017]序列计数

Time Limit: 30 Sec  Memory Limit: 128 MB
Submit: 1250  Solved: 743
[Submit][Status][Discuss]

Description

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

Input

一行三个数,n,m,p。
1<=n<=10^9,1<=m<=2×10^7,1<=p<=100

Output

一行一个数,满足Alice的要求的序列数量,答案对20170408取模。

Sample Input

3 5 3

Sample Output

33

HINT

Source

鸣谢infinityedge上传

[Submit][Status][Discuss]

HOME Back