白噪音

• 时间限制：$2$ 秒
• 空间限制：$512\text{ MB}$

题目背景

- 为什么题面里没有鸡煲？

- 那是因为我还在启动。

题目描述

有一个由 $n \times n$ 个边长为 $1$ 的小正方形拼接而成的 $n$ 行 $n$ 列网格。每个小正方形有一种颜色，初始时，所有正方形都是白色。

Ironclad 和 Silent 按某种任意顺序 在网格内涂色若干次。Ironclad 可以选择网格中一个大小为 $1 \times 2$ 的子矩形区域，并将其涂为红色；Silent 可以选择网格中一个大小为 $1\times 3$ 的子矩形区域，并将其涂为绿色。

注意，两人选择的子矩形 可以旋转。换句话说，只要在网格范围内，Ironclad 既可以选择 $1$ 行 $2$ 列的矩形，也可以选择 $2$ 行 $1$ 列的矩形；Silent 同理。此外，两人的涂色可以重复，也就是不限制所选择的子矩形区域必须均为白色。

最终的网格里，每个小正方形 必须 为红色或绿色之一，不包括白色。特别地，有 $k$ 个不同的位置 $(x_i, y_i)$ 有额外限制，要求其颜色必须为 $c_i$，其中 $c_i = 0$ 表示红色，$c_i = 1$ 表示绿色。

你需要帮助 Watcher 评估共有多少种不同的最终网格。两种网格不同，当且仅当存在至少一个相同位置的小正方形颜色不同，而与 Ironclad 和 Silent 的操作顺序及操作位置无关。由于答案可能很大，请对 $998\,244\,353$ 取模。

输入格式

本题包含多组测试数据。

输入第一行包含两个整数 $r, t$，分别表示测试点所在的子任务编号和测试数据组数，其中样例满足 $r=0$。

接下来依次输入每组测试数据，对于每组测试数据：

• 第一行包含两个整数 $n, k$，分别表示网格的大小和额外限制的数量。
• 接下来 $k$ 行中第 $i$ 行包含三个整数 $x_i, y_i, c_i$，分别表示第 $i$ 个额外要求的位置与其要求的颜色。

输出格式

对于每组测试数据，输出一行一个整数，表示答案对 $998\,244\,353$ 取模后的结果。

样例输入

0 9
1 0
2 2
1 1 0
2 2 0
3 2
1 2 1
2 3 1
4 3
1 2 1
2 2 0
3 3 0
6 5
2 2 1
4 1 1
3 2 1
6 3 0
1 1 1
7 0
9 2
5 8 1
4 8 1
14 1
7 3 0
15 3
5 8 1
9 2 0
7 11 0

样例输出

0
1
120
8185
150994940
32990316
191006747
155490384
843115889

样例解释

对于第一组数据，由于两人都无法选出对应大小的矩形，显然不可能得到全部都不为白色的网格。

对于第二组数据，唯一可能的网格是

$$ \begin{bmatrix} 0 &0 \\ 0 &0\end{bmatrix}. $$

数据规模与约定

本题使用捆绑测试。 各个子任务对应的特殊数据范围如下：

• Subtask 1（13 分）：$t \leq 10^4$，$n \leq 3$。
• Subtask 2（11 分）：$t \leq 100$，$n \leq 15$。
• Subtask 3（25 分）：$t \leq 50$，$n \leq 50$。
• Subtask 4（16 分）：$t \leq 10$，$n \leq 3\cdot 10^3$。
• Subtask 5（22 分）：$k = 0$。
• Subtask 6（13 分）：无特殊限制。

对于所有数据，满足：

• $1 \leq t \leq 10^5$；
• $1 \leq n \leq 2\cdot 10^5$，$\sum n \leq 10^6$；
• $0 \leq k \leq \min(10^6, n^2)$，$\sum k \leq 2\cdot 10^6$；
• $1 \leq x_i, y_i \leq n$，$0 \leq c_i \leq 1$；
• 同一组测试数据内的 $(x_i, y_i)$ 互不相同。