#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
#define fir first
#define sec second
typedef vector <int> vi;
typedef vector <ll> vl;

#ifdef LCX
#define msg(args...) fprintf(stderr, args)
#else
#define msg(...) void()
#endif

constexpr int maxn = 5010, mod = 1e9 + 7;
int n, ans[maxn][maxn], ans2[maxn][maxn];
bitset <maxn> e[maxn];

int hextodec(char ch) {
    if (isalpha(ch)) return ch - 'A' + 10;
    return ch - '0';
}

int dfn[maxn], low[maxn], idx, stk[maxn], tp, ins[maxn], scc[maxn], cnt_scc, siz[maxn];
void dfs(int u) {
    dfn[u] = low[u] = ++idx;
    stk[++tp] = u, ins[u] = 1;
    for (int v = 1; v <= n; ++v) if (e[u][v]) {
        if (!dfn[v]) dfs(v), low[u] = min(low[u], low[v]);
        else if (ins[v]) low[u] = min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u]) {
        int x;
        ++cnt_scc;
        do {
            x = stk[tp--];
            ins[x] = 0;
            scc[x] = cnt_scc;
            siz[cnt_scc]++;
        } while (x != u);
    }
}
int vis[maxn], deg[maxn], sum[maxn], p[maxn];
void solve(int c) {
    vi vec, a;
    for (int i = 1; i <= n; ++i)
        if (scc[i] == c) vec.push_back(i), vis[i] = 0, deg[i] = 0;
    // for (int x : vec) msg("%d ", x);
    // msg("\n");
    for (int u : vec)
        for (int v : vec) if (e[u][v]) deg[u]++;
    int m = vec.size();
    for (int x : vec) {
        a.push_back(x);
        int i = a.size() - 1;
        while (1) {
            int flg = 1;
            if (i) flg &= e[a[i - 1]][a[i]];
            if (i < (int) a.size() - 1) flg &= e[a[i]][a[i + 1]];
            if (flg) break;
            swap(a[i], a[i - 1]), --i;
        }
    }
    for (int i = 0; i < m; ++i) vis[a[i]] = i;
    auto calc = [&] (int x, int y) {
        deg[x]--, deg[y]++;
        for (int i = 0; i <= m; ++i) sum[i] = 0;
        for (int x : vec) sum[deg[x]]++;
        for (int i = 1; i <= m; ++i) sum[i] += sum[i - 1];
        for (int x : vec) p[sum[x]--] = deg[x];
        int s = 0, cnt = 0;
        for (int i = 1; i <= m; ++i)
            s += p[i], cnt += (s == i * (i - 1) / 2);
        ans[x][y] = ans[y][x] = cnt - 1 + cnt_scc;
        deg[x]++, deg[y]--;
    };
    int l = m - 1;
    // for (int i = 0; i < m; ++i) msg("%d%c", a[i], " \n"[i == m - 1]);
    for (int i = 0; i < m - 1; ++i) calc(a[i], a[i + 1]);
    for (int i = m - 1; i >= 0; --i) {
        int u = a[i];
        for (int v : vec) if (e[u][v]) {
            if (l > vis[v]) calc(u, v), l = vis[v];
            else if (vis[v] != i + 1) {
                ans[u][v] = ans[v][u] = cnt_scc;
                if (ans[u][v] != ans2[u][v]) assert(0);
            }
        }
    }
}

mt19937 rnd(time(0));

void work() {
    // scanf("%d", &n);
    n = 5;
    for (int i = 2; i <= n; ++i) {
        // static char s[maxn];
        // scanf("%s", s);
        for (int j = 1; j < i; ++j) {
            // int c = (hextodec(s[(j - 1) / 4]) >> ((j - 1) % 4)) & 1;
            int c = rnd() & 1;
            e[i][j] = c, e[j][i] = !c;
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j)
            msg("%d", (int) e[i][j]);
        msg("\n");
    }
    for (int u = 1; u <= n; ++u)
        for (int v = 1; v < u; ++v) {
            e[u].flip(v), e[v].flip(u);
            idx = tp = cnt_scc = 0;
            for (int i = 1; i <= n; ++i) dfn[i] = low[i] = ins[i] = siz[i] = 0;
            for (int i = 1; i <= n; ++i) if (!dfn[i]) dfs(i);
            e[u].flip(v), e[v].flip(u);
            ans2[u][v] = ans2[v][u] = cnt_scc;
        }
    idx = tp = cnt_scc = 0;
    for (int i = 1; i <= n; ++i) dfn[i] = low[i] = ins[i] = siz[i] = 0;
    for (int i = 1; i <= n; ++i) if (!dfn[i]) dfs(i);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j < i; ++j)
            if (scc[i] != scc[j]) {
                if (abs(scc[i] - scc[j]) == 1 && siz[scc[i]] == 1 && siz[scc[j]] == 1)
                    ans[i][j] = ans[j][i] = cnt_scc;
                else
                    ans[i][j] = ans[j][i] = cnt_scc - abs(scc[i] - scc[j]);
            }
    for (int i = 1; i <= cnt_scc; ++i) solve(i);
    // for (int i = 1; i <= n; ++i)
    //     for (int j = 1; j <= n; ++j)
    //         printf("%d%c", ans[i][j], " \n"[j == n]);
    int pw2 = 1, res = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j < i; ++j)
            res = (res + (ll) ans[i][j] * pw2) % mod, pw2 = pw2 * 2 % mod;
    printf("%d\n", res);
}
int main() {
    int T; scanf("%d", &T);
    while (T--) work();
    return 0;
}