序列统计

【题目描述】

小 $C$ 有一个集合 $S$，里面的元素都是小于 $M$ 的非负整数。

他用程序编写了一个数列生成器，可以生成一个长度为 $N$ 的数列，数列中的每个数都属于集合 $S$。

小 $C$ 用这个生成器生成了许多这样的数列。但是小 $C$ 有一个问题需要你的帮助：

给定整数 $x$，求所有可以生成出的，且满足数列中所有数的乘积 $mod$ $M$ 的值等于 $x$ 的不同的数列的有多少个。

小 $C$ 认为，两个数列 ${A_i}$ 和 ${B_i}$ 不同，当且仅当至少存在一个整数 $i$，满足 $A_i ≠ B_i$。

另外，小 $C$ 认为这个问题的答案可能很大，因此他只需要你帮助他求出答案 $mod$ $1004535809$ 的值就可以了。

【输入格式】

一行，四个整数，$N、M、x、|S|$，其中 $|S|$ 为集合 $S$ 中元素个数。

第二行，$|S|$ 个整数，表示集合 $S$ 中的所有元素。

【输出格式】

一行，一个整数，表示你求出的权值和 $mod$ $1004535809$ 的值。

【样例1输入】

4 3 1 2
1 2

【样例1输出】

8

【样例2】

点击下载样例2 

【数据规模与约定】

对于 $10\%$ 的数据，$1 \leq N \leq 1000$；

对于 $30\%$ 的数据，$3 \leq M \leq 100$；

对于 $60\%$ 的数据，$3 \leq M \leq 800$；

对于全部的数据，$1 \leq N \leq 10^9，3 \leq M \leq 8000$，$M$ 为质数，$1 \leq x \leq M-1$，输入数据保证集合 $S$ 中元素不重复。