Background

This is a template problem.

Problem Description

Given $n$ and an $n\times n$ matrix $A$, find its characteristic polynomial modulo $998244353$.

Input Format

The first line contains a positive integer $n$.
Next $n$ lines each contain $n$ non-negative integers, representing the matrix $A$.

Output Format

Output one line with $n+1$ positive integers, representing the coefficients of its characteristic polynomial $p_A(x)$ from low degree to high degree.

3
1 2 3
4 5 6
7 8 9

0 998244335 998244338 1 

Hint

For an $n\times n$ matrix $A$, let its characteristic polynomial be $p_A(x)$, which satisfies

where $I_n$ is the $n\times n$ identity matrix.

For $10\%$ of the testdata, $1\le n\le 5$.
For $40\%$ of the testdata, $1\le n\le 50$.
For another $10\%$ of the testdata, $\forall1\le i\le n,1\le j\le i-1,A_{i,j}=0$, i.e. $A$ is an upper triangular matrix.
For another $20\%$ of the testdata, $\forall1\le i\le n,1\le j\le i-2,A_{i,j}=0$, i.e. $A$ is an upper Hessenberg matrix.
For $100\%$ of the testdata, $1\le n\le 500$, $A_{i,j}\in[0,998244352]$.

Translated by ChatGPT 5