如果一个连通无向图没有环，或者其中所有的简单环都至少共享一个公共点，我们称该图为“几乎无环的”（almost-acyclic）。

给定一个包含 $n$ 个顶点的完全无向图 $G = (V, E)$。每条边 $(i, j)$ 都有一个权重 $w_{i,j}$。计算下式（其中若 $G$ 是几乎无环的，则 $f(G) = 1$，否则 $f(G) = 0$）：

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

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 16$)，表示测试用例的数量。 对于每个测试用例，第一行包含一个整数 $n$ ($1 \le n \le 16$)。 接下来的 $n$ 行，每行包含 $n$ 个整数。第 $i$ 行的第 $j$ 个数表示 $w_{i,j}$ ($0 \le w_{i,j} < 10^9 + 7$)。 保证 $w_{i,j} = w_{j,i}$ 且 $w_{i,i} = 0$。 保证对于每个 $1 \le i \le 16$，满足 $n = i$ 的测试用例最多只有一个。

输出格式

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

样例

输入 1

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
1 1 1 0 1
1 1 0 1 0

输出 1

7
120