입자 실험

Albert는 작은 입자를 이용해 연구하고 있다. 각 입자는 양성(+) 전하 또는 음성(-) 전하를 가지며, 실험 기구를 이용해 전하를 바꿀 수 있다. 구체적으로, 크기가 $R \times C$인 격자 모양의 실험 기구를 수직으로 세워 둔다. 각 열의 1행 위에서 입자를 하나씩 발사하고, $R$행 아래에 있는 감지 센서가 입자를 감지한다.

예를 들어 아래 그림에서 $R = 3$, $C = 4$이고, 문자열 $S$ = +-++는 1열부터 4열까지 차례로 양성, 음성, 양성, 양성 입자를 발사함을 뜻한다. 각 입자는 1행부터 $R$행까지 직선으로 지나가며 총 $R$개의 칸을 통과해 가장 아래에 있는 감지 센서에 도달한다.

실험 기구의 일부 $1 \times 1$ 칸에는 미리 설치된 스위치가 있다. 해당 칸을 지나는 입자는 양성에서 음성으로, 또는 음성에서 양성으로 바뀐다. 미리 설치된 스위치의 개수를 $K$라 하고, $i$번째 스위치가 설치된 행과 열의 인덱스를 $X_i$, $Y_i$라 하자.

아래 그림에서는 $K = 3$, $X = [1, 1, 2]$, $Y = [2, 4, 4]$이다. 최종적으로 감지되는 입자는 모두 양성이다. 2열의 입자는 음성에서 양성으로 바뀌고, 4열의 입자는 음성으로 바뀌었다가 다시 양성으로 바뀌기 때문이다.

Albert는 $1 \times 2$ 크기의 스위치(가로로 두 칸을 차지하는 스위치)도 여러 개 가지고 있다. 이를 이용해 모든 입자가 감지 센서에 도달할 때 양성이 되도록 하려고 한다. 이 스위치는 항상 가로로 두 칸을 덮도록 설치해야 하며, 어떤 칸도 두 개 이상의 스위치로 덮이면 안 된다. 위 예제의 경우 다음 세 가지 방법으로 목표를 달성할 수 있다.

• 2행 1-2열과 3행 1-2열에 스위치를 각각 설치한다.
• 2행 2-3열과 3행 2-3열에 스위치를 각각 설치한다.
• 스위치를 추가로 설치하지 않는다.

이 예에서 편의상 두 스위치를 AA, BB로 적었지만, 스위치는 모두 같은 모양이라 서로 구별되지 않는다.

또 다른 예로, $R = 2$, $C = 4$, $K = 0$인 경우 Albert는 총 다섯 가지 방법으로 목표를 달성할 수 있다.

입력으로 $R$, $C$, $K$, $X$, $Y$가 주어질 때, $1 \times 2$ 스위치를 실험 기구에 추가하여 모든 입자가 양성인 채로 감지 센서에 도달하게 하는 방법이 몇 가지인지 구하라. 답이 매우 커질 수 있으므로 $10^9 + 7$로 나눈 나머지를 출력한다.

입력 첫 줄에 테스트 케이스의 수 $T$가 주어진다.

각 테스트 케이스의 첫 줄에는 $R$, $C$, $K$가 공백으로 구분되어 주어진다. 둘째 줄에는 처음 실험 기구에서 발사되는 입자의 전하를 나타내는 길이 $C$인 문자열 $S$가 주어진다. 이어서 $K$줄에 걸쳐 각 줄마다 $X_i$, $Y_i$가 공백으로 구분되어 주어진다.

각 테스트 케이스의 정답을 한 줄에 하나씩 출력한다.

• $1 \le T \le 5$
• $1 \le R \le 500$
• $1 \le C \le 10$
• $0 \le K \le \min(R \cdot C, 1000)$
• 모든 $i$($1 \le i \le K$)에 대하여 $1 \le X_i \le R$이고 $1 \le Y_i \le C$이다.
• 각 테스트 케이스 내에서 $(X_i, Y_i)$ 정수쌍은 고유하다. 즉, 같은 칸이 두 번 이상 입력으로 주어지지 않는다.
• Albert는 충분히 많은 스위치를 갖고 있으므로 얼마든지 사용할 수 있다고 가정한다.