1261: #2002. 「SDOI2017」序列计数

Memory Limit:256 MB Time Limit:2.000 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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

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

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

输入格式

一行三个数 n n nm m mp 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 1n100,1m100
对于 50% 50\% 50% 的数据,1≤m≤100 1 \leq m \leq 100 1m100
对于 80% 80\% 80% 的数据,1≤m≤106 1 \leq m \leq 10 ^ 6 1m106
对于 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 1n109,1m2×107,1p100