Given a matrix of ~n~ rows and ~m~ columns numbered from top to bottom, left to right, each cell in the matrix is a random number whose absolute value does not exceed ~10^9~. From the upper left position, find a path to the lower right corner position so that the number of squares to go through is minimal (each move only goes to the square with a common edge). Among those ways, find a way to maximize the sum of the values of the cells on the path and how many path have the same maximum sum.

Input

• The first line is ~2~ integers ~n~, ~m~ (~n~, ~m \leq 2 \times 10^3~).
• The ~i~th line of the next ~n~ lines contains ~m~ space-separated integers. The ~j~th value in line ~i~ corresponds to the ~a_{ij}~ value in the matrix(~|a| \leq 10^9~).

Output

• The first integer is the total value of the path, the second is the number of paths as described. (the 2nd number should be remainder after dividing by ~10^7~)

Example Input 1

6 4
12 11 -12 11
12 11 10 12
-11 11 -10 -10
12 -10 -11 10
11 11 11 -10
12 -11 12 12

Example Output 1

82 2