题目描述

$Bob$ 正在研究“网格数字”问题，其中一种描述如下：

给定一个 $n\times n$ 的由 $1 \dots 9$ 构成的数字网格，从上往下第 $i$ 行 ，从左往右第 $j$ 列的数字是 $a_{i,j}$ .

$Bob$ 控制的机器人从 (1,1) 出发，向下或向右 走到 (n,n) 。机器人每到一个格子，$Bob$ 依次在纸上写下走过的这些数字，数字串的长度也就是机器人走到路径长度 $2n-1$。

$Bob$ 获得的奖励是这个数字取 $m$ 的余数，那么如何控制机器人使得 $Bob$ 获得最大的奖励。

注意：答案是余数最大，不是原始数字最大。

输入格式

输入格式如下：

$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}$

输出格式

一个整数，表示最大的奖励

2 7
1 2
3 1

5

样例1解释

有两条路线，一条路线是 (1,1),(1,2),(2,2) 走过的数字是 121 , 取 7 的余数是 2 ; 另一条路线是 (1,1),(2,1),(2,2) ,数字是 131, 余数是 5 ，答案就是 5 。

9 1000000000000000000
9 2 2 6 7 2 4 7 2 
4 9 6 8 5 9 7 5 4 
5 5 2 5 6 4 4 3 6 
5 8 6 7 4 2 1 4 2 
4 7 8 8 8 9 6 8 1 
8 8 1 1 6 2 6 8 3 
2 3 7 4 4 8 2 9 5 
4 8 2 3 1 2 2 1 1 
3 1 4 7 5 5 9 1 1 

94968597546213511

10 925638029
9 9 1 9 2 7 2 6 1 5 
4 4 2 1 9 1 6 9 7 8 
2 2 3 4 5 1 9 8 8 9 
7 4 3 2 5 5 4 7 3 4 
5 2 6 6 5 2 9 1 4 6 
6 6 9 2 9 4 5 9 9 3 
4 2 8 6 2 7 9 3 4 6 
2 6 9 6 1 6 9 5 9 8 
4 7 3 1 9 9 3 9 4 8 
8 6 4 9 8 4 4 2 3 1 

925368977

20 414290878
5 5 2 7 9 6 3 5 5 4 2 8 7 7 7 4 1 2 8 9 
6 1 1 9 5 5 6 1 4 6 2 3 4 7 6 4 8 8 8 8 
5 7 6 9 3 6 5 2 3 3 1 9 2 9 4 4 7 3 2 6 
9 4 1 2 3 8 2 3 3 1 2 1 1 1 3 1 7 2 9 3 
3 8 1 5 4 3 6 1 3 3 1 3 4 9 8 2 2 5 2 6 
2 9 2 9 7 7 6 9 8 8 2 9 2 1 8 7 9 7 1 3 
4 8 1 2 5 1 4 3 2 4 5 2 9 7 2 2 1 7 3 6 
9 7 7 9 1 6 6 8 4 2 5 8 9 7 6 1 5 1 9 2 
5 7 5 5 9 3 8 7 9 7 7 2 4 6 1 8 7 8 1 9 
8 1 4 6 9 2 3 7 8 9 5 2 9 5 7 9 5 1 9 2 
6 4 3 2 8 1 5 1 8 1 9 5 5 5 4 8 2 5 8 9 
4 4 3 7 6 9 6 2 8 4 6 2 8 5 8 3 2 6 8 8 
5 9 1 9 1 8 2 2 1 9 8 2 1 9 2 5 8 4 2 7 
9 7 4 3 5 8 9 9 3 5 7 1 9 2 1 5 4 8 9 2 
6 4 1 9 4 3 8 5 8 5 7 8 1 8 1 1 9 9 6 1 
1 8 5 9 6 5 1 1 2 2 5 6 3 3 7 8 3 2 4 1 
6 2 1 8 6 1 9 2 8 1 6 6 9 1 2 2 7 5 3 2 
1 9 6 6 7 6 6 3 5 2 5 3 5 5 7 1 1 7 9 9 
7 8 4 3 6 2 9 3 3 8 5 8 8 2 2 6 9 1 8 8 
6 5 9 7 5 1 9 4 6 5 1 3 7 5 2 5 2 8 5 4

414290876

数据规模与约定

所有数据满足：$2\le n \le 20 ,1\le m \le 10^{18}, 1\le a_{i,j} \le 9$

$Subtask1$ : $2\le n \le 9 ,m=10^{18}$ ,$10$ 分 (样例2)

$Subtask2$ : $2\le n \le 10$ ,$20$ 分 (样例3)

$Subtask3$ : $2\le n \le 20$ ,$70$ 分 (样例4)