Chef and Maximum Sum Matrices

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Dreaming to manipulate the dimensions of spacetime one day, Chef satisfies himself with manipulating dimensions of abstract mathematical entities for now. Today, Chef has N lists consisting of integers. The i^{th} list is represented as L_{i}, and has size S_{i}.
Chef has transformed the given lists of integers to form an N dimensional matrix M of size S_{1} × S_{2} × S_{3} × … × S_{N} such that an entry j_{1}, j_{2}, j_{3}, … , j_{N} in the matrix M is obtained by taking product of given N integers L_{1}[j_{1}], L_{2}[j_{2}], L_{3}[j_{3}], ..., L_{N}[j_{N}], where L_{i}[j_{i}] denotes the j^{th} integer in the i^{th} list (1based indexing).
To explore the mathematics of the matrix M deeply, Chef wants to compute the maximum submatrix sum in this matrix; but he is afraid of its high dimensionality. So, he asked you to help him. He asked you to compute two quantities, the maximum submatrix sum in the matrix M, and the number of submatrices having this maximum sum.
Since the second answer to this problem can be very large, output it modulo 10^{9}+7.
Input
 First line of input contains a single integer T denoting the number of test cases.
 First line of each test case contains a single integer N denoting the number of lists of integers.
 Next N lines of each test case contains some space separated integers where integers in the i^{th} line make up the i^{th} list. Each list description has the following format.
 First integer S_{i} in the i^{th} line denotes the size of the i^{th} list, and
 the next S_{i} space separated integers are the elements in the list.
Output
For each test case, output 2 space separated integers (second integer modulo 10^{9} + 7) where the first integer denotes the maximum submatrix sum and the second denotes the number of such submatrices.
Constraints
 1 ≤ T ≤ 100
 1 ≤ N ≤ 9
 1 ≤ S_{i} ≤ 9
 9 ≤ L_{i}[j] ≤ 9
Example
Input
2 2 2 3 4 2 4 5 2 3 4 5 4 3 2 3 2 Output 63 1 12 2
Explanation
All the matrices with maximum sum are highlighted with coloured fencing.
Author:  ma5termind 
Tester:  antoniuk1 
Editorial  http://discuss.codechef.com/problems/MXSM 
Tags  adhoc, cook66, easymedium, greedy, ma5termind 
Date Added:  10112015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 