Codeforces Round 213 (Div. 1) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

divide and conquer

two pointers

*3000

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Empty Rectangles

time limit per test

12 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputYou'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.

Input

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.

Output

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.

Examples

Input

3 3 2

101

000

101

Output

8

Input

5 5 1

00000

00000

00100

00000

00000

Output

81

Input

5 5 6

01010

10101

01010

10101

01010

Output

12

Input

3 3 0

001

010

000

Output

15

Input

4 4 0

0000

0101

0000

0000

Output

52

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/14/2024 09:09:25 (l1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|