Problem Description

We call a **connected** undirected graph _almost-acyclic_, if the graph has no cycles, or all the simple cycles in it share at least one common point.

You are given a complete undirected graph $G=(V,E)$ with $n$ vertices. Each edge $(i,j)$ has a weight $w_{i,j}$. Calculate ($f(G)$ is $1$ if $G$ is almost-acyclic, or $0$ otherwise):

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

Input

The first line contains a single integer $T$ ($1\le T\le 16$), denoting the number of test cases.

For each test case, the first line contains an integer $n$ ($1\le n\le 16$).

The next $n$ lines each contains $n$ integers. The $j$-th number in the $i$-th line denotes $w_{i,j}$ ($0\le w_{i,j}<10^9+7$).

It is guaranteed that $w_{i,j}=w_{j,i}$, $w_{i,i}=0$.

It is guaranteed that for each $1\le i\le 16$, there is at most one test case satisfying $n=i$.

Output

For each test case, output one line with an integer denoting the answer.

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

7
120