Дана таблица n × m (n строк и m столбцов), в каждой ячейке которой стоит «0» или «1».
Требуется посчитать количество прямоугольников со сторонами, параллельными сторонам таблицы и проходящими по границам ячеек, таких, что количество единиц в прямоугольнике равно k.
Выходные данные
Выведите единственное число — количество прямоугольников, количество единиц в которых равно k.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-битных чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3 2
101
000
101
|
8
|
|
2
|
5 5 1
00000
00000
00100
00000
00000
|
81
|
|
3
|
5 5 6
01010
10101
01010
10101
01010
|
12
|
|
4
|
3 3 0
001
010
000
|
15
|
|
5
|
4 4 0
0000
0101
0000
0000
|
52
|