#include<bits/stdc++.h>
#define MAXN (5005)
#define ll long long
using namespace std;
const int mod=1000000007;
void File()
{
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
}
template<typename type>
void read(type &x)
{
    bool f=0;char ch=0;x=0;
    while(ch<'0'||ch>'9'){f|=!(ch^'-');ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    x=f?-x:x;
}
template<typename type,typename... Args>
void read(type &x,Args &... args)
{
    read(x);
    read(args...);
}
bool vis[MAXN][MAXN];
char str[MAXN];
int test,n,s,t,scnt,pw,ans;
int deg[MAXN],sum[MAXN],pre[MAXN][MAXN],posl[MAXN],posr[MAXN];
void solve()
{
    read(n);
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) vis[i][j]=0,pre[i][j]=0;
    for(int i=0;i<=n;i++) posl[i]=posr[i]=0;
    for(int i=2,m;i<=n;i++)
    {
        scanf("%s",str+1);
        m=(i+2)>>1;
        for(int j=1,x;j<=m;j++)
        {
            x=isdigit(str[j])?(str[j]^48):(str[j]-'A'+10);
            for(int k=0,p;k<4;k++)
            {
                p=(j<<2)+k-3;
                if(p>=i) break;
                if((x>>k)&1) vis[i][p]=1;
                else vis[p][i]=1;
            }
        }
    }
    for(int i=1;i<=n;i++) deg[i]=0;
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) deg[i]+=vis[i][j];
    for(int i=1;i<=n;i++) sum[i]=deg[i];
    sort(sum+1,sum+n+1);
    scnt=0;
    for(int i=1;i<=n;i++)
    {
        sum[i]+=sum[i-1];
        if(sum[i]==i*(i-1)/2) ++scnt;
    }
    for(int l=1,x,y;l<=n;l++)
    {
        x=y=scnt;
        for(int r=l;r<n;r++)
        {
            x+=(sum[r]-1==r*(r-1)/2)-(sum[r]==r*(r-1)/2);
            y+=(sum[r]+1==r*(r-1)/2)-(sum[r]==r*(r-1)/2);
            pre[l][r+1]=x,pre[r+1][l]=x;
        }
    }
    for(int i=n;i;i--) posl[sum[i]-sum[i-1]]=i;
    for(int i=1;i<=n;i++) posr[sum[i]-sum[i-1]]=i;
    pw=1,ans=0;
    for(int i=1,x,y,res;i<=n;i++)
    {
        for(int j=1;j<i;j++)
        {
            x=i,y=j;
            if(vis[y][x]) swap(x,y);
            res=(deg[x]==deg[y]+1)?scnt:pre[posl[deg[x]]][posr[deg[y]]];
            ans=(ans+1ll*pw*res)%mod;
            pw=2ll*pw%mod;
        }
    }
    printf("%d\n",ans);
}
int main()
{
#ifndef ONLINE_JUDGE
    File();
#endif
    read(test);
    for(int i=1;i<=test;i++) solve();
}