/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 525 点
問題文
N 行 N 列のグリッドがあります。上から i 行目、左から j 列目のマスをマス (i,j) と表します。各マスには 1 から 9 までの数字が書かれており、マス (i,j) には数字 A_{i,j} が書かれています。
はじめ、コマがマス (1,1) にあります。また、 S を空文字列とし、以下の操作を 2N-1 回繰り返します：
- S の末尾に現在コマが存在するマスに書かれた数字を連結する。
- コマを現在のマスの下か右に 1 マス移動する。ただし、 2N-1 回目の操作では移動させない。
2N-1 回の操作の後、コマはマス (N,N) に存在し、 S の長さは 2N-1 となります。
最終的な文字列 S を整数としてみた値を M で割ったあまりがスコアとなります。
達成可能なスコアの最大値を求めてください。
制約
- 1\le N\le 20
- 2\le M\le 10^9
- 1\le A_{i,j}\le 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
コマの動かし方は以下の 2 通りがあります：
- コマを (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
Score : 525 points
Problem Statement
There is an N\times N grid. Let cell (i,j) denote the cell in the i-th row from the top and j-th column from the left. Each cell contains a digit from 1 to 9; cell (i,j) contains A_{i,j}.
Initially, a token is on cell (1,1). Let S be an empty string. Repeat the following operation 2N-1 times:
- Append to the end of S the digit in the current cell.
- Move the token one cell down or one cell to the right. However, do not move it in the (2N-1)-th operation.
After 2N-1 operations, the token is on cell (N,N) and the length of S is 2N-1.
Interpret S as an integer. The score is the remainder when this integer is divided by M.
Find the maximum achievable score.
Constraints
- 1 \leq N \leq 20
- 2 \leq M \leq 10^9
- 1 \leq A_{i,j} \leq 9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
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}
Output
Print the answer.
Sample Input 1
2 7 1 2 3 1
Sample Output 1
5
There are two ways to move the token:
- Move through (1,1),(1,2),(2,2). Then S=
121, and the score is the remainder when 121 is divided by 7, which is 2. - Move through (1,1),(2,1),(2,2). Then S=
131, and the score is the remainder when 131 is divided by 7, which is 5.
The maximum score is 5, so print 5.
Sample Input 2
3 100000 1 2 3 3 5 8 7 1 2
Sample Output 2
13712
Sample Input 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
Sample Output 3
384