高数Umaru系列(2)——占座儿

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

想必大家都在教室占过座位,彪悍的高数巨也是占座大军中的一员,击败过的对手可绕地球两圈儿。

大家都知道,上课教室的座位是有行有列的,由于高数巨比较热心,时常帮同学舍友占座,但是作为摩(chu)羯(nv)座(zuo)的高数巨最不能容忍的是跟自己的同学舍友分开坐,所以高数巨占座的原则是必须占同一行上连续的几个座位,如果没有连续的座位可以选择,那么她就呵呵了。当然,高数巨不一定是最先去占座的,所以她去教室的时候会有已经占了的座位

假设教室的座位是呈N*M ( 1 < = N , M < = 100 ) 分布,行号由1~N,列号由1~M,高数巨要帮包括自己在内的K ( 1 < = K < = M )个人占座,给你教室已占座位的分布,你能求出高数巨有多少种占座的情况吗?

Input

 多组输入。

对于每组数据,第一行有三个整数N, M,K,分别表示教室座位的行数、列数和高数巨要占的座位数

接下来的N行每行有M个整数,表示座位的当前状态,0代表未占,1代表已占

Output

 对于每组数据,输出一个整数代表高数巨可以占座的情况总数,每组输出占一行

Sample Input

3 3 2
1 1 0
1 0 0
0 0 0
4 4 3
1 1 0 0
0 0 1 0
0 1 0 1
0 0 1 1

Sample Output

3
0

Hint

 

Source

Shannon