# QOJ

Time Limit: 3 s Memory Limit: 2048 MB Total points: 100 Hackable ✓

# # 59. Determinant of A+Bz

You are given two $n \times n$ matrices $\mathbf{A}$ and $\mathbf{B}$. For each $k = 0, 1, 2, \cdots, n$, you need to calculate $f_k=[z^k] \det (\mathbf A + \mathbf B z) \bmod 998,244,353$.

### Input

The first line contains a single integer $n$ ($1 \leq n \leq 500$).

The next $n$ lines describes the matrix $\mathbf{A}$:

• The $i$-th line of these lines contains $n$ integers $\mathbf{A}_{i,1}, \mathbf{A}_{i,2}, \cdots, \mathbf{A}_{i, n}$ ($0 \leq \mathbf{A}_{i,j} < 998,244,353$).

The next $n$ lines describes the matrix $\mathbf{B}$:

• The $i$-th line of these lines contains $n$ integers $\mathbf{B}_{i,1}, \mathbf{B}_{i,2}, \cdots, \mathbf{B}_{i, n}$ ($0 \leq \mathbf{B}_{i,j} < 998,244,353$).

### Output

Output a single line contains $n + 1$ integers $f_0, f_1, \cdots, f_n$ - describes $\det (\mathbf A + \mathbf B z) = \sum_{i=0}^n f_i z^i$

### Examples

#### Input 1

2
2 1
0 1
1 3
1 0

#### Output 1

2 0 998244350

#### Explanation 1

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

#### Input 2

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

#### Output 2

11 9 6 1

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

#### Output 3

0 0 0 998244352 0

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

#### Output 4

0 0 998068769 997897737 998126353 79000 3360 0 0

#### Input / Output 5

You can find them in the additional files.

### Scoring

• 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}$

### 输入格式

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

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

### 样例数据

#### 样例 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

### 子任务

• 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}$