Coloring Cards with Shuffles

Little Chun has n cards on his desk and 3 colors available, namely red, blue, and green. He considers three different questions:

1. What is the number of ways to color the n cards (each card can be colored arbitrarily with one of the three colors)? The answer should be computed modulo a prime P. In other words, compute \(3^n \bmod P\).
2. Now, Little Chun requires that exactly \(S_r\) cards are painted red, \(S_b\) cards blue, and \(S_g\) cards green (it is guaranteed that \(S_r+S_b+S_g=n\)). What is the number of valid colorings modulo \(P\)? That is, compute the multinomial coefficient \[ \frac{n!}{S_r!\,S_b!\,S_g!} \bmod P, \] where all operations are done modulo \(P\), a prime number.
3. Finally, Little Chun has invented m different shuffling operations. Each shuffle is a permutation of the n cards. Two colorings are considered equivalent if one can be transformed into the other by applying a sequence (each shuffle can be used arbitrarily many times, in any order) of these shuffling operations. Under this equivalence relation, how many different colorings (without any restrictions on the number of cards of each color) are there modulo \(P\)? By Burnside's lemma, the answer is given by \[ \frac{1}{|G|}\sum_{g\in G}3^{c(g)} \bmod P, \] where \(G\) is the subgroup of the symmetric group generated by the given m shuffles, and \(c(g)\) denotes the number of cycles in the permutation \(g\). Note that since \(P\) is prime, you may use modular inverses when dividing by \(|G|\).

You are given n, \(S_r, S_b, S_g\), m and P on the first line. It is guaranteed that \(S_r+S_b+S_g=n\). Then, the next m lines each contain a permutation of \(\{1,2,\dots,n\}\) representing a shuffling operation. Print three space‐separated integers:

1. The number of colorings with 3 colors modulo \(P\).
2. The number of colorings with exactly \(S_r\) red, \(S_b\) blue and \(S_g\) green, modulo \(P\).
3. The number of equivalence classes of colorings under the group generated by the m shuffles (i.e. the number of orbits in the set of all colorings), modulo \(P\).

Input Format:

• The first line contains six integers: n S_r S_b S_g m P (with \(P\) prime and \(S_r+S_b+S_g=n\)).
• Each of the next m lines contains n space‐separated integers: a permutation of \(\{1,2,\dots,n\}\).

Output Format:

• Print three space-separated integers representing the answers to the three questions described above, each modulo \(P\).

Note: It is guaranteed that the provided shuffles generate a subgroup \(G\) which is small enough so that you can enumerate all its elements.

inputFormat

The first line contains six integers: n S_r S_b S_g m P (with \(S_r+S_b+S_g=n\) and \(P\) being prime).

Then, there are m lines, each containing n integers which form a permutation of \(\{1, 2, \dots, n\}\), representing a shuffling operation.

outputFormat

Output three space‐separated integers on one line:

1. The number of ways to color n cards using 3 colors modulo \(P\).
2. The number of ways to color the cards with exactly \(S_r\) red, \(S_b\) blue, and \(S_g\) green modulo \(P\).
3. The number of equivalence classes of colorings (under the group generated by the shuffles) modulo \(P\).

sample

3 1 1 1 1 1000003
2 3 1

27 6 11