缺失的子序列

Problem Description

定义一个长为 $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$ 取模的结果。

Input

第一行包含一个整数 $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$。

Output

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

Sample Input

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

Sample Output

1
22
2
4045764

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（6）