物理学家 Matthew 正在研究硅基矩形微芯片的量子电动力学。该微芯片由一个非常大的 $N \times M$ 电子网格组成。每个电子都有正（上）或负（下）自旋，分别记为 $+$ 和 $-$。

Matthew 不知道所有电子的自旋，但他进行了 $K$ 次测量。在第 $i$ 次测量中，他发现位置 $(y_i, x_i)$ 处的电子具有给定的自旋 $s_i$。他还知道，在每个 $2 \times 2$ 的子网格中，正自旋和负自旋的电子数量相等。他想知道能否根据测量结果恢复每个电子的状态。如果不能，他想知道有多少种可能的状态与他的测量结果一致。出于保密原因，他希望得到对 $10^9 + 7$ 取模后的答案。

CC0 Public Domain, Marian Sigler via Wikimedia Commons

输入格式

第一行包含三个数字 $N$、$M$ 和 $K$：网格的高度、网格的宽度以及测量次数。接下来的 $K$ 行包含一个自旋 $s_i$（$s_i$ 为 $+$ 或 $-$）以及两个数字 $1 \le y_i \le N$ 和 $1 \le x_i \le M$，表示电子的坐标。Matthew 从未在完全相同的位置进行过两次测量。

数据范围

始终满足 $1 \le N, M \le 10^9$ 且 $0 \le K \le 100\,000$。对于子任务，输入满足以下进一步限制：

• 组 1：12 分，$N, M \le 5$
• 组 2：42 分，$N, M \le 1\,000$
• 组 3：46 分，无其他限制。

输出格式

输出与 Matthew 的测量结果一致的有效状态总数，对 $10^9 + 7$ 取模。

说明

样例 1 的解释： 仅有的两个有效网格是 +-+- +-+- 和 +-+- -+-+

样例

输入 1

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

输出 1

2

输入 2

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

输出 2

0