P6576 [BalticOI 2017] Plus Minus

Physicist Matthew is studying the quantum electrodynamics of silicon-based rectangular microchips.

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$.

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

#### 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](https://boi.cses.fi/files/boi2017_day2.pdf) T3 Plus Minus.** Translator: @[一只书虫仔](https://www.luogu.com.cn/user/114914)。 Translated by ChatGPT 5