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