该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

Shiro 与 Kuro 最近喜欢上了涂格子。

现在他们拥有了一个大小为 $n \times m$ 的网格图，一开始每个格子都没有颜色。

接下来他们会给整个网格图中的每一个格子都涂上黑色或者白色，但他们同时又希望每一块相同颜色的连通块在整个网格图当中都是以一个矩形样式呈现。

如下图，第一行的三种涂法是合法的，第二行的三种涂法是不合法的。

除此之外，网格图中还有 $k$ 个特殊的格子，这些格子最终所涂的颜色应该是固定的。其中第 $i$ 个格子出现在 $(x_i, y_i)$ 位置，应该涂上 $c_i$ 这个颜色。

请你帮他们找出总共有多少种符合条件的涂色方案，并对 $998244353$ 取模。

输入格式

第一行包含三个正整数 $n, m, k$，表示网格的行数、列数以及特殊格子的数量。

接下来 $k$ 行，第 $i$ 行包含三个正整数 $x_i, y_i, c_i$，表示坐标为 $(x_i, y_i)$ 的格子应该被涂为 $c_i$ 颜色。其中 $c_i = 0$ 表示白色，$c_i = 1$ 表示黑色。

输出格式

一个整数，表示方案数。答案可能很大，请输出对 $998244353$ 取模后的结果。

样例 1

输入

2 2 2
1 2 1
2 1 0

输出

2

样例 2

输入

4 5 5
1 4 1
2 2 0
4 1 1
3 5 0
4 5 0

输出

8

样例 3

输入

123 321 3
100 200 1
120 200 0
100 150 1

输出

131616716

样例 4

见下发文件 grid4.in/out.

数据范围

对于 $20\%$ 的数据，保证 $n, m \le 6,\ k \le 10$ 。

对于 $50\%$ 的数据，保证 $n, m \le 5\,000,\ k \le 5\,000$

对于 $100\%$ 的数据，保证 $1 \le n, m \le 10^9, \ 0 \le k \le 3 \times 10^5, \ 1 \le x_i \le n ,\ 1 \le y_i \le m$ 。