你有一个 n × m 的表格(n 行和 m 列),表格的每个单元格包含一个“0”或一个“1”。
您的任务是计算边与表格边平行并沿着单元格边框的矩形的数量,使得数字 1 在矩形中恰好出现 k 次。
输入
第一行包含三个空格分隔的整数 n、m 和 k (1 ≤ n, m ≤ 2500, 0 ≤ k ≤ 6) — 表格的大小和所需的数字个数。
接下来的 n 行每行包含 m 个字符“0”或“1”。第 j 行的第 i 个字符对应于表的第 j 行第 i 列中的字符。
输出
打印单个数字 — 恰好包含 k 个数字 1 的矩形的数量。
请不要编写 %lld 说明符来读取或写入 С++ 中的 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。
示例
输入 #1
3 3 2 101 000 101
输出 #1
8
输入 #2
5 5 1 00000 00000 00100 00000 00000
输出 #2
81
输入 #3
5 5 6 01010 10101 01010 10101 01010
输出 #3
12
输入#4
3 3 0 001 010 000
输出#4
15
输入 #5
4 4 0 0000 0101 0000 0000
输出 #5
52