Problem Description
A graph G with n×m nodes forms a n×m grid with n×m vertices.
(n−1)×m weighted edges connect the vertices of adjacent rows, and n×(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 τ(T)=∏uLRdeg(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 τ(T) of all minimum spanning trees. Two MST(s) are considered different if they contain different subsets of edges.
Input
The input contains several test cases. The first line of the input is a single integer t (1≤t≤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≤n≤800) and m (1≤m≤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.
Output
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 τ(T) for all different minimum spanning trees, modulo 109+7.
Sample Input
2
2 5
9 8 5 6
4 6 2 3
1 7 8 3 8
5 5
8 10 5 4
1 7 7 7
5 4 5 5
3 2 2 2
8 7 8 3
8 5 7 8 6
10 3 2 4 3
8 7 2 8 9
9 4 8 3 9
Sample Output
Case #1: 37 288
Case #2: 96 4478976
