Optimal Path

Version: Phuoc Hung OJ Extended

Problem Statement

You are given an $N$ by $M$ integer grid. Cell $(i,j)$ contains the integer $A_{i,j}$.

A path starts at $(1,1)$ and ends at $(N,M)$. From a cell, you may move only one cell to the right or one cell downward.

The value of a path is the sum of all cell values on it. Determine:

• The maximum possible path value.
• The number of paths attaining exactly that maximum, modulo $10^9+7$.

Input

• The first line contains two positive integers $N,M$.
• The next $N$ lines each contain $M$ integers; the $j$-th number on row $i$ is $A_{i,j}$.

Output

Print two integers separated by one space: the maximum path value and the number of optimal paths modulo $10^9+7$.

Subtasks

• Subtask 1 (30%): $1 \le N,M \le 8$, $A_{i,j}>0$.
• Subtask 2 (30%): $1 \le N,M \le 200$, $|A_{i,j}| \le 10^9$.
• Subtask 3 (40%): $1 \le N,M \le 1000$, $|A_{i,j}| \le 10^9$.

Examples

Example 1

Input

3 3
1 2 3
4 5 6
7 8 9

Output

29 1

Explanation

The optimal path visits values $1,4,7,8,9$, with sum $29$. No other path reaches this sum, so the number of optimal paths is $1$.

Example 2

Input

2 2
1 1
1 1

Output

3 2

Explanation

There are two paths: right then down, or down then right. Both visit three cells of value $1$, so both have sum $3$.

Example 3

Input

2 3
1 5 1
1 1 5

Output

12 2

Explanation

There are three paths from $(1,1)$ to $(2,3)$. Exactly two of them attain the maximum sum $12$, so the answer is 12 2.