#1281. [SDOI2017] 序列计数

[SDOI2017] 序列计数

题目描述

Alice 想要得到一个长度为 nn 的序列,序列中的数都是不超过 mm 的正整数,而且这 nn 个数的和是 pp 的倍数。

Alice 还希望,这 nn 个数中,至少有一个数是质数。

Alice 想知道,有多少个序列满足她的要求。

输入格式

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

输出格式

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

样例

3 5 3
33

题目来源:洛谷 P3702