Rock‐Paper‐Scissors Tournament

We have (n=3^m) players who compete in a tournament of (t) rounds. Each player (x) (with (0\le x<n)) uses a fixed (m)-move strategy in every round. The strategy is determined by writing (x) in base 3 with exactly (m) digits; the digit (0) represents scissors, (1) represents rock, and (2) represents paper.

In each round, every player (x) plays an (m)-game match against every player (y) (including themselves). For the match between (x) and (y), let [ u = W(x,y)=#{i:, \text{in game } i,; x\text{ wins}}, \quad v = L(x,y)=#{i:, \text{in game } i,; x\text{ loses}}, ] where a win in a single game is determined by the rules

• Scissors (0) beat Paper (2),
• Rock (1) beats Scissors (0), and
• Paper (2) beats Rock (1).

Ties (when the two moves are equal) are not counted. A given scoring array (b_{u,v}) (for (0\le u,v\le m)) provides a multiplier for a match whose outcome (for (x)) is ((u,v)). (In particular, when (x=y) the outcome is always ((0,0)) and the multiplier (b_{0,0}) applies.)

Initially, player (x) has score (f_{0,x}). After each round, the scores are updated by

[ f_{i,x}=\sum_{y=0}^{n-1} f_{i-1,y}, b_{u,v} \quad (i\ge1), ]

where for each pair ((x,y)) the numbers (u,v) are determined as above. Since the scores may become very large, every time a score is stored it is reduced modulo (p); that is, whenever (f\ge p) we take (f \bmod p).

A key observation is that the update is a convolution on the group ( \mathbb{Z}_3^m), with the kernel defined by

[ g(z)=b_{u,v},\quad \text{where } u=#{i:, z_i=1},; v=#{i:, z_i=2}, \quad \text{and } z=(z_0,z_1,\dots,z_{m-1})\in\mathbb{Z}_3^m. ]

Thus the final scores after (t) rounds satisfy

[ f_{t}=g^{*t} * f_{0} \quad (\text{convolution on } \mathbb{Z}_3^m), ]

which can be computed via the multidimensional discrete Fourier transform. (In our formulas the characters on (\mathbb{Z}_3) are given by the third roots of unity (\omega) satisfying (\omega^3=1) and (\omega\neq 1); note that all formulas involving (\omega) must be interpreted in (\bmod, p) arithmetic.)

One final remark: It is guaranteed that the prime (p) satisfies the special property that there do not exist two positive integers whose reciprocals sum to (\frac{3}{p}).

Your task is to compute the final scores (f_{t,0}, f_{t,1}, \dots, f_{t,n-1}) modulo (p).

Input Format: described below.

Output Format: described below.

inputFormat

The first line contains three integers: m, t, and p.

The second line contains \(3^m\) integers: \(f_{0,0}, f_{0,1}, \dots, f_{0,3^m-1}\), representing the initial scores.

The following m+1 lines each contain m+1 integers. The j-th integer in the i-th of these lines is \(b_{i,j}\) (for \(0\le i,j\le m\)).

outputFormat

Output \(3^m\) integers: \(f_{t,0}, f_{t,1}, \dots, f_{t,3^m-1}\), separated by spaces, where each score is given modulo \(p\).

sample

1 1 7
1 2 3
1 2
3 4

0 4 4