특성 다항식의 군주 (1)

$n \times n$ 행렬 $A$의 행렬식(determinant) $\det A$는 다음과 같이 정의한다. $a_{ij}$는 $A$의 $i$행 $j$열 원소를 뜻한다. $S_n$은 $\{1, \cdots, n\}$의 순열들의 집합이며, 각 $\sigma \in S_n$에 대해 $\{1, \cdots, n\} = \{\sigma(1), \cdots, \sigma(n)\}$이 성립한다.

$\det A = \sum_{\sigma \in S_n} \mathrm{sgn}(\sigma) \left(\prod_{i = 1}^{n} a_{i \sigma(i)}\right)$

$A$의 특성 다항식 $\phi_A(x)$는 $x$에 대한 $n$차 다항식으로, $\phi_A(x) = \det(xI - A) = c_n x^n + c_{n-1} x^{n-1} + \cdots + c_0$로 정의한다.

각 원소가 $0$ 이상 $10^9$ 미만인 정수 행렬 $A$가 주어진다. $\phi_A(x)$의 계수 $c_0, \cdots, c_n$도 정수임을 증명할 수 있다. 주어진 정수 $M$에 대해, 각 계수를 $M$으로 나눈 나머지를 구하는 프로그램을 작성하시오.

첫 줄에 행렬의 크기 $n$과 나눗셈에 사용할 정수 $M$이 주어진다.

둘째 줄부터 $n$개의 줄에 걸쳐 행렬 $A$의 원소가 각 줄에 공백으로 구분되어 $n$개씩 주어진다. $i$번째 줄의 $j$번째 수는 $A$의 $i$행 $j$열 원소 $a_{ij}$이다.

$n+1$개의 줄에 $c_0, \cdots, c_n$을 $M$으로 나눈 나머지를 순서대로 출력한다.

정수 $a$를 $M$으로 나눈 나머지는, $a - b$가 $M$의 배수가 되는 가장 작은 음이 아닌 정수 $b$이다.

• $1 \le n \le 500$
• $2 \le M \le 10^{9}$
• $0 \le a_{ij} < 10^{9}$ $(1 \le i, j \le n)$