题目描述

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

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

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

输入格式

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

输出格式

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

样例输入

3 5 3

样例输出

33

数据范围与约定

对 $20\%$ 的数据，$1\leq n,m\leq100$；

对 $50\%$ 的数据，$1\leq m \leq 100$；

对 $80\%$ 的数据，$1\leq m\leq 10^6$；

对 $100\%$ 的数据，$1\leq n \leq 10^9$，$1\leq m \leq 2\times 10^7$，$1\leq p\leq 100$。