对于任意一种可能相交的方案，把路径合并在一起，把第一行的每个点从右到左处理，每次走的时候都尽量向下走。这样我们还可以得到上面的点和下面的点的对应关系，尽管不一定是题目中给的对应关系了。不难发现，按照原排列走的每一种方案和任意一种新排列的行走方案是一一对应的。
不妨考虑容斥，我们可以对于每一种全排列计算出方案数，再通过逆序对数确定它的系数。不难发现，这实质上就是一个矩阵求行列式的过程。于是我们可以 O(n+Tk3) 解决问题。
#include<cstdio>
#include<algorithm>
using namespace std;
#define LL long long
const int maxn=200000,p=1000000007;
int fac[maxn+10],inv[maxn+10],a[110][110],f[110],g[110],n,m;
int inc(int x,int y)
{x+=y;return x>=p?x-p:x;
}
int dec(int x,int y)
{x-=y;return x<0?x+p:x;
}
int pow(int b,int k)
{int ret=1;for (;k;k>>=1,b=(LL)b*b%p)if (k&1) ret=(LL)ret*b%p;return ret;
}
int c(int n,int m)
{if (n<m) return 0;return (LL)fac[n]*inv[m]%p*inv[n-m]%p;
}
void solve()
{int flag=1,ans=1,x,y;scanf("%d%d",&n,&m);for (int i=1;i<=m;i++) scanf("%d",&f[i]);for (int i=1;i<=m;i++) scanf("%d",&g[i]);for (int i=1;i<=m;i++)for (int j=1;j<=m;j++)a[i][j]=c(n-1+g[j]-f[i],n-1);for (int i=1;i<=m;i++){x=-1;for (int j=i;j<=m;j++)if (a[j][i]){x=j;break;}if (x==-1) continue;if (x!=i){flag=-flag;for (int j=1;j<=m;j++) swap(a[x][j],a[i][j]);}x=pow(a[i][i],p-2);for (int j=i+1;j<=m;j++)if (a[j][i]){y=(LL)a[j][i]*x%p;for (int k=i;k<=m;k++)a[j][k]=dec(a[j][k],(LL)a[i][k]*y%p);}}for (int i=1;i<=m;i++) ans=(LL)ans*a[i][i]%p;if (flag==-1) ans=dec(0,ans);printf("%d\n",ans);
}
int main()
{//freopen("d.in","r",stdin);int T;fac[0]=inv[0]=1;for (int i=1;i<=maxn;i++) fac[i]=(LL)fac[i-1]*i%p;inv[maxn]=pow(fac[maxn],p-2);for (int i=maxn-1;i;i--) inv[i]=(LL)inv[i+1]*(i+1)%p;scanf("%d",&T);while (T--) solve();
}