几乎无环图

中文题目为机翻，原题目请参考英文题面

我们称连通无向图为几乎无环图，如果图中没有环，或者所有的简单环至少有一个共同点。

给你一个完整的无向图 $G=(V,E)$，有 $n$ 个顶点。每条边 $(i,j)$ 有一个权值 $w_{i,j}$ 。计算 （如果 $G$ 几乎是无环的，则 $f(G)$ 为 $1$，否则为 $0$ ）:

$$\sum_{E'\subseteq E,\: G'=(V,E')} f(G') \prod_{(i,j) \in E'} w_{i,j} \bmod 10^9+7 $$

输入

第一行包含一个整数 $T \: (1\leq T \leq 16)$，表示测试用例的数量。

对于每个测试用例，第一行包含一个整数 $n \: (1\leq n \leq 16)$ 。

接下来的 $n$ 行每行包含 $n$ 个整数。$i$ 第一行中的 $j$ 表示 $w_{i,j} \: (0 \leq w_{i,j} < 10^9+7)$ 。

可以保证 $w_{i,j} \: = w_{j,i}$ , $w_{i,i} = 0$ 。

可以保证，对于每个 $1 \leq i \leq 16$，最多有一个测试用例满足 $n = i$ 。

输出

对于每个测试用例，输出一行带有表示答案的整数。

样例

2
3
0 1 2
1 0 1
2 1 0
5
0 1 0 1 1
1 0 1 1 1
0 1 0 1 0
11 11 10 1
1 1 0 1 0

7
120