Time Limit: 12000/6000 MS (Java/Others)

Memory Limit: 131072/131072 K (Java/Others)

A graph $G$ with $n\times m$ nodes forms a $n\times m$ grid with $n\times m$ vertices.

$(n-1)\times m$ weighted edges connect the vertices of adjacent rows, and $n\times(m-1)$ weighted edges connect the vertices of adjacent columns.

A spanning tree of graph $G$ is a subgraph that is a tree and connects all the vertices together.

A minimum spanning tree (MST) or minimum weight spanning tree is then a spanning tree with weight less than or equal to the weight of every other spanning tree.

Graph $G$ has many different minimum spanning trees.

For each MST $T$, the $LRdeg(u)$ of node $u$ is defined as the number of nodes, in the previous column or the previous row connecting with $u$, plus one.

And we define $\tau(T)=\prod_u LRdeg(u)$ as the product of $LRdeg(u)$ for all nodes.

Your mission is to find the weight of the minimum spanning tree of graph $G$, and count $\tau(T)$ of all minimum spanning trees. Two MST(s) are considered different if they contain different subsets of edges.

$(n-1)\times m$ weighted edges connect the vertices of adjacent rows, and $n\times(m-1)$ weighted edges connect the vertices of adjacent columns.

A spanning tree of graph $G$ is a subgraph that is a tree and connects all the vertices together.

A minimum spanning tree (MST) or minimum weight spanning tree is then a spanning tree with weight less than or equal to the weight of every other spanning tree.

Graph $G$ has many different minimum spanning trees.

For each MST $T$, the $LRdeg(u)$ of node $u$ is defined as the number of nodes, in the previous column or the previous row connecting with $u$, plus one.

And we define $\tau(T)=\prod_u LRdeg(u)$ as the product of $LRdeg(u)$ for all nodes.

Your mission is to find the weight of the minimum spanning tree of graph $G$, and count $\tau(T)$ of all minimum spanning trees. Two MST(s) are considered different if they contain different subsets of edges.

The input contains several test cases. The first line of the input is a single integer $t~(1\le t\le 32)$ which is the number of test cases. Then $t$ test cases follow.

For each test case, the first line contains the two integers $n~(1\le n\le 800)$ and $m~(1\le m\le 7)$.

Each line of the next $n$ lines contains $m-1$ integers, which describe the weights of edges connecting the vertices of adjacent columns.

And each line of the next $n-1$ lines contains $m$ integers, which describe the weights of edges connecting the vertices of adjacent rows. The weights of edges are no more than $10$.

For each test case, the first line contains the two integers $n~(1\le n\le 800)$ and $m~(1\le m\le 7)$.

Each line of the next $n$ lines contains $m-1$ integers, which describe the weights of edges connecting the vertices of adjacent columns.

And each line of the next $n-1$ lines contains $m$ integers, which describe the weights of edges connecting the vertices of adjacent rows. The weights of edges are no more than $10$.

For each test case, you should output two integers in one line. The first one is the weight of the minimum spanning tree.

The second one is the sum of $\tau(T)$ for all different minimum spanning trees, modulo $10^9+7$.

The second one is the sum of $\tau(T)$ for all different minimum spanning trees, modulo $10^9+7$.

提交代码