Codah ClubTrain. Submit. Improve.
Sign in
English
#0005EF

Šljivik - Okružno

Srba has a plum garden in the heart of Shumadija. Since Srba is a perfectionist, he maintains his plum garden in the shape of a rectangle, so that each of a total of N rows contains exactly M plum trees. Srba keeps control of the number of plum fruits on each tree.


Srba is a proud father of K kids, who love plums, and to make them happy, he decided to skim the same number of plum fruits for his every child. But, since he is a perfectionist, Srba will choose the part of his plum garden in the shape of a rectangle, with sides parallel to the sides of the garden, so that when he finishes skimming all the fruits, all his children get the same number of plum fruits.


Count the number of ways Srba can choose the desired part of his plum garden.


InputIn the first line there are three integers N, M i K (1 ≤ N, M ≤ 250, 1 ≤ K ≤ 1.000.000), the number of rows and columns, and the number of children Srba has, respectively. In the next N lines there are M numbers from the interval [1, 10^9] which represent the number of fruits on each tree.

OutputIn the first and only line output the number of ways Srba can choose the desired part of his garden.

Sample input:
3 3 5
2 9 3
10 8 6
1 4 12
Sample output:
4

Explanation.

The following rectangles are solutions (the first two numbers are the coordinates of the upper left corner, and the other two are the coordinates of the lower right corner of the rectangle): (1,1)-(3,3) , (2,1)-(2,1) , (3,1)-(3,2) , (2,2)-(3,3).

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.