CF1615F.LEGOndary Grandmaster

After getting bored by playing with crayons, you decided to switch to Legos! Today, you're working with a long strip, with height $1$ and length $n$, some positions of which are occupied by $1$ by $1$ Lego pieces.

In one second, you can either remove two adjacent Lego pieces from the strip (if both are present), or add two Lego pieces to adjacent positions (if both are absent). You can only add or remove Lego's at two adjacent positions at the same time, as otherwise your chubby fingers run into precision issues.

You want to know exactly how much time you'll spend playing with Legos. You value efficiency, so given some starting state and some ending state, you'll always spend the least number of seconds to transform the starting state into the ending state. If it's impossible to transform the starting state into the ending state, you just skip it (so you spend $0$ seconds).

The issue is that, for some positions, you don't remember whether there were Legos there or not (in either the starting state, the ending state, or both). Over all pairs of (starting state, ending state) that are consistent with your memory, find the total amount of time it will take to transform the starting state to the ending state. Print this value modulo $1\,000\,000\,007$ ($10^9 + 7$).

玩腻了蜡笔后，你决定改玩乐高积木！今天，你正在处理一条高度为 $1$、长度为 $n$ 的长条形底板，其上某些位置已放置了 $1 \times 1$ 的乐高积木块。

每秒钟，你可以执行以下两种操作之一：

• 若两个相邻位置上均已有乐高积木块，则可将它们同时移除；
• 若两个相邻位置上均为空，则可将两块乐高积木同时添加到这两个位置。

你只能对两个相邻位置同时进行添加或移除操作，否则你的胖手指会因精度问题而无法完成操作。

你想精确知道玩乐高积木总共要花多少时间。你崇尚效率，因此在给定初始状态和目标状态的前提下，你总会选择将初始状态变换为目标状态所需的最少秒数。若该变换不可能实现，你便直接跳过（即花费 $0$ 秒）。

但问题在于：对于某些位置，你不记得初始状态和/或目标状态中这些位置上是否有乐高积木（即这些位置的状态是未知的）。
请考虑所有满足你记忆约束的（初始状态，目标状态）组合，并计算将每个初始状态变换为目标状态所需时间的总和。请将该总和对 $1\,000\,000\,007$（即 $10^9 + 7$）取模后输出。

The first line contains one integer $t$ ($1 \leq t \leq 1000$) — the number of test cases. Then $t$ cases follow.

The first line of each test case contains one integer $n$ ($2 \leq n \leq 2000$) — the size of the Lego strip.

The second line of each test case contains a string $s$ of length $n$, consisting of the characters 0, 1, and ? — your memory of the starting state:

• 1 represents a position that definitely has a Lego piece,
• 0 represents a position that definitely does not have a Lego piece,
• and ? represents a position that you don't remember.

The third line of each test case contains a string $t$ of length $n$, consisting of the characters 0, 1, and ? — your memory of the ending state. It follows a similar format to the starting state.

It's guaranteed that the sum of $n$ over all test cases doesn't exceed $2000$.

第一行包含一个整数 $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$。

For each test case, output a single integer — the answer to the problem modulo $1\,000\,000\,007$ ($10^9 + 7$).

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

For the first test case, $00$ is the only possible starting state, and $11$ is the only possible ending state. It takes exactly one operation to change $00$ to $11$.

For the second test case, some of the possible starting and ending state pairs are:

• $(000, 011)$ — takes $1$ operation.
• $(001, 100)$ — takes $2$ operations.
• $(010, 000)$ — takes $0$ operations, as it's impossible to achieve the ending state.

对于第一个测试用例，$00$ 是唯一的可能初始状态，$11$ 是唯一的可能结束状态。将 $00$ 变为 $11$ 恰好需要一次操作。

对于第二个测试用例，一些可能的初始状态与结束状态对包括：

• $(000, 011)$ — 需要 $1$ 次操作。
• $(001, 100)$ — 需要 $2$ 次操作。
• $(010, 000)$ — 需要 $0$ 次操作，因为该结束状态无法达成。