/*
 * Time Spent: 
	 0. Expect: min
	 1. Idea: 
	 2. Code: 
 * Solution: 
	 Tag: 
	 https://www.cnblogs.com/CloudWings/p/18471311
 * Summary: 
 */
#include <bits/stdc++.h>
using namespace std;
double _st = clock();
const int N = 5005, mod = 1e9 + 7;
struct mint {
	int val;
	mint (int x=0) : val(x) {}
	inline mint operator + (const mint& x) { return val+x.val >= mod ? val+x.val-mod : val+x.val; }
	inline mint operator * (const mint& x) { return 1ll*val*x.val%mod; }
	inline mint operator += (const mint& x) { return *this = *this + x; }
	friend ostream& operator << (ostream& out, const mint& x) { return out << x.val; }
} qpow[N*N];
int n, out[N];
int L[N], R[N];  // 每一种出度在 p(排序后) 中最先/最后出现的位置
int f0[N][N], f1[N][N], f_1[N][N];  // 区间内前缀和跟 C(i,2) 相差 0/1/-1
bool e[N][N];
int main () {
	#ifdef LOCAL
	freopen("_1.in", "r", stdin);
	freopen("_1.out", "w", stdout);
	#else
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	#endif
	int T; cin >> T;
	while (T--) {
		cin >> n;
		qpow[0] = 1;
		for (int i = 1; i <= n*n; i++) qpow[i] = qpow[i-1] * 2;
		for (int i = 1; i <= n; i++) out[i] = 0;
		for (int i = 1; i < n; i++)
			for (int j = 1; j <= (i+3)/4; j++) {
				char ch; cin >> ch;
				int x = isdigit(ch) ? ch-'0' : ch-'A'+10;
				for (int k = 0; k <= 3; k++) {
					int u = i+1, v = 4*j+k-3;
					if (v >= u) break;
					if (!(x>>k&1)) swap(u, v);
					// printf("(%d,%d)\n", u, v);
					e[u][v] = 1, e[v][u] = 0;
					out[u]++;
				}
			}
		static int p[N]; static long long sum[N];
		for (int i = 1; i <= n; i++) p[i] = out[i];
		sort(p+1, p+n+1);
		for (int i = 1; i <= n; i++) R[p[i]] = i, sum[i] = sum[i-1] + p[i];
		for (int i = n; i >= 1; i--) L[p[i]] = i;
		for (int i = 1; i <= n; i++)
			for (int j = i; j <= n; j++)
				f0[i][j] = f0[i][j-1] + (1ll*j*(j-1)/2 - sum[j] == 0),
				f1[i][j] = f1[i][j-1] + (1ll*j*(j-1)/2 - sum[j] == 1),
				f_1[i][j] = f_1[i][j-1] + (1ll*j*(j-1)/2 - sum[j] == -1);
		// printf("%d\n", f0[1][n]);
		mint ans = 0;
		for (int i = 1; i <= n; i++)
			for (int j = 1; j < i; j++) {
				// printf("(%d,%d) ---------\n", i, j);
				int x = i, y = j;
				if (out[x] > out[y]) swap(x, y);
				int res = f0[1][n];
				// printf("(%d,%d) %d %d\n", x, y, out[x], out[y]);
				if (e[x][y]) {
					printf("opt=1\n");
					res -= f0[L[out[x]]][R[out[y]]-1];
					res += f_1[L[out[x]]][R[out[y]]-1];
				} else {
					// printf("opt=2\n");
					if (out[x] + 1 != out[y]) {
						// printf("%d %d\n", out[x], out[y]);
						res -= f0[R[out[x]]][L[out[y]]-1];
						res += f1[R[out[x]]][L[out[y]]-1];
					}
				}
				// printf("res=%d\n", res);
				ans += qpow[(i-2)*(i-1)/2+j-1] * res;
			}
		cout << ans << '\n';
	}
	cerr << (clock()-_st)/CLOCKS_PER_SEC << 's';
	return 0;
}
/*
g++ _1.cpp -o _1 -O2 -std=c++11 -DLOCAL; ./_1.exe
*/