Movie Booking Chaos

Interview

Time limit1sMemory limit1024 MB

Summary

Count the ways to place K club members in consecutive empty seats along one horizontal row, where '1' marks reserved seats.

Level: Easy3 of 10
Topics: Array, Sliding window
Solved: No attempts yet

Problem

Doeun is going to a movie with her club members on the club culture day. The theater has seats arranged in a rectangle with $M$ rows and $N$ columns. Doeun values the bond among club members, so she wants to book seats that avoid the seats already reserved and let all club members sit side by side in a horizontal line. Help Doeun count the number of ways to book seats so that all club members can sit in a horizontal line. Arrangements that reserve the same seats, where only the positions of each person are swapped, count as one way.

Input

The first line contains $N$ ( $1 \leq N \leq 1\,000$ ), the number of vertical lines of the theater, $M$ ( $1 \leq M \leq 5\,000$ ), the number of horizontal lines, and $K$ ( $1 \leq K \leq 10$ ), the number of club members who will watch the movie.

From the second line onward, the next $N$ lines each contain a string $s_i$ of length $M$ . The $j$ -th character of $s_i$ shows the reservation status of seat $j$ in column $i$ . A '0' means the seat is empty and can be reserved, and a '1' means the seat is already reserved and cannot be booked.

Output

Print the number of ways to book the movie so that all club members can sit side by side in a horizontal line. If no booking satisfies the conditions, print $0$ .

Examples2

Example 1
Input
```
3 5 3
11000
01010
10000
```
Expected output
```
3
```
Example 2
Input
```
3 4 3
1101
1001
0101
```
Expected output
```
0
```