G.

中文名：花子的艺术
时间限制：2 秒
难度评估：CF 2600
题型标签：组合计数、非交叉匹配、括号结构、模运算

题目描述

二维平面上有一个边长为 $n$ 的正方形，它的四个顶点为 $(0,0),(0,n),(n,n),(n,0)$。

在这个正方形的边上有 $2m$ 个点，每个点被涂成黑色或白色。

艺术家花子想在平面上画 $m$ 条线段，构成一幅“杰作”。按照花子的审美，一幅杰作必须满足：

• 每条线段的两个端点都是给出的 $2m$ 个点，并且一个端点为黑色，另一个端点为白色；
• 每条线段除端点外，不与正方形的边有公共点；
• 任意两条线段没有公共点，特别地，也不能共享端点。

请根据这 $2m$ 个点的信息，求花子能画出的杰作种数。

线段本身互不区分。若两幅图中线段上所有点构成的集合不同，则认为两幅杰作不同；否则认为相同。

答案可能很大，请输出其对素数 $998244353$ 取模的结果。

输入格式

输入只有一个数据集：

n m
x_1 y_1 c_1
...
x_{2m} y_{2m} c_{2m}

其中：

• $1\le n\le 10^9$；
• $1\le m\le 300000$；
• 每个点都在正方形边上，即 $0\le x_i,y_i\le n$，且 $x_i=0$、$x_i=n$、$y_i=0$、$y_i=n$ 中至少一个成立；
• $c_i=0$ 表示黑点，$c_i=1$ 表示白点；
• 任意两点坐标不同。

输出格式

输出花子能画出的杰作数量对 $998244353$ 取模的结果。

样例输入 1

50 6
0 20 1
0 30 0
0 40 0
10 50 1
20 50 1
30 0 0
30 50 0
40 0 0
40 50 1
50 10 1
50 30 1
50 40 0

样例输出 1

2

样例输入 2

50 5
0 0 0
10 0 1
20 0 1
30 0 0
40 0 1
10 50 1
20 50 0
30 50 0
40 50 1
50 50 0

样例输出 2

1

样例输入 3

50 2
0 0 0
50 0 1
50 50 0
0 50 1

样例输出 3

0