Xiao C has a set $S$ consisting of non-negative integers less than $M$. He has written a program that generates a sequence of length $N$, where every element in the sequence belongs to the set $S$.

Xiao C has generated many such sequences using this generator. However, he needs your help with a problem: given an integer $x$, find the number of distinct sequences that can be generated such that the product of all numbers in the sequence modulo $M$ is equal to $x$. Xiao C considers two sequences $\{A_i\}$ and $\{B_i\}$ to be different if and only if there exists at least one integer $i$ such that $A_i \neq B_i$. Additionally, since the answer to this problem may be very large, he only needs you to find the answer modulo $1004535809$.

Input

The first line contains four integers $N$, $M$, $x$, and $|S|$, where $|S|$ is the number of elements in set $S$.

The second line contains $|S|$ integers, representing all elements in set $S$.

Output

A single integer representing the calculated count modulo $1004535809$.

Examples

Input 1

4 3 1 2
1 2

Output 1

8

Note

The distinct sequences that satisfy the requirements 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)$, and $(2,2,2,2)$.

Constraints

For $10\%$ of the data, $1 \le N \le 1000$;

For $30\%$ of the data, $3 \le M \le 100$;

For $60\%$ of the data, $3 \le M \le 800$;

For all data, $1 \le N \le 10^9$, $3 \le M \le 8000$, $M$ is a prime number, $1 \le x \le M-1$. The input guarantees that the elements in set $S$ are distinct.