#include<bits/stdc++.h>
#define ll long long
#define mod 1000000007
using namespace std;
ll T,n,i,j,val[17][17],a[17][17],tr,cir[17],ans1,ans2,ans,f[1<<17][17][17],id[17],g[1<<17],h[1<<17],h2[1<<17];
inline ll calc(ll x){return x*(x-1)/2;}
inline ll qmi(ll a,ll b,ll p){
	ll res = 1%p,t = a;
	while(b){
		if(b&1) res=res*t%p;
		t=t*t%p;
		b>>=1;
	}
	return res;
}
inline ll solve_tree(ll n){
	ll has=0,i,j,k,ans=1,res;
	for(i=1;i<n;i++) for(j=1;j<n;j++) a[i][j]=(a[i][j]%mod+mod)%mod;
	for(i=1;i<n;i++){
		for(j=i+1;j<n;j++){
			if(a[j][i]){
				swap(a[i],a[j]),has^=1;
				break;
			}
		}
		ll inv = qmi(a[i][i],mod-2,mod);
		for(j=1;j<n;j++){
			if(i==j) continue;
			ll res = a[j][i]*inv%mod;
			for(k=i;k<n;k++) a[j][k]=(a[j][k]-a[i][k]*res)%mod;
		}
	}
	if(i<n){
		cout<<0<<endl;
		return 0;
	}
	for(i=1;i<n;i++) ans=ans*a[i][i]%mod;
	ans=(ans%mod+mod)%mod;
	if(has) ans=(mod-ans)%mod;
	return ans;
}
inline ll solve_ans1(){
	ll ans = 0;
	for(ll i=1;i<(1<<n);i++){
		memset(id,0,sizeof(id));
		ll tot = 0;
		for(ll j=0;j<n;j++) if(((i>>j)&1)) id[j+1]=++tot;
		memset(a,0,sizeof(a));
		for(ll j=1;j<=n;j++){
			for(ll k=j+1;k<=n;k++){
				if(!id[j]||!id[k]) continue;
				a[id[j]][id[k]]-=val[j][k];
				a[id[k]][id[j]]-=val[j][k];
				a[id[j]][id[j]]+=val[j][k];
				a[id[k]][id[k]]+=val[j][k];
			}
		}
		g[i]=solve_tree(tot);
	}
	for(ll i=1;i<=n;i++){
		ll upp = (1<<n)-1-(1<<i-1);
		for(ll j=0;j<(1<<n);j++){
			if((j&upp)!=j) continue;
			h[j]=0;
			ll res=1;
			for(ll k=0;k<n;k++) if((j>>k)&1) res=res*(1+val[k+1][i])%mod;
			res=(res-1+mod)%mod;
			h2[j]=g[j]*res%mod;
		}
		h[0]=1;
		for(ll j=1;j<(1<<n);j++){
			if((j&upp)!=j) continue;
			ll up = (j&(-j));
			for(ll k=j-up;;k=((j-up)&(k-1))){
				h[j]=(h[j]+h[j-(k|up)]*h2[k|up])%mod;
				if(k==0) break;
			}
		}
		ans=(ans+h[(1<<n)-1-(1<<i-1)])%mod;
	} 
	return ans;
}
inline ll solve_ans2(){
	ll ans = 0;
	for(ll i=1;i<=n;i++){
		for(ll j=i+1;j<=n;j++){
			ll up = (1<<n)-1-(1<<i-1)-(1<<j-1);			
			for(ll k=0;k<(1<<n);k++){
				if((k&up)!=k) continue;
				ll pos1 = 1,pos2 = 1;
				for(ll l=0;l<n;l++) if((k>>l)&1) pos1=(pos1+val[l+1][i])%mod,pos2=(pos2+val[l+1][j])%mod;
				h2[k] = g[k]*(pos1*pos2%mod-1+mod)%mod,h[k] = 0;
			}
			h[0]=1;
			for(ll l=1;l<(1<<n);l++){
				if((l&up)!=l) continue;
				ll up = (l&(-l));
				for(ll k=l-up;;k=((l-up)&(k-1))){
					h[l]=(h[l]+h[l-(k|up)]*h2[k|up])%mod;
					if(k==0) break;
				}
			}
			ans=(ans+h[(1<<n)-1-(1<<i-1)-(1<<j-1)]*(val[i][j]+1))%mod;
			for(ll k=0;k<(1<<n);k++){
				if((k>>(i-1))&1) continue;
				if(!((k>>j-1)&1)) continue;
				ans=(ans-g[k]*g[(1<<n)-1-k]%mod+mod)%mod;
			}
		}
	}
	return ans;
}
inline void solve_cir(){
	for(ll i=1;i<=n;i++) for(ll j=1;j<=n;j++) for(ll k=0;k<(1<<n);k++) f[k][i][j]=0;
	for(ll i=1;i<=n;i++) f[1<<i-1][i][i]=1;
	for(ll i=1;i<(1<<n);i++){
		ll res = 0,cnt = __builtin_popcount(i),tot = 0;
		if(cnt<=2) goto end;
		for(ll j=0;j<n;j++){
			for(ll k=0;k<n;k++){
				if(j!=k&&((i>>j)&1)&&((i>>k)&1)) res=(res+f[i][j+1][k+1]*val[j+1][k+1])%mod; 
			}
		}
		res = res*qmi(2*cnt,mod-2,mod)%mod;
		memset(a,0,sizeof(a));
		for(ll j=0;j<n;j++){
			if(!((i>>j)&1)) id[j+1]=++tot;
			else id[j+1]=n-cnt+1;
		}
		for(ll j=1;j<=n;j++){
			for(ll k=j+1;k<=n;k++){
				a[id[j]][id[k]]-=val[j][k];
				a[id[k]][id[j]]-=val[j][k];
				a[id[j]][id[j]]+=val[j][k];
				a[id[k]][id[k]]+=val[j][k];
			}
		}
		cir[cnt] = (cir[cnt]+res*solve_tree(n-cnt+1))%mod;
		end:;
		for(ll j=0;j<n;j++) for(ll k=0;k<n;k++) for(ll l=0;l<n;l++) if(!((i>>l)&1)&&((i>>j)&1)&&((i>>k)&1)) f[i|(1<<l)][j+1][l+1]=(f[i|(1<<l)][j+1][l+1]+f[i][j+1][k+1]*val[k+1][l+1])%mod;
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin>>T;
	while(T--){
		memset(cir,0,sizeof(cir));
		memset(a,0,sizeof(a));
		cin>>n;
		for(i=1;i<=n;i++) for(j=1;j<=n;j++) cin>>val[i][j];
		if(n==1){
			cout<<1<<endl;
			continue;
		}
		for(i=1;i<=n;i++) for(j=i+1;j<=n;j++) a[i][i]+=val[i][j],a[j][j]+=val[i][j],a[i][j]-=val[i][j],a[j][i]-=val[i][j];
		tr = solve_tree(n);
		ans1 = solve_ans1();
		ans2 = solve_ans2();
		solve_cir();
		ans = ans1-ans2+tr*(calc(n)-n+1)%mod;
		for(i=1;i<=n;i++) ans+=cir[i]*(calc(i)-i+1)%mod;
		cout<<(ans%mod+mod)%mod<<endl;
	}
	return 0;
}