Alice 想要得到一个长度为 n n n 的序列，序列中的数都是不超过 m m m 的正整数，而且这 n n n 个数的和是 p p p 的倍数。
Alice 还希望，这 n n n 个数中，至少有一个数是质数。
Alice 想知道，有多少个序列满足她的要求。
一行三个数 n n n、m m m 和 p p p。
一行一个数，满足 Alice 要求的序列的数量。由于满足条件的序列可能很多，输出结果对 20170408 20170408 20170408 取模。
3 5 3
33
对于 20% 20\% 20% 的数据，1≤n≤100,1≤m≤100 1 \leq n \leq 100, 1 \leq m \leq 100 1≤n≤100,1≤m≤100；对于 50% 50\% 50% 的数据，1≤m≤100 1 \leq m \leq 100 1≤m≤100；对于 80% 80\% 80% 的数据，1≤m≤106 1 \leq m \leq 10 ^ 6 1≤m≤106；对于 100% 100\% 100% 的数据，1≤n≤109,1≤m≤2×107,1≤p≤100 1 \leq n \leq 10 ^ 9, 1 \leq m \leq 2 \times 10 ^ 7, 1 \leq p \leq 100 1≤n≤109,1≤m≤2×107,1≤p≤100。