/*
由兰道定理得，竞赛图的强连通分量个数为 $\sum_{i=1}^{n}[\sum_{j=1}^i out_j=C(i,2)]$。
每次反转一条边可以做到 O(1) 修改。 
*/
#include<bits/stdc++.h>
#define int long long
typedef long long ll;
using namespace std;
const int N = 5005;
const ll mod = 1e9 + 7;
bool flg[N][N];
int n;
char s[N];
int out[N], sum[N], nxt[N]; 
int cnt1[N], cnt2[N];
int turn(char x) {return (x >= '0' && x <= '9' ? (x ^ 48) : (10 + (x - 'A')));}
void solve() {
	scanf("%lld", &n);
	for(int i = 1; i <= n; i++) out[i] = 0;
	for(int i = 2, l; i <= n; i++) { l = (i - 1) / 4 + 1;
        cin>>(s + 1);
        for(int j = 1; j <= l; j++) for(int k = 4 * j - 3, x = turn(s[j]); k <= 4 * j && k < i; k++, x >>= 1) 
			if(x & 1) flg[i][k] = true, flg[k][i] = false, out[i]++;
			else flg[k][i] = true, flg[i][k] = false, out[k]++;
    }
    for(int i = 1; i <= n; i++) sum[i] = out[i], nxt[i] = 0;
	sort(sum + 1, sum + n + 1);
	for(int i = 1; i <= n; i++) nxt[sum[i]] = i;
	for(int i = 1; i <= n; i++) if(!nxt[i]) nxt[i] = nxt[i - 1];
	for(int i = 1; i <= n; i++) {
		int p = i * (i - 1) / 2; sum[i] += sum[i - 1];
		if(sum[i] == p) cnt1[i] = cnt1[i - 1] + 1;
		else if(sum[i] == p - 1) cnt2[i] = cnt2[i - 1] + 1;
	} 
	ll ans = 0;
	for(int i = n; i >= 1; i--) for(int j = i - 1; j >= 1; j--) {
		int sum = cnt1[n];
		if(flg[i][j]) {
			if(out[j] >= out[i]) sum += (cnt2[nxt[out[j]] - 1] - cnt2[nxt[out[i] - 1]]);
			if(out[j] + 1 < out[i]) sum -= (cnt1[nxt[out[i] - 1]] - cnt1[nxt[out[j]] - 1]);
		} else {
			if(out[i] >= out[j]) sum += (cnt2[nxt[out[i]] - 1] - cnt2[nxt[out[j] - 1]]);
			if(out[i] + 1 < out[j]) sum -= (cnt1[nxt[out[j] - 1]] - cnt1[nxt[out[i]] - 1]);
		}
		ans = (ans * 2 + sum) % mod;
	}
	printf("%lld\n", ans);
}
signed main() {
	int t; cin>>t;
	while(t--) solve();
	return 0;
}