CF364E.Empty Rectangles

You've got an n × m table (n rows and m columns), each cell of the table contains a "0" or a "1".

Your task is to calculate the number of rectangles with the sides that are parallel to the sides of the table and go along the cell borders, such that the number one occurs exactly k times in the rectangle.

你有一个 $n \times m$ 的表格（共 $n$ 行、$m$ 列），表格中每个单元格包含一个“0”或一个“1”。

你的任务是计算满足以下条件的矩形的数量：该矩形的边与表格的边平行，并且沿单元格的边界；且矩形内部恰好包含 $k$ 个数字“1”。

The first line contains three space-separated integers n, m and k (1 ≤ n, m ≤ 2500, 0 ≤ k ≤ 6) — the sizes of the table and the required number of numbers one.

Next n lines each contains m characters "0" or "1". The i-th character of the j-th line corresponds to the character that is in the j-th row and the i-th column of the table.

第一行包含三个以空格分隔的整数 $n$、$m$ 和 $k$（$1 \leq n, m \leq 2500$，$0 \leq k \leq 6$）——分别表示表格的尺寸以及所需数字 1 的个数。

接下来的 $n$ 行，每行包含 $m$ 个字符 '0' 或 '1'。第 $j$ 行的第 $i$ 个字符对应于表格中第 $j$ 行、第 $i$ 列的字符。

Print a single number — the number of rectangles that contain exactly k numbers one.

Please, do not write the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

输出一个整数——即恰好包含 k 个数字 1 的矩形的数量。

请注意，在 C++ 中读写 64 位整数时，请勿使用 %lld 说明符。推荐使用 cin、cout 流，或 %I64d 说明符。