「SDOI2015」序列统计

题目描述

小 C 有一个集合 $S$，里面的元素都是小于 $M$ 的非负整数。
他有一个数列生成器，可以生成长度为 $N$ 的数列，数列中的每个数都属于集合 $S$。

给定整数 $x$，求所有可以生成的，且满足 数列中所有数的乘积 $\bmod M$ 的值等于 $x$ 的不同的数列的个数。
两个数列不同当且仅当至少存在一个位置 $i$，满足 $A_i \neq B_i$。

答案对 $1004535809$ 取模。

输入格式

第一行：$N, M, x, |S|$
第二行：$|S|$ 个整数，表示集合 $S$ 中的所有元素。

输出格式

一行，一个整数，表示答案 $\bmod 1004535809$。

样例

输入：

4 3 1 2
1 2

输出：

8

数据范围与提示

对于 $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$ 中元素不重复。