题目描述

小 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$ 的值。

4 3 1 2
1 2

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≤n\le 1000$；

对于 $30\%$ 的数据，$3≤m\le 100$；

对于 $60\%$ 的数据，$3\le m\le 800$；

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