棋盘可以看成一个N*M 的网格.棋子可以摆放在任何一个格子里,而不是网格线的交叉点上.现将一个棋子放在了左上角的格子上,棋子只会向右或者向下移动.每个格子有一个权值,请问,从左上角到右下角的所有路径中:
1.经过的格子的权值和最大是多少?
2.权值和最大的路径一共有多少条?
第一行两个整数NM. 接下来N 行,每行M 个整数,表示每个格子的权值.
Aij 表示第i 行第j 列格子的权值.
30%的数据保证,N≤5,M≤5.
60%的数据保证,N≤100,M≤100.
另有20%的数据保证,对于任意的i 和j,Aij = 1.
输出两行,第一行表示最大权值和,第二行表示权值和最大的路径数除以 1e9+7 的余数.