3160: 对布满灰尘的西洋棋宣告将军
内存限制：256 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：5
解决：2
题目描述
维多利加：这里的确有许多书，但是…… 这里没有你。
【问题描述】 布洛瓦侯爵想利用维多利加来占卜二战的局势。侯爵只给了她一盘西洋棋和 许多书，便将她关在了王宫的地牢。 西洋棋盘可以看成一个 N*M 的网格。西洋棋可以摆放在任何一个格子里， 而不是网格线的交叉点上。 维多利加将一个棋子放在了左上角的格子上。她试着移动这个棋子，棋子只 会向右或者向下移动。 每个格子有一个权值，维多利加想知道，从左上角到右下角的所有路径中： 1.经过的格子的权值和最大是多少？ 2.权值和最大的路径一共有多少条？
输入
第一行两个整数 N,M。 接下来 N 行，每行 M 个整数，表示每个格子的权值。
输出
输出两行，第一行表示最大权值和，第二行表示权值和最大的路径数除以 1e9+7 的余数。
样例输入 复制
3 3
1 1 1
1 1 2
1 1 1 样例输出 复制
6
4
提示
【数据范围】 Ai,j 表示第 i 行第 j 列格子的权值。 30%的数据保证，N≤5，M≤5。 60%的数据保证，N≤100，M≤100。 另有 20%的数据保证，对于任意的 i 和 j，Ai,j = 1。 100%的数据保证，N≤2000，M≤2000，|Ai,j|≤10^9。