题目描述

给定一个 $n \times n$ 的矩阵 $M$，定义其特征多项式为 $f(\lambda) = \det (\lambda I - M)$，求 $f$ 的各项系数取模 $998,244,353$。

输入格式

输入的第一行包含一个整数 $n$。

接下来 $n$ 行，包含 $n$ 个整数 $M_{i,j}$。

输出格式

输出一行 $n + 1$ 个整数 $f_0, f_1, \cdots, f_n$，表示 $f(\lambda) = \sum_{i=0}^n f_i \lambda^i$。

样例数据

样例 1 输入

2
1 2
1 1

样例 1 输出

998244352 998244351 1

样例 1 解释

$f(\lambda) = \det \left(\begin{matrix}\lambda - 1 & -2 \\ -1 & \lambda-1\end{matrix}\right) = \lambda^2 - 2\lambda - 1$。

样例 2 输入

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

样例 2 输出

998244350 112 998244338 998244341 1

子任务

对于所有数据，$1 \leq n \leq 500$。

• Subtask 1(40 pts): $n \leq 50$
• Subtask 2(60 pts): $n \leq 500$