Description

The chip has size $n \times m$, and it can be divided into $n \times m$ electrons.
As we all know, an electron can only be in one of two states: positive + or negative -.
So, each electron has exactly one state, either + or -.

Matthew does not know the state of each electron, but he can perform $k$ measurements.
In the $i$-th measurement, he can obtain the state $s_i$ of the electron at position $(y_i, x_i)$.
($s_i$ is + or -.)

Matthew also knows that in any $2 \times 2$ block of electrons, the number of + electrons equals the number of - electrons.
Then he came to you and asked you to determine how many electron arrangements satisfy the measurement results and the requirement above.
Output the answer modulo $10^9+7$.

Input Format

The first line contains three integers $n, m, k$, representing the chip size and the number of measurements.
The next $k$ lines each contain a character $s_i$ (the state observed in this measurement) and the integers $y_i, x_i$ (the measured position).

Output Format

Output one integer: the number of valid electron arrangements.
Output the answer modulo $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

Hint

Sample Explanation

For sample $1$, there are the following $2$ cases:

+-+-
+-+-

and

+-+-
-+-+

Constraints

This problem uses bundled testdata.

• Subtask 1 (12 pts): $n, m \le 5$.
• Subtask 2 (42 pts): $n, m \le 1000$.
• Subtask 3 (46 pts): no special constraints.

For $100\%$ of the testdata, $1 \le n, m \le 10^9$, $0 \le k \le 10^5$, $1 \le y_i \le n$, and $1 \le x_i \le m$.

Note

Translated from BOI 2017 D2 T3 Plus Minus.
Translator: @一只书虫仔。

Translated by ChatGPT 5