Description

Xiaochun is quite idle. Facing $n$ cards on the desk, he decides to color each card. He currently has $3$ colors: red, blue, and green. He asks Sun how many colorings there are, and Sun quickly gives the answer.

Furthermore, Xiaochun requires exactly $S_r$ red, $S_b$ blue, and $S_g$ green cards. He asks again how many colorings there are; Sun thinks for a moment and gives the correct answer. Finally, Xiaochun invents $m$ different shuffles. He asks Sun how many essentially different colorings there are now. Two colorings are considered the same if and only if one can be transformed into the other by applying arbitrary shuffles (that is, you may use multiple shuffles, and each shuffle may be used multiple times).

Sun finds this problem somewhat challenging and decides to leave it to you. Since the answer may be large, you only need to output the result modulo $P$. It is guaranteed that $P$ is a prime.

Description

Input Format

The first line contains $5$ integers: $S_r, S_b, S_g, m, P$ (with $m \le 60, m+1 < P < 100$). Here, the $n$ mentioned in the statement is $S_r + S_b + S_g$, i.e., $n = S_r + S_b + S_g$.

The next $m$ lines each describe a shuffle. Each line has $n$ space-separated integers $X_1, X_2, \dots, X_n$, guaranteed to be a permutation of $1$ to $n$, meaning that when using this shuffle, position $i$ becomes the card that was originally at position $X_i$. The input guarantees that any number of shuffles can be replaced by one of these $m$ shuffles, and that for every shuffle, there exists a shuffle that brings you back to the original state.

Also, for $100\%$ of the testdata, $\max\{S_r, S_b, S_g\} \le 20$.

Output Format

Output the number of distinct colorings modulo $P$.

1 1 1 2 7
2 3 1
3 1 2

2

Hint

There are $2$ essentially different colorings: RGB and RBG. Using shuffle 231 once gives GBR and BGR; using shuffle 312 once gives BRG and GRB.

Translated by ChatGPT 5