Alice 想要得到一个长度为 n 的序列，序列中的数都是不超过 m 的正整数，而且这 n 个数的和是 p 的倍数。
Alice 还希望，这 n 个数中，至少有一个数是质数。
Alice 想知道，有多少个序列满足她的要求。

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

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

对 20% 的数据，1≤n,m≤100。
对 50% 的数据，1≤m≤100。
对 80% 的数据，1≤m≤10⁶。
对 100% 的数据，1≤n≤10⁹,1≤m≤2×10⁷,1≤p≤100。

FFT