P1446 [HNOI2008] Cards

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

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

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 the number of distinct colorings modulo $P$.

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