Subrectangle Sum Divisibility

Little F once loved math. In high school he often struggled with math, but he never forgot the excitement of discovering algorithms. One day he remembered how matrix multiplication once allowed him to compute the \(10^{100}\)th term of the Fibonacci sequence!

Now he has drawn an \(n \times m\) matrix where each cell contains a positive integer not exceeding \(k\). He wonders: how many distinct subrectangles in the matrix have the property that the sum of their elements is divisible by \(k\)?

A subrectangle is defined by its top-left and bottom-right coordinates \((x_1,y_1,x_2,y_2)\) (with \(x_1\le x_2\) and \(y_1\le y_2\)). Two subrectangles are considered the same if they have the same \((x_1,y_1,x_2,y_2)\) representation.

inputFormat

The first line contains three positive integers \(n\), \(m\), and \(k\), where \(n\) and \(m\) denote the number of rows and columns of the matrix respectively, and \(k\) is the divisor.

Then follow \(n\) lines, each containing \(m\) positive integers. The \(j\)-th integer in the \(i\)-th line represents the element in the \(i\)-th row and \(j\)-th column of the matrix. Each integer is at most \(k\).

outputFormat

Output a single integer: the number of distinct subrectangles whose elements' sum is divisible by \(k\).

sample

1 1 5
5

1