题目描述

题目译自 BalticOI 2017 Day2「Plus Minus」

物理学家马修正在研究硅基矩形微芯片的量子电动力学。
这一块芯片的大小为 $n \times m$ ，可以分成 $n \times m$ 个电子。
我们都知道电子的状态只有正电 + 和负电 -。
所以，每一个电子都只有一个状态，+ 或者 -。
马修不知道每个电子的状态，但他可以进行 $k$ 次测量。
第 $i$ 次测量他可以得到 $(y_i,x_i)$ 这个电子的状态 $s_i$。
（$s_i$ 是 + 或者 -）
马修还知道，在任意一个 $2\times2$ 的大小的电子块中，拥有 + 的电子和拥有 - 的电子数量相等。
然后他找到了你，想让你给出有多少种电子排列的形式满足测量的结果和上述要求。
答案对 $10^9+7$ 取模。

输入格式

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

输出格式

一行一个整数代表有多少种电子排布的形式。
答案对 $10^9+7$ 取模。

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

2

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

0

数据范围与提示

对于 $100\%$ 的数据，$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$。

详细子任务分值及附加限制如下：

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