29700번 - 우당탕탕 영화예매

도은이는 동아리 문화의 날을 맞이하여 동아리원들과 함께 좌석이 $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$을 출력한다.