Counting Submatrices with Divisible Sums

You are given an N×M matrix. A submatrix is formed by choosing a contiguous range of rows and a contiguous range of columns. In other words, choose 1 ≤ r1 ≤ r2 ≤ N and 1 ≤ c1 ≤ c2 ≤ M, then include every element from rows r1 through r2 and columns c1 through c2.

Count how many submatrices have an element sum divisible by K.

The first line contains three natural numbers N, M, and K. (1 ≤ N, M ≤ 256, 1 ≤ K ≤ 1,000,000)

Each of the next N lines contains M integers, the elements of the matrix. Every element is a natural number between 1 and 50, inclusive.

Print the number of submatrices whose element sum is divisible by K.