题目描述

You are given a 3-dimensional integer array $A$ of size $N \times N \times N$.

Initialize the following variables:

integer x = 0;
integer w = 1;
stack s = {};

Then, for each $t = 0, 1, \ldots, N - 1$, choose an integer $y_t$ such that $-1 \leq y_t < N$ and do the following action:

If $0 \leq y_t$, do the following:

w *= A[t][x][y];
s.push(x);
x = y;

The above $y$ denotes $y_t$.

If $y_t = -1$, do the following:

assert (!s.empty());
w *= A[t][x][s.top()];
x = (x + s.top()) % N;
s.pop();

You can't choose $y_t = -1$ if the stack is empty before the action.

Note that the stack has the following operations:

• push(x): adds an element $x$ to the collection.
• pop(): removes the most recently added element.
• top(): returns the value of the most recently added element.

For each $i = 0, 1, \ldots, N - 1$, consider all possible sequences $y_0, y_1, \ldots, y_{N-1}$ such that the final value of $x$ is $i$. Compute the sum of the corresponding values of $w$ over all such sequences, and output the result modulo $998244353$.

输入格式

The input is given in the following format:

$$\begin{aligned} & N \\ & A_{0,0,0} \cdots A_{0,0,N-1} \\ & \vdots \\ & A_{0,N-1,0} \cdots A_{0,N-1,N-1} \\ & \vdots \\ & \vdots \\ & A_{N-1,0,0} \cdots A_{N-1,0,N-1} \\ & \vdots \\ & A_{N-1,N-1,0} \cdots A_{N-1,N-1,N-1} \end{aligned}$$

$A_{i,j,k}$ means the value of $A[i][j][k]$.

• $1 \leq N \leq 30$
• $0 \leq A_{i,j,k} \leq 10^9 \ (1 \leq i, j, k \leq N)$
• All input values are integers.

输出格式

Output $N$ lines. On the $i$-th line ($0 \leq i < N$), output the answer for $i$.

2
1 10
100 1000
1 3
9 27

92
363

3
2 1 2
1 2 1
1 1 1
2 1 1
2 2 1
2 2 2
2 1 1
1 2 1
1 2 2

63
68
56

4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

120
120
120
120