페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#10446

슈뢰딩거와 파블로프 10s 1024MB

문제

이 문제 설명에 등장하는 이야기, 이름, 인물, 사건은 모두 허구이다. 실제 인물과의 동일시를 의도하지 않으며, 그렇게 추론해서도 안 된다.

1935년, 두 명의 노벨상 수상자가 만나 놀라운 결과를 만들어 내고 있다. 유명한 물리학자 슈뢰딩거(Schrödinger)는 유명한 생리학자 파블로프(Pavlov)를 초대해 상자 속 고양이 실험을 보여 주었다. 파블로프는 자신의 연구를 계속하기 위해 개도 함께 데려왔고, 이 조합은 말 그대로 흥미로웠다.

슈뢰딩거는 \mathbf{N}개의 상자를 일렬로 놓아 두었다. 어떤 상자에는 고양이가 확실히 있고, 어떤 상자에는 확실히 없으며, 어떤 상자에는 있을 수도 없을 수도 있다. 각 상자는 고양이 한 마리만 들어갈 수 있을 만큼만 크다. 또한 각 상자에는 특수한 양자 터널이 달려 있어, 목적지 상자가 비어 있다면 상자 안의 고양이가 특정 다른 상자로 이동할 수 있다. 터널은 한 방향으로만 작동한다.

고양이들은 보통 온순하고 조용해서, 깜짝 놀라지 않으면 터널을 사용하지 않는다. 그런데 초대받지 않은 세 번째 손님이 벨을 누르자, 파블로프의 개는 즉시 흥분해 달리고 짖기 시작한다. 개는 1번 상자에서 출발해 \mathbf{N}번 상자 쪽으로 달려간다. 개가 달리는 동안, 각 상자를 하나씩 지나가며 바로 옆을 스친다. 고양이가 들어 있는 상자 옆을 지나갈 때마다, 그 상자 안의 고양이는 깜짝 놀란다. 깜짝 놀란 고양이는 가능한 터널을 확인하고, 목적지 상자가 비어 있다면 그 터널을 이용해 도망친다. 목적지 상자가 차 있다면, 고양이는 현재 상자에 그대로 남는다. 고양이가 개가 나중에 지나갈 상자로 이동했다면, 같은 고양이가 여러 번 놀랄 수도 있으며, 놀랄 때마다 같은 방식으로 행동한다 (매번 그 시점에 사용할 수 있는 터널 하나만을 고려한다).

Illustration of Sample Case #1 with a dog shown walking from left to right.

파블로프의 개가 마침내 마지막 상자 옆에서 멈춘 뒤, 파블로프는 슈뢰딩거에게 마지막 상자에 고양이가 있는지 묻는다. 슈뢰딩거는 자신의 명성에 걸맞게, 모른다고 답한다. 파블로프는 답이 미지의 상자들에 실제로 고양이가 있었는지에 따라 달라질 수 있음을 알아차렸다. 또한 미지의 상자가 k개라면, 각 상자의 상태 조합마다 하나씩 총 2^k개의 초기 구성(initial configuration)이 가능함도 알아차렸다. 파블로프는 슈뢰딩거에게, 이 2^k개의 초기 구성 중 마지막 상자에 고양이가 남게 되는 경우가 몇 개인지 계산해 보자고 제안한다. 당신의 과제는 그 계산을 재현하는 것이다. 결과는 매우 클 수 있으므로, 소수 10^9+7(1000000007)로 나눈 나머지만 출력하면 된다.

이 문제 설명을 만드는 동안 고양이도, 개도, 노벨상 수상자도 피해를 입지 않았다.


입력

입력의 첫 줄에는 테스트 케이스 수 \mathbf{T}가 주어진다. \mathbf{T}개의 테스트 케이스가 이어지며, 각 테스트 케이스는 정확히 3줄로 주어진다. 테스트 케이스의 첫 줄에는 정수 \mathbf{N}이 주어지며, 이는 슈뢰딩거의 실험에 있는 상자의 수이다. 상자는 파블로프의 개가 지나가는 순서대로 1번부터 \mathbf{N}번까지 번호가 매겨져 있다. 둘째 줄에는 길이가 \mathbf{N}인 문자열 \mathbf{S}가 주어진다. 왼쪽에서부터 i번째 문자는 i번 상자의 내용을 나타내며, 대문자 C면 고양이가 있고, 마침표 .면 고양이가 없고, 물음표 ?면 고양이가 있는지 없는지 알 수 없다는 뜻이다. 셋째 줄에는 \mathbf{N}개의 정수 \mathbf{B_1}, \mathbf{B_2}, \dots, \mathbf{B_N}가 주어진다. 이는 모든 i에 대해 i번 상자에서 \mathbf{B_i}번 상자로 향하는 터널이 있음을 의미한다.


출력

각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력하라. 여기서 x는 (1부터 시작하는) 테스트 케이스 번호이고, y는 마지막 상자에 고양이가 들어 있으며 짖는 소리를 듣고도 도망치지 못하게 되는 초기 구성의 개수이다. 이 값은 소수 10^9+7(1000000007)로 나눈 나머지로 출력하라.


예제 

4
4
??.C
2 3 1 3
4
????
2 3 1 3
6
?.????
6 6 6 6 6 5
34
????????????????????????????????CC
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 33
Case #1: 1
Case #2: 2
Case #3: 15
Case #4: 294967268
샘플 케이스 #1은 문제 설명에 나온 그림에 표시되어 있다. 가능한 배치는 4가지다: ...C: 첫 3개의 상자에는 고양이가 없으므로 개는 아무 변화 없이 지나간다. 마지막 상자에 도착하면 고양이가 소리를 듣고 3번 상자로 도망가므로, 이 경우 마지막 상자에는 고양이가 없다. C..C: 1번 상자 근처에서 개가 짖으면 고양이가 놀라 터널을 통해 비어 있는 2번 상자로 이동한다. 그 다음 2번 상자 근처에서 다시 짖으면 같은 고양이가 놀라 3번 상자로 이동한다. 그리고 3번 상자 근처에서 짖으면 고양이가 소리를 듣고 1번 상자로 돌아간다. 따라서 개가 4번 상자에 도착해 다른 고양이가 소리를 들을 때, 3번 상자가 비어 있으므로 고양이가 도망가서 마지막 상자는 비게 된다. .C.C: 이 경우는 이전 경우와 매우 비슷하다. 개가 첫 번째 상자를 지나도 아무 일도 일어나지 않으므로 상태가 동일하고, 최종 결과도 같다: 마지막 상자는 비어 있다. CC.C: 이 경우에는 첫 번째 상자의 고양이가 개 소리를 들어도 도망갈 수 없어 1번 상자에 남는다. 그 다음 2번 상자의 고양이가 놀라 3번 상자로 이동하여 상태가 C.CC가 된다. 개가 3번 상자에 도착하면 그곳의 고양이는 1번 상자로 도망갈 수 없으므로 상태는 그대로다. 마지막으로 개가 마지막 상자에 도착하면 그곳의 고양이는 이번에는 3번 상자가 차 있어서 도망갈 수 없다. 따라서 이 경우에는 개가 이동을 끝낸 뒤 마지막 상자에 고양이가 남는다. 4가지 중 마지막 경우 1가지만 마지막 상자에 고양이가 남으므로 답은 1이다. 샘플 케이스 #2에서는 터널 구성이 샘플 케이스 #1과 같다. 마지막 상자에서 끝나는 터널이 없으므로, 처음에 마지막 상자에 고양이가 없는 배치는 결국에도 그곳에 고양이가 남지 않는다. 따라서 그것들은 셀 필요가 없다. 그러면 추가로 8개의 배치가 있다. 샘플 케이스 #1에서 고려한 4개 중 마지막 상자에 고양이가 남는 것은 1개뿐이다. 나머지 4개의 배치는 ..CC, C.CC, .CCC, CCCC이다. 이 추가 4개 중 마지막에 나열한 경우에만 마지막 상자에 고양이가 남으므로 총 2가지가 된다. 샘플 케이스 #3에서는, 개가 마지막 상자 근처에서 짖은 뒤에도 고양이가 마지막 상자에 남으려면 그 상자와 5번 상자가 모두 그때 점유되어 있어야 한다(그렇지 않으면 마지막 상자에 고양이가 없거나 5번 상자로 도망간다). 5번 상자로 들어가는 터널이 없으므로 고양이는 처음부터 5번 상자에 있어야 한다. 다른 어느 상자에든 또 한 마리가 있으면, 5번 상자의 고양이가 도망갈 기회를 갖기 전에 6번 상자가 (또는 계속) 점유되므로 그런 배치들은 모두 마지막 상자에 고양이가 남는다. 앞에서 논의했듯이 고양이 한 마리만으로는 부족하다. 따라서 5번 상자에 고양이가 있고 다른 상자에 최소 한 마리가 더 있는 배치 수를 세면 된다. 5번 상자에 고양이가 있는 배치는 2^4가지이고, 그중 다른 고양이가 없는 경우는 1가지뿐이므로 답은 2^4-1=15이다. 샘플 케이스 #4에서는 미정인 k개의 상자에 고양이가 있을 수 있는 모든 2^k가지 경우에서 마지막 상자에 고양이가 남는다.

출처

GCJ 2022wf D

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