| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1.5 초 | 512 MB | 39 | 29 | 25 | 73.529% |
Albert는 작은 입자를 이용한 연구를 하고 있다. 각 입자는 양성(+) 전하를 갖거나 음성(-) 전하를 갖는데, 실험 기구를 이용하여 이를 바꿀 수도 있다. 구체적으로, 크기가 $R \times C$ 인 격자 모양의 실험 기구를 이용하여 실험을 진행하는데, 실험 기구를 수직으로 세워둔 후 각 열의 1행 위에서 입자를 하나 발사하여 $R$행 아래에서 감지하는 방법으로 실험을 한다.
예를 들어 아래 그림의 경우 $R$ = 3, $C$ = 4 이며 문자열 $S$ = "+-++"는 각 열에 양성/음성/양성/양성의 입자를 순서대로 발사함을 알려준다. 각 입자는 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$ 크기의 (좌우로 두 칸을 차지하는) 스위치도 여럿 가지고 있는데, 이를 활용하여 모든 입자가 감지 센서에 도달할 때 양성이 되도록 하고 싶다. 단, 이 스위치의 특성상 언제나 가로로 두 칸을 덮도록 설치해야 하고, 임의의 칸이 두 개 이상의 스위치로 덮이면 안 된다. 위 예제의 경우 아래 세 가지 다른 방법으로 이를 달성할 수 있다.
다른 예로, 아래 그림처럼 $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$값이 공백으로 구분되어 주어진다.
각 테스트 케이스의 정답을 각 줄에 공백으로 구분하여 출력한다.
5 3 4 3 +-++ 1 2 1 4 2 4 2 4 0 ++++ 1 6 0 ++--++ 1 6 0 +++++- 3 6 3 +-+--+ 1 1 2 3 2 5
3 5 1 0 8
예제 1-1: 본문에서 다루었다.
예제 1-2: 본문에서 다루었다.
예제 1-3: 1행 3-4열에 스위치를 하나 설치한다.
예제 1-4: 모든 입자가 양성인채로 감지 센서에 도달할 방법은 없다.
예제 1-5: 추가 설명 없음.
1 16 4 0 ++++
78867036
예제 2-1: 정답이 매우 커질 수 있으므로 109+7로 나눈 나머지를 출력해야한다.