题目名来自：晴る - ヨルシカ

题目描述

考虑 $n\times m$ 的网格，现在你需要给每个格子黑白染色。定义一种染色方案合法，当且仅当能够用 $1\times 2$ 的纸条不重叠且不超出网格边界地恰好覆盖所有白色格子，恰好不覆盖所有黑色格子。

现在有 $q$ 个约束 $(x_i,y_i,c_i)$（$1\le i\le q$），其中 $1\le x_i\le n,1\le y_i\le m,c_i\in\{0,1\}$。如果 $c_i=0$，表示格子 $(x_i,y_i)$ 必须染成白色；否则表示格子 $(x_i,y_i)$ 必须被染成黑色。

在此基础上，云浅想让你求出合法染色方案数对 $998244353$ 取模的值。

输入格式

第一行三个正整数 $n,m,q$。

接下来 $q$ 行，第 $i+1$ 三个非负整数 $x_i,y_i,c_i$。

输出格式

输出一行一个非负整数表示合法染色方案数对 $998244353$ 取模的值。

样例 $1$ 输入

2 2 0

样例 $1$ 输出

6

样例 $1$ 解释

用 0 表示这个格子染白，1 表示染黑，则所有合法方案为：

00 10 01 11 00 11
00 10 01 00 11 11

样例 $2$ 输入

2 2 1
1 1 1

样例 $2$ 输出

3

样例 $2$ 解释

用 0 表示这个格子染白，1 表示染黑，则所有合法方案为：

10 11 11
10 00 11

样例 $3$ 输入

3 4 2
1 2 1
2 3 0

样例 $3$ 输出

146

样例 $4$ 输入

5 1145141919 0

样例 $4$ 输出

200647880

测试点约束

对于所有数据：$1\le n\le 7,1\le m\le 10^{18},0\le q\le 300$。保证不存在 $i\neq j$ 使得 $(x_i,y_i)=(x_j,y_j)$。

子任务编号	$n$	$m$	$q$	分值	依赖子任务
Subtask #1	$\le 4$	$\le 5$		$10$	无
Subtask #2		$\le 100$	$=0$	$6$
Subtask #3			$\le 100$	$11$	$1,2$
Subtask #4	$\le 5$	$\le 10^5$		$10$	$1,2,3$
Subtask #5		$\le 10^9$	$=0$	$5$	$2$
Subtask #6			$\le 300$	$13$	$1,2,3,4,5$
Subtask #7	$\le 6$	$\le 10^{18}$	$=0$	$10$	$2,5$
Subtask #8			$\le 300$	$15$	$1,2,3,4,5,6,7$
Subtask #9	$\le 7$			$20$	$1,2,3,4,5,6,7,8$