西洋棋盘
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
问题说明
西洋棋盘可以看成一个 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。