分数: 525 点
问题陈述
有一个 N\times N 网格。让细胞 (i,j) 表示中的单元格 i从顶部算起的第行和 j左起第 列。每个单元格包含一个数字 1 to 9;细胞 (i,j) 包含 A_{i,j}.
最初,令牌位于单元格上 (1,1)。让 S 是一个空字符串。重复以下操作 2N-1 次:
- 追加到末尾 S 当前单元格中的数字。
- 将标记向下移动一个单元格或向右移动一个单元格。但是,请勿在 (2N-1)-第次操作。
之后 2N-1 操作,令牌位于单元格上 (N,N) 和长度 S is 2N-1.
解释 S 作为整数。分数是该整数除以的余数 M.
找到可达到的最高分数。
约束
- 1 \leq N \leq 20
- 2 \leq M \leq 10^9
- 1 \leq A_{i,j} \leq 9
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M
A_{1,1} A_{1,2} \ldots A_{1,N}
A_{2,1} A_{2,2} \ldots A_{2,N}
\vdots
A_{N,1} A_{N,2} \ldots A_{N,N}
输出
打印答案。
示例输入 1
2 7 1 2 3 1
示例输出 1
5
移动令牌有两种方法:
- 移过 (1,1),(1,2),(2,2)。然后 S=
121,得分为以下情况下的余数: 121 除以 7,即 2. - 移过 (1,1),(2,1),(2,2)。然后 S=
131,得分为以下情况下的余数: 131 除以 7,即 5.
最高分数为 5,所以打印 5.
示例输入 2
3 100000 1 2 3 3 5 8 7 1 2
示例输出 2
13712
示例输入 3
5 402 8 1 3 8 9 8 2 4 1 8 4 1 8 5 9 6 2 1 6 7 6 6 7 7 6
示例输出 3
384