//第二题 #include<iostream> #include<algorithm> #include<vector> #include<string.h> #define M 1000000007 using namespace std; long long pow(long long k){ if(k==0) return 1; if(k==1) return 3; long long t=pow(k/2); t=t*t; if(k%2==1) t*=3; return t%M; } long long a[2][2]={0,3,1,2}; void getAns(long long k, long long b[][2]){ if(k==1) { for(int i=0;i<2;++i) for(int j=0;j<2;++j) b[i][j]=a[i][j]; return ; } long long t[2][2]; getAns(k/2,t); long long tt[2][2]={0}; for(int i=0;i<2;++i) for(int j=0;j<2;++j) for(int k=0;k<2;++k) tt[i][j]+=t[i][k]*t[k][j],tt[i][j]%=M; if(k%2==1){ long long ttt[2][2]; for(int i=0;i<2;++i) for(int j=0;j<2;++j) ttt[i][j]=tt[i][j],tt[i][j]=0; for(int i=0;i<2;++i) for(int j=0;j<2;++j) for(int k=0;k<2;++k) tt[i][j]+=ttt[i][k]*a[k][j],tt[i][j]%=M; } for(int i=0;i<2;++i) for(int j=0;j<2;++j) b[i][j]=tt[i][j]; return ; } long long getTot(long long k,int p){ if(k==0){ if(p==0) return 0; return 1; } if(k==1) { if(p==0) return 3; else return 2; } long long b[2][2]; getAns(k-1,b); if(p==0) { long long tot=b[0][0]*3+b[0][1]*2; return tot%=M; } else { long long tot=b[1][0]*3+b[1][1]*2; return tot%=M; } } int check(int x,int y){ if(x==y) return 0; return 1; } long long t,n,m; long long f[1005][5]; long long w[1005]; int c[1005]; int main(){ cin>>t; while(t-- > 0){ cin>>n>>m; memset(f,sizeof(f),0); memset(w,sizeof(w),0); memset(c,sizeof(c),0); if(m==0){ cout<<(4*pow(n-1))%M<<endl; continue; } for(int i=0;i<m;++i){ cin>>w[i]; } for(int i=0;i<m;++i){ cin>>c[i]; } f[0][c[0]]=pow(w[0]-1); for(int i=1;i<m;++i){ f[i][c[i]]=f[i-1][c[i-1]]*getTot(w[i]-w[i-1]-1,check(c[i],c[i-1])); f[i][c[i]]%=M; } if(w[m-1]==n){ cout<<f[m-1][c[m-1]]<<endl; } else{ long long ans = f[m-1][c[m-1]]*pow(n-w[m-1]); ans%=M; cout<<ans<<endl; } } return 0; }