특성 다항식의 군주 (2)

$n \times n$ 행렬 $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) \cdot \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}$로 정의한다.

이번 문제의 행렬 원소는 특이하다. 1보다 큰 제곱수로 나누어떨어지지 않는 정수 $D \neq 1$이 주어진다. $A$의 모든 원소는 정수 $a, b$에 대해 $a + b\sqrt{D}$ 꼴로 나타낼 수 있는 수, 즉 다음 집합의 원소이다.

$\mathbb{Z}[\sqrt{D}] = \{a + b\sqrt{D} \mid a, b \in \mathbb{Z} \}$

$\phi_{A}(x)$의 계수 $c_{0}, \cdots, c_{n}$도 $\mathbb{Z}[\sqrt{D}]$의 원소임을 증명할 수 있다. 각 $c_{i} = p_{i} + q_{i}\sqrt{D}$를 만족하는 정수 $p_{i}, q_{i}$는 유일하게 존재한다. 주어진 정수 $M$에 대해, 각 $p_{i}$와 $q_{i}$를 $M$으로 나눈 나머지를 구하는 프로그램을 작성하시오.

첫 줄에 행렬의 크기 $n$, 나눗셈에 사용되는 정수 $M$, 정수 $D$가 주어진다.

이어지는 $n$개의 줄에는 각각 $2n$개의 정수가 주어진다. $i$번째 줄의 $2j-1$번째 수를 $x$, $2j$번째 수를 $y$라고 하면 $a_{ij} = x + y\sqrt{D}$이다.

총 $n+1$개의 줄에 걸쳐, $i$번째 줄에는 $p_{i}$와 $q_{i}$를 $M$으로 나눈 나머지를 공백으로 구분하여 출력한다.

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

• $1 \le n \le 100$
• $1 \le M \le 10^{9}$
• $-10^{9} \le D \le 10^{9}$
• $D \neq 1$이고, $D$는 1보다 큰 제곱수로 나누어떨어지지 않는다.
• 모든 $1 \le i, j \le n$에 대해 $a_{ij} = x + y\sqrt{D}$라고 두면, $0 \le x, y < M$이다.

• 각 $x \in \mathbb{Z}[\sqrt{D}]$에 대해, $x = a + b\sqrt{D}$를 만족하는 정수 $a, b$는 유일하게 존재한다.
• $(a + b\sqrt{D}) + (c + d\sqrt{D}) = (a + c) + (b + d)\sqrt{D}$
• $(a + b\sqrt{D})(c + d\sqrt{D}) = (ac + bdD) + (ad + bc)\sqrt{D}$