EIU Programming Practices and Exams

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<=2x10^3).

The ith line of the next n lines contains m space-separated integers. The jth value in line i corresponds to the aij value in the matrix(|a|<=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⁷)

Example

Input:
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

Output:
82 2