小 K 有一张含有 $n$ 个点的竞赛图。点的编号依次为 $1\sim n$。众所周知，竞赛图是一张有向图，满足 $\forall 1\le i < j \le n$，有向边 $i\to j$ 和 $j\to i$ 中恰好存在一条边。

小 K 在学习网络课程，这个课程的其中一项作业是将这个竞赛图传输到另外一台计算机上。但是传输时可能遇到了信号干扰，导致传输到新的计算机上的时候会有恰好 $1$ 条边的方向被反转。小 K 快速地解决了这个问题。但是小 K 很好奇，对于这一张给定的竞赛图，$\forall 1 \le i < j \le n$，如果连接 $i, j$ 的边方向被反转了，这一张新的竞赛图有多少个极大强连通分量。

输入格式

第一行一个数 $T$（$1 \le T \le 10\,000$）表示数据组数。

对于每组数据：

第一行一个数 $n$（$1 \le n \le 5000$）表示节点数。

接下来 $n-1$ 行，第 $i$ 行为一个长度为 $\left\lceil\frac i4\right\rceil$ 的字符串，其中第 $j$ 个字符为 $\sum_{k=0}^3 2^k E_{i+1, 4j+k-3}$ 对应的 $16$ 进制数（即 $10\sim 15$ 对应大写字母 $\texttt A \sim \texttt F$），其中 $E_{i,j}=1$ 当且仅当 $j < i$ 且 $i, j$ 之间的边的方向是从 $i$ 指向 $j$。

保证至多只有一组数据 $n > 10$。

输出格式

对于每组数据，输出一行一个数，即 $\sum_{i=1}^n \sum_{j=1}^{i-1} 2^{(i-2)(i-1)/2+j-1} ans_{i,j}$ 对 $10^9+7$ 取模的值，其中 $ans_{i,j}$ 表示 $i,j$ 之间的边翻转之后得到的竞赛图的极大强连通分量个数。

样例数据

样例输入

2
3
0
2
6
1
3
7
F
F1

样例输出

19
153406

样例解释

样例的第一组数据有 $3$ 个点，边集为 $\{(1, 2), (1, 3), (3, 2)\}$，$ans_{1,2} = 1$，$ans_{1,3} = ans_{2,3} = 3$。

数据范围

对于全部数据，$T \le 10\,000$，$1 \le n \le 5000$。

子任务 1（$20\%$）：$n \le 100$；

子任务 2（$20\%$）：$n \le 300$；

子任务 3（$20\%$）：$n \le 500$；

子任务 4（$20\%$）：$n \le 1500$；

子任务 5（$20\%$）：$n \le 5000$。