Expert.
Put your skills to the test.

Problem summary

Count right/down paths from the top-left to bottom-right cell of a signed integer grid whose cell sum is divisible by P.

Constraints

2 ≤ N,M ≤ 20; 1 ≤ P ≤ 1000000; −1000000000 ≤ a[i][j] ≤ 1000000000.

Worked example

Official statement example.

3 3 7
1 2 3
4 5 6
7 8 9

1

Solution analysis

1. A complete path has N+M−2 moves, up to 38, so enumerating all paths is too expensive. Split after floor((N+M−2)/2) moves. Every path meets exactly one cell of that diagonal.
2. Enumerate all prefix paths to the diagonal and store their sums modulo P grouped by meeting cell. Enumerate suffix paths backward from the destination, including the meeting cell as well. Matching residues x and y must satisfy x+y−a[meeting] ≡ 0 mod P, because that cell was counted twice. Sort the prefix lists and count equal complements by binary search.
3. For the official example the qualifying route along the top row then down has sum 21. Its two halves meet at (1,3); prefix sum 6 and suffix sum 18 share cell value 3, giving 6+18−3=21.

Why it works

Splitting at a fixed move count uniquely decomposes each complete path into one enumerated prefix and one enumerated suffix meeting at the same cell. The complement condition is equivalent to divisibility of their combined sum. Counting all matching pairs therefore counts every qualifying path once and excludes every nonqualifying path.

Watch out. Normalize negative residues. Include the meeting cell in both halves and subtract it once. The answer needs 64 bits.

An independently written complete program with standard headers.

// Key idea: Splitting at a fixed move count uniquely decomposes each complete path into one enumerated
// prefix and one enumerated suffix meeting at the same cell. The complement condition is equivalent to
// divisibility of their combined sum.
#include<algorithm>
#include<functional>
#include<iostream>
#include<vector>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m,p;
    cin>>n>>m>>p;
    vector<vector<int>>a(n,vector<int>(m));
    for(auto&row:a){
        for(int&value:row){
            long long x;
            cin>>x;
            value=static_cast<int>((x%p+p)%p);
        }
    }
    int half=(n+m-2)/2;
    vector<vector<int>>prefix(n);
    function<void(int,int,int)>forward=[&](int r,int c,int sum){
        sum=(sum+a[r][c])%p;
        if(r+c==half){
            prefix[r].push_back(sum);
            return;
        }
        if(r+1<n){
            forward(r+1,c,sum);
        }
        if(c+1<m){
            forward(r,c+1,sum);
        }
    };
    forward(0,0,0);
    for(auto&values:prefix){
        sort(values.begin(),values.end());
    }
    long long answer=0;
    function<void(int,int,int)>backward=[&](int r,int c,int sum){
        sum=(sum+a[r][c])%p;
        if(r+c==half){
            int need=(a[r][c]-sum+p)%p;
            auto range=equal_range(prefix[r].begin(),prefix[r].end(),need);
            answer+=range.second-range.first;
            return;
        }
        if(r>0){
            backward(r-1,c,sum);
        }
        if(c>0){
            backward(r,c-1,sum);
        }
    };
    backward(n-1,m-1,0);
    cout<<answer<<'\n';
}