← 返回题目列表

AtCoder · abc402_f

I. 整数路径

中文机器翻译题面 查看原题

分数: 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