Đường đi tối ưu (Optimal Path)

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho một bảng số gồm $N$ dòng và $M$ cột. Ô ở dòng $i$, cột $j$ chứa số nguyên $A_{i,j}$.

Một đường đi bắt đầu tại ô $(1,1)$ và kết thúc tại ô $(N,M)$. Từ một ô, chỉ được đi sang ô ngay bên phải hoặc ô ngay phía dưới.

Giá trị của một đường đi là tổng các số trên tất cả các ô mà đường đi đi qua. Hãy xác định:

• Giá trị lớn nhất có thể đạt được.
• Số đường đi đạt đúng giá trị lớn nhất đó, lấy modulo $10^9+7$.

Input

• Dòng đầu chứa hai số nguyên dương $N,M$.
• $N$ dòng tiếp theo, mỗi dòng chứa $M$ số nguyên; số thứ $j$ trên dòng thứ $i$ là $A_{i,j}$.

Output

In hai số nguyên cách nhau bởi một dấu cách: giá trị lớn nhất của đường đi và số đường đi đạt giá trị đó modulo $10^9+7$.

Subtask

• 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$.

Ví dụ

Ví dụ 1

Input

3 3
1 2 3
4 5 6
7 8 9

Output

29 1

Giải thích

Đường đi tối ưu đi qua các giá trị $1,4,7,8,9$, có tổng $29$. Không có đường đi khác đạt tổng này nên số cách là $1$.

Ví dụ 2

Input

2 2
1 1
1 1

Output

3 2

Giải thích

Có hai đường đi: phải rồi xuống, hoặc xuống rồi phải. Cả hai đều đi qua ba ô có giá trị $1$, nên cùng đạt tổng $3$.

Ví dụ 3

Input

2 3
1 5 1
1 1 5

Output

12 2

Giải thích

Có ba đường đi từ $(1,1)$ đến $(2,3)$. Hai trong số đó đạt tổng lớn nhất $12$, nên kết quả là 12 2.