Indian National Olympiad in Informatics 2014
Due to resurfacing work, all north-south traffic on the highway is being diverted through the town of Siruseri. Siruseri is a modern, planned town and the section of roads used for the diversion forms a rectangular grid where all cars enter at the top-left intersection (north- west) and leave at the bottom-right intersection (south-east). All roads within the grid are one-way, allowing traffic to move north to south (up-down) and west to east (left-right) only.
The town authorities are concerned about highway drivers overspeeding through the town. To slow them down, they have made a rule that no car may travel more than d consecutive road segments in the same direction without turning. (Closed-circuit TV cameras have been installed to enforce this rule.)
Of course, there is also repair work going on within the town, so some intersections are blocked and cars cannot pass through these.
You are given the layout of the rectangular grid of roads within Siruseri and the constraint on how many consecutive road segments you may travel in the same direction. Your task is to compute the total number of paths from the entry (top-left) to the exit (bottom-right).
For instance, suppose there are 3 rows and 4 columns of intersec- tions, numbered from (1,1) at the top-left to (3,4) at the bottom-right, as shown on the right. Intersection (2,1) in the second row, first column is blocked, and no car may travel more than 2 consecutive road seg- ments in the same direction.

Here, (1,1) → (1,2) → (2,2) → (3,2) → (3,3) → (3,4) is a valid path from (1,1) to (3,4), but (1,1) → (1,2) → (1,3) → (1,4) → (2,4) → (3,4) is not, because this involves 3 consecutive road segments from left to right. The path (1, 1) → (2, 1) → (2, 2) → (2, 3) → (3, 3) → (3, 4) is ruled out because it goes through a blocked intersection. In this example, you can check that the total number of valid paths is 5.

-----Input format-----
• Line 1: Three space-separated integers, R, C and d, where R is the number of rows in the grid, C is the number of columns in the grid and d is the maximum number of consecutive segments you can travel in any direction.
• Lines 2 to R+1: Each line contains C integers, each of which is 0 or 1, describing one row of intersections in the grid. An intersection marked 0 is blocked and an intersection marked 1 is available to pass through. The start (top-left) and finish (bottom-right) intersections are always marked 1.

-----Output format-----
A single integer—the number of paths from the top-left intersection to the bottom-right intersection that go only down and right, and obey the d constraint.
Since the final answer may not fit in a variable of type int, report your answer modulo 20011. Be careful to avoid overflows in intermediate computations.

-----Test Data-----
The testdata is grouped into three subtasks. In all subtasks, 1 ≤ R ≤ 300, 1 ≤ C ≤ 300 and 1 ≤ d ≤ 300. In addition, each subtask has the following constraints on the inputs.
• Subtask 1 [20 points]: d = max(R, C) − 1. (In other words, there is no limit on the number of consecutive segments you can travel in one direction.)
• Subtask 2 [30 points]: d=2.
• Subtask 3 [50 points]: No additional constraint on d.

-----Example-----
Here is the sample input and output corresponding to the example above.

-----Sample input-----
3 4 2
1 1 1 1
0 1 1 1
1 1 1 1

-----Sample output-----
5

Note: Your program should not print anything other than what is specified in the output format. Please remove all diagnostic print statements before making your final submission. A program with extraneous output will be treated as incorrect!

Difficulty: interview

Starter code:

Solutions:
class PathNode:

    def __init__(self, row, col, st_x, st_y, p_count=0):
        self.x = row
        self.y = col
        self.pathCount = p_count

    def __str__(self):
        return str(self.x) + " | " + str(self.y) + " | " + str(self.pathCount)


class GraphUtil:
    def __init__(self, mat, R,C, d):
        self.mat = mat
        self.R = R
        self.C = C
        self.d = d
        self.tab = {}

    def isValidMove(self, r, c, blockVal):
        return r < self.R and c < self.C and self.mat[r][c] != blockVal

    def possbilePathUtil(self, r, c, blockVal, step,direction):

        if(not self.isValidMove(r, c, 0)):
            return 0
            
        if (r == self.R - 1 and c == self.C - 1):
            return 1

        if ((r,c,step,direction) in self.tab):
            return self.tab[(r,c,step,direction)]

        result = 0
        
        if direction == 1:
            if step < self.d:
                result = (result + self.possbilePathUtil(r, c + 1, blockVal, step + 1,1)) % 20011
            result = (result +  self.possbilePathUtil(r+1, c, blockVal, 1,2)) % 20011
        else:
            if step < self.d:
                result = (result + self.possbilePathUtil(r + 1, c, blockVal, step + 1, 2)) % 20011
            result = (result + self.possbilePathUtil(r, c + 1, blockVal, 1,1)) % 20011
        
        self.tab[(r,c,step,direction)] = result
        
        return result

    def possbilePath(self):
        if (not self.mat or len(self.mat) < 1):
            return 0

        return self.possbilePathUtil(0, 0, 0,0,2)


numbers = [int(n) for n in input().split()]

mat = [[int(n) for n in input().split()] for r in range(0, numbers[0])]

result = GraphUtil(mat, numbers[0], numbers[1], numbers[2])

print(result.possbilePath())
# print(result.count)# cook your dish here


MODULO = 20011

def solve(grid, R, C, d):
    if grid[1][1] == 0 or grid[R][C] == 0:
        return 0
    # count paths from (r=1, c=1) to (r=R, c=C)
    path_top = [[0] * (C + 1) for row in range(R + 1)]
    path_left = [[0] * (C + 1) for row in range(R + 1)]
    # 1st row:
    # from (1,1) going right, you can travel all the
    # way to (1,d+1) but no further than (1,C)
    for col in range(1, min(d + 2, C + 1)):
        if grid[1][col] == 1:
            path_left[1][col] = 1
        else:
            break
    # row-th row, row>1
    for row in range(2, R + 1):
        for col in range(1, C + 1):
            if grid[row][col] == 1:
                # entering (row,col) from the top:
                for i in range(1, min(d + 1, row)):
                    if grid[row - i][col] == 1:
                        path_top[row][col] += path_left[row - i][col]
                    else:
                        break
                # entering (row,col) from the left:
                for i in range(1, min(d + 1, col)):
                    if grid[row][col - i] == 1:
                        path_left[row][col] += path_top[row][col - i]
                    else:
                        break
    # return solution
    return path_top[R][C] + path_left[R][C]

def __starting_point():
    R, C, d = list(map(int, input().strip().split()))
    grid = [[0] * (C + 1) for row in range(R + 1)]
    for row in range(1, R + 1):
        grid[row] = [0] + list(map(int, input().strip().split()))
    print(solve(grid, R, C, d) % MODULO)

__starting_point()

# cook your dish here
r, c, k = map(int, input().split())
matrix=[]
for _ in range(r):
    matrix.append(list(map(int, input().split())))
left=[[[0,0] for _ in range(c)] for i in range(r)]
up=[[[0,0] for _ in range(c)] for i in range(r)]
left[0][0][0]=1 
up[0][0][0]=1 
for i in range(1,min(k+1,c)):
    if matrix[0][i]==1:
        left[0][i][0]=left[0][i-1][0]
        if left[0][i-1][0]>0:
            left[0][i][1]=left[0][i-1][1]+1
for i in range(1,min(k+1,r)):
    if matrix[i][0]==1:
        up[i][0][0]=up[i-1][0][0]
        if up[i-1][0][0]>0:
            up[i][0][1]=up[i-1][0][1]+1
for i in range(1,min(k+1,r)):
    for j in range(1,min(k+1,c)):
        if matrix[i][j]==1:
            left[i][j][0]=left[i][j-1][0]+up[i][j-1][0]
            if left[i][j-1][0]+up[i][j-1][0]>0:
                left[i][j][1]=left[i][j-1][1]+1
            up[i][j][0]=up[i-1][j][0]+left[i-1][j][0]
            if left[i-1][j][0]+up[i-1][j][0]>0:
                up[i][j][1]=up[i-1][j][1]+1
    for j in range(min(k+1,c), c):
        if matrix[i][j]==1:
            up[i][j][0]=up[i-1][j][0]+left[i-1][j][0]
            if left[i-1][j][0]+up[i-1][j][0]>0:
                up[i][j][1]=up[i-1][j][1]+1
            left[i][j][0]=left[i][j-1][0]+up[i][j-1][0]
            if left[i][j-1][0]+up[i][j-1][0]>0:
                left[i][j][1]=left[i][j-1][1]+1
            if left[i][j][1]>k:
                left[i][j][0]-=up[i][j-k-1][0]
            
for i in range(min(k+1,r),r):
    for j in range(1,min(k+1,c)):
        if matrix[i][j]==1:
            left[i][j][0]=left[i][j-1][0]+up[i][j-1][0]
            if left[i][j-1][0]+up[i][j-1][0]>0:
                left[i][j][1]=left[i][j-1][1]+1
            up[i][j][0]=up[i-1][j][0]+left[i-1][j][0]
            if left[i-1][j][0]+up[i-1][j][0]>0:
                up[i][j][1]=up[i-1][j][1]+1
            if up[i][j][1]>k:
                up[i][j][0]-=left[i-k-1][j][0]
            
    for j in range(min(k+1,c), c):
        if matrix[i][j]==1:
            up[i][j][0]=up[i-1][j][0]+left[i-1][j][0]
            if left[i-1][j][0]+up[i-1][j][0]>0:
                up[i][j][1]=up[i-1][j][1]+1
            if up[i][j][1]>k:
                up[i][j][0]-=left[i-k-1][j][0]
            left[i][j][0]=left[i][j-1][0]+up[i][j-1][0]
            if left[i][j-1][0]+up[i][j-1][0]>0:
                left[i][j][1]=left[i][j-1][1]+1
            if left[i][j][1]>k:
                left[i][j][0]-=up[i][j-k-1][0]
'''
for i in range(r):
    print([el for el in up[i]])
for i in range(r):
    print([el[0] for el in left[i]])
'''
print((up[-1][-1][0]+left[-1][-1][0])%20011)

# cook your dish here
MOD = 20011
import copy
R,C,D = map(int,input().split())
list1=[]
for i in range(R):
    temp = list(map(int,input().split()))
    list1.append(temp)
for j in range(C):
    if list1[0][j] ==0:
        for i in range(j,C):
            list1[0][i]=0
        break
for i in range(R):
    if list1[i][0] ==0:
        for j in range(i,R):
            list1[j][0] =0
        break
if D+1<C:
    for j in range(D+1,C):
        list1[0][j] = 0
if D+1<R:
    for i in range(D+1,R):
        list1[i][0] = 0
list2 = copy.deepcopy(list1)
for j in range(1,R):
    count=[ 0 for i in range(R)]
    count1=[0 for j in range(C)]
    for i in range(1,C):
        if list2[j][i]!=0:
            list2[j][i] = list2[j-1][i]+list2[j][i-1]
        if j-D-1>=0 and list2[j-1][i]!=0:
            list2[j][i] -= list2[j-D-1][i]
            if j-D-2>=0:
                list2[j][i] += list2[j-D-2][i]
        if i-D-1>=0 and list2[j][i-1]!=0:
            list2[j][i]-=list2[j][i-D-1]
            if i-D-2>=0:
                list2[j][i] += list2[j][i-D-2]
        if list2[j][i]<0:
            list2[j][i] =0
answer = (list2[R-1][C-1])%MOD
#for i in range(len(list1)):
    #print(list1[i],list2[i])
print(answer)


# cook your dish here
MOD = 20011
import copy
R,C,D = map(int,input().split())
list1=[]
for i in range(R):
    temp = list(map(int,input().split()))
    list1.append(temp)
for j in range(C):
    if list1[0][j] ==0:
        for i in range(j,C):
            list1[0][i]=0
        break
for i in range(R):
    if list1[i][0] ==0:
        for j in range(i,R):
            list1[j][0] =0
        break
if D+1<C:
    count = 1
    for j in range(D+1,C):
        list1[0][j] = list1[0][j] - count
        count +=1
if D+1<R:
    count=1
    for i in range(D+1,R):
        list1[i][0] = list1[i][0]-count
        count +=1
list2 = copy.deepcopy(list1)
for j in range(1,R):
    for i in range(1,C):
        if list2[j][i]!=0:
            list2[j][i] = list2[j-1][i]+list2[j][i-1]
answer = (list2[R-1][C-1])%MOD
#for i in range(len(list1)):
    #print(list1[i])
#print()
#for j in range(len(list2)):
    #print(list2[j])
print(answer)


# cook your dish here
MOD = 20011
import copy
R,C,D = map(int,input().split())
list1=[]
for i in range(R):
    temp = list(map(int,input().split()))
    list1.append(temp)
for j in range(C):
    if list1[0][j] ==0 or j>D:
        for i in range(j,C):
            list1[0][i]=0
        break
for i in range(R):
    if list1[i][0] ==0 or i >D:
        for j in range(i,R):
            list1[j][0] =0
        break
list2 = copy.deepcopy(list1)
for j in range(1,R):
    for i in range(1,C):
        if list2[j][i]!=0:
            list2[j][i] = list2[j-1][i]+list2[j][i-1]
answer = (list2[R-1][C-1])%MOD
#for i in range(len(list1)):
    #print(list1[i],list2[i])
print(answer)


# import all important libraries and inbuilt functions

from fractions import Fraction
import numpy as np
import sys,bisect,copyreg,copy,statistics,os
from math import *
from collections import Counter,defaultdict,deque,OrderedDict   
from itertools import combinations,permutations,accumulate,groupby 
from numpy.linalg import matrix_power as mp
from bisect import bisect_left,bisect_right,bisect,insort,insort_left,insort_right
from statistics import mode
from functools import reduce,cmp_to_key 
from io import BytesIO, IOBase
from scipy.spatial import ConvexHull
from heapq import *
from decimal import *
from queue import Queue,PriorityQueue
from re import sub,subn

# end of library import

# map system version faults
if sys.version_info[0] < 3:
    from builtins import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip

# template of many functions used in competitive programming can add more later 
# based on need we will use this commonly.

# bfs in a graph
def bfs(adj,v): # a schema of bfs
    visited=[False]*(v+1);q=deque()
    while q:pass

# definition of vertex of a graph
def graph(vertex): return [[] for i in range(vertex+1)]

def powermodulo(x, y, p) : 
    res = 1;x = x % p        
    if (x == 0) : return 0  
    while (y > 0) : 
        if ((y & 1) == 1) :   res = (res * x) % p 
        y = y >> 1 
        x = (x * x) % p           
    return res

def lcm(a,b): return (a*b)//gcd(a,b)

# most common list in a array of lists
def most_frequent(List):return Counter(List).most_common(1)[0][0]

# element with highest frequency
def most_common(List):return(mode(List))

#In number theory, the Chinese remainder theorem states that 
#if one knows the remainders of the Euclidean division of an integer n by 
#several integers, then one can determine uniquely the remainder of the 
#division of n by the product of these integers, under the condition 
#that the divisors are pairwise coprime.
def chinese_remainder(a, p):
    prod = reduce(op.mul, p, 1);x = [prod // pi for pi in p]
    return sum(a[i] * powermodulo(x[i], p[i] - 2, p[i]) * x[i] for i in range(len(a))) % prod

# make a matrix
def createMatrix(rowCount, colCount, dataList):   
    mat = []
    for i in range (rowCount):
        rowList = []
        for j in range (colCount):
            if dataList[j] not in mat:rowList.append(dataList[j])
        mat.append(rowList) 
    return mat

# input for a binary tree
def readTree(): 
    v=int(inp());adj=[set() for i in range(v+1)]
    for i in range(v-1):u1,u2=In(); adj[u1].add(u2);adj[u2].add(u1)
    return adj,v
    
# sieve of prime numbers    
def sieve():
    li=[True]*1000001;li[0],li[1]=False,False;prime=[]
    for i in range(2,len(li),1):
        if li[i]==True:
            for j in range(i*i,len(li),i):li[j]=False    
    for i in range(1000001):
        if li[i]==True:prime.append(i)
    return prime

#count setbits of a number.
def setBit(n):
    count=0
    while n!=0:n=n&(n-1);count+=1
    return count

# sum of digits of a number
def digitsSum(n):
    if n == 0:return 0
    r = 0
    while n > 0:r += n % 10;n //= 10
    return r

# ncr efficiently
def ncr(n, r):
    r = min(r, n - r);numer = reduce(op.mul, list(range(n, n - r, -1)), 1);denom = reduce(op.mul, list(range(1, r + 1)), 1)
    return numer // denom  # or / in Python 2

#factors of a number
def factors(n):return list(set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))

#prime fators of a number
def prime_factors(n):
    i = 2;factors = []
    while i * i <= n:
        if n % i:i += 1
        else:n //= i;factors.append(i)
    if n > 1:factors.append(n)
    return len(set(factors))

def prefixSum(arr):
    for i in range(1, len(arr)):arr[i] = arr[i] + arr[i-1]
    return arr    

def binomial_coefficient(n, k):
    if 0 <= k <= n:
        ntok = 1;ktok = 1
        for t in range(1, min(k, n - k) + 1):ntok *= n;ktok *= t;n -= 1
        return ntok // ktok
    else:return 0
 
def powerOfK(k, max):
    if k == 1:return [1]
    if k == -1:return [-1, 1] 
    result = [];n = 1
    while n <= max:result.append(n);n *= k
    return result

# maximum subarray sum use kadane's algorithm
def kadane(a,size):
    max_so_far = 0;max_ending_here = 0 
    for i in range(0, size):
        max_ending_here = max_ending_here + a[i]
        if (max_so_far < max_ending_here):max_so_far = max_ending_here 
        if max_ending_here < 0:max_ending_here = 0
    return max_so_far                                    
                  
def divisors(n):
    result = []
    for i in range(1,ceil(sqrt(n))+1):
        if n%i == 0:
            if n/i == i:result.append(i)
            else:result.append(i);result.append(n/i)
    return result

def sumtilln(n): return ((n*(n+1))//2)

def isPrime(n) : 
	if (n <= 1) :return False
	if (n <= 3) :return True
	if (n % 2 == 0 or n % 3 == 0) :return False
	for i in range(5,ceil(sqrt(n))+1,6):
		if (n % i == 0 or n % (i + 2) == 0) :return False
	return True

def isPowerOf2(n):
    while n % 2 == 0:n //= 2
    return (True if n == 1 else False)

def power2(n):
    k = 0
    while n % 2 == 0:k += 1;n //= 2
    return k

def sqsum(n):return ((n*(n+1))*(2*n+1)//6)
    
def cusum(n):return ((sumn(n))**2)

def pa(a):
    for i in range(len(a)):print(a[i], end = " ")
    print()

def pm(a,rown,coln):
    for i in range(rown):
        for j in range(coln):print(a[i][j],end = " ")
        print()

def pmasstring(a,rown,coln):
    for i in range(rown):
        for j in range(coln):print(a[i][j],end = "")
        print()
        
def isPerfectSquare(n):return pow(floor(sqrt(n)),2) == n

def nC2(n,m):return (((n*(n-1))//2) % m)

def modInverse(n,p):return powermodulo(n,p-2,p)

def ncrmodp(n, r, p):  
	num = den = 1
	for i in range(r):num = (num * (n - i)) % p ;den = (den * (i + 1)) % p 
	return (num * powermodulo(den,p - 2, p)) % p 

def reverse(string):return "".join(reversed(string))        

def listtostr(s):return ' '.join([str(elem) for elem in s]) 

def binarySearch(arr, l, r, x): 
	while l <= r: 
		mid = l + (r - l) // 2; 
		if arr[mid] == x:return mid 
		elif arr[mid] < x:l = mid + 1
		else:r = mid - 1
	return -1

def isarrayodd(a):
    r = True
    for i in range(len(a)):
        if a[i] % 2 == 0:
            r = False
            break
    return r

def isPalindrome(s):return s == s[::-1] 

def gt(x,h,c,t):return ((x*h+(x-1)*c)/(2*x-1))

def CountFrequency(my_list): 
    freq = {} 
    for item in my_list:freq[item] = (freq[item] + 1 if (item in freq) else 1)
    return freq

def CountFrequencyasPair(my_list1,my_list2,freq): 
    for item in my_list1:freq[item][0] = (freq[item][0] + 1 if (item in freq) else 1)
    for item in my_list2:freq[item][1] = (freq[item][1] + 1 if (item in freq) else 1)     
    return freq 
 
def binarySearchCount(arr, n, key):   
    left = 0;right = n - 1;count = 0  
    while (left <= right):  
        mid = int((right + left) / 2) 
        if (arr[mid] <= key):count,left = mid + 1,mid + 1
        else:right = mid - 1      
    return count

def primes(n):
  sieve,l = [True] * (n+1),[]
  for p in range(2, n+1):
    if (sieve[p]):
      l.append(p)
      for i in range(p, n+1, p):sieve[i] = False
  return l

def Next_Greater_Element_for_all_in_array(arr): 
	s,n,reta,retb = list(),len(arr),[],[];arr1 = [list([0,i]) for i in range(n)]
	for i in range(n - 1, -1, -1): 
		while (len(s) > 0 and s[-1][0] <= arr[i]):s.pop() 
		if (len(s) == 0):arr1[i][0] = -1					
		else:arr1[i][0] = s[-1]	 
		s.append(list([arr[i],i]))		
	for i in range(n):reta.append(list([arr[i],i]));retb.append(arr1[i][0])
	return reta,retb

def polygonArea(X,Y,n):   
    area = 0.0;j = n - 1
    for i in range(n):area += (X[j] + X[i]) * (Y[j] - Y[i]);j = i   
    return abs(area / 2.0)

def merge(a, b):
	ans = defaultdict(int)
	for i in a:ans[i] += a[i]
	for i in b:ans[i] += b[i]
	return ans
 
#defining a LRU Cache
# where we can set values and get values based on our requirement
class LRUCache: 
	# initialising capacity 
	def __init__(self, capacity: int): 
		self.cache = OrderedDict() 
		self.capacity = capacity 

	# we return the value of the key 
	# that is queried in O(1) and return -1 if we 
	# don't find the key in out dict / cache. 
	# And also move the key to the end 
	# to show that it was recently used. 
	def get(self, key: int) -> int: 
		if key not in self.cache:return -1
		else:self.cache.move_to_end(key);return self.cache[key] 

	# first, we add / update the key by conventional methods. 
	# And also move the key to the end to show that it was recently used. 
	# But here we will also check whether the length of our 
	# ordered dictionary has exceeded our capacity, 
	# If so we remove the first key (least recently used) 
	def put(self, key: int, value: int) -> None: 
		self.cache[key] = value;self.cache.move_to_end(key) 
		if len(self.cache) > self.capacity:self.cache.popitem(last = False)

class segtree:
    def __init__(self,n):
        self.m = 1
        while self.m < n:self.m *= 2
        self.data = [0] * (2 * self.m)
    def __setitem__(self,i,x):
        x = +(x != 1);i += self.m;self.data[i] = x;i >>= 1
        while i:self.data[i] = self.data[2 * i] + self.data[2 * i + 1];i >>= 1
    def __call__(self,l,r):
        l += self.m;r += self.m;s = 0
        while l < r:
            if l & 1:s += self.data[l];l += 1
            if r & 1:r -= 1;s += self.data[r]
            l >>= 1;r >>= 1
        return s        

class FenwickTree:
  def __init__(self, n):self.n = n;self.bit = [0]*(n+1)  
  def update(self, x, d):
    while x <= self.n:self.bit[x] += d;x += (x & (-x))  
  def query(self, x):
    res = 0
    while x > 0:res += self.bit[x];x -= (x & (-x))
    return res
  def range_query(self, l, r):return self.query(r) - self.query(l-1)        
# can add more template functions here
    
# end of template functions

# To enable the file I/O i the below 2 lines are uncommented.
# read from in.txt if uncommented
if os.path.exists('in.txt'): sys.stdin=open('in.txt','r')
# will print on Console if file I/O is not activated
#if os.path.exists('out.txt'): sys.stdout=open('out.txt', 'w')

# inputs template
#for fast input we areusing sys.stdin
def inp(): return sys.stdin.readline().strip()

#for fast output, always take string
def out(var): sys.stdout.write(str(var))  

# cusom base input needed for the program
def I():return (inp())
def II():return (int(inp()))
def FI():return (float(inp()))
def SI():return (list(str(inp())))
def MI():return (map(int,inp().split()))
def LI():return (list(MI()))
def SLI():return (sorted(LI()))
def MF():return (map(float,inp().split()))
def LF():return (list(MF()))
def SLF():return (sorted(LF()))

# end of inputs template

# common modulo values used in competitive programming
MOD = 998244353
mod = 10**9+7

# any particular user-defined functions for the code.
# can be written here.  
 
# end of any user-defined functions

# main functions for execution of the program.
def __starting_point():  
    # execute your program from here.
    # start your main code from here
        
    # Write your code here
    r,c,d = MI()
    l = []
    for _ in range(r):l.append(LI())
    dp = [[[0,0] for _ in range(c)] for iiii in range(r)]                                  
    dp[0][0] = [1,1]
    for j in range(r):
        for i in range(c):
            if l[j][i] == 0:
                continue
            for z in range(i-1,max(-1,i-1-d),-1):
                if l[j][z] == 0:break
                dp[j][i][0] += dp[j][z][1]
            for z in range(j-1,max(-1,j-1-d),-1):
                if l[z][i] == 0:break
                dp[j][i][1] += dp[z][i][0]
    print(sum(dp[-1][-1])%20011)
    # end of main code
    # end of program

# This program is written by :
#   Shubham Gupta
#   B.Tech (2019-2023)
#   Computer Science and Engineering,
#   Department of EECS
#   Contact No:8431624358
#   Indian Institute of Technology(IIT),Bhilai
#   Sejbahar,
#   Datrenga,
#   Raipur,
#   Chhattisgarh
#   492015

#   THANK YOU FOR 
#YOUR KIND PATIENCE FOR READING THE PROGRAM.    
__starting_point()

# cook your dish here
R,C,d = map(int,input().split())
table = []
for i in range(R):
    temp = list(map(int,input().split()))
    table.append(temp)
if R>=C:
    temp1 =R
else:
    temp1=C
for i in range(d+1,temp1):
    try:
        table[0][i]=0
        table[i][0]=0
    except:
        try:
            table[i][0]=0
        except:
            continue
for i in range(C):
    if table[0][i] == 0:
        for j in range(i,C):
            table[0][j]=0
        break
for i in range(R):
    if table[i][0] == 0:
        for j in range(i,R):
            table[j][0] = 0
        break
answer=table.copy()
#print(answer)
for i in range(1,R):
    for j in range(1,C):
        if answer[i][j] !=0:
            answer[i][j] = answer[i-1][j]+answer[i][j-1]
print(str(answer[R-1][C-1] % 20011))
#for row in answer:
    #print(row)

class PathNode:

    def __init__(self, row, col, st_x, st_y, p_count=0):
        self.x = row
        self.y = col
        self.pathCount = p_count

    def __str__(self):
        return str(self.x) + " | " + str(self.y) + " | " + str(self.pathCount)


class GraphUtil:
    def __init__(self, mat, R,C, d):
        self.mat = mat
        self.R = R
        self.C = C
        self.d = d
        self.tab = {}

    def isValidMove(self, r, c, blockVal):
        return r < self.R and c < self.C and self.mat[r][c] != blockVal

    def possbilePathUtil(self, r, c, blockVal, step,direction):

        if(not self.isValidMove(r, c, 0)):
            return 0
            
        if (r == self.R - 1 and c == self.C - 1):
            return 1

        if ((r,c,step,direction) in self.tab):
            return self.tab[(r,c,step,direction)]

        result = 0
        
        if direction == 1:
            if step < self.d:
                result = (result + self.possbilePathUtil(r, c + 1, blockVal, step + 1,1)) % 20011
            result = (result +  self.possbilePathUtil(r+1, c, blockVal, 1,2)) % 20011
        else:
            if step < self.d:
                result = (result + self.possbilePathUtil(r + 1, c, blockVal, step + 1, 2)) % 20011
            result = (result + self.possbilePathUtil(r, c + 1, blockVal, 1,1)) % 20011
        
        self.tab[(r,c,step,direction)] = result
        
        return result

    def possbilePath(self):
        if (not self.mat or len(self.mat) < 1):
            return 0

        return self.possbilePathUtil(0, 0, 0,0,2)


numbers = [int(n) for n in input().split()]

mat = [[int(n) for n in input().split()] for r in range(0, numbers[0])]

result = GraphUtil(mat, numbers[0], numbers[1], numbers[2])

print(result.possbilePath())
# print(result.count)

class PathNode:

    def __init__(self, row, col, st_x, st_y, p_count=0):
        self.x = row
        self.y = col
        self.pathCount = p_count

    def __str__(self):
        return str(self.x) + " | " + str(self.y) + " | " + str(self.pathCount)


class GraphUtil:
    def __init__(self, mat, R,C, d):
        self.mat = mat
        self.R = R
        self.C = C
        self.d = d
        self.tab = {}

    def isValidMove(self, r, c, blockVal):
        return r < self.R and c < self.C and self.mat[r][c] != blockVal

    def possbilePathUtil(self, r, c, blockVal, step,direction):

        if(not self.isValidMove(r, c, 0)):
            return 0
            
        if (r == self.R - 1 and c == self.C - 1):
            return 1

        if ((r,c,step,direction) in self.tab):
            return self.tab[(r,c,step,direction)]

        result = 0
        
        if direction == 1:
            if step < self.d:
                result = (result + self.possbilePathUtil(r, c + 1, blockVal, step + 1,1)) % 20011
            result = (result +  self.possbilePathUtil(r+1, c, blockVal, 1,2)) % 20011
        else:
            if step < self.d:
                result = (result + self.possbilePathUtil(r + 1, c, blockVal, step + 1, 2)) % 20011
            result = (result + self.possbilePathUtil(r, c + 1, blockVal, 1,1)) % 20011
        
        self.tab[(r,c,step,direction)] = result
        
        return result

    def possbilePath(self):
        if (not self.mat or len(self.mat) < 1):
            return 0

        return self.possbilePathUtil(0, 0, 0,0,2)


numbers = [int(n) for n in input().split()]

mat = [[int(n) for n in input().split()] for r in range(0, numbers[0])]

result = GraphUtil(mat, numbers[0], numbers[1], numbers[2])

print(result.possbilePath())
# print(result.count)

#for _ in range(int(input())):
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
#dt = {k:v for k,v in sorted(x.items(), key=lambda i: i[1])}
ipnl = lambda n: [int(input()) for _ in range(n)]
inp = lambda :int(input())
ip = lambda :[int(w) for w in input().split()]
mp = lambda :map(int,input().split())

r,c,d = mp()
x = [[{'D':0,'R':0,'f':1} for i in range(c)] for j in range(r)]
for i in range(r):
    t = ip()
    for j in range(c):
        if t[j] == 0:
            x[i][j] = {'D':0,'R':0,'f':0}
x[0][0] = {'D':1,'R':1,'f':1}
for i in range(r):
    for j in range(c):
        if x[i][j]['f']:
            ind = i-1
            ctr = 0
            while ind>=0 and ctr < d and x[ind][j]['f']:
                x[i][j]['D'] += x[ind][j]['R']
                ind -= 1
                ctr += 1
            ind = j-1
            ctr = 0
            while ind>=0 and ctr < d and x[i][ind]['f']:
                x[i][j]['R'] += x[i][ind]['D']
                ind -= 1
                ctr += 1
ans = x[-1][-1]['R'] + x[-1][-1]['D']
print(ans%20011)

#for _ in range(int(input())):
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
#dt = {k:v for k,v in sorted(x.items(), key=lambda i: i[1])}
ipnl = lambda n: [int(input()) for _ in range(n)]
inp = lambda :int(input())
ip = lambda :[int(w) for w in input().split()]
mp = lambda :map(int,input().split())

r,c,d = mp()
x = [[{'D':0,'R':0,'CT':0,'f':1} for i in range(c+1)] for j in range(r+1)]
for i in range(1,r+1):
    t = ip()
    for j in range(c):
        if t[j] == 0:
           x[i][j+1]['f'] = 2
for i in range(1,r+1):
    for j in range(1,c+1):
        flag = 0
        if i==1 and j==1:
            x[i][j] = {'D':0,'R':0,'CT':1,'f':0}
        elif x[i][j]['f'] != 2:
            x[i][j] = {'D':0,'R':0,'CT':0,'f':0}
            #from up
            if x[i-1][j]['f'] == 0 and x[i-1][j]['D'] < d:
                flag += 1
                x[i][j]['D'] = x[i-1][j]['D'] + 1
                x[i][j]['CT'] += x[i-1][j]['CT']
            #from left
            if x[i][j-1]['f'] == 0 and x[i][j-1]['R'] < d:
                flag += 1
                x[i][j]['R'] = x[i][j-1]['R'] + 1
                x[i][j]['CT'] += x[i][j-1]['CT']
            if flag == 0:
                x[i][j] = {'D':0,'R':0,'CT':0,'f':2}
print(x[r][c]['CT']%20011)
"""
for i in range(r+1):
    print(*x[i])
"""

# cook your dish here
r, c, d = map(int, input().split())
l = []
for _ in range(r):
    l.append(list(map(int, input().split())))
    
#hori, verti
dp = [[[0,0] for _ in range(c)] for _ in range(r)]

dp[0][0] = [1, 1]
for j in range(r):
    for i in range(c):
        if l[j][i] == 0:
            continue
        for ii in range(i-1, max(-1, i-1-d), -1):
            if l[j][ii] == 0:
                break
            dp[j][i][0] += dp[j][ii][1]
            
        for jj in range(j-1, max(-1, j-1-d), -1):
            if l[jj][i] == 0:
                break
            dp[j][i][1] += dp[jj][i][0]
# print('\n'.join(str(v) for v in dp))
# if r == 1 and c == 1:
#     print(1)
# else:
print(sum(dp[-1][-1])%20011)

MOD = 20011

n, m, d = map(int, input().split())
gr = [list(map(int, input().split())) for _ in range(n)]

dp = [[0] * m for _ in range(n)]

for i in range(min(n, d+1)):
    if gr[i][0] == 0:
        break

    dp[i][0] = 1

for i in range(min(m, d+1)):
    if gr[0][i] == 0:
        break

    dp[0][i] = 1

for i in range(1, n):
    for j in range(1, m):
        if gr[i][j] == 0:
            dp[i][j] = 0
            continue

        dp[i][j] = dp[i-1][j] + dp[i][j-1]

        if i - d - 1 >= 0:
            for r in range(i-d, i):
                if not gr[r][j]:
                    break
            else:
                dp[i][j] -= dp[i - d - 1][j]

                if i - d - 2 >= 0:
                    dp[i][j] += dp[i - d - 2][j]

        if j - d - 1 >= 0:
            for r in range(j-d, j):
                if not gr[i][r]:
                    break
            else:
                dp[i][j] -= dp[i][j - d - 1]

                if j - d - 2 >= 0:
                    dp[i][j] += dp[i][j - d - 2]

        dp[i][j] = max(dp[i][j], 0) % MOD

print(dp[n-1][m-1])


MOD = 20011

def lego(x , y , consec , prev):

	#X --> 0
	#Y -- > 1

	if x >= r or y >= c:
		return 0

	if grid[x][y] == 0:
		return 0

	if x == r-1 and y == c-1:
		return 1


	if dp[x][y][consec][prev] != -1:
		return dp[x][y][consec][prev]

	if consec == 0:
		if prev == 0:
			dp[x][y][consec][prev] = lego(x , y +1 , d-1 , 1)%MOD
		else:
			dp[x][y][consec][prev] = lego(x + 1 , y , d-1 , 0)%MOD

	else:

		if prev == 0:
			dp[x][y][consec][prev] = (lego(x+1 , y , consec - 1 , 0) + lego(x , y+1, d-1 , 1))%MOD

		else:

			dp[x][y][consec][prev] = (lego(x , y+1 , consec - 1 , 1) + lego(x+1 , y, d-1 , 0))%MOD



	return dp[x][y][consec][prev] 






r,c,d = map(int , input().split())

grid = []
for  i in range(r):
	alpha = list(map(int , input().split()))
	grid.append(alpha)
	


dp = [[[[-1 , -1] for z in range(d)] for j in range(c)] for i in range(r)]

print((lego(1 , 0 , d-1 , 0) + lego(0,1,d-1 , 1))%MOD)






# -*- coding: utf-8 -*-

import math
import collections
import bisect
import heapq
import time
import random
import itertools
import sys

"""
created by shhuan at 2019/11/30 12:31

"""

R, C, D = map(int, input().split())
A = []
for r in range(R):
    A.append([int(x) for x in input().split()])

if A[0][0] == 0:
    print(0)
    exit(0)

dp = [[[[0 for _ in range(D+1)] for _ in range(2)] for _ in range(C)] for _ in range(R)]
for c in range(1, min(C, D+1)):
    if A[0][c] == 0:
        break
    dp[0][c][0][c] = 1
for r in range(1, min(R, D+1)):
    if A[r][0] == 0:
        break
    dp[r][0][1][r] = 1

MOD = 20011
for r in range(1, R):
    for c in range(1, C):
        if A[r][c] == 0:
            continue
        for d in range(2, D+1):
            dp[r][c][0][d] = dp[r][c-1][0][d-1]
            dp[r][c][1][d] = dp[r-1][c][1][d-1]
            dp[r][c][0][d] %= MOD
            dp[r][c][1][d] %= MOD
        dp[r][c][0][1] = sum(dp[r][c-1][1][1:]) % MOD
        dp[r][c][1][1] = sum(dp[r-1][c][0][1:]) % MOD

print(sum(dp[R-1][C-1][0]) + sum(dp[R-1][C-1][1]) % MOD)

# -*- coding: utf-8 -*-

import math
import collections
import bisect
import heapq
import time
import random
import itertools
import sys

"""
created by shhuan at 2019/11/30 12:31

"""

R, C, D = map(int, input().split())
A = []
for r in range(R):
    A.append([int(x) for x in input().split()])

if A[0][0] == 0:
    print(0)
    exit(0)

dp = [[[[0 for _ in range(D+1)] for _ in range(2)] for _ in range(C)] for _ in range(R)]
for c in range(1, min(C, D+1)):
    if A[0][c] == 0:
        break
    dp[0][c][0][c] = 1
for r in range(1, min(R, D+1)):
    if A[r][0] == 0:
        break
    dp[r][0][1][r] = 1

MOD = 20011
for r in range(1, R):
    for c in range(1, C):
        if A[r][c] == 0:
            continue
        for d in range(2, D+1):
            dp[r][c][0][d] = dp[r][c-1][0][d-1]
            dp[r][c][1][d] = dp[r-1][c][1][d-1]
            dp[r][c][0][d] %= MOD
            dp[r][c][1][d] %= MOD
        dp[r][c][0][1] = sum(dp[r][c-1][1][1:]) % MOD
        dp[r][c][1][1] = sum(dp[r-1][c][0][1:]) % MOD

print(sum(dp[R-1][C-1][0]) + sum(dp[R-1][C-1][1]) % MOD)

# -*- coding: utf-8 -*-

import math
import collections
import bisect
import heapq
import time
import random
import itertools
import sys

"""
created by shhuan at 2019/11/30 12:31

"""
# import random

R, C, D = map(int, input().split())

# R, C, D = 5, 5, 15

A = []
for r in range(R):
    A.append([int(x) for x in input().split()])


def solve1():
    if A[0][0] == 0:
        return 0
    MOD = 20011
    dp = [[0 for _ in range(C)] for _ in range(R)]
    dp[0][0] = 1
    for r in range(R):
        for c in range(C):
            if A[r][c] != 0:
                dp[r][c] += dp[r-1][c] if r > 0 else 0
                dp[r][c] += dp[r][c-1] if c > 0 else 0
                # dp[r][c] %= MOD

    # for row in dp:
    #     print(row)

    return dp[R-1][C-1]

def solve2():
    if A[0][0] == 0:
        return 0

    dp = [[[[0 for _ in range(D+1)] for _ in range(2)] for _ in range(C)] for _ in range(R)]
    for c in range(1, min(C, D+1)):
        if A[0][c] == 0:
            break
        dp[0][c][0][c] = 1
    for r in range(1, min(R, D+1)):
        if A[r][0] == 0:
            break
        dp[r][0][1][r] = 1

    MOD = 20011
    for r in range(1, R):
        for c in range(1, C):
            if A[r][c] == 0:
                continue
            for d in range(2, D+1):
                dp[r][c][0][d] = dp[r][c-1][0][d-1]
                dp[r][c][1][d] = dp[r-1][c][1][d-1]
                dp[r][c][0][d] %= MOD
                dp[r][c][1][d] %= MOD
            dp[r][c][0][1] = sum(dp[r][c-1][1][1:]) % MOD
            dp[r][c][1][1] = sum(dp[r-1][c][0][1:]) % MOD


    # for r in range(R):
    #     for c in range(C):
    #         print('='*10 + '{}-{}'.format(r, c)+'='*10)
    #         for row in dp[r][c]:
    #             print(row)
    # print(dp[R-1][C-1][0])
    # print(dp[R - 1][C - 1][1])
    return (sum(dp[R-1][C-1][0]) + sum(dp[R-1][C-1][1])) % MOD

# while True:
#     R, C = random.randint(2, 22), random.randint(2, 22)
#     # A = []
#     # for i in range(R):
#     #     # A.append([int(x) for x in input().split()])
#     #     A.append([1 if random.randint(1, 10) > 2 else 0 for _ in range(C)])
#
#     A = [
#         [1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1],
#         [1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0],
#         [0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
#         [1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1],
#         [1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1],
#         [0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1],
#         [0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1],
#         [1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1],
#         [1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1],
#         [1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1],
#         [1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1],
#         [1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0],
#         [1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1],
#         [0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1],
#         [1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1],
#         [1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1],
#         [1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1],
#         [1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1],
#         [0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1],
#         [1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1],
#         [1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1],
#         [1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
#     ]
#
#
#     R, C = len(A), len(A[0])
#     D = max(R, C) + 1
#     print(solve2())
#
#     a, b = solve1(), solve2()
#     print(a, b)
#     if a != b:
#         # print(R, C)
#         # for row in A:
#         #     print(row)
#         # print('=' * 40)
#         # print(a, b)
#         exit(0)
#     exit(0)

print(solve2())

# -*- coding: utf-8 -*-

import math
import collections
import bisect
import heapq
import time
import random
import itertools
import sys

"""
created by shhuan at 2019/11/30 12:31

"""
# import random

R, C, D = map(int, input().split())
#
# R, C, D = 5, 5, 15

A = []
for r in range(R):
    A.append([int(x) for x in input().split()])


def solve1():
    if A[0][0] == 0:
        return 0
    MOD = 20011
    dp = [[0 for _ in range(C)] for _ in range(R)]
    dp[0][0] = 1
    for r in range(R):
        for c in range(C):
            if A[r][c] != 0:
                dp[r][c] += dp[r-1][c] if r > 0 else 0
                dp[r][c] += dp[r][c-1] if c > 0 else 0
                dp[r][c] %= MOD

    # for row in dp:
    #     print(row)

    return dp[R-1][C-1]

def solve2():
    if A[0][0] == 0:
        return 0

    dp = [[[[0 for _ in range(D+1)] for _ in range(2)] for _ in range(C)] for _ in range(R)]

    if A[0][1] != 0:
        dp[0][1][0][1] = 1
    if A[1][0] != 0:
        dp[1][0][1][1] = 1

    A[0][1] = 0
    A[1][0] = 0

    MOD = 20011
    for r in range(R):
        for c in range(C):
            if A[r][c] == 0:
                continue
            for d in range(2, D+1):
                dp[r][c][0][d] += dp[r][c-1][0][d-1] if c > 0 else 0
                dp[r][c][1][d] += dp[r-1][c][1][d-1] if r > 0 else 0
                dp[r][c][0][d] %= MOD
                dp[r][c][1][d] %= MOD
            dp[r][c][0][1] = (sum(dp[r][c-1][1][1:]) if c > 0 else 0) % MOD
            dp[r][c][1][1] = (sum(dp[r-1][c][0][1:]) if r > 0 else 0) % MOD


    # for r in range(R):
    #     for c in range(C):
    #         print('='*10 + '{}-{}'.format(r, c)+'='*10)
    #         for row in dp[r][c]:
    #             print(row)

    return sum(dp[R-1][C-1][0]) + sum(dp[R-1][C-1][1]) % MOD

# while True:
#     R, C = random.randint(2, 10), random.randint(2, 10)
#     A = []
#     for i in range(R):
#         # A.append([int(x) for x in input().split()])
#         A.append([1 if random.randint(1, 10) > 2 else 0 for _ in range(C)])
#
#     R, C = len(A), len(A[0])
#     a, b = solve1(), solve2()
#     print(a, b)
#     if a != b:
#         for row in A:
#             print(row)
#         print('=' * 40)
#         print(a, b)
#         exit(0)

print(solve1())

MOD = 20011

n, m, d = map(int, input().split())
gr = [list(map(int, input().split())) for _ in range(n)]

dp = [[0] * m for _ in range(n)]

for i in range(min(n, d+1)):
    if gr[i][0] == 0:
        break

    dp[i][0] = 1

for i in range(min(m, d+1)):
    if gr[0][i] == 0:
        break

    dp[0][i] = 1

for i in range(1, n):
    for j in range(1, m):
        if gr[i][j] == 0:
            dp[i][j] = 0
            continue

        dp[i][j] = dp[i-1][j] + dp[i][j-1]

        if i - d - 1 >= 0:
            for r in range(i-d, i):
                if not gr[r][j]:
                    break
            else:
                dp[i][j] -= dp[i - d - 1][j]

        if j - d - 1 >= 0:
            for r in range(j-d, j):
                if not gr[i][r]:
                    break
            else:
                dp[i][j] -= dp[i][j - d - 1]

        dp[i][j] = max(dp[i][j], 0) % MOD

print(dp[n-1][m-1])

"""

3 4 2
1 1 1 1
1 1 1 1
1 1 0 1


"""

MOD = 20011

n, m, d = map(int, input().split())
gr = [list(map(int, input().split())) for _ in range(n)]

dp = [[0] * m for _ in range(n)]

for i in range(min(n, d+1)):
    if gr[i][0] == 0:
        break

    dp[i][0] = 1

for i in range(min(m, d+1)):
    if gr[0][i] == 0:
        break

    dp[0][i] = 1

for i in range(1, n):
    for j in range(1, m):
        if gr[i][j] == 0:
            dp[i][j] = 0
            continue

        dp[i][j] = dp[i-1][j] + dp[i][j-1]

        if i - d - 1 >= 0:
            for r in range(i-d, i):
                if not gr[r][j]:
                    break
            else:
                dp[i][j] -= dp[i - d - 1][j]

        if j - d - 1 >= 0:
            for r in range(j-d, j):
                if not gr[i][r]:
                    break
            else:
                dp[i][j] -= dp[i][j - d - 1]

        dp[i][j] = max(dp[i][j] % MOD, 0)

print(dp[n-1][m-1])

"""

3 4 2
1 1 1 1
1 1 1 1
1 1 0 1


"""

MOD = 20011

n, m, d = map(int, input().split())
gr = [list(map(int, input().split())) for _ in range(n)]

dp = [[0] * m for _ in range(n)]

for i in range(min(n, d+1)):
    if gr[i][0] == 0:
        break

    dp[i][0] = 1

for i in range(min(m, d+1)):
    if gr[0][i] == 0:
        break

    dp[0][i] = 1

for i in range(1, n):
    for j in range(1, m):
        if gr[i][j] == 0:
            dp[i][j] = 0
            continue

        dp[i][j] = dp[i-1][j] + dp[i][j-1]

        if i - d - 1 >= 0:
            for r in range(i-d-1, i):
                if not gr[r][j]:
                    break
            else:
                dp[i][j] -= dp[i - d - 1][j]

        if j - d - 1 >= 0:
            for r in range(j-d-1, j):
                if not gr[i][r]:
                    break
            else:
                dp[i][j] -= dp[i][j - d - 1]

        dp[i][j] = max(dp[i][j] % MOD, 0)

print(dp[n-1][m-1])


MOD = 20011

n, m, d = map(int, input().split())
gr = [list(map(int, input().split())) for _ in range(n)]

dp = [[0] * m for _ in range(n)]

for i in range(min(n, d+1)):
    if gr[i][0] == 0:
        break

    dp[i][0] = 1

for i in range(min(m, d+1)):
    if gr[0][i] == 0:
        break

    dp[0][i] = 1

for i in range(1, n):
    for j in range(1, m):
        if gr[i][j] == 0:
            dp[i][j] = 0
            continue

        dp[i][j] = dp[i-1][j] + dp[i][j-1]

        if i - d - 1 >= 0:
            for r in range(i-d, i):
                if not gr[r][j]:
                    break
            else:
                dp[i][j] -= dp[i - d - 1][j]

        if j - d - 1 >= 0:
            for r in range(j-d, j):
                if not gr[i][r]:
                    break
            else:
                dp[i][j] -= dp[i][j - d - 1]

        dp[i][j] = max(dp[i][j], 0) % MOD

print(dp[n-1][m-1])


MOD = 20011

n, m, d = map(int, input().split())
gr = [list(map(int, input().split())) for _ in range(n)]

dp = [[0] * m for _ in range(n)]

for i in range(min(n, d+1)):
    if gr[i][0] == 0:
        break

    dp[i][0] = 1

for i in range(min(m, d+1)):
    if gr[0][i] == 0:
        break

    dp[0][i] = 1

for i in range(1, n):
    for j in range(1, m):
        if gr[i][j] == 0:
            dp[i][j] = 0
            continue

        dp[i][j] = dp[i-1][j] + dp[i][j-1]

        if i - d - 1 > 0:
            for r in range(i-d, i):
                if not gr[r][j]:
                    break
            else:
                dp[i][j] -= dp[i - d - 1][j]

        if j - d - 1 > 0:
            for r in range(j-d, j):
                if not gr[i][r]:
                    break
            else:
                dp[i][j] -= dp[i][j - d - 1]

        dp[i][j] = max(dp[i][j], 0) % MOD

print(dp[n-1][m-1])


MOD = 20011

n, m, d = map(int, input().split())
gr = [list(map(int, input().split())) for _ in range(n)]

dp = [[0] * (m + 1) for _ in range(n + 1)]
dp[1][1] = 1

for i in range(1, n+1):
    for j in range(1, m+1):
        if gr[i-1][j-1] == 0:
            dp[i][j] = 0
            continue

        if i == j == 1:
            continue


        dp[i][j] = dp[i-1][j] + dp[i][j-1]

        if i - d - 1 > 0:
            for r in range(i-d-1, i):
                if not gr[r][j-1]:
                    break
            else:

                dp[i][j] -= dp[i - d - 1][j]

        if j - d - 1 > 0:
            for r in range(j-d-1, j):
                if not gr[i-1][r]:
                    break
            else:
                dp[i][j] -= dp[i][j - d - 1]

        dp[i][j] = max(dp[i][j], 0) % MOD

print(dp[n][m])