P7776 [Template] Characteristic Polynomial

This is a template problem.

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

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

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

For an $n\times n$ matrix $A$, let its characteristic polynomial be $p_A(x)$, which satisfies $$p_A(x)=\det(xI_n-A)$$ 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