#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int mod = (int)1e9 + 7;
int mult(int a, int b) {
    return (1LL * a * b) % mod;
}
int sum(int a, int b) {
    int s = a + b;
    if (s >= mod) s -= mod;
    return s;
}
int sub(int a, int b) {
    int s = a - b;
    if (s < 0) s += mod;
    return s;
}
const int maxN = (1 << 16) + 2;
int w[16][16];
int n;
int tree[maxN];
int forest[maxN];
int uni[maxN];
int uni_bad[maxN];
int trans[16][maxN][4];
int DP2[maxN];
int DP[16][maxN];
void upd(int& a, int b) {
    a += b;
    if (a >= mod) a -= mod;
}
int help[maxN];

int pw(int a, int b) {
    if (b == 0) return 1;
    if (b & 1) return mult(a, pw(a, b - 1));
    int res = pw(a, b / 2);
    return mult(res, res);
}

struct Det{
    vector < vector < int > > a;
    int n;
    Det(vector < vector < int > >& b) {
        a = b;
        n = a.size();
    }
    int calc() {
        int ans = 1;
        for (int col = 0; col < n; col++) {
            int where = -1;
            for (int row = col; row < n; row++) {
                if (a[row][col] != 0) {
                    where = row;
                    break;
                }
            }
            if (where == -1) return 0;
            if (where != col) {
                swap(a[col], a[where]);
                ans = sub(0, ans);
            }
            int coef = pw(a[col][col], mod - 2);
            ans = mult(ans, a[col][col]);
            for (int other_row = col + 1; other_row < n; other_row++) {
                if (a[other_row][col] == 0) continue;
                int to_mult = mult(a[other_row][col], coef);
                for (int j = col + 1; j < n; j++) {
                    a[other_row][j] = sub(a[other_row][j], mult(to_mult, a[col][j]));
                }
            }
        }
        return ans;
    }
};

int dp[maxN][16];
int CUR[maxN];
void solve() {
     cin >> n;
//    n = 16;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
             cin >> w[i][j];
//            w[i][j] = i + j;
        }
    }
    for (int i = 0; i < n; i++) {
        for (int mask = 0; mask < (1 << n); mask++) {
            if (mask & (1 << i)) continue;
            int prod = 1;
            int s1 = 0;
            int s2 = 0;
            for (int b = 0; b < n; b++) {
                if (mask & (1 << b)) {
                    prod = mult(prod, sum(w[i][b], 1));
                    s2 = sum(s2, mult(w[i][b], s1));
                    s1 = sum(s1, w[i][b]);
                }
            }
            trans[i][mask][0] = s1;
            trans[i][mask][1] = s2;
            trans[i][mask][2] = prod;
            trans[i][mask][3] = sub(prod, 1);
        }
    }
    for (int mask = 1; mask < (1 << n); mask++) {
        int x = __builtin_ctz(mask);
        if (mask == (1 << x)) {
            tree[mask] = 1;
        }
        else {
            tree[mask] = 0;
            int y = __builtin_ctz(mask ^ (1 << x));
            int M = (mask ^ (1 << x)) ^ (1 << y);
            int T = M;
            while (true) {
                tree[mask] = sum(tree[mask],
                                 mult(tree[T ^ (1 << y)], mult(tree[(M ^ T) ^ (1 << x)], trans[x][T ^ (1 << y)][0])));

                if (T == 0) break;
                T = M & (T - 1);
            }
        }
    }
    const int inv2 = (mod + 1) / 2;
    int tot_tree = tree[(1 << n) - 1];
    int S = mult(tot_tree, sub(mult(n, mult(n - 1, inv2)), n - 1));
    for (int mask = 0; mask < (1 << n); mask++) CUR[mask] = 0;
    for (int x = 0; x < n; x++) {
        for (int j = 0; j < (1 << x); j++) {
            for (int q = 0; q <= x; q++) {
                dp[j][q] = 0;
            }
        }
        dp[0][x] = 1;
        for (int mask = 0; mask < (1 << x); mask++) {
            for (int last = 0; last <= x; last++) {
                for (int will = 0; will < x; will++) {
                    if (mask & (1 << will)) continue;
                    upd(dp[mask ^ (1 << will)][will], mult(dp[mask][last], w[last][will]));
                }
            }
        }
        for (int mask = 1; mask < (1 << x); mask++) {
            for (int last = 0; last < x; last++) {
                if (mask == (1 << last)) continue;
                upd(CUR[mask ^ (1 << x)], mult(inv2, mult(dp[mask][last], w[last][x])));
            }
        }
    }
    vector<int> by_c(n + 1);
    for (int mask = 1; mask < (1 << n); mask++) {
        vector<int> id(n);
        int T = 0;
        vector<int> bck(n, -1);
        for (int x = 0; x < n; x++) {
            if (!(mask & (1 << x))) {
                id[x] = T++;
                bck[id[x]] = x;
            }
        }
        if (T == 0) {
            upd(by_c[n], CUR[mask]);
            continue;
        }
        vector<vector<int>> A(T, vector<int>(T, 0));
        for (int i = 0; i < T; i++) {
            for (int j = 0; j < T; j++) {
                if (i == j) continue;
                A[i][j] = sub(0, w[bck[i]][bck[j]]);
                A[i][i] = sum(A[i][i], w[bck[i]][bck[j]]);
            }
            for (int p = 0; p < n; p++) {
                if (mask & (1 << p)) {
                    A[i][i] = sum(A[i][i], w[bck[i]][p]);
                }
            }
        }
        upd(by_c[n - T], mult(CUR[mask], Det(A).calc()));
    }
    for (int len = 3; len <= n; len++) {
        S = sum(S, mult(by_c[len], sub(mult(mult(len, len - 1), inv2), len - 1)));
    }
    //connected
    for (int a = 0; a < n; a++) {
        DP[a][0] = 1;
        for (int mask = 1; mask < (1 << n); mask++) {
            if (mask & (1 << a)) continue;
            DP[a][mask] = 0;
            int x = __builtin_ctz(mask);
            int M = (mask ^ (1 << x));
            int T = M;
            while (true) {
                upd(DP[a][mask], mult(DP[a][M ^ T], mult(tree[T ^ (1 << x)],
                                                         trans[a][T ^ (1 << x)][3])));

                if (T == 0) break;
                T = M & (T - 1);
            }
        }
        S = sum(S, DP[a][((1 << n) - 1) ^ (1 << a)]);
    }

    //48

    for (int a = 0; a < n; a++) {
        for (int b = a + 1; b < n; b++) {
            DP2[0] = sum(w[a][b], 1);
            //
            for (int mask = 1; mask < (1 << n); mask++) {
                if (mask & (1 << a)) continue;
                if (mask & (1 << b)) continue;
                DP2[mask] = 0;
                help[mask] = mult(tree[mask], sub(mult(trans[a][mask][0] + 1, trans[b][mask][0] + 1), 1));
                //any 2 w_i + w_j + w_p
                int x = __builtin_ctz(mask);
                int M = (mask ^ (1 << x));
                int T = M;
                while (true) {
                    upd(DP2[mask], mult(DP2[M ^ T], help[T ^ (1 << x)]));
                    if (T == 0) break;
                    T = M & (T - 1);
                }
            }
            int F = ((1 << n) - 1) ^ (1 << a) ^ (1 << b);
            S = sub(S, DP2[F]);
//            cout << S << endl;
            for (int P = 0; P <= F; P++) {
                if ((F & P) == P) {
                    S = sum(S, mult(tree[(1 << a) ^ P], tree[(1 << b) ^ ((F ^ P))]));
                }
            }
        }
    }
    cout << S << '\n';
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef DEBUG
    freopen("input.txt", "r", stdin);
#endif
    int tst = 1;
     cin >> tst;
    while (tst--) solve();
    return 0;
}