[SDOI2015] 序列统计
题目描述
小C有一个集合 $S$,里面的元素都是小于 $m$ 的非负整数。他用程序编写了一个数列生成器,可以生成一个长度为 $n$ 的数列,数列中的每个数都属于集合 $S$。
小C用这个生成器生成了许多这样的数列。但是小C有一个问题需要你的帮助:给定整数 $x$,求所有可以生成出的,且满足数列中所有数的乘积 $\bmod \ m$ 的值等于 $x$ 的不同的数列的有多少个。
小C认为,两个数列 $A$ 和 $B$ 不同,当且仅当 $\exists i \text{ s.t. } A_i \neq B_i$。另外,小C认为这个问题的答案可能很大,因此他只需要你帮助他求出答案对 $1004535809$ 取模的值就可以了。
输入输出格式
输入格式
一行,四个整数,$n,m,x,|S|$,其中 $|S|$ 为集合 $S$ 中元素个数。
第二行,$|S|$ 个整数,表示集合 $S$ 中的所有元素。
输出格式
一行一个整数表示答案。
输入输出样例
输入样例 #1
4 3 1 2
1 2
输出样例 #1
8
说明
【样例说明】
可以生成的满足要求的不同的数列有(1,1,1,1)、(1,1,2,2)、(1,2,1,2)、(1,2,2,1)、(2,1,1,2)、(2,1,2,1)、(2,2,1,1)、(2,2,2,2)。
【数据规模和约定】
对于 $10\%$ 的数据,$1\le n \le 1000$;
对于 $30\%$ 的数据,$3 \le m \le 100$;
对于 $60\%$ 的数据,$3 \le m \le 800$;
对于 $100\%$ 的数据,$1 \le n \le 10^9$,$3 \le m \le 8000$,$1\le x < m$。
$m$ 为质数,输入数据保证集合 $S$ 中元素不重复。