题目描述

有一个 $H \times W$ 的网格，每个单元格中都包含一个整数 $0$ 或 $1$。

网格通过 $H$ 个长度为 $W$ 的字符串 $S_1, S_2, \ldots, S_H$ 描述。$S_i$ 的第 $j$ 个字符为 0 时，第 $i$ 行第 $j$ 列的单元格写有 $0$；为 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$；
• 矩形区域 $\{(i, j) \mid r_1 \le i \le r_2, c_1 \le j \le c_2\}$ 内所有整数之和等于 $K$。

输入格式

H W K
S_1
S_2
...
S_H

输出格式

输出答案。

输入示例 1

3 4 2
0110
1011
0110

输出示例 1

16

输入示例 2

1 1 0
0

输出示例 2

1

示例 2 说明

只有一个单元格、内容为 $0$，矩形为 $(1, 1, 1, 1)$，和为 $0 = K$，所以答案为 $1$。

输入示例 3

3 3 9
111
111
111

输出示例 3

1

示例 3 说明

只有整个 $3 \times 3$ 网格的和恰好等于 $9$。

约束条件

• $1 \le H, W \le 500$
• $0 \le K \le H \times W$
• $S_i$ 是长度为 $W$，由 0、1 组成的字符串
• 所有输入值均为整数