序列统计 ### 题目描述 小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 \le n \le 10^9$，$3 \le m \le 8000$，$1\le x < m$。 ### 输出描述 输出一个整数表示答案。 ### 输入输出样例 #### 示例 1 >输入 ```txt 4 3 1 2 1 2 ``` >输出 ```txt 8 ```