Description

Xiao C has a set $S$ whose elements are non-negative integers less than $m$. He wrote a sequence generator that can generate a sequence of length $n$, where every term belongs to the set $S$.

Xiao C generated many such sequences. However, he needs your help with the following question: given an integer $x$, count how many different sequences can be generated such that the product of all numbers in the sequence $\bmod \ m$ equals $x$.

Xiao C considers two sequences $A$ and $B$ different if and only if $\exists i \text{ s.t. } A_i \neq B_i$. Since the answer may be large, he only needs the answer modulo $1004535809$.

Input Format

One line with four integers $n, m, x, |S|$, where $|S|$ is the number of elements in the set $S$.
The second line contains $|S|$ integers, representing all elements of the set $S$.

Output Format

Output a single integer on one line, representing the answer.

4 3 1 2
1 2

8

Hint

Sample explanation:

The different sequences that can be generated and satisfy the requirement are $(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)$.

Constraints:

For $10\%$ of the testdata, $1 \le n \le 1000$.
For $30\%$ of the testdata, $3 \le m \le 100$.
For $60\%$ of the testdata, $3 \le m \le 800$.
For $100\%$ of the testdata, $1 \le n \le 10^9$, $3 \le m \le 8000$, $1 \le x < m$.
$m$ is a prime, and the input guarantees that the elements in set $S$ are distinct.

Translated by ChatGPT 5