시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB12101083.333%

문제

Matthew the physicist studies the quantum electro-dynamics of a silicon-based rectangular microchip. The microchip consists of a very large N ×M grid of electrons. Each electron has either positive (up) or negative (down) spin, denoted by + and − respectively.

Matthew does not know the spin of all the electrons, but he has done K measurements. In the i-th measurement, he discovered that the electron at position (yi, xi) has a given spin si. He also knows that in each 2 × 2 subgrid, there are equally many electrons with positive and negative spin. He wants to know whether he can recover the state of every electron based on his measurements. If not, he would like to know how many possible states are consistent with his measurements. For classified reasons, he wants the answer modulo 109 + 7.

입력

The first line contain three numbers N, M and K: the height of the grid, the width of the grid and the number of measurements. The next K lines contain a spin si where si is either + or -, and two numbers 1 ≤ yi ≤ N and 1 ≤ xi ≤ M – the coordinates of the electron. Matthew never did two measurments at the exact same location.

출력

Output the total number of valid states consistent with Matthew’ measurements modulo 109 + 7.

제한

We always have 1 ≤ N, M ≤ 109 and 0 ≤ K ≤ 100 000. For subcases, the inputs have these further restrictions.

서브태스크

번호배점제한
112

N, M ≤ 5

242

N, M ≤ 1 000

346

No further restrictions.

예제 입력 1

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

예제 출력 1

2

The only two valid grids are

+-+-
+-+-

and

+-+-
-+-+

예제 입력 2

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

예제 출력 2

0

채점 및 기타 정보

  • 예제는 채점하지 않는다.