题目背景

我已启动

题目描述

$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$으로 나눈 나머지를 출력하세요.

예제

입력 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} $$

데이터 규모와 약정

이 문제는 번들 테스트를 사용합니다. 각 서브태스크의 데이터 범위는 다음과 같습니다.

• 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 \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)$는 모두 서로 다릅니다.