#include<bits/stdc++.h>
using namespace std;
constexpr int N=16,M=(1<<16)+5,mod=1e9+7;
int n,lim,a[N][N],p[N],c2[N],id[N],rec[N][N];
int tree[M],cyc[M][N],rec1[N][M],rec2[N][M],dp[M],val[M],sum[M];
int read(){
    int x=0;char ch=getchar();
    while (!isdigit(ch)) ch=getchar();
    while (isdigit(ch)) x=x*10+ch-48,ch=getchar();
    return x;
}
int rdc(int x){return x>=mod?x-mod:x;}
int qpow(int x,int n){
    int s=1; while (n){
        if (n&1) s=1ll*s*x%mod;
        x=1ll*x*x%mod; n>>=1;
    } return s;
}
int SpanningTree(int n){ int ans=1;
    for (int i=0;i<n;i++){ int p=-1;
        for (int j=i;j<n;j++)
            if (rec[j][i]) {p=j;break;}
        if (!~p) return 0;
        if (i!=p){ ans=mod-ans;
            for (int j=i;j<n;j++)
                swap(rec[i][j],rec[p][j]);
        }
        ans=1ll*ans*rec[i][i]%mod;
        const int inv=qpow(rec[i][i],mod-2);
        for (int j=i;j<n;j++) rec[i][j]=1ll*rec[i][j]*inv%mod;
        for (int j=i+1;j<n;j++) if (rec[j][i]){
            const int coef=mod-rec[j][i];
            for (int k=i;k<n;k++) rec[j][k]=(rec[j][k]+1ll*coef*rec[i][k])%mod;
        }
    }
    return ans;
}
int getans1(){ // u
    int ans=0;
    for (int u=0;u<n;u++){
        for (int sta=0;sta<=lim;sta++)
            dp[sta]=sta?-1:1,val[sta]=1ll*(rec2[u][sta]-1)*tree[sta]%mod;
        auto dfs=[&](auto self,auto sta) ->int {
            if (~dp[sta]) return dp[sta];
            const int low=sta&-sta,s=sta^low;
            dp[sta]=1ll*self(self,s)*val[low]%mod;
            for (int t=s;t;(--t)&=s) dp[sta]=(dp[sta]+1ll*self(self,s^t)*val[t^low])%mod;
            return dp[sta];
        };
        ans=rdc(ans+dfs(dfs,lim^1<<u));
    }
    return ans;
}
int getans2(){ // u,v
    int ans=0;
    for (int u=0;u<n;u++)
        for (int v=u+1;v<n;v++){
            for (int sta=0;sta<=lim;sta++)
                dp[sta]=sta?-1:1,val[sta]=1ll*(rec1[u][sta]+rec1[v][sta]+1ll*rec1[u][sta]*rec1[v][sta])%mod*tree[sta]%mod;
            auto dfs=[&](auto self,auto sta) ->int {
                if (~dp[sta]) return dp[sta];
                const int low=sta&-sta,s=sta^low;
                dp[sta]=1ll*self(self,s)*val[low]%mod;
                for (int t=s;t;(--t)&=s) dp[sta]=(dp[sta]+1ll*self(self,s^t)*val[t^low])%mod;
                return dp[sta];
            };
            ans=(ans+1ll*dfs(dfs,lim^1<<u^1<<v)*(a[u][v]+1))%mod;
        }
    for (int sta=1;sta<lim-sta;sta++){
        const int cnt=__builtin_popcount(sta);
        ans=(ans-1ll*tree[sta]*tree[lim^sta]%mod*cnt%mod*(n-cnt))%mod;
    }
    return ans<0?ans+mod:ans;
}
int getans3(){ // tree
    return 1ll*(c2[n]-n+1)*tree[lim]%mod;
}
int getans4(){ // pseudotree
    for (int sta=0;sta<=lim;sta++) sum[sta]=0;
    for (int s=0;s<n;s++){
        const int lim=(1<<s+1)-1;
        for (int sta=0;sta<=lim;sta++)
            for (int i=0;i<=s;i++) cyc[sta][i]=0;
        cyc[1<<s][s]=1;
        for (int sta=1;sta<=lim;sta++)
            for (int i=0;i<=s;i++) if (sta>>i&1)
                for (int j=0;j<=s;j++) if (~sta>>j&1)
                    cyc[sta^1<<j][j]=(cyc[sta^1<<j][j]+1ll*cyc[sta][i]*a[i][j])%mod;
        for (int sta=1;sta<=lim;sta++)
            for (int i=0;i<=s;i++) if (cyc[sta][i]&&a[i][s])
                sum[sta]=(sum[sta]+1ll*cyc[sta][i]*a[i][s])%mod;
    }
    int ans=0;
    for (int sta=1;sta<=lim;sta++){
        const int cnt=__builtin_popcount(sta);
        if (cnt<3) continue; int m=0;
        sum[sta]=1ll*sum[sta]*(mod+1>>1)%mod;
        for (int i=0;i<n;i++)
            if (~sta>>i&1) id[i]=m++;
        for (int i=0;i<n;i++)
            if (sta>>i&1) id[i]=m;
        for (int i=0;i<=m;i++)
            for (int j=0;j<=m;j++)
                rec[i][j]=0;
        for (int i=0;i<n;i++)
            for (int j=i+1;j<n;j++){
                if (id[i]==id[j]) continue;
                rec[id[i]][id[i]]=rdc(rec[id[i]][id[i]]+a[i][j]);
                rec[id[j]][id[j]]=rdc(rec[id[j]][id[j]]+a[i][j]);
                rec[id[i]][id[j]]=rec[id[j]][id[i]]=rdc(rec[id[i]][id[j]]+mod-a[i][j]);
            }
        sum[sta]=1ll*sum[sta]*SpanningTree(m)%mod;
        ans=(ans+1ll*sum[sta]*(c2[cnt]-cnt+1))%mod;
    }
    return ans;
}
void solve(){
    n=read();lim=(1<<n)-1;
    for (int i=0;i<n;i++)
        for (int j=0;j<n;j++)
            a[i][j]=read();
    for (int sta=1;sta<=lim;sta++){
        int m=0;
        for (int i=0;i<n;i++)
            if (sta>>i&1) p[m++]=i;
        for (int i=0;i<m;i++) rec[i][i]=0;
        for (int i=0;i<m;i++)
            for (int j=i+1;j<m;j++){
                rec[i][i]=rdc(rec[i][i]+a[p[i]][p[j]]);
                rec[j][j]=rdc(rec[j][j]+a[p[i]][p[j]]);
                rec[i][j]=rec[j][i]=mod-a[p[i]][p[j]];
            }
        tree[sta]=SpanningTree(m-1);
    }
    for (int i=1;i<=n;i++) c2[i]=i*(i-1)/2;
    for (int i=0;i<n;i++){ rec1[i][0]=0;rec2[i][0]=1;
        for (int j=0;j<n;j++) rec1[i][1<<j]=a[i][j],rec2[i][1<<j]=a[i][j]+1;
        for (int s=1;s<=lim;s++){
            const int t=s^(s&-s);
            rec1[i][s]=rdc(rec1[i][t]+rec1[i][s&-s]);
            rec2[i][s]=1ll*rec2[i][t]*rec2[i][s&-s]%mod;
        }
    }
    int ans1=getans1(),ans2=getans2(),ans3=getans3(),ans4=getans4();
    printf("%d\n",(0ll+ans1+mod-ans2+ans3+ans4)%mod);
}
int main(){
    int T=read();while (T--) solve();
    return 0;
}