#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int NN=1e9+7;
int  mat[50][50];
int id[100100];
int g[100100][4],h[100100][4];
int gg[100100],hh[100100];
int w[50][50];
int f[100100];
int mi(int x,int y){
	int sum=1;
	for(;y;y>>=1,x=x*x%NN)
	if(y&1)sum=sum*x%NN;
	return sum;
}
int lowbit(int x){return x&(-x);}
int solve1(int n){
	int ans=1;

	for (int i=0;i<n;i++){
		int xu=-1;
		for (int j=i;j<n;j++)
		if(mat[j][i]!=0){xu=j;break;}
		if(xu==-1)continue;
		if(xu!=i){
			for (int j=0;j<n;j++)
			swap(mat[xu][j],mat[i][j]);
			ans=-ans;
		}
		for (int j=i+1;j<n;j++){
			int tmp=mat[j][i]*mi(mat[i][i],NN-2)%NN;
			for (int k=0;k<n;k++)
			mat[j][k]=(mat[j][k]-mat[i][k]*tmp%NN+NN)%NN;
		}
	}
	
	for (int i=0;i<n;i++)ans=ans*mat[i][i]%NN;
	return ans;
}
int solve2(int n){
	int nn=1<<n,ans=0;
	for (int i=0;i<nn;i++){
		int tot=0;
		for (int j=0;j<n;j++)if(i>>j&1)id[tot++]=j;
		for (int j=0;j<tot;j++)
		for (int k=0;k<tot;k++)
		mat[j][k]=0;
		for (int j=0;j<tot;j++)
		for (int k=j+1;k<tot;k++)
		mat[j][k]-=w[id[j]][id[k]],mat[k][j]-=w[id[j]][id[k]],
		mat[j][j]+=w[id[j]][id[k]],mat[k][k]+=w[id[j]][id[k]];
		for (int j=0;j<tot;j++)
		for (int k=0;k<tot;k++)
		mat[j][k]%=NN;
		f[i]=solve1(tot-1);
//		cout<<i<<"***"<<f[i]<<"\n";
	}
	for (int i=0;i<n;i++){
		for (int j=0;j<nn;j++)h[j][0]=h[j][1]=h[j][2]=0;
		h[0][0]=1;
		for (int j=0;j<nn;j++)if(!(j>>i&1)){
			int sum=1,sum1=0,sum2=0;
			for (int k=0;k<n;k++)if(j>>k&1)sum=sum*(1+w[i][k])%NN,sum1=(sum1+w[i][k])%NN
			,sum2=(sum2+w[i][k]*w[i][k])%NN;
			g[j][0]=f[j]*sum1%NN;
			g[j][1]=f[j]*(sum1*sum1%NN-sum2)%NN*mi(2,NN-2)%NN;
			g[j][2]=f[j]*(sum-sum1-(sum1*sum1-sum2)%NN*mi(2,NN-2)%NN-1)%NN;
		}
		for (int j=0;j<nn;j++)if(!(j>>i&1)){
			int tmp=lowbit(nn-1-j-(1<<i));
			int tmp2=nn-1-j-(1<<i)-tmp;
			for (int k=tmp2;;k=(k-1)&tmp2){
				h[j|k|tmp][0]=(h[j][0]*g[k|tmp][0]+h[j|k|tmp][0])%NN;
				h[j|k|tmp][1]=(h[j][1]*g[k|tmp][0]+h[j][0]*g[k|tmp][1]+h[j|k|tmp][1])%NN;
				h[j|k|tmp][2]=(h[j][2]*(g[k|tmp][0]+g[k|tmp][1]+g[k|tmp][2])%NN
				+h[j][1]*(g[k|tmp][1]+g[k|tmp][2])+h[j][0]*g[k|tmp][2]+h[j|k|tmp][2])%NN;
				if(!k)break;
			}
		}
		ans=(ans+h[nn-1-(1<<i)][2])%NN;
	}
	return ans;
}
int solve3(int n){
	int nn=1<<n,ans=0;
	for (int i=0;i<n;i++)
	for (int ii=i+1;ii<n;ii++){
		for (int j=0;j<nn;j++)h[j][0]=h[j][1]=h[j][2]=h[j][3]=hh[j]=gg[j]=0;
		for (int j=0;j<nn;j++)if(!(j>>i&1)&&!(j>>ii&1)){
			int sum=0,sum2=0;
			for (int k=0;k<n;k++)if((j>>k&1))sum=(sum+w[ii][k])%NN,sum2=(sum2+w[i][k])%NN;
			gg[j]=f[j]*sum%NN*sum2%NN;
		}
		for (int j=0;j<nn;j++)if(!(j>>i&1)&&!(j>>ii&1)){
			int tmp2=nn-1-j-(1<<i)-(1<<ii);
			for (int k=tmp2;;k=(k-1)&(tmp2))if(!(k>>ii&1)&&!(k>>i&1)){
				hh[j|k|(1<<i)|(1<<ii)]=(hh[j|k|(1<<i)|(1<<ii)]+f[j|(1<<i)]*f[k|(1<<ii)])%NN;
				if(!k)break;
			}
		}
		for (int j=0;j<nn;j++)h[j][0]=hh[j];
		
		for (int j=0;j<nn-1;j++)if((j>>i&1)&&(j>>ii&1)){
			int tmp=lowbit(nn-1-j);
			int tmp2=nn-1-j-tmp;
			for (int k=tmp2;;k=(k-1)&tmp2){
				h[j|k|tmp][1]=(h[j][0]*gg[k|tmp]+h[j|k|tmp][1])%NN;
				h[j|k|tmp][2]=(h[j][1]*gg[k|tmp]+h[j|k|tmp][2])%NN;
				h[j|k|tmp][3]=(h[j][3]*gg[k|tmp]+h[j][2]*gg[k|tmp]+h[j|k|tmp][3])%NN;
				if(!k)break;
			}
		}
		ans=(ans+h[nn-1][3]*(1+w[i][ii])+h[nn-1][2]*w[i][ii])%NN;
//		ans=(ans+h[nn-1-(1<<i)-(1<<ii)][3]*(1+w[i][ii])+h[nn-1-(1<<i)-(1<<ii)][2]*w[i][ii])%NN;
	}
	return ans;
}
int lg[100100],ff[100100][20];
int solve4(int n){
	int nn=1<<n,ans=0;
	for (int i=0;i<nn;i++)gg[i]=f[i];
	for (int ti=0;ti<nn;ti++){
		for (int i=0;i<=n;i++)
		for (int j=0;j<=n;j++)
		mat[i][j]=0;
		for (int i=0;i<n;i++)
		for (int j=i+1;j<n;j++)
		mat[i][j]-=w[i][j],mat[j][i]-=w[i][j],
		mat[i][j]%=NN,mat[j][i]%=NN,
		mat[i][i]+=w[i][j],mat[j][j]+=w[i][j],
		mat[i][i]%=NN,mat[j][j]%=NN;
		for (int j=0;j<n;j++)
		if(ti>>j&1)mat[j][n]--,mat[n][j]--,mat[n][n]++,mat[j][j]++;
		f[ti]=solve1(n);
		for (int i=(ti-1)&ti;;i=(i-1)&ti){
			f[ti]=(f[ti]-f[i]+NN)%NN;
			if(!i)break;
		}
//		cout<<ti<<" "<<f[ti]<<"\n";
	}
	lg[1]=0;for (int i=2;i<nn;i++)lg[i]=lg[i>>1]+1;
	for (int i=0;i<nn;i++)
	for (int j=0;j<n;j++)ff[i][j]=0;
	for (int i=0;i<n;i++)
	ff[1<<i][i]=1;
	for (int i=0;i<nn;i++){
		int sum=0;
		for (int j=0;j<n;j++)if((i>>j&1)&&((1<<j)!=lowbit(i))) 
		for (int k=0;k<n;k++)if(k!=j&&(i>>k&1)){
			ff[i][j]=(ff[i][j]+ff[i^(1<<j)][k]*w[j][k])%NN;
			if((1<<k)!=lowbit(i))
			sum=(sum+ff[i^(1<<j)][k]*w[j][k]%NN*w[j][lg[lowbit(i)]])%NN;
		}
//		cout<<i<<"***"<<sum<<"\n";
		ans=(ans+f[i]*sum%NN*mi(2,NN-2))%NN;
	}
	return ans;
}
void solve(){
	int n;
	cin>>n;
	for (int i=0;i<n;i++)
	for (int j=0;j<n;j++)
	mat[i][j]=0;
	for (int i=0;i<n;i++)
	for (int j=0;j<n;j++)
	cin>>w[i][j],mat[i][j]-=w[i][j],mat[i][i]+=w[i][j];
	for (int i=0;i<n;i++)
	for (int j=0;j<n;j++)
	mat[i][j]%=NN;
	int a1=solve1(n-1);
	int a2=solve2(n);
	int a3=solve3(n);
	int a4=solve4(n);
//	cout<<a1<<"&&&"<<a2<<" "<<a3<<" "<<a4<<"\n";
	cout<<((a1+a2-a3+a4)%NN+NN)%NN<<"\n";
}
signed main(){
	int T;cin>>T;
	while(T--)solve();
}