Page not loading? Try clicking here.
Placeholder

#8162
Subtask

전자 격자 1s 512MB

Problems

매튜는 실리콘 기반의 N \times M 크기의 전자 격자를 연구하고 있다. 각 전자는 다음과 같은 두 가지 스핀 중 하나를 가진다:

  • + (positive): 위쪽 스핀

  • - (negative): 아래쪽 스핀

매튜는 다음 정보를 알고 있다:

  1. 일부 전자의 스핀 정보: K개의 측정을 통해 몇몇 전자의 스핀을 알고 있다.

  2. 2×2 서브그리드 조건: 모든 2×2 크기의 서브그리드에는 양의 스핀과 음의 스핀이 정확히 2개씩 있어야 한다.

매튜는 다음을 해결하려고 한다:

  1. 모든 전자의 스핀 상태를 유일하게 결정할 수 있는가?

  2. 그렇지 않다면, 그의 측정 결과와 위 조건을 만족하는 가능한 격자 상태의 개수를 10^9 + 7로 나눈 나머지를 계산해야 한다.


Input

  • 첫 번째 줄: 세 개의 정수 N, M, K

    • N: 격자의 높이

    • M: 격자의 너비

    • K: 측정된 전자의 수

  • 다음 K개의 줄:

    • 각 줄은 스핀 s_i​ (+ 또는 -)와 두 정수 y_i, x_i​ (1 \leq y_i \leq N, 1 \leq x_i \leq M)를 포함한다.


Output

유효 상태의 총 개수를 10^9 + 7로 나눈 나머지를 출력한다.


Subtask

# Score Condition
#112

N, M ≤ 5

#242

N, M ≤ 1 000

#346

추가 제약 조건 없음


Example #1

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

가능한 전자 격자는 아래와 같은 두 형태이다.

+-+-
+-+-
+-+-
-+-+

Example #2

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


Source

BOI 2017 F번

You must sign in to write code.