Description:


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

Alice还希望,这 \(n\) 个数中,至少有一个数是质数。

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

Input:


一行三个数, \(n,m,p\)

\(1\le n\le10^9,1\le m\le 2\times 10^7,1\le p\le 100\)

Output:


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

Sample Input:


Sample Output:


题解:


看看题面,可以很容易地想到这样一个DP,设 \(dp(i, j, 0/1)\) 表示长度为 \(i\) 的序列,总和在模 \(p\) 意义下为 \(j\) ,是否出现质数的方案数。

于是就有:

然后发现可以矩阵快速幂。

本来以为就这样就可以了,但最后发现过不去。于是我们想办法把最后一维去掉。

我们需要求的是包含质数的情况,那么只要拿全部的方案数减去不包含质数的就可以了。