题目描述

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

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

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

输入格式

一行三个数 $ n $、$ m $ 和 $ p $。

输出格式

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

样例

input

3 5 3

output

33

数据范围与提示

对于 $ 20\% $ 的数据，$ 1 \leq n \leq 100, 1 \leq m \leq 100 $；
对于 $ 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 $。