题目描述
Alice 想要得到一个长度为 n 的序列,序列中的数都是不超过 m 的正整数,而且这 n 个数的和是 p 的倍数。
Alice 还希望,这 n 个数中,至少有一个数是质数。
Alice 想知道,有多少个序列满足她的要求。
输入格式
一行三个数 n、m 和 p。
输出格式
一行一个数,满足 Alice 要求的序列的数量。
由于满足条件的序列可能很多,输出结果对 20170408 取模。
样例
3 5 3
33
数据范围与提示
对于 20% 的数据,1≤n≤100,1≤m≤100;
对于 50% 的数据,1≤m≤100;
对于 80% 的数据,1≤m≤106;
对于 100% 的数据,1≤n≤109,1≤m≤2×107,1≤p≤100。