测试数据来自 system/2015

描述

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

Alice还希望，这n个数中，至少有一个数是质数。

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

格式

输入格式

一行三个数，n，m和p。

输出格式

一行一个数，满足Alice的要求的序列的数量。由于满足条件的序列可能很多，输出结果对20170408取模。

样例1

样例输入1

3 5 3

样例输出1

33

限制

对于20％的数据，\(1\le n\le 100\)，\(1\le m\le 100\)

对于50％的数据，\(1\le m\le 100\)

对于80％的数据，\(1\le m\le 10^6\)

对100％的数据，\(1\le n\le 10^9\)，\(1\le m\le 2\times 10^7\)，\(1\le p\le 100\)

来源

SDOI 2017 Round1 Day1