AT_caddi2018_d.Square

高桥君有一个 $N$ 行 $N$ 列的网格。网格中从上往下第 $i$ 行，从左往右第 $j$ 列的格子记作 $(i,j)$。特别地，左上角的格子是 $(1,1)$，右下角的格子是 $(N,N)$。

在高桥君拥有的网格中，有 $M$ 个格子已经被写入了整数 $0$ 或 $1$。第 $i$ 个被写入的格子的相关信息用三个整数 $a_i, b_i, c_i$ 表示，表示在格子 $(a_i, b_i)$ 上写入了整数 $c_i$。

高桥君打算在剩下的格子中填入 $0$ 或 $1$，使得满足以下条件。请你求出所有可能的填法数量对 $998244353$ 取模的结果。

• 对于任意 $1 \leq i < j \leq N$，以 $(i,i)$ 为左上角、$(j,j)$ 为右下角的正方形区域内，填入的 $1$ 的个数必须是偶数。

输入以如下格式从标准输入读入。

$N$ $M$
$a_1$ $b_1$ $c_1$
$a_2$ $b_2$ $c_2$
$\vdots$
$a_M$ $b_M$ $c_M$

输出所有满足条件的填法数量对 $998244353$ 取模的结果。

限制条件

• $2 \leq N \leq 10^5$
• $0 \leq M \leq \min(5 \times 10^4, N^2)$
• $1 \leq a_i, b_i \leq N \ (1 \leq i \leq M)$
• $0 \leq c_i \leq 1 \ (1 \leq i \leq M)$
• 如果 $i \neq j$，则 $(a_i, b_i) \neq (a_j, b_j)$
• 所有输入均为整数

样例说明 1

例如，以下几种填法都满足条件。

101   111
011   111
000   011

由 ChatGPT 4.1 翻译