Grid Path Divisibility

Given a grid containing integers with ( n ) rows and ( m ) columns, find the number of paths from the top-left corner to the bottom-right corner such that the sum of the numbers along the path is divisible by a given integer ( k ).

You can only move either down or right at any point in time. The solution should be developed using dynamic programming to efficiently count the number of valid paths.

inputFormat

The input is read from stdin. The first line contains three space-separated integers: ( n ), ( m ), and ( k ). The following ( n ) lines each contain ( m ) space-separated integers representing the grid.

outputFormat

Output to stdout a single integer: the number of valid paths from the top-left to the bottom-right such that the sum of the numbers along the path is divisible by ( k ).## sample

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

2