题目描述

给定两个集合 $S_1$，$S_2$，定义一个长度为 $3n$ 且仅包含 ABC 三种字符的串 $s$ 是好的，当且仅当存在一种方案将 $s$ 划分成 $n$ 个长度为 $3$ 的子序列，且这 $n$ 个子序列都是 ABC，BCA 或 CAB。设 $n$ 个子序列中 ABC 的个数为 $x$，BCA 的个数为 $y$，还要求 $x \in S_1$，$y \in S_2$。

现在有一个长度为 $3n$ 的字符串 $s$，字符串中仅包含 ABC? 四种字符，你需要计算将所有 ? 都分别替换成 ABC 三个字符中的某一个的方案，使得串 $s$ 是好的。

对 $2^{32}$ 取模。

输入格式

本题单个测试点内有多组测试数据。

第一行两个整数 $T$，$id$，表示数据组数和子任务编号，保证 $T = 60$，$id \in [0, 5]$，$id = 0$ 表示是样例。

对于每组数据，第一行一个整数 $n$。

第二行一个长度为 $n+1$ 的 01 串 $s_1$。若 $s_1$ 中第 $i$ 个字符为 $1$，则表示 $S_1$ 中含有 $i-1$ 这个元素，否则不含。第三行以同样的格式刻画 $S_2$。

第四行一个长度为 $3n$ 的字符串 $s$。

对于第 $i$ 组数据，保证 $n = i$。

输出格式

对于每组数据，输出一行一个整数，表示答案。

你可以选择是否回答每组数据，详情见说明部分。

样例

样例输入 1

3 0
1
11
11
ABC
2
101
101
A????C
3
1111
1111
?????????

样例输出 1

1
5
1077

样例解释 1

这个样例不满足 $T = 60$ 的限制，仅为理解题意用。

样例 2,3

见下发文件，分别满足子任务 1,2 的性质。

提示与说明

对于所有数据，保证 $T = 60$。对于每个测试点内的第 $i$ 组测试数据，保证 $n = i$。

测试时开启所有合理的子任务依赖。

对于每个测试点内的每组测试数据，如果你不打算回答这组测试数据，请输出 $-1$。否则输出一个整数表示答案。如果格式不正确，不保证能得到对应的分数。

对于每个测试点，会根据你的输出给出你在这组数据上的评分系数 $p \in [0, 1]$。每个 Subtask 的得分是这个 Subtask 中所有测试点得分系数的最小值乘以这个 Subtask 的分值。

首先，你的程序需要正常结束并且所有你选择回答的答案均正确，否则 $p = 0$。

在此基础上，记 $d$ 为在所有数据中你的程序选择回答的最大的 $n$，则有

$$ p = \begin{cases} \frac{1}{20} d & d \leq 5 \\ \frac{1}{4} + \frac{1}{50} (d - 5) & 5 < d \leq 15 \\ \frac{9}{20} + \frac{3}{200} (d - 15) & 15 < d \leq 35 \\ \frac{3}{4} + \frac{1}{100} (d - 35) & 35 < d \leq 60 \\ \end{cases} $$

$p$ 与 $d$ 的大致图像如下图所示。