给定两个 $n \times n$ 的矩阵 $\mathbf{A}$ 和 $\mathbf{B}$. 对每个 $k = 0, 1, 2, \cdots, n$, 你需要计算 $f_k = [z^k] \det (\mathbf A + \mathbf B z) \bmod 998,244,353$.

输入格式

输入的第一行包含一个整数 $n$ ($1 \leq n \leq 500$).

接下来 $n$ 行描述矩阵 $\mathbf{A}$:

• 这些行中的第 $i$ 行包含 $n$ 个整数 $\mathbf{A}_{i,1}, \mathbf{A}_{i,2}, \cdots, \mathbf{A}_{i, n}$ ($0 \leq \mathbf{A}_{i,j} < 998,244,353$).

接下来 $n$ 行描述矩阵 $\mathbf{B}$:

• 这些行中的第 $i$ 行包含 $n$ 个整数 $\mathbf{B}_{i,1}, \mathbf{B}_{i,2}, \cdots, \mathbf{B}_{i, n}$ ($0 \leq \mathbf{B}_{i,j} < 998,244,353$).

输出格式

输出一行包含 $n + 1$ 个整数 $f_0, f_1, \cdots, f_n$ - 表示 $\det (\mathbf A + \mathbf B z) = \sum_{i=0}^n f_i z^i$.

样例数据

样例 1 输入

2
2 1
0 1
1 3
1 0

样例 1 输出

2 0 998244350

样例 1 解释

$\det (\mathbf A + \mathbf Bz) = \det \left|\begin{matrix}2+z&1+3z\\z&1\end{matrix}\right| = -3z^2 + 2$

样例 2 输入

3
998244352 998244351 998244350
3 2 0
2 1 2
0 998244352 0
1 0 1
1 1 2

样例 2 输出

11 9 6 1

样例 3 输入

4
0 0 0 0
0 0 0 1
0 1 0 0
0 0 0 1
0 1 0 0
1 1 1 0
0 0 1 1
0 0 0 0

样例 3 输出

0 0 0 998244352 0

样例 4 输入

8
0 0 0 1 8 5 7 6
2 8 3 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 1 1 1 1 1 1
0 0 2 2 2 2 2 2
0 0 3 8 9 5 4 4
7 6 5 4 3 2 1 0
8 6 9 4 1 2 3 4
0 0 0 0 0 0 0 0
0 0 0 0 0 5 5 5
1 2 3 4 5 6 7 8
9 9 9 9 5 5 5 4
3 7 8 5 1 7 0 6
2 4 9 8 5 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1

样例 4 输出

0 0 998068769 997897737 998126353 79000 3360 0 0

样例 5

你可以在附加文件中找到.

子任务

• Subtask 1(30 points): $1 \leq n \leq 50$
• Subtask 2(30 points): $\mathbf B_{i,j} = \begin{cases} 1 & i = j \\ 0 & \mathrm{otherwise}\end{cases}$
• Subtask 3(40 points): 没有额外的限制.