8818: BZOJ4818:[Sdoi2017]序列计数

Memory Limit:128 MB Time Limit:3 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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


输入格式

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


输出格式

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


样例输入

3 5 3

样例输出

33

提示

没有写明提示


题目来源

鸣谢infinityedge上传

加入题单

上一题 下一题 算法标签: