定义一个长为 $n$ 的排列 $p_1,p_2,\dots,p_n$ 是好的，当且仅当排列中不存在一组 $1\leq i_1<i_2<i_3<i_4\leq n$，使得 $p_{i_3}<p_{i_1}<p_{i_4}<p_{i_2}$ 或 $p_{i_2}<p_{i_4}<p_{i_1}<p_{i_3}$。

$cats$ 有 $n$ 个集合 $S_1,S_2,\dots,S_n$，其中每个集合 $S_i$ 都是 $1,2,\dots,n$ 的子集。现在，$cats$ 想知道有多少长为 $n$ 的好的排列 $p_1,p_2,\dots,p_n$，使得对于任意的 $1\leq i\leq n$，都有 $p_i\in S_i$。由于答案可能很大，你只需要输出答案对 $10^9+7$ 取模的结果。

输入格式

第一行包含一个整数 $T$ $(1\leq T\leq 1000)$，表示一共有 $T$ 组测试数据。

对于每组测试数据：

第一行为一个整数 $n$ $(1\leq n\leq 100)$，表示排列的长度。

接下来 $n$ 行，每行为一个长度为 $n$ 的 $01$ 字符串，表示第 $i$ 个集合 $S_i$。其中第 $i$ 行第 $j$ 个字符为 $0$ 代表 $j\notin S_i$，第 $i$ 行第 $j$ 个字符为 $1$ 代表 $j\in S_i$。

保证所有测试数据的 $n^3$ 之和不超过 $5\cdot 10^6$。

输出格式

对于每组测试数据，输出一个整数，表示所有满足条件的排列 $p$ 的总数对 $10^9+7$ 取模的结果。

样例

输入

4
1
1
4
1111
1111
1111
1111
5
11111
10001
10101
10001
11111
13
1111110111111
1111111111111
0111110101111
1111111111011
1111110011111
1111111111111
1011110111011
1111100011111
1111101111111
1110111111111
1100111111111
1111111011101
1111101111111

输出

1
22
2
4045764