If we assume that cell \((i,j)\) has an integer \(A_{i,j}10^{2N-i-j}\) written on it instead of a digit \(A_{i,j}\), the score becomes the sum of the integers written on each cell modulo \(M\). So from now on, we assume that an integer \(A_{i,j}10^{2N-i-j}\) is written on cell \((i,j)\) instead of digit \(A_{i,j}\).

Notice that when the piece travels from cell \((1,1)\) to cell \((N,N)\), it always visits exactly one of cells \((1,N),(2,N-1),\ldots,(N,1)\).

If the piece passes through cell \((k,N+1-k)\), then the score is the sum of the following two values, modulo \(M\):

• the sum of the integers written on the cells visited while traveling from cell \((1,1)\) to cell \((k,N+1-k)\) (including cell \((k,N+1-k)\)) \(\ldots(\text{A})\)
• the sum of the integers written on the cells visited while traveling from cell \((k,N+1-k)\) to cell \((N,N\)) (excluding cell \((k,N+1-k)\)) \(\ldots(\text{B})\)

Let \(S_1\) be the set of the possible values for \((\text{A})\) modulo \(M\), and \(S_2\) be the set of the possible values for \((\text{B})\) modulo \(M\). Then the maximum score is \(\displaystyle \max_{x\in S_1,y\in S_2}((x+y)\ \text{mod}\ M)\).

If we fix \(x\in S_1\), the value \(y\in S_2\) that maximizes \((x+y)\ \text{mod}\ M\) is the maximum element among \(S_2\) that is strictly less than \(M-x\) (or the maximum element if there is no such \(y\)). Such an \(y\) can be found fast enough with binary search.

By applying this algorithm for all \(1\le k\le N\), the problem can be solved. The time complexity is \(O(N2^N)\).

Sample code (Python 3)

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)