稀疏矩阵行列式

【题目描述】

给定一个 $N \times N$ 的矩阵 $M$。

$M$ 中只有 $K$ 个元素非零，其中第 $i$ 个为 $M(a_i, b_i) = c_i$。

【输入】

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

【输出】

输出 $\mathrm{det}(M) \bmod 998244353$。

【输入样例】

3 3
0 0 1
1 1 2
2 2 3

【输出样例】

6

【输入样例2】

3 1
0 0 1

【输出样例2】

0

【数据范围】

• $1 \leq N \leq 3000$
• $1 \leq K \leq 10000$
• $0 \leq a_i, b_i \leq N - 1$
• $(a_i, b_i)$ 互不相同。
• $1 \leq c_i < 998244353$

【来源】

Library Checker（yosupo06） sparse_matrix_det