题目描述

题目译自 BalticOI 2017 Day2「Plus Minus」

物理学家马修正在研究硅基矩形微芯片的量子电动力学。
这块芯片的大小为 $n \times m$，可以分成 $n \times m$ 个电子。
每个电子的状态只有 正电（$+$）和 负电（$-$）两种。
马修不知道每个电子的状态，但他可以进行 $k$ 次测量。

第 $i$ 次测量他可以得到位置 $(y_i, x_i)$ 的电子的状态 $s_i$（$s_i$ 是 $+$ 或 $-$）。

马修还知道，在任意一个 $2 \times 2$ 大小的电子块中，拥有 $+$ 的电子和拥有 $-$ 的电子数量相等。
也就是说，每个 $2\times 2$ 子矩阵中，$+$ 和 $-$ 的数量各为 $2$。

请你计算有多少种电子排列方式，满足所有测量结果和上述 $2\times 2$ 约束条件。
答案对 $10^9+7$ 取模。

---

输入格式

第一行三个整数 $n, m, k$，代表芯片的大小和测量次数。
接下来 $k$ 行，每行一个字符 $s_i$ 和两个整数 $y_i, x_i$，代表测量的状态和位置。

---

输出格式

一行一个整数，代表满足条件的电子排布方式数量，对 $10^9+7$ 取模。

---

样例 1

输入

2 4 4
+ 1 1
- 1 2
+ 1 3
- 1 4

输出

2

解释
对于样例 1，有以下 2 种情况：

+-+-
+-+-

和

+-+-
-+-+

---

样例 2

输入

3 3 3
- 2 1
+ 2 3
+ 3 3

输出

0

---

数据范围与提示

• $1 \le n, m \le 10^9$
• $0 \le k \le 10^5$
• $1 \le y_i \le n$
• $1 \le x_i \le m$

子任务：

1. Subtask 1（12 分）：$n, m \le 5$
2. Subtask 2（42 分）：$n, m \le 1000$
3. Subtask 3（46 分）：无特殊限制

---