LEGOndary Grandmaster
https://www.luogu.com.cn/problem/CF1615F
神题！看到题解一眼就知道自己大概率想不出来了。
主要还是积累两个套路：
Trick 1
考虑将原序列的奇数位位置上的数取反，惊讶地发现操作简化为了每次交换相邻两个数。显然地，如果交换两个一样的数，那么对于原序列是没有影响的。对应回原序列就是交换不了。
Trick 2
这个看着没有上一个那么妙，比较平凡。考虑对于序列计数。设 \(a_i\) 表示 \(s\) 中前 \(i\) 个位置中 1 的个数，\(b_i\) 表示 \(t\) 中前 \(i\) 个位置中 1 的个数，那么答案就是 \(\sum |a_i - b_i|\)。
知道了上面两个转换后，就很好计数了。
// Problem: LEGOndary Grandmaster
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1615F
// Memory Limit: 500 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
const long long inf = 1e18;
const int mininf = 1e9 + 7;
#define int long long
#define pb emplace_back
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void write(int x){if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0');}
#define put() putchar(' ')
#define endl puts("")
const int mod = 1e9 + 7;
const int MAX = 2e3 + 10;
int pre[MAX][2 * MAX];
int suf[MAX][2 * MAX];
void solve(){
int n = read();
string s, t;
cin>>s>>t;
s = " " + s;
t = " " + t;
for(int i = 1; i <= n; i++){
if(i & 1){
if(s[i] == '0') s[i] = '1';
else if(s[i] == '1') s[i] = '0';
if(t[i] == '0') t[i] = '1';
else if(t[i] == '1') t[i] = '0';
}
}
pre[0][n] = 1;
for(int i = 1; i <= n; i++){
for(int j = -n; j <= n; j++){
int now = n + j;
if(s[i] == '?' and t[i] == '?'){
pre[i][now] = 2 * pre[i - 1][now] + pre[i - 1][now + 1] + pre[i - 1][now - 1];
}else if(s[i] == '?'){
if(t[i] == '0'){
pre[i][now] = pre[i - 1][now] + pre[i - 1][now + 1];
}else{
pre[i][now] = pre[i - 1][now] + pre[i - 1][now - 1];
}
//now = a_i - b_i
}else if(t[i] == '?'){
if(s[i] == '0'){
pre[i][now] = pre[i - 1][now] + pre[i - 1][now - 1];
}else{
pre[i][now] = pre[i - 1][now] + pre[i - 1][now + 1];
}
}else{
pre[i][now] = pre[i - 1][now + (s[i] - t[i])];
}
pre[i][now] %= mod;
}
}
suf[n + 1][n] = 1;
for(int i = n; i >= 1; i--){
for(int j = -n; j <= n; j++){
int now = n + j;
if(s[i] == '?' and t[i] == '?'){
suf[i][now] = 2 * suf[i + 1][now] + suf[i + 1][now + 1] + suf[i + 1][now - 1];
}else if(s[i] == '?'){
if(t[i] == '0'){
suf[i][now] = suf[i + 1][now] + suf[i + 1][now + 1];
}else{
suf[i][now] = suf[i + 1][now] + suf[i + 1][now - 1];
}
//now = a_i - b_i
}else if(t[i] == '?'){
if(s[i] == '0'){
suf[i][now] = suf[i + 1][now] + suf[i + 1][now - 1];
}else{
suf[i][now] = suf[i + 1][now] + suf[i + 1][now + 1];
}
}else{
suf[i][now] = suf[i + 1][now + (s[i] - t[i])];
}
suf[i][now] %= mod;
}
}
// for(int i = n; i >= 1; i--){
// for(int j = -(n - i + 1); j <= (n - i + 1); j++){
// write(suf[i][n + j]), put();
// }endl;
// }
// write(pre[1][1]), endl;
// write(suf[2][3]), endl;
int ans = 0;
for(int i = 1; i <= n; i++){
for(int j = -i; j <= i; j++){
ans += abs(j) * pre[i][n + j] % mod * (suf[i + 1][n - j]) % mod;
ans %= mod;
}
}
write(ans), endl;
// endl;
for(int i = 0; i <= n; i++){
for(int j = -n; j <= n; j++){
pre[i][n - j] = 0;
}
}
for(int i = 0; i <= n; i++){
for(int j = -n; j <= n; j++){
suf[i][n - j] = 0;
}
}
}
signed main(){
int t = read();
while(t--) solve();
return 0;
}