Almost Acyclic

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.

Sample Input

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

Sample Output

7
120

Source

2023“钉耙编程”中国大学生算法设计超级联赛（10）