연립 일차 방정식

$N \times M$ 행렬 $A$와 크기가 $N$인 벡터 $b$가 주어진다. $Ax = b$를 만족하는 크기 $M$의 벡터 $x$를 구한다. 모든 것은 $\mathbb{F}_{998244353}$에서 고려한다.

제약 조건

• $1 \leq N, M \leq 500$
• $0 \leq A_{ij} < 998244353$

$N$ $M$
$A_{0,0}$ $A_{0,1}$ ... $A_{0,M-1}$
$A_{1,0}$ $A_{1,1}$ ... $A_{1,M-1}$
:
$A_{N-1,0}$ $A_{N-1,1}$ ... $A_{N-1,M-1}$
$b_0$ $b_1$ ... $b_{N-1}$

해가 없다면 다음을 출력한다.

-1

해가 존재한다면 다음과 같이 출력한다.

$R$
$c_0$ $c_1$ ... $c_{M-1}$
$d_{0,0}$ $d_{0,1}$ ... $d_{0,M-1}$
:
$d_{R-1,0}$ $d_{R-1,1}$ ... $d_{R-1,M-1}$

$R$는 해의 랭크이다. $c_i$는 해 중 하나이다. 각 $j$에 대해, $d_{j,0}, ..., d_{j,M-1}$는 해의 기저이다.