题目背景

我已启动

题目描述

$n \times m$ 크기의 격자가 있으며, 각 칸은 처음에 흰색입니다.

Defect와 Flaw는 임의의 순서로 격자에 여러 번 색을 칠합니다. Defect는 $1 \times 2$ 크기의 직사각형 영역을 선택하여 짙은 파란색으로 칠할 수 있고, Flaw는 $1 \times 3$ 크기의 직사각형 영역을 선택하여 옅은 파란색으로 칠할 수 있습니다.

두 사람 모두 선택한 직사각형을 회전할 수 있습니다. 즉, 격자 범위 내라면 Defect는 $1 \times 2$ 또는 $2 \times 1$ 직사각형을 선택할 수 있으며, Flaw도 마찬가지입니다. 또한, 이미 칠해진 칸을 다시 칠할 수 있습니다.

최종 격자의 모든 칸은 반드시 짙은 파란색 또는 옅은 파란색 중 하나여야 하며, 흰색 칸은 존재할 수 없습니다. 특히, $k$개의 위치 $(x_i, y_i)$에 대해 색상 제한이 주어지며, $c_i = 0$이면 짙은 파란색, $c_i = 1$이면 옅은 파란색이어야 합니다.

Architect를 도와 가능한 서로 다른 최종 격자의 개수를 구하세요. 두 격자가 다르다는 것은 적어도 한 칸의 색상이 다름을 의미하며, Defect와 Flaw의 조작 순서나 위치와는 무관합니다. 결과값이 클 수 있으므로 $998\,244\,353$으로 나눈 나머지를 출력하세요.

입력 형식

이 문제는 여러 개의 테스트 케이스를 포함합니다.

첫 번째 줄에는 테스트 케이스가 속한 서브태스크 번호 $r$과 테스트 케이스의 개수 $t$가 주어집니다. 첫 번째 예제는 $r=0$을 만족하며, 나머지 예제는 해당 서브태스크 번호를 따릅니다.

각 테스트 케이스의 형식은 다음과 같습니다:

• 첫 번째 줄에는 격자의 행 수 $n$, 열 수 $m$, 추가 제한의 개수 $k$가 주어집니다.
• 이어지는 $k$개의 줄에는 각 제한의 위치 $x_i, y_i$와 색상 $c_i$가 주어집니다.

输出格式

각 테스트 케이스마다 가능한 서로 다른 격자의 개수를 $998\,244\,353$으로 나눈 나머지를 출력하세요.

样例解释

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

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

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

数据规模与约定

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

• Subtask 1（10 分）：$t \leq 100$，$n, m \leq 15$。
• Subtask 2（30 分）：$t \leq 10$，$n, m \leq 3\cdot 10^3$。
• Subtask 3（30 分）：$k = 0$。
• Subtask 4（30 分）：无特殊限制。

对于所有数据，满足：

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

예제

입력 1

0 8
1 1 0
2 2 2
1 1 0
2 2 0
3 3 2
1 2 1
2 3 1
4 4 3
1 2 1
2 2 0
3 3 0
2 6 2
2 5 1
1 3 0
7 4 4
1 3 1
2 2 1
6 4 1
7 4 0
14 13 0
5 19 0

출력 1

0
1
120
8185
150994940
32990316
191006747
155490384
843115889

참고

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

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

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