SP26928 CROSSOVER - The Crossover

今天，科学家 Aftab 在染色体交叉领域取得了一项突破性的发现！ 在详细讲解之前，我们先来了解一些定义。根据 Holland 的约定，基因可以用 0 或 1 表示，染色体则是由基因组成的字符串。在交叉过程中，两个父代染色体会在相同的位置被切割成四个非空的部分，然后这些部分组合生成两个后代。例如，设 A 和 B 是两条长度为 $N$ 的父代染色体。在某个位置 $X$ 处切割后，我们可以得到四个部分 $L_A$、$R_A$、$L_B$、$R_B$。其中，$L_A$ 由 $A[0, \ldots, X]$ 组成，$R_A$ 由 $A[X+1, \ldots, N-1]$ 组成，而 $L_B$ 和 $R_B$ 同理。经过交叉后，我们便得到两个后代 $O_1 = L_A + R_B$ 和 $O_2 = L_B + R_A$，这里的‘+’表示字符串的连接。 Aftab 认为，在 $O_1$ 和 $O_2$ 中，适应度最高的后代就是数值更大的那一个。这里，染色体的数值是按照位串计算的，最左边的位是最高位（即最显著位，MSB），而最右边的位是最低位（即最不显著位，LSB）。 虽然 Aftab 是卓越的遗传学研究者，但他不擅长处理大规模的染色体数据。因此他请求你的帮助。你将获得两条长度为 $N$ 的染色体，并需要输出经过交叉后，适应度最高的后代的十进制值，并对结果取模 $10^9 + 7$。

输入以一个整数 **T (≤30)** 开始，表示测试用例的数量。每个测试用例包含两行字符串，每行长度为 **N (2 ≤ N ≤ 100000)**。字符串仅包含字符 0 和 1。

对于每个测试用例，输出一行，格式为“Case #x: y”，其中 x 是测试用例编号，y 是交叉后适应度最高的后代的十进制值并对结果取模 $10^9 + 7$。 **本翻译由 AI 自动生成**