Empty Rectangles

## 题目描述： 你有一个n*m的01矩阵，现在询问在这其中有多少个子矩阵满足包含k个1，即和为k。 ## 输入格式： 第一行包含3个正整数，分别为n，m，k 下面有n行，每行中有m个由0或1组成的数。 ## 输出格式： 输出一个正整数，表示满足条件的子矩阵的个数。 注意：请不要在С++中编写％lld说明符来读取或写入64位整数。优选使用cin，cout流或％I64d说明符。（cf声明） ## 数据范围： n,m≤2500；0≤k≤6

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.

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.

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.

3 3 2
101
000
101

8

5 5 1
00000
00000
00100
00000
00000

81

5 5 6
01010
10101
01010
10101
01010

12

3 3 0
001
010
000

15

4 4 0
0000
0101
0000
0000

52