Divisible Path Sum

Given a matrix of non-negative integers, determine the total number of paths from the top-left corner to the bottom-right corner such that the sum of the values along the path is divisible by a given integer \(P\). You may only move either down or right at any point in time.

Details:

• Each path starts at the cell in the top-left corner and ends at the cell in the bottom-right corner.
• The sum of all numbers along the path, when taken modulo \(P\), must equal zero.
• This problem can be efficiently solved using recursive depth-first search combined with memoization (dynamic programming).

Your task is to implement a function that computes the number of such valid paths.

inputFormat

The first line contains three integers \(m\), \(n\), and \(P\): the number of rows, the number of columns of the matrix, and the divisor, respectively. This is followed by \(m\) lines, each containing \(n\) space-separated integers representing the matrix.

outputFormat

Output a single integer representing the number of valid paths from the top-left corner to the bottom-right corner in which the sum of the values is divisible by \(P\).

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

2