희소 행렬의 행렬식

$N \times N$ 행렬 $M$가 주어진다. $M$의 원소 중 $K$개만 0이 아니며, $i$번째 원소는 $M(a_i, b_i) = c_i$이다. $\mathrm{det}(M) \bmod 998244353$를 출력한다.

제약 조건

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

$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$를 출력한다.