# Determinant of Sparse Matrix

AC一覧

## Problem Statement問題文

Given $N \times N$ matrix $M$. Only $K$ elements of $M$ is non-zero, and $i$-th is $M(a_i, b_i) = c_i$. Print $\mathrm{det}(M) \bmod 998{,}244{,}353$.

$N \times N$ 正方行列 $M$ が与えられます。 $M$ は $K$ 個の要素のみが非零で、$i$ 個目は $M(a_i, b_i) = c_i$ です。 $M$ の行列式を $\bmod 998{,}244{,}353$ で求めてください。

## Constraints制約

• $1 \leq N \leq 3{,}000$
• $1 \leq K \leq 10{,}000$
• $0 \leq a_i, b_i \leq N - 1$
• $(a_i, b_i)$
is distinct
は全て異なる
• $1 \leq c_i < 998{,}244{,}353$

## Input入力

$N$ $K$
$a_1$ $b_1$ $c_1$
$a_2$ $b_2$ $c_2$
:
$a_K$ $b_K$ $c_K$


## Sampleサンプル

### # 1

3 3
0 0 1
1 1 2
2 2 3

6


### # 2

3 1
0 0 1

0


Timelimit: 5 secs

Before submitting, please confirm terms and conditions