Electron Arrangement

We are given a chip of size \(n \times m\) which is divided into \(n \times m\) electrons. Each electron can be in one of two states: positive (+) or negative (-). Matthew does not know the state of every electron but he can perform \(k\) measurements. In the \(i\)th measurement he learns the state \(s_i\) (either + or -) at cell \((y_i, x_i)\) (1-indexed).

In addition, it is known that in every contiguous \(2\times2\) block of electrons the number of positive and negative electrons are equal. In other words, if we assign a value \(+1\) to + and \(-1\) to -, then for every \(2\times2\) block the condition \[ v_{i,j}+v_{i,j+1}+v_{i+1,j}+v_{i+1,j+1}=0 \] holds (which forces exactly two positives and two negatives in that block).

Your task is to count the number of arrangements of electron states that satisfy both the measurements and the 2x2 block condition. Since the answer can be large, output it modulo \(10^9+7\).

inputFormat

The first line contains three integers \(n\), \(m\) and \(k\) (the number of rows, columns and measurements respectively). Each of the next \(k\) lines contains a measurement in the format \(y\; x\; s\), where \(1 \le y \le n\), \(1 \le x \le m\), and \(s\) is either + or -.

Note: If \(n=1\) or \(m=1\) then there is no \(2\times2\) block and the condition is ignored.

outputFormat

Output one integer: the number of valid electron state arrangements modulo \(10^9+7\).

sample

2 2 0

6