分数: 900 点
问题陈述
高桥有一个 N \times N 网格。广场位于 i第行和 j网格的第列表示为 (i,j)。 特别是,网格的左上角方块是 (1,1),右下方块是 (N,N).
一个整数, 0 or 1,写在 高桥网格中的方块的 M 。 三个整数 a_i,b_i 和 c_i 描述 i- 第一个写有整数的正方形:整数 广场上写着 c_i 广场上写着 (a_i,b_i).
高桥决定写一个整数, 0 or 1,在每个剩余的方块上,以满足以下条件。 求这种写法的数量,取模 998244353.
- 对于所有人 1\leq i < j\leq N,有偶数个 1位于左上角正方形为的正方形区域中 (i,i) 右下角的方块是 (j,j).
约束
- 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)
- If i \neq j,那么 (a_i,b_i) \neq (a_j,b_j).
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N M a_1 b_1 c_1 : a_M b_M c_M
输出
打印写整数的可能方式的数量,模数 998244353.
示例输入 1
3 3 1 1 1 3 1 0 2 3 1
示例输出 1
8
例如,以下写入整数的方式满足条件:
101 111 011 111 000 011
示例输入 2
4 5 1 3 1 2 4 0 2 3 1 4 2 1 4 4 1
示例输出 2
32
示例输入 3
3 5 1 3 1 3 3 0 3 1 0 2 3 1 3 2 1
示例输出 3
0
示例输入 4
4 8 1 1 1 1 2 0 3 2 1 1 4 0 2 1 1 1 3 0 3 4 1 4 4 1
示例输出 4
4
示例输入 5
100000 0
示例输出 5
342016343