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!

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


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())


MODULO = 20011

def solve(grid, R, C, d):
	if grid[1][1] == 0 or grid[R][C] == 0:
		return 0
	path_top = [[0] * (C + 1) for row in range(R + 1)]
	path_left = [[0] * (C + 1) for row in range(R + 1)]
	for col in range(1, min(d + 2, C + 1)):
		if grid[1][col] == 1:
			path_left[1][col] = 1
		else:
			break
	for row in range(2, R + 1):
		for col in range(1, C + 1):
			if grid[row][col] == 1:
				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
				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 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()


(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]
print((up[-1][-1][0] + left[-1][-1][0]) % 20011)


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
print(answer)


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
print(answer)


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
if sys.version_info[0] < 3:
	from builtins import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip

def bfs(adj, v):
	visited = [False] * (v + 1)
	q = deque()
	while q:
		pass

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)

def most_frequent(List):
	return Counter(List).most_common(1)[0][0]

def most_common(List):
	return mode(List)

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

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

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)

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

def setBit(n):
	count = 0
	while n != 0:
		n = n & n - 1
		count += 1
	return count

def digitsSum(n):
	if n == 0:
		return 0
	r = 0
	while n > 0:
		r += n % 10
		n //= 10
	return r

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

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))))

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

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

class LRUCache:

	def __init__(self, capacity: int):
		self.cache = OrderedDict()
		self.capacity = capacity

	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]

	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)
if os.path.exists('in.txt'):
	sys.stdin = open('in.txt', 'r')

def inp():
	return sys.stdin.readline().strip()

def out(var):
	sys.stdout.write(str(var))

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())
MOD = 998244353
mod = 10 ** 9 + 7

def __starting_point():
	(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)
__starting_point()


(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()
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))


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)


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}
			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']
			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)


(r, c, d) = map(int, input().split())
l = []
for _ in range(r):
	l.append(list(map(int, input().split())))
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(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):
	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
	elif 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)


import math
import collections
import bisect
import heapq
import time
import random
import itertools
import sys
(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)


import math
import collections
import bisect
import heapq
import time
import random
import itertools
import sys
(R, C, D) = map(int, input().split())
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
	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
	return sum(dp[R - 1][C - 1][0]) + sum(dp[R - 1][C - 1][1]) % MOD
print(solve1())