1935年，两位诺贝尔奖得主的一次会面产生了惊人的成果。著名物理学家薛定谔邀请了著名生理学家巴甫洛夫来参观他关于“盒中猫”的实验。巴甫洛夫带着他的狗一同前来，以便继续他自己的研究，而这两者的结合至少可以说是有趣的。

薛定谔有一排共 $\mathbf{N}$ 个盒子。有些盒子确定有猫，有些确定没有猫，还有些可能含有也可能不含有猫。每个盒子的大小仅够容纳一只猫。每个盒子都配备了一个特殊的量子隧道，如果目标盒子为空，猫可以通过该隧道移动到指定的另一个盒子。这些隧道是单向的。

猫通常温顺安静，除非受到惊吓，否则不会使用隧道。当第三位不速之客按响门铃时，巴甫洛夫的狗立即兴奋起来，开始奔跑和吠叫。狗从 $1$ 号盒子开始，向 $\mathbf{N}$ 号盒子跑去。当狗奔跑时，它会依次经过每一个盒子。当它经过一个装有猫的盒子时，盒子里的猫会受到惊吓。受惊的猫会检查可用的隧道，如果目标盒子是空的，它就会利用隧道逃走。如果目标盒子已被占用，猫则留在原处。同一只猫如果移动到了狗之后会经过的盒子，它可能会被多次惊吓，并且每次受惊时都会以同样的方式行动（每次都只使用新可用的隧道）。

当巴甫洛夫的狗最终停在最后一个盒子旁边时，巴甫洛夫问薛定谔最后一个盒子里是否有猫。薛定谔不愧其名，回答说他不知道。巴甫洛夫注意到，答案可能取决于未知盒子中是否有猫。此外，他还注意到，由于有 $k$ 个未知盒子，因此存在 $2^k$ 种可能的初始配置，每种配置对应未知盒子状态的一种组合。巴甫洛夫告诉薛定谔，他们应该尝试计算这 $2^k$ 种初始配置中有多少种会导致最后一个盒子里有猫。你需要重新进行这项计算。由于输出可能是一个非常大的数字，我们仅要求你输出结果除以质数 $10^9+7$ ($1000000007$) 的余数。

在编写本题的过程中，没有猫、狗或诺贝尔奖得主受到伤害。

输入格式

输入的第一行包含测试用例的数量 $\mathbf{T}$。接下来是 $\mathbf{T}$ 个测试用例，每个测试用例由三行描述。第一行包含一个整数 $\mathbf{N}$，表示薛定谔实验中盒子的数量。盒子按巴甫洛夫的狗经过的顺序编号为 $1$ 到 $\mathbf{N}$。第二行包含一个长度为 $\mathbf{N}$ 的字符串 $\mathbf{S}$。$\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$) 取模。

数据范围

时间限制：10 秒。 内存限制：1 GB。

• $1 \le \mathbf{T} \le 1234$。
• $\mathbf{S}$ 的长度为 $\mathbf{N}$。
• $\mathbf{S}$ 的每个字符均为大写字母 'C'、句点 '.' 或问号 '?'。
• $1 \le \mathbf{B_i} \le \mathbf{N}$，对于所有 $i$。
• $\mathbf{B_i} \neq i$，对于所有 $i$。

子任务 1 (8 分)

• $1 \le \mathbf{N} \le 100$。
• $i - 5 \le \mathbf{B_i} \le i + 5$，对于所有 $i$。（所有隧道均连接到附近的盒子。）

子任务 2 (42 分)

• $1 \le \mathbf{N} \le 5000$。

样例

输入 1

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

输出 1

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$ 的隧道，猫必须从那里开始。只要其他任何盒子里还有另一只猫，盒子 $6$ 就会在盒子 $5$ 里的猫有机会逃脱之前被占用（或保持占用），因此所有这些情况最终都会在最后一个盒子里留下一只猫。正如我们之前所论证的，单只猫是不够的。因此，我们需要计算盒子 $5$ 里有猫且至少还有另一只猫的配置数量。盒子 $5$ 里有猫的配置有 $2^4$ 种，其中只有 $1$ 种没有其他猫，所以答案是 $2^4-1=15$。

在样例 4 中，在 $k$ 个未知盒子的所有 $2^k$ 种存在方式中，最后一个盒子最终都会留下一只猫。