本問は 白噪音 の高難易度版である。

問題背景

起動しました

問題概要

$n \times m$ 個の $1 \times 1$ の正方形からなる $n$ 行 $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$ でなければならない（$c_i = 0$ は濃い青色、$c_i = 1$ は薄い青色を表す）。

Architect を助け、条件を満たす最終的なグリッドが何通り存在するかを求めよ。2つのグリッドが異なるとは、少なくとも1つの位置で正方形の色が異なることを指し、Defect と Flaw の操作順序や操作位置には依存しない。答えは非常に大きくなる可能性があるため、$998\,244\,353$ で割った余りを求めよ。

入力形式

本問題は複数のテストケースを含む。

入力の1行目には2つの整数 $r, t$ が与えられる。$r$ はサブタスク番号、$t$ はテストケースの数である。最初のサンプルケースは $r=0$ を満たし、それ以外のケースは対応するサブタスク番号に従う。

各テストケースは以下の形式で与えられる。

• 1行目に3つの整数 $n, m, k$ が与えられる。これらはグリッドの行数、列数、および追加の制約の数である。
• 続く $k$ 行の各行には3つの整数 $x_i, y_i, c_i$ が与えられる。これは $i$ 番目の制約の位置と要求される色を表す。

出力形式

各テストケースについて、条件を満たすグリッドの総数を $998\,244\,353$ で割った余りを1行に出力せよ。

入出力例

入力 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

注記

1番目のデータセットでは、どちらの操作も適用可能な長方形が存在しないため、すべてのマスを青色に塗ることは不可能である。

2番目のデータセットでは、唯一可能なグリッドは以下の通りである。

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

制約

本問題はサブタスク制を採用している。 各サブタスクの制約は以下の通りである。

• サブタスク 1（10 点）：$t \leq 100$、$n, m \leq 15$。
• サブタスク 2（30 点）：$t \leq 10$、$n, m \leq 3\cdot 10^3$。
• サブタスク 3（30 点）：$k = 0$。
• サブタスク 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)$ はすべて異なる。