P7776 【模板】特征多项式

这是一道模板题。

给出 $n$ 和一个 $n\times n$ 的矩阵 $A$，在模 $998244353$ 意义下求其特征多项式。

无

无

对于一个 $n\times n$ 的矩阵 $A$，设其特征多项式为 $p_A(x)$，满足 $$p_A(x)=\det(xI_n-A)$$ 其中，$I_n$ 为一个 $n\times n$ 的单位矩阵。 对于 $10\%$ 的数据，$1\le n\le 5$；\ 对于 $40\%$ 的数据，$1\le n\le 50$；\ 对于另外 $10\%$ 的数据，$\forall1\le i\le n,1\le j\le i-1,A_{i,j}=0$，即 $A$ 为上三角矩阵；\ 对于另外 $20\%$ 的数据，$\forall1\le i\le n,1\le j\le i-2,A_{i,j}=0$，即 $A$ 为上海森堡矩阵；\ 对于 $100\%$ 的数据，$1\le n\le 500$，$A_{i,j}\in[0,998244352]$。