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 $ 回繰り返します： - $ S $ の末尾に現在コマが存在するマスに書かれた数字を連結する。 - コマを現在のマスの下か右に $ 1 $ マス移動する。ただし、 $ 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} $

答えを出力せよ。

### Sample Explanation 1 コマの動かし方は以下の $ 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 $ を出力してください。 ### Constraints - $ 1\le N\le 20 $ - $ 2\le M\le 10^9 $ - $ 1\le A_{i,j}\le 9 $ - 入力される値は全て整数である