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 翻译