P1007：杭电/2025-6/1006 缺失的子序列

题目描述

定义一个长度为 $n$ 的排列 $p_1,p_2,\dots,p_n$ 是好的，当且仅当排列中不存在一组 $1 \le i_1 < i_2 < i_3 < i_4 \le 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 \le i \le n$，都有 $p_i \in S_i$。由于答案可能很大，你只需要输出答案对 $10^9 + 7$ 取模的结果。

输入输出格式

输入

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

对于每组测试数据：

第一行为一个整数 $n\ (1 \le n \le 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$。

输出

对于每组测试数据，输出一行，包含一个整数，表示满足条件的排列个数对 $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
1111110111011
1111101111111

1
22
2
4045764

数据范围

• $1 \le T \le 1000$
• $1 \le n \le 100$
• $\sum n^3 \le 5\cdot 10^6$