# System of Linear Equations

AC一覧

## Problem Statement問題文

Given $N \times M$ matrix $A$, a size $N$ vector $b$. Please calculate a (size $M$) vector $x$ s.t. $Ax = b$. We consider everything $\mathbb{Z}_{998244353}$.

$N \times M$ 行列 $A$, 長さ $N$ のベクトル $b$ が与えられます。$Ax = b$ を満たす(長さ $M$ の)ベクトル $x$ を求めてください。ただし全ての要素は $\mathbb{Z}_{998244353}$ で考えることとします。

## Constraints制約

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

## Input入力

$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}$


## Output出力

If there is no solution, print

-1


and if exists, print as follows.

と出力してください。存在する場合、

$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}$


We note that $R$ is the rank of solution. $c_i$ is one of the solution. For each $j$, $d_{j,0}, ..., d_{j,M-1}$ is the basis of solution.

と出力してください。ただし、$R$ は解空間の次元、$c_i$ は解のうち $1$ つとし、各 $j$ について、$d_{j,0}, ..., d_{j,M-1}$ は解空間の(それぞれ独立な)基底ベクトルとします。

## Sampleサンプル

### # 1

2 3
1 2 3
4 5 6
50 122

1
998244351 26 0
1 998244351 1


Timelimit: 5 secs

Before submitting, please confirm terms and conditions