You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

问题说明

西洋棋盘可以看成一个 N*M 的网格。西洋棋可以摆放在任何一个格子里，而不是网格线的交叉点上。 小雨将一个棋子放在了左上角的格子上。他试着移动这个棋子，棋子只会向右或者向下移动。 每个格子有一个权值，小雨想知道，从左上角到右下角的所有路径中：1.经过的格子的权值和最大是多少？ 2.权值和最大的路径一共有多少条？

输入格式

第一行两个整数 N,M。 接下来N行，每行M个整数，表示每个格子的权值。

输出格式

输出两行，第一行表示最大权值和，第二行表示权值和最大的路径数除以1000000007的余数。

3 3
1 1 1
1 2 1
1 1 1

6
4

数据范围

对于30%的数据，满足N≤5，M≤5。

对于60%的数据，满足N≤100，M≤100。

对于再20%的数据，满足每个格子权值为1。

对于100%的数据，满足N≤2000，M≤2000，|权值|≤10^9。