U188718 k 倍子矩形

给定一个 $n\times m$ 的矩阵，其第 $i$ 行第 $j$ 列数字记作 $a_{i,j}$。 求这个矩阵有多少非空子矩阵 $(l,u,r,d)$，满足子矩阵内的数字的和是k的倍数。 换句话说，有多少 $(l,u,r,d)$ 满足： $$ 1\le l\le r\le n,1\le u\le d\le m\\ k\ \left|\ \left(\sum_{l\le i\le r}\sum_{u\le j\le d}a_{i,j}\right)\right. $$ 其中 $k\ |\ s$ 表示 $k$ 整除 $s$ ，即 $s$ 是 $k$ 的倍数。

第一行三个整数 $n,m,k$； 接下来 $n$ 行，每行 $m$ 个数字，表示矩阵 $(a_{i,j})$。

一行一个整数表示答案。

#### 样例解释 容易验证，仅有下述子矩阵满足条件： $$ (1, 1, 1, 3),\ (1, 1, 2, 2),\ (1, 2, 1, 2),\ (1, 2, 2, 3),\ (2, 1, 2, 1),\ (2, 3, 2, 3) $$ 故答案为 $6$ 。 #### 数据范围 对于 $20\%$ 的数据，$n,m\le 16$； 存在另外 $5\%$ 的数据， $m=1$； 存在另外 $5\%$ 的数据，$m=2$； 存在另外 $20\%$ 的数据，$k=2$； 存在另外 $10\%$ 的数据，所有 $a_{i,j}$ 均相等； 存在另外 $20\%$ 的数据，$n,m\le 100$； 对于 $100\%$ 的数据，$1\le n,m\le 400,2\le k\le 10^6,1\le a_{i,j}\le k$。