#1116. [Sdoi2017]序列计数

[Sdoi2017]序列计数

Description

Alice想要得到一个长度为n的序列,序列中的数都是不超过m的正整数,而且这n个数的和是p的倍数。Alice还希望

,这n个数中,至少有一个数是质数。Alice想知道,有多少个序列满足她的要求。

Format

Input

一行三个数,n,m,p。

1<=n<=10^9,1<=m<=2×10^7,1<=p<=100

Output

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

Samples

3 5 3
33