AT_abc461_d.Count Subgrid Sum = K

There is an $H \times W$ grid, and each cell contains an integer $0$ or $1$.
The information of the integer written in each cell is given as $H$ strings $S_1, S_2, \dots, S_H$ of length $W$. If the $j$-th character of $S_i$ is 0, then $0$ is written in the cell at the $i$-th row from the top and the $j$-th column from the left of the grid; if the $j$-th character of $S_i$ is 1, then $1$ is written in that cell.

Find the number of rectangular regions where the sum of the written integers equals $K$.
More formally, find the number of quadruples of integers $(r_1, c_1, r_2, c_2)$ satisfying all of the following conditions:

• $1 \le r_1 \le r_2 \le H$
• $1 \le c_1 \le c_2 \le W$
• The sum of the integers written in the cell at the $i$-th row from the top and the $j$-th column from the left, over all pairs of integers $(i, j)$ satisfying $r_1 \le i \le r_2, c_1 \le j \le c_2$, equals $K$.

有一个 $H \times W$ 的网格，每个格子中包含一个整数 $0$ 或 $1$。
每个格子中所写整数的信息由 $H$ 个长度为 $W$ 的字符串 $S_1, S_2, \dots, S_H$ 给出。若 $S_i$ 的第 $j$ 个字符为 0，则网格中从上往下第 $i$ 行、从左往右第 $j$ 列的格子中写有数字 $0$；若 $S_i$ 的第 $j$ 个字符为 1，则该格子中写有数字 $1$。

求所有满足其中所写整数之和恰好等于 $K$ 的矩形区域的个数。
更准确地说，求满足以下所有条件的四元组整数 $(r_1, c_1, r_2, c_2)$ 的个数：

• $1 \le r_1 \le r_2 \le H$
• $1 \le c_1 \le c_2 \le W$
• 对所有满足 $r_1 \le i \le r_2$ 且 $c_1 \le j \le c_2$ 的整数对 $(i, j)$，对应格子（即从上往下第 $i$ 行、从左往右第 $j$ 列）中所写整数的总和等于 $K$。

The input is given from Standard Input in the following format:

$H$ $W$ $K$
$S_1$
$S_2$
$\vdots$
$S_H$

输入从标准输入中按以下格式给出：

$H$ $W$ $K$
$S_1$
$S_2$
$\vdots$
$S_H$

Output the answer.

输出答案。

Sample 1 Explanation:
There are eight rectangular regions where the sum of the written integers equals $K$:

• The rectangular region extracted from row $1$ to row $2$ from the top and column $1$ to column $2$ from the left
• The rectangular region extracted from row $1$ to row $2$ from the top and column $1$ to column $3$ from the left
• The rectangular region extracted from row $1$ to row $2$ from the top and column $2$ to column $4$ from the left
• The rectangular region extracted from row $1$ to row $3$ from the top and column $2$ to column $3$ from the left
• The rectangular region extracted from row $1$ to row $3$ from the top and column $3$ to column $4$ from the left
• The rectangular region extracted from row $2$ to row $2$ from the top and column $1$ to column $4$ from the left
• The rectangular region extracted from row $2$ to row $3$ from the top and column $1$ to column $2$ from the left
• The rectangular region extracted from row $2$ to row $3$ from the top and column $2$ to column $3$ from the left

Constraints

• $H$ and $W$ are integers between $1$ and $500$, inclusive.
• $K$ is an integer between $0$ and $HW$, inclusive.
• $S_i$ is a string of length $W$ consisting of 0 and 1.

样例 1 解释：
共有八个矩形区域，其中所写整数之和等于 $K$：

• 从上往下第 $1$ 行到第 $2$ 行、从左往右第 $1$ 列到第 $2$ 列所构成的矩形区域
• 从上往下第 $1$ 行到第 $2$ 行、从左往右第 $1$ 列到第 $3$ 列所构成的矩形区域
• 从上往下第 $1$ 行到第 $2$ 行、从左往右第 $2$ 列到第 $4$ 列所构成的矩形区域
• 从上往下第 $1$ 行到第 $3$ 行、从左往右第 $2$ 列到第 $3$ 列所构成的矩形区域
• 从上往下第 $1$ 行到第 $3$ 行、从左往右第 $3$ 列到第 $4$ 列所构成的矩形区域
• 从上往下第 $2$ 行到第 $2$ 行、从左往右第 $1$ 列到第 $4$ 列所构成的矩形区域
• 从上往下第 $2$ 行到第 $3$ 行、从左往右第 $1$ 列到第 $2$ 列所构成的矩形区域
• 从上往下第 $2$ 行到第 $3$ 行、从左往右第 $2$ 列到第 $3$ 列所构成的矩形区域

约束条件

• $H$ 和 $W$ 是介于 $1$ 到 $500$（含）之间的整数。
• $K$ 是介于 $0$ 到 $HW$（含）之间的整数。
• $S_i$ 是一个长度为 $W$ 的字符串，仅由字符 0 和 1 组成。