#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=5005;
const int Mod=1e9+7;
int n;
bool vis[N][N];
inline int Read(){
	char ch;
	int f=1;
	while((ch=getchar())<'0'||ch>'9')
		if(ch=='-') f=-1;
	int x=ch^48;
	while((ch=getchar())>='0'&&ch<='9')
		x=(x<<3)+(x<<1)+(ch^48);
	return x*f;
}
inline void print(int x){
	if(x>=10) print(x/10);
	putchar(x%10+48);
	return ;
}
inline void Print(int x,char ch='\n'){
	if(x<0){
		putchar('-');
		print(-x);
	}
	else print(x);
	putchar(ch);
	return ;
}
inline int Get(char ch){
	if(ch>='0'&&ch<='9') return ch-'0';
	if(ch>='A'&&ch<='F') return ch-'A'+10;
	return -1;
}
int deg[N];
inline void Init(){
	n=Read();
	for(int i=1;i<=n;i++)
		deg[i]=0;
	for(int i=2;i<=n;i++){
		for(int j=1;j<=(i-1+3)/4;j++){
			char ch;
			while((ch=getchar())&&Get(ch)==-1);
			for(int k=0;k<=3;k++){
				if(4*j+k-3>=i) break ;
				vis[i][4*j+k-3]=Get(ch)&(1<<k);
				vis[4*j+k-3][i]=vis[i][4*j+k-3]^1;
			}
		}
	}
	/*for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			printf("i=%d j=%d %d\n",i,j,vis[i][j]);*/
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(vis[i][j]) deg[j]++;
	return ;
}
inline int Max(int x,int y){
	return x>y?x:y;
}
inline int Min(int x,int y){
	return x<y?x:y;
}
inline void Cmax(int&x,int y){
	if(y>x) x=y;
	return ;
}
inline void Cmin(int&x,int y){
	if(y<x) x=y;
	return ;
}
int mn[N],mx[N],id[N];
int pre[N],suf[N];
int add[N],sub[N];
inline bool Cmp(int x,int y){
	return deg[x]<deg[y];
}
inline void GetAns(){
	for(int i=0;i<=n-1;i++)
		mn[i]=n+1,mx[i]=0;
	for(int i=1;i<=n;i++)
		id[i]=i;
	sort(id+1,id+n+1,Cmp);
	int tot=0,cnt=0;
	for(int i=1;i<=n;i++){
		Cmax(mx[deg[id[i]]],i);
		Cmin(mn[deg[id[i]]],i);
		tot+=deg[id[i]];
		cnt++;
		pre[i]=suf[i]=(tot==cnt*(cnt-1)/2);
		add[i]=(tot+1==cnt*(cnt-1)/2);
		sub[i]=(tot-1==cnt*(cnt-1)/2);
	}
	for(int i=1;i<=n;i++)
		pre[i]+=pre[i-1];
	suf[n+1]=0;
	for(int i=n;i;i--)
		suf[i]+=suf[i+1];
	for(int i=1;i<=n;i++){
		add[i]+=add[i-1];
		sub[i]+=sub[i-1];
	}
	return ;
}
inline int GetAdd(int ll,int rr){
	return add[rr]-add[ll-1];
}
inline int GetSub(int ll,int rr){
	return sub[rr]-sub[ll-1];
}
//u++,v--
inline int Query(int u,int v){
	if(deg[u]<=deg[v]){
		if(deg[u]+1==deg[v]) return pre[n];
		if(deg[u]==deg[v]){
			int idu=mx[deg[u]];
			int idv=mn[deg[v]];
			return pre[idv-1]+suf[idu]+GetSub(idv,idu-1);
		}
		int idu=mx[deg[u]];
		int idv=mn[deg[v]];
		return pre[idu-1]+suf[idv]+GetAdd(idu,idv-1);
	}
	else{
		int idu=mn[deg[u]];
		int idv=mx[deg[v]];
		return pre[idv-1]+suf[idu]+GetSub(idv,idu-1);
	}
}
inline int Quick_Pow(int a,int b){
	int ss=1;
	for(;b;b>>=1){
		if(b&1) ss=1ll*ss*a%Mod;
		a=1ll*a*a%Mod;
	}
	return ss;
}
int ans;
inline void Solve(){
	ans=0;
	GetAns();
	for(int u=1;u<=n;u++){
		int pw=Quick_Pow(2,(u-2)*(u-1)/2);
		for(int v=1;v<u;v++){
			int ss;
			if(vis[u][v]) ss=Query(u,v);
			else ss=Query(v,u);
			ss=1ll*ss*pw%Mod;
			ans=(ans+ss)%Mod;
			pw=2*pw%Mod;
		}
	}
	return Print(ans);
}
int T;
#include<ctime>
int main(){
	//freopen("tournament.in","r",stdin);
	//freopen("tournament.out","w",stdout);
	//#define LOCAL
	#ifdef LOCAL
	int st=clock();
	#endif
	for(T=Read();T;T--){
		Init();
		Solve();
	}
	#ifdef LOCAL
	int en=clock();
	printf("cost %d ms\n",en-st);
	#endif
	return 0;
}