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.
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, 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$.