T2：画画
首先观察题目，发现走过去再走回来的操作像极了NOIP某年的dp题
所以运用套路走两次
我开始的想法是因为只会往右走或往下走，所以能走就一定走完，后来发现走两次，就以为不行，结果发现没法判断只有1条路径的情况
正解：
对于第一条路径：能往下走就走，不能走就往右走
对于第二条路径，能往右走就往右走，不能走就往下
对于重合的点乘2，因为来到重合点的路径对于第一条和第二条可以互换
注意点：
- 如果遇到连续的重合点只用乘1次2，因为对于连续的重合点，重合点之间的路径是唯一的，互换不会产生新的方案
- 收尾两个点的路径互换只能算一次，如果交换两次的话，和原来的方案是相同的（我代码中算的是尾点）
- 起点开始的连续路径不能计入答案（如果和我一样计算尾点的话）
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;//
int a[N],b[N],suma[N],sumb[N];
int n;
ll ans=1,mod=1e9+7;//
bool flag=false,flag2=false;//
void dfs(int x,int y,int xx,int yy,bool ff){//ff用来判断连续的重合点
if(suma[x]>a[x]||sumb[y]>b[y]||suma[xx]>a[xx]||sumb[yy]>b[yy]) {if(x==xx&&y==yy) ans/=2;return;};
if(x!=xx||y!=yy){
flag=true;
}
if(x==n&&y==n&&xx==n&&yy==n){
flag2=true;
return;
}
if(suma[x]+1<=a[x]&&sumb[yy]+1<=b[yy]&&y+1<=n&&xx+1<=n){
suma[x]++,sumb[yy]++;
bool f=false;
if(x!=xx+1||y!=yy+1)sumb[y+1]++,suma[xx+1]++;
if(x==xx+1&&y+1==yy) {if(!ff) ans=ans*2%mod;f=true;};
dfs(x,y+1,xx+1,yy,f);
suma[x]--,sumb[yy]--;
if(x!=xx+1||y!=yy+1)sumb[y+1]--,suma[xx+1]--;
}
if(suma[x]==a[x]&&x+1<=n&&xx+1<=n&&sumb[yy]+1<=b[yy]){
suma[x+1]++,sumb[yy]++;
bool f=false;
if(x+1!=xx+1||y!=yy)suma[xx+1]++,sumb[y]++;
if(x+1==xx+1&&y==yy){if(!ff) ans=ans*2%mod;f=true;}
dfs(x+1,y,xx+1,yy,f);
suma[x+1]--,sumb[yy]--;
if(x+1!=xx+1||y!=yy)suma[xx+1]--,sumb[y]--;
}
if(sumb[yy]==b[yy]&&yy+1<=n&&y+1<=n&&suma[x]+1<=a[x]){
suma[x]++,sumb[yy+1]++;
bool f=false;
if(x!=xx||y+1!=yy+1)suma[xx]++,sumb[y+1]++;
if(x==xx&&y+1==yy+1){if(!ff) ans=ans*2%mod;f=true;}
dfs(x,y+1,xx,yy+1,f);
suma[x]--,sumb[yy+1]--;
if(x!=xx||y+1!=yy+1)suma[xx]--,sumb[y+1]--;
}
if(sumb[yy]==b[yy]&&suma[x]==a[x]&&x+1<=n&&yy+1<=n){
sumb[y]++;suma[xx]++;
bool f=false;
if(x+1!=xx||y!=yy+1)suma[x+1]++,sumb[yy+1]++;
if(x+1==xx&&y==yy+1){if(!ff) ans=ans*2%mod;f=true;}
dfs(x+1,y,xx,yy+1,f);
sumb[y]--;suma[xx]--;
if(x+1!=xx||y!=yy+1)suma[x+1]--,sumb[yy+1]--;
}
}
int main(){
int T;
scanf("%d",&T);
while(T--){
flag2=false;flag=false;
memset(suma,0,sizeof(suma));
memset(sumb,0,sizeof(sumb));
scanf("%d",&n); ans=1;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
for(int i=1;i<=n;i++){
scanf("%d",&b[i]);
}
suma[1]++,sumb[1]++;
dfs(1,1,1,1,1);
if(!flag2){
puts("0");
continue;
}
if(!flag){
puts("1");
continue;
}
printf("%lld\n",ans);
}
}