CF1615F LEGOndary Grandmaster

在玩腻了蜡笔之后，你决定换成乐高积木！今天，你手上有一条高度为 $1$、长度为 $n$ 的长条，其中某些位置被 $1 \times 1$ 的乐高积木占据。 每秒钟，你可以从长条上移除两个相邻的乐高积木（如果这两个位置都有积木），或者在两个相邻的位置上同时放上两个乐高积木（如果这两个位置都没有积木）。你只能同时在两个相邻的位置上添加或移除乐高积木，否则你胖胖的手指就会出现精度问题。 你想知道你玩乐高到底要花多少时间。你很注重效率，所以对于给定的初始状态和目标状态，你总是会用最少的秒数将初始状态变换为目标状态。如果无法将初始状态变换为目标状态，你就会跳过（即花费 $0$ 秒）。 问题在于，对于某些位置，你不记得那里是否有乐高积木（无论是在初始状态、目标状态，还是两者之一）。对于所有与你的记忆一致的（初始状态，目标状态）对，计算将初始状态变换为目标状态所需的总时间。请输出该值对 $1\,000\,000\,007$（$10^9 + 7$）取模后的结果。

第一行包含一个整数 $t$（$1 \leq t \leq 1000$）——表示测试用例的数量。接下来是 $t$ 组测试数据。 每组测试数据的第一行包含一个整数 $n$（$2 \leq n \leq 2000$）——乐高长条的长度。 第二行包含一个长度为 $n$ 的字符串 $s$，由字符 $0$、$1$ 和 $?$ 组成，表示你对初始状态的记忆： - $1$ 表示该位置一定有乐高积木， - $0$ 表示该位置一定没有乐高积木， - $?$ 表示你不记得该位置的情况。 第三行包含一个长度为 $n$ 的字符串 $t$，由字符 $0$、$1$ 和 $?$ 组成，表示你对目标状态的记忆，格式与初始状态类似。 保证所有测试用例中 $n$ 的总和不超过 $2000$。

对于每个测试用例，输出一个整数，表示答案对 $1\,000\,000\,007$（$10^9 + 7$）取模后的结果。

对于第一个测试用例，$00$ 是唯一可能的初始状态，$11$ 是唯一可能的目标状态。将 $00$ 变为 $11$ 只需一次操作。 对于第二个测试用例，部分可能的（初始状态，目标状态）对如下： - $ (000, 011) $ —— 需要 $1$ 次操作。 - $ (001, 100) $ —— 需要 $2$ 次操作。 - $ (010, 000) $ —— 需要 $0$ 次操作，因为无法实现目标状态。 由 ChatGPT 4.1 翻译