Strange Dream

Dumitru had a very strange dream: he was locked inside a room. In that room there were $n$ boxes, and each box contained exactly $m$ plates. Every plate has a single integer greater than or equal to $1$ written on it. There was also a note in the room with two integers $k$ and $l$ on it, describing the following task.

• Step 1: Take one plate from the first box, write the number on it into your notebook, change the number on that plate to $1$, and put the plate back into the box. Then, in the same way, take one plate from the second box, then one from the third box, $\dots$, up to and including the $n$-th (last) box. Each time, take one plate from the current box, write its number in the notebook, change that plate's number to $1$, and put it back.
• Step 2: After that, in the same way, take one plate from box $n-1$, then one from box $n-2$, $\dots$, down to and including the second box. Each time, take one plate from the current box, write its number in the notebook, change that plate's number to $1$, and put it back.

Let $T$ be the number of different ways of picking the plates as described above such that the product of all the numbers written in the notebook is divisible by $k$. Because $T$ can be extremely large, compute the remainder of $T$ when divided by $l$.

The first line contains two integers $n$ and $m$ separated by a single space. The second line contains two integers $k$ and $l$ separated by a single space. Then follow $n$ lines, each containing $m$ integers separated by single spaces. The first of these lines holds the $m$ numbers written on the plates in the first box, the second line holds the numbers of the second box, and so on.

Print a single integer: the remainder of $T$ when divided by $l$.

• $3 \le n \le 200$
• $3 \le m \le 10\,000$
• $2 \le k \le 200\,000$
• $2 \le l \le 30\,000$
• Each number written on a plate is an integer between $1$ and $1\,000\,000$ inclusive.

In the first example there are exactly $12$ ways of picking the plates so that the product of the numbers written in the notebook is divisible by $12$. Two points are important.

• If in some box you pick the same plate in both Step 1 and Step 2, then its number was already changed to $1$ during Step 1, so the value written in the notebook during Step 2 is $1$.
• Two ways are counted as different whenever the combination of chosen plate indices differs, even if the multiset of picked plate values is the same.