Schrödinger와 Pavlov

이 문제 설명에 묘사된 이야기, 모든 이름, 등장인물 및 사건은 허구이다. 실제 인물과의 동일시는 의도된 것이 아니며 그렇게 추론해서도 안 된다.

때는 1935이고, 두 Nobel상 수상자의 만남이 놀라운 결과를 낳고 있다. 유명한 물리학자 Schrödinger는 유명한 생리학자 Pavlov를 초대하여 상자 속 고양이를 이용한 자신의 실험을 보여 주었다. Pavlov는 자신의 연구도 계속하기 위해 개를 데려왔고, 이 조합은 아무리 적게 말해도 흥미로운 결과를 낳았다.

Schrödinger에게는 일렬로 놓인 $\mathbf{N}$개의 상자가 있었다. 어떤 상자에는 고양이가 확실히 들어 있고, 어떤 상자에는 고양이가 확실히 들어 있지 않으며, 어떤 상자에는 고양이가 들어 있을 수도 있고 없을 수도 있다. 각 상자는 고양이 한 마리만 들어갈 만큼만 크다. 또한 각 상자에는 특별한 양자 터널이 설치되어 있어, 목적지 상자가 비어 있다면 상자 안의 고양이가 특정한 다른 상자로 이동할 수 있다. 터널은 한 방향으로만 작동한다.

고양이는 대개 온순하고 조용하며, 놀라지 않는 한 터널을 사용하지 않는다. 예고 없이 찾아온 세 번째 손님이 초인종을 누르자 Pavlov의 개는 즉시 흥분하여 뛰어다니며 짖기 시작한다. 개는 상자 $1$에서 출발해 상자 $\mathbf{N}$을 향해 달린다. 달리는 동안 개는 각 상자 바로 옆을 한 번에 하나씩 지나간다. 고양이가 들어 있는 상자 옆을 지나가면 그 상자 안의 고양이가 놀란다. 놀란 고양이는 이용할 수 있는 터널을 확인하고, 목적지 상자가 비어 있으면 그 터널을 이용해 탈출한다. 목적지 상자가 차 있으면 고양이는 현재 상자에 머문다. 같은 고양이가 개가 나중에 도달할 상자로 이동하면 두 번 이상 놀랄 수 있으며, 놀랄 때마다 같은 방식으로 행동한다(그 이후에는 매번 새롭게 이용할 수 있게 된 터널만 사용한다).

After Pavlov's 개가 마침내 마지막 상자 바로 옆에서 멈추자, Pavlov는 Schrödinger에게 그 마지막 상자에 고양이가 있는지 묻는다. 명성에 걸맞게 Schrödinger는 모른다고 답한다. Pavlov는 그 답이 미지의 상자들에 고양이가 있었는지 여부에 따라 달라질 수 있음을 알아챈다. 또한 미지의 상자가 $k$개이므로 가능한 초기 구성은 $2^k$개이며, 이는 미지의 상자 상태의 각 조합마다 하나씩이라는 점도 알아챈다. Pavlov는 $2^k$개의 초기 구성 중 몇 개가 마지막 상자에 고양이가 있게 되는 결과를 만드는지 계산해 보자고 Schrödinger에게 말한다. 그 계산을 재현해야 한다. 출력값이 매우 큰 수일 수 있으므로, 결과를 소수 $10^9+7$ ($1000000007$)로 나눈 나머지만 출력해야 한다.

이 문제 설명을 만드는 동안 고양이도, 개도, Nobel상 수상자도 다치지 않았다.

제한

시간 제한: 10초. 메모리 제한: 1 GB. $1 \le \mathbf{T} \le 1234$. $\mathbf{S} = \mathbf{N}$의 길이. $\mathbf{S}$의 각 문자는 대문자 'C', 마침표 '.', 물음표 '?' 중 하나이다. 모든 $i$에 대해 $1 \le \mathbf{B_i} \le \mathbf{N}$. 모든 $i$에 대해 $\mathbf{B_i} \neq i$.

테스트 세트 1 (Visible Verdict)

$1 \le \mathbf{N} \le 100$. 모든 $i$에 대해 $i - 5 \le \mathbf{B_i} \le i + 5$. (모든 터널은 가까운 상자들을 연결한다.)

테스트 세트 2 (Hidden Verdict)

$1 \le \mathbf{N} \le 5000$.

입력의 첫 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 각각 정확히 세 줄로 설명되는 $\mathbf{T}$개의 테스트 케이스가 주어진다. 테스트 케이스의 첫 줄에는 Schrödinger의 실험에 사용되는 상자의 수를 나타내는 정수 $\mathbf{N}$ 하나가 주어진다. 상자에는 Pavlov의 개가 지나가는 순서대로 $1$부터 $\mathbf{N}$까지 번호가 매겨져 있다. 테스트 케이스의 둘째 줄에는 $\mathbf{N}$개의 문자로 이루어진 문자열 $\mathbf{S}$ 하나가 주어진다. $\mathbf{S}$의 $i$번째 문자(왼쪽에서 오른쪽으로 셈)는 상자 $i$의 내용물을 나타낸다. 상자에 고양이가 있으면 대문자 'C', 고양이가 없으면 마침표 '.', 고양이가 있는지 알 수 없으면 물음표 '?'이다. 테스트 케이스의 셋째 줄에는 모든 $i$에 대해 상자 $i$에서 나와 상자 $\mathbf{B_i}$로 들어가는 터널이 있음을 나타내는 $\mathbf{N}$개의 정수 $\mathbf{B_1}, \mathbf{B_2}, \dots, \mathbf{B_N}$가 주어진다.

각 테스트 케이스마다 Case #$x$: $y$를 포함하는 한 줄을 출력한다. 여기서 $x$는 테스트 케이스 번호(1부터 시작)이고, $y$는 짖는 소리를 들었음에도 탈출하지 못한 고양이가 마지막 상자에 있게 되는 초기 구성의 수를 소수 $10^9+7$ ($1000000007$)로 나눈 나머지이다.

예제 케이스 #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$의 고양이가 탈출할 기회를 얻기 전에 상자 $6$이 차게 되거나 계속 차 있는 상태로 유지되므로, 그러한 구성은 모두 마지막 상자에 고양이가 있는 상태로 끝난다. 앞서 설명했듯이 고양이 한 마리로는 충분하지 않다. 따라서 상자 $5$에 고양이가 있고 적어도 한 마리의 다른 고양이도 있는 구성의 수를 세어야 한다. 상자 $5$에 고양이가 있는 구성은 $2^4$개이고, 그중 다른 고양이가 없는 구성은 $1$개뿐이므로 답은 $2^4-1=15$이다.

예제 케이스 #4에서는 $k$개의 미지의 상자에 고양이가 존재할 수 있는 $2^k$가지 모든 경우에 마지막 상자에 고양이가 남는다.