P3321 [SDOI2015] Sequence Statistics

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$.

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 a single integer on one line, representing the answer.

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