Characteristic polynomial
Work modulo \(p=1\,000\,000\,007\). Given an \(n\times n\) matrix \(A\),
compute
\[
\chi_A(x)=\det(xI-A).
\]
Input
The first line contains \(n\). The next \(n\) lines contain \(A\).
Output
Print \(n+1\) coefficients
\[
c_n\ c_{n-1}\ \ldots\ c_1\ c_0,
\]
where \(\chi_A(x)=c_nx^n+c_{n-1}x^{n-1}+\cdots+c_0\). Entries are modulo
\(p\), and any representatives are accepted.
Constraints
- \(1\le n\le 8\)
- Every matrix entry is an integer in \([0,p)\)