Placeholder

#8162
서브태스크

전자 격자 1초 512MB

문제

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

  • + (positive): 위쪽 스핀

  • - (negative): 아래쪽 스핀

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

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

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

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

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

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


입력

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

    • NN: 격자의 높이

    • MM: 격자의 너비

    • KK: 측정된 전자의 수

  • 다음 KK개의 줄:

    • 각 줄은 스핀 sis_i​ (+++ 또는 −-−)와 두 정수 yi,xiy_i, x_i​ (1≤yi≤N1 \leq y_i \leq N, 1≤xi≤M1 \leq x_i \leq M)를 포함한다.


출력

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


부분문제

번호 점수 조건
#112점

N,M≤5N, M ≤ 5

#242점

N,M≤1000N, M ≤ 1 000

#346점

추가 제약 조건 없음


예제1

입력
2 4 4
+ 1 1
- 1 2
+ 1 3
- 1 4
출력
2

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

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

예제2

입력
3 3 3
- 2 1
+ 2 3
+ 3 3
출력
0


출처

BOI 2017 F번


역링크 공식 문제집만

로그인해야 코드를 작성할 수 있어요.