← 返回题目列表

AtCoder · caddi2018_d

F. 方形

中文机器翻译题面 查看原题

分数: 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