マス \((i,j)\) に数字 \(A_{i,j}\) ではなく整数 \(A_{i,j}10^{2N-i-j}\) が書かれているとすると、スコアはコマが通ったマスに書かれている整数の総和を \(M\) で割ったあまりとなります。以降はマス \((i,j)\) に数字 \(A_{i,j}\) ではなく整数 \(A_{i,j}10^{2N-i-j}\) が書かれているとします。

コマをマス \((1,1)\) からマス \((N,N)\) へ動かす際に、マス \((1,N),(2,N-1),\ldots,(N,1)\) のどれかちょうど \(1\) つを必ず通ることに着目します。

コマがマス \((k,N+1-k)\) を通るとすると、スコアは

• マス \((1,1)\) からマス \((k,N+1-k)\) へ到達するまでにコマが通ったマスに書かれた整数の総和（マス \((k,N+1-k)\) を含む）\(\ldots(\text{A})\)
• マス \((k,N+1-k)\) からマス \((N,N)\) へ到達するまでにコマが通ったマスに書かれた整数の総和（マス \((k,N+1-k)\) を含まない）\(\ldots(\text{B})\)

の \(2\) つの値の和を \(M\) で割ったあまりとなります。

\((\text{A})\) としてあり得る値を \(M\) で割ったあまりの集合を \(S_1\) 、 \((\text{B})\) としてあり得る値を \(M\) で割ったあまりの集合を \(S_2\) とすると、スコアの最大値は \(\displaystyle \max_{x\in S_1,y\in S_2}((x+y)\ \text{mod}\ M)\) となります。

ここで、 \(x\in S_1\) を固定すると、 \((x+y)\ \text{mod}\ M\) を最大化する \(y\in S_2\) は \(S_2\) の \(M-x\) 未満の最大の要素です（そのような \(y\) が存在しない場合は \(S_2\) の最大の要素）。このような \(y\) は二分探索で高速に求めることができます。

以上のアルゴリズムを全ての \(1\le k\le N\) に対して適用することで答えを求めることができます。計算量は \(O(N2^N)\) 時間です。

実装例(Python3)

from bisect import bisect_left

n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
for i in range(n):
    for j in range(n):
        a[i][j] *= pow(10, n - 1 - i + n - 1 - j, m)
        a[i][j] %= m
nn = 1 << (n - 1)
g1 = [[] for _ in range(n)]
for bit in range(nn):
    s = 0
    x, y = 0, 0
    for i in range(n - 1):
        s += a[x][y]
        if (bit >> i) & 1:
            x += 1
        else:
            y += 1
    s += a[x][y]
    s %= m
    g1[x].append(s)
g2 = [[] for _ in range(n)]
for bit in range(nn):
    s = 0
    x, y = n - 1, n - 1
    for i in range(n - 1):
        s += a[x][y]
        if (bit >> i) & 1:
            x -= 1
        else:
            y -= 1
    s %= m
    g2[x].append(s)
ans = 0
for r1, r2 in zip(g1, g2):
    r2.sort()
    for v in r1:
        idx = bisect_left(r2, m - v) - 1
        ans = max(ans, (v + r2[idx]) % m)
print(ans)