AT_abc402_f [ABC402F] Path to Integer

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.

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

Print the answer.

### Sample Explanation 1 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 $ . ### Constraints - $ 1 \leq N \leq 20 $ - $ 2 \leq M \leq 10^9 $ - $ 1 \leq A_{i,j} \leq 9 $ - All input values are integers.