题目描述

小蓝正在玩一个涂格子的游戏。他有一个大小为 $n \times m$ 的矩阵，他要给这个矩阵中的每个格子都涂上黑色或白色。小蓝希望最终涂完的格子像国际象棋棋盘一样整齐。具体来说，他希望每一个同色连通块都是矩形，且与上下左右四个异色的矩形相邻（如果存在的话）。下图中第一行的两个涂色方案是合法的，第二行的两个涂色方案是不合法的。

同时小蓝希望 $k$ 个格子具有特定的颜色。其中第 $i$ 个格子位置是 $(x_i, y_i)$，具有特定的颜色 $c_i$。你需要帮助他求出符合要求的合法涂色方案有多少种。因为方案数可能很大，请对 $998244353$ 取模后输出。

输入格式

输入第一行包含三个正整数 $n, m, k$，含义如问题描述所述。

接下来 $k$ 行，每行三个正整数 $x_i, y_i, c_i$，表示格子 $(x_i, y_i)$ 必须被涂成颜色 $c_i$。注意 $x_i, y_i$ 可能重复出现。

输出格式

输出共一个整数，表示答案。

2 2 4
1 1 0
1 2 0
2 1 0
2 2 1

0

3 3 2
1 1 0
2 2 1

8

提示

【评测用例规模与约定】

对于 $20\%$ 的评测用例，$n \times m \leq 20$。

对于 $50\%$ 的评测用例，$n, m, k \leq 5000$。

另存在 $30\%$ 的评测用例，$c_i = 0$。

另存在 $10\%$ 的评测用例，$k = 0$。

对于 $100\%$ 的评测用例，$1 \leq n, m \leq 10^9$，$1 \leq k \leq 3 \times 10^5$，$1 \leq x_i \leq n$，$1 \leq y_i \leq m$，$c_i \in \{0, 1\}$。