우당탕탕 영화예매

면접 대비

시간 제한1초메모리 제한1024 MB

요약

M열 격자에서 한 행에 K명이 가로로 연속해 앉을 수 있는 빈 좌석 구간의 수를 센다. 같은 좌석 집합은 한 가지로 본다.

난이도: 보통10점 중 5점
유형: 배열, 슬라이딩 윈도우, 구현, 조합론
정답자: 아직 제출이 없습니다

문제

도은이는 동아리 문화의 날을 맞이하여 동아리원들과 함께 좌석이 $M$ 행 $N$ 열의 직사각형 모양으로 배치되어 있는 영화관에서 영화를 보기로 했다. 도은이는 동아리원의 유대감을 중요하게 생각하기 때문에 이미 예매가 완료된 좌석을 피해 동아리원들이 모두 가로로 이어서 앉을 수 있도록 자리를 예매하고 싶어 한다. 도은이를 도와 모든 동아리원들이 가로로 이어서 앉을 수 있도록 예매하는 경우의 수는 총 몇 가지가 있을지 구해보자. 단, 예매한 좌석은 동일하지만, 각 사람이 앉는 위치만 바뀌는 경우는 한 가지로 본다.

입력

첫째 줄에 영화관 세로줄의 개수 $N$ ( $1 \leq N \leq 1\\,000$ )과 가로줄의 개수 $M$ ( $1 \leq M \leq 5\\,000$ ), 영화를 관람할 동아리원의 수 $K$ ( $1 \leq K \leq 10$ )가 주어진다.

둘째 줄부터 $N$ 개의 줄에 걸쳐 그중 $i$ 번째 줄에는 $i$ 번째 열의 좌석 예매 현황이 길이 $M$ 인 문자열 $s\_i$ 로 주어진다. $s\_i$ 의 $j$ 번째 문자는 $i$ 열 $j$ 번째 좌석의 예매 현황을 나타내는데, 이 문자가 ' $0$ '이라면 예매 가능한 빈 좌석을, 이 문자가 ' $1$ '이라면 예매가 완료되어 예매가 불가능한 좌석을 나타낸다.

출력

동아리원들이 모두 가로로 이어서 앉을 수 있도록 영화를 예매하는 경우의 수를 출력한다. 단, 문제에서 주어진 조건에 맞게 영화를 예매할 수 있는 방법이 없다면 $0$ 을 출력한다.

예제2

예제 1
입력
```
3 5 3
11000
01010
10000
```
예상 출력
```
3
```
예제 2
입력
```
3 4 3
1101
1001
0101
```
예상 출력
```
0
```