Maniacal Midsummer Marathon 2014 by AL, TL, JJ

Dorian loves pies, and he especially loves his local pie shop - that's why he's bought an all-you-can-eat pie dinner! The pies have been arranged into a grid with $R$ rows and $C$ columns $(1\le R,C\le 16)$. The pie in row $i$ and column $j$ has a tastiness value $t_{i,j}$ $(0\le t_{i,j}\le 1000)$. Dorian is a messy eater, and whenever he eats a pie, he destroys all pies adjacent to it. He would like to maximize the sum of the tastiness values of the pies he eats, and also figure out how many ways he can achieve this sum.

Two pies respectively located at $(r_1,c_1)$ and $(r_2$, $c_2)$ are adjacent if they are exactly $1$ unit of distance apart; that is, $|r_1-r_2|+|c_1-c_2|=1$.

Input Specification

The first line contains two space-separated integers $R$ and $C$.
The next $R$ lines each contain $C$ space-separated integers representing the tastiness values of the pies.

Output Specification

A single line containing two space-separated integers: the maximum possible sum and the number of ways to reach this sum. Since the number of ways may be very large, you should give the value modulo $1000000007$ (${10}^9+7$).

Sample Input 1

3 4
1 2 3 1
5 7 2 1
1 4 1 0

Sample Output 1

14 3

Sample Input 2

3 3
1 1 0
0 0 1
1 1 0

Sample Output 2

3 5

Scoring

If your output is incorrectly formatted, then your program will score $0$ points.
Otherwise, if you correctly determine the first number but not the second, then your program will score $40\mathrm{\%}$ of points for the test case.
If both numbers are correct, then you will receive $100\mathrm{\%}$ of points for the test case.

Subtask	Score	Constraints
$1$	$30\mathrm{\%}$	$R=1$
$2$	$30\mathrm{\%}$	$R\le 10$
$3$	$40\mathrm{\%}$	No additional restrictions.