#P9899. Almost Acyclic

    ID: 8121 传统题 10000ms 512MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>CF3000状压DP组合数学矩阵图论2023“钉耙编程”中国大学生算法设计超级联赛(10)

Almost Acyclic

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)G=(V,E) with nn vertices. Each edge (i,j)(i,j) has a weight wi,jw_{i,j}. Calculate (f(G)f(G) is 11 if GG is almost-acyclic, or 00 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 TT (1≤T≤161\le T\le 16), denoting the number of test cases. For each test case, the first line contains an integer nn (1≤n≤161\le n\le 16). The next nn lines each contains nn integers. The jj-th number in the ii-th line denotes wi,jw_{i,j} (0≤wi,j<109+70\le w_{i,j}<10^9+7). It is guaranteed that wi,j=wj,iw_{i,j}=w_{j,i}, wi,i=0w_{i,i}=0. It is guaranteed that for each 1≤i≤161\le i\le 16, there is at most one test case satisfying n=in=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)