LEGOndary Grandmaster
Contest: Codeforces Global Round 18
Difficulty rating: 2800
Tags: combinatorics, dp, math

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$$$).

Input format:
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$$$.

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

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
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.

Example input:
6
2
00
11
3
???
???
3
??1
0?0
4
??0?
??11
5
?????
0??1?
10
?01??01?1?
??100?1???

Example output:
1
16
1
14
101
1674

Editorial:
First, let's consider a fixed pair of strings $$$s$$$ and $$$t$$$, and find a simple way to calculate the amount of time it takes.
Key observation: Flip every bit at an even position in both strings $$$s$$$ and $$$t$$$. Now, the operation is equivalent to swapping two adjacent bits of $$$s$$$. This is because the operation is equivalent to flipping two adjacent bits and swapping them. Flipping bits on an even position takes care of the first part of the operation (as any operation includes one bit at an even and one bit at an odd position), so the problem reduces to simple swapping.
Now, for a fixed pair of strings, you want to find the minimum number of swaps to transform one into the other. Obviously, the answer is $$$0$$$ if the number of 1's in both strings is different. Now, let the number of 1's in each string be $$$k$$$, and the position of the $$$i$$$-th 1 from the left in $$$s$$$ be $$$x_i$$$, and the $$$i$$$-th 1 from the left in $$$t$$$ be $$$y_i$$$. The answer for a fixed pair of strings is $$$\sum\limits_{i = 1}^k|x_i - y_i|$$$, as the $$$i$$$-th 1 in $$$s$$$ will always be matched with the $$$i$$$-th 1 in $$$t$$$.
This expression can be transformed into a more convenient one. Let $$$a_i$$$ be the number of 1's in $$$s$$$ in the prefix ending at $$$i$$$, and $$$b_i$$$ the number of 1's in $$$t$$$ in the prefix ending at $$$i$$$. The previous expression is equivalent to $$$\sum\limits_{i = 1}^n|a_i - b_i|$$$. This is because the $$$i$$$-th index contributes $$$1$$$ to each 1 in the previous expression if and only if a $$$1$$$ needs to "cross" the $$$i$$$-th index when moving to it's corresponding location in $$$t$$$. Exactly $$$|a_i - b_i|$$$ 1's will cross over the index, so the answer is the sum over all of the values.
Now going back to the original problem, apply the initial transformation on the strings $$$s$$$ and $$$t$$$, where for each even index, you change 0 to 1, 1 to 0, and keep ? the same. Let $$$p_{i, j}$$$ be the number of ways, if you only consider indices $$$\leq i$$$, to replace the ?'s with 0's and 1's so that $$$a_i - b_i = j$$$. $$$s_{i, j}$$$ is defined similarly, except you only consider indices $$$\geq i$$$. Both of these have $$$\mathcal{O}(n^2)$$$ states and $$$\mathcal{O}(1)$$$ transitions. The final answer is $$$\sum\limits_{i=1}^{n-1} \sum\limits_{j=-n}^n |\ j \cdot p_{i, j} \cdot s_{i+1, -j} \ |$$$.