플러스 마이너스

물리학자 Matthew는 실리콘 기반 직사각형 마이크로칩의 양자 전기역학을 연구한다. 마이크로칩은 매우 큰 N × M 격자의 전자로 이루어져 있다. 각 전자는 양의 스핀(업) 또는 음의 스핀(다운)을 가지며, 각각 +와 -로 표시한다.

Matthew는 모든 전자의 스핀을 알지는 못하지만, K번의 측정을 수행했다. i번째 측정에서 그는 위치 (yi, xi)의 전자가 주어진 스핀 si를 가진다는 것을 알아냈다. 또한 그는 모든 2 × 2 부분 격자에서 양의 스핀을 가진 전자와 음의 스핀을 가진 전자의 수가 같다는 것을 알고 있다. 그는 측정 결과를 바탕으로 모든 전자의 상태를 알아낼 수 있는지 알고 싶어 한다. 알아낼 수 없다면, 측정 결과와 일치하는 가능한 상태의 수를 알고 싶어 한다. 기밀 사유로 그는 답을 109 + 7로 나눈 나머지로 구하려고 한다.

첫 번째 줄에 격자의 높이, 격자의 너비, 측정 횟수를 나타내는 세 수 N, M, K가 주어진다. 다음 K개의 줄에는 스핀 si와 두 수 1 ≤ yi ≤ N, 1 ≤ xi ≤ M가 주어진다. si는 + 또는 -이고, yi와 xi는 전자의 좌표이다. Matthew는 정확히 같은 위치에서 두 번 측정하지 않았다.

Matthew의 측정 결과와 일치하는 유효한 상태의 총 개수를 109 + 7로 나눈 나머지를 출력한다.

항상 1 ≤ N, M ≤ 109이고 0 ≤ K ≤ 100 000이다. 부분 문제의 입력에는 다음과 같은 추가 제한이 있다.