[Sdoi2017]序列计数

时间限制:30s      空间限制:128MB

题目描述

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上传