#include <bits/stdc++.h>
using namespace std;
static const long long M=1000000007LL;static inline long long n(long long x){x%=M;if(x<0)x+=M;return x;}static inline long long u(long long a,long long b){return(long long)((__int128)a*b%M);}long long p(long long a,long long e){long long r=1;while(e>0){if(e&1)r=u(r,a);a=u(a,a);e>>=1;}return r;}struct P{vector<long long>f,g,h;long long i,j;explicit P(int a=0){q(a);}void q(int a){int b=4*a;f.assign(b+1,1);for(int c=1;c<=b;++c)f[c]=u(f[c-1],c);g.assign(b+1,1);g[b]=p(f[b],M-2);for(int c=b;c>=1;--c)g[c-1]=u(g[c],c);i=p(2,M-2);j=u(i,i);h.assign(2*a+1,1);for(int c=1;c<=2*a;++c)h[c]=u(h[c-1],i);}long long r(int a,int b)const{return u(f[a],g[b]);}long long s(int a,int b)const{return u(f[4*a-b-1],h[2*a-b]);}};long long t(const vector<int>&a,const P&b){int c=(int)a.size()/2;vector<int>d(c),e(c);for(int k=0;k<c;++k){d[k]=a[2*k];e[k]=a[2*k+1];}for(int k=0;k<c;++k){if(e[k]>d[k])return 0;if(e[k]>d[(k+1)%c])return 0;}long long l=0;auto v=[&](int k,long long m){l+=u(n(m),b.s(c,k));if(l>=M)l-=M;};int w=0;for(int k:d)w+=k;if(w==0){v(1,c);for(int k=2;k<=2*c;++k){long long m=u(k,u(c,c-1LL));m=u(m,b.r(2*c-2,2*c-k));v(k,m);}return l;}bool x=1,y=1;for(int k=0;k<c;++k){if(d[k]!=1)x=0;if(e[k]!=1)y=0;}if(x&&y){for(int k=2;k<=2*c;++k){long long m=u(k,u(c,c));m=u(m,b.i);m=u(m,b.r(2*c-2,2*c-k));v(k,m);}return l;}vector<int>z;z.reserve(w);for(int k=0;k<c;++k){int m=(k==0?c-1:k-1);if(d[k]==1&&e[m]==0){int o=1,aa=k;while(e[aa]==1){aa=(aa+1==c?0:aa+1);++o;}z.push_back(o);}}int A=(int)z.size();long long B=0,C=0;for(int k:z){B+=k;C+=1LL*k*k;}for(int k=2*A;k<=2*c;++k){int m=k-2*A;long long o=0;if(m==0)o=1LL*A*A;else if(m==1)o=2LL*A*(B+1LL*A*(c-A-1));else{long long aa=u(k,b.j);aa=u(aa,b.r(2*c-2*A-2,2*c-k));long long ab=n(8LL*(c-A)+1);__int128 ac=(__int128)4*(c-A)*((long long)c*(2LL*A-1)-2LL*A*(A+1LL));long long ad=n((long long)(ac%M));long long ae=n(u(ab,n(B))+ad-n(C));o=u(aa,ae);}v(k,o);}return l;}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int a;cin>>a;vector<vector<int>>b(a);int c=0;for(int d=0;d<a;++d){int e;cin>>e;c=max(c,e);b[d].resize(2*e);for(int f=0;f<2*e;++f)cin>>b[d][f];}P g(c);for(const auto&h:b){int i=(int)h.size()/2;long long j=0;bool k=1;for(int l:h)if(l!=0&&l!=1)k=0;if(k){j+=t(h,g);if(j>=M)j-=M;}bool m=1;for(int l:h)if(l!=1&&l!=2)m=0;if(m){vector<int>n(2*i);for(int o=0;o<2*i;++o){int p=(o==0?2*i-1:o-1);n[o]=2-h[p];}j+=t(n,g);if(j>=M)j-=M;}cout<<j%M<<'\n';}return 0;}