You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

1935 年的秋天，薛定谔邀请巴甫洛夫观看他在盒子里对猫的实验。巴甫洛夫带着他的狗来了。

薛定谔有 $n$ 个盒子摆成一排。有些盒子肯定包含猫，有些盒子肯定不包含猫，有些盒子可能包含也可能不包含猫。每个盒子只够容纳一只猫。每个盒子 $i$ 有一个单向隧道 $i \to b_i$。如果盒子 $b_i$ 为空，盒子 $i$ 的猫可以移动到盒子 $b_i$。

当一个不速之客按响门铃时，巴甫洛夫的狗立即兴奋起来，开始奔跑和吠叫。狗从盒子 $1$ 开始，奔向盒子 $n$，依次从每个盒子旁边经过。当狗经过一个装有猫的盒子旁边时，那个盒子里的猫会受到惊吓。受惊的猫会检查该盒子的隧道，如果隧道的目标盒子是空的，则用隧道来逃跑，否则猫会留在其当前盒子里。注意，如果同一只猫移动到狗之后将要到达的盒子中，它可能会受到不止一次的惊吓。

设有 $k$ 个未知的盒子，求 $2^k$ 种每个盒子是否包含猫的初始配置中，有多少种将导致最终最后一个盒子中有一只猫。

输入格式

从 experiment.in 文件读入数据。

第一行一个整数 $T$，表示数据组数。

接下来 $T$ 组数据，每组数据格式如下：

• 第一行一个整数 $n$。
• 第二行一个长为 $n$ 的字符串 $s$，只包含字符 $\texttt{C.?}$。若 $s_i$ 为 $\texttt{C}$ 则盒子 $i$ 包含猫，若 $s_i$ 为 $\texttt{.}$ 则盒子 $i$ 不包含猫，若 $s_i$ 为 $\texttt{?}$ 则盒子 $i$ 可能包含也可能不包含猫。
• 第三行 $n$ 个整数 $b_1, b_2, \cdots, b_n$。保证 $1 \leq b_i \leq n$ 且 $b_i \neq i$。

输出格式

输出到 experiment.out 文件。

$T$ 行，每行一个整数，表示该组数据的答案对 $10^9 + 7$ 取模的值。

样例

6
4
??.C
2 3 1 3
4
????
2 3 1 3
6
?.????
6 6 6 6 6 5
10
????????CC
2 3 4 5 6 7 8 9 10 9
10
C???.?C.??
9 1 8 3 9 3 5 3 1 9
10
??????????
7 10 1 6 2 2 8 3 5 1

1
2
15
256
24
480

说明/提示

对于所有数据，保证 $1 \leq T \leq 1234, 2 \leq n \leq 5000$。