E. Пустые прямоугольники
ограничение по времени на тест
12 секунд
ограничение по памяти на тест
512 мегабайт
ввод
stdin
вывод
stdout

Дана таблица n × m (n строк и m столбцов), в каждой ячейке которой стоит «0» или «1».

Требуется посчитать количество прямоугольников со сторонами, параллельными сторонам таблицы и проходящими по границам ячеек, таких, что количество единиц в прямоугольнике равно k.

Входные данные

В первой строке, разделенные пробелами, записаны три целых числа n, m и k (1 ≤ n, m ≤ 2500, 0 ≤ k ≤ 6) — размеры таблицы и требуемое количество единиц.

В следующих n строках записано по m символов «0» или «1». i-й символ j-й строке соответствует символу, находящемуся в j-й строке и i-м столбце таблицы.

Выходные данные

Выведите единственное число — количество прямоугольников, количество единиц в которых равно k.

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-битных чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.

Примеры
Входные данные
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