AT_abc402_f.[ABC402F] Path to Integer

有一个 $N$ 行 $N$ 列的网格。从上往下第 $i$ 行、从左往右第 $j$ 列的格子记作格子 $(i,j)$。每个格子上都写有 1 到 9 的数字，格子 $(i,j)$ 上写的数字是 $A_{i,j}$。

初始时，棋子位于格子 $(1,1)$。同时，设 $S$ 为空字符串，接下来进行 $2N-1$ 次操作：

1. 将当前棋子所在格子的数字追加到 $S$ 的末尾。
2. 将棋子向右或向下移动一格（第 $2N-1$ 次操作时不移动）。

$2N-1$ 次操作后，棋子将位于格子 $(N,N)$，且 $S$ 的长度为 $2N-1$。

将最终得到的字符串 $S$ 视为整数，其值对 $M$ 取模的结果即为得分。

请计算可以获得的最高得分。

输入通过标准输入给出，格式如下：

$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 \leq N \leq 20$
• $2 \leq M \leq 10^9$
• $1 \leq A_{i,j} \leq 9$
• 输入中的所有数值均为整数

样例解释 1

棋子的移动方式有以下两种：

1. 按 $(1,1)\rightarrow(1,2)\rightarrow(2,2)$ 的顺序移动。此时 $S=$ 121，得分为 $121 \bmod 7 = 2$。
2. 按 $(1,1)\rightarrow(2,1)\rightarrow(2,2)$ 的顺序移动。此时 $S=$ 131，得分为 $131 \bmod 7 = 5$。

最高得分为 5，因此输出 5。

翻译由 DeepSeek V3 完成