AT_abc461_d [ABC461D] 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 $ .

The input is given from Standard Input in the following format: > $ H $ $ W $ $ K $ $ S_1 $ $ S_2 $ $ \vdots $ $ S_H $

Output the answer.

### Sample Explanation 1 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`.