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!

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = '# -*- coding: utf-8 -*-\r\n\r\nimport math\r\nimport collections\r\nimport bisect\r\nimport heapq\r\nimport time\r\nimport random\r\nimport itertools\r\nimport sys\r\n\r\n"""\r\ncreated by shhuan at 2019/11/30 12:31\r\n\r\n"""\r\n# import random\r\n\r\nR, C, D = map(int, input().split())\r\n\r\n# R, C, D = 5, 5, 15\r\n\r\nA = []\r\nfor r in range(R):\r\n    A.append([int(x) for x in input().split()])\r\n\r\n\r\ndef solve1():\r\n    if A[0][0] == 0:\r\n        return 0\r\n    MOD = 20011\r\n    dp = [[0 for _ in range(C)] for _ in range(R)]\r\n    dp[0][0] = 1\r\n    for r in range(R):\r\n        for c in range(C):\r\n            if A[r][c] != 0:\r\n                dp[r][c] += dp[r-1][c] if r > 0 else 0\r\n                dp[r][c] += dp[r][c-1] if c > 0 else 0\r\n                # dp[r][c] %= MOD\r\n\r\n    # for row in dp:\r\n    #     print(row)\r\n\r\n    return dp[R-1][C-1]\r\n\r\ndef solve2():\r\n    if A[0][0] == 0:\r\n        return 0\r\n\r\n    dp = [[[[0 for _ in range(D+1)] for _ in range(2)] for _ in range(C)] for _ in range(R)]\r\n    for c in range(1, min(C, D+1)):\r\n        if A[0][c] == 0:\r\n            break\r\n        dp[0][c][0][c] = 1\r\n    for r in range(1, min(R, D+1)):\r\n        if A[r][0] == 0:\r\n            break\r\n        dp[r][0][1][r] = 1\r\n\r\n    MOD = 20011\r\n    for r in range(1, R):\r\n        for c in range(1, C):\r\n            if A[r][c] == 0:\r\n                continue\r\n            for d in range(2, D+1):\r\n                dp[r][c][0][d] = dp[r][c-1][0][d-1]\r\n                dp[r][c][1][d] = dp[r-1][c][1][d-1]\r\n                dp[r][c][0][d] %= MOD\r\n                dp[r][c][1][d] %= MOD\r\n            dp[r][c][0][1] = sum(dp[r][c-1][1][1:]) % MOD\r\n            dp[r][c][1][1] = sum(dp[r-1][c][0][1:]) % MOD\r\n\r\n\r\n    # for r in range(R):\r\n    #     for c in range(C):\r\n    #         print(\'=\'*10 + \'{}-{}\'.format(r, c)+\'=\'*10)\r\n    #         for row in dp[r][c]:\r\n    #             print(row)\r\n    # print(dp[R-1][C-1][0])\r\n    # print(dp[R - 1][C - 1][1])\r\n    return (sum(dp[R-1][C-1][0]) + sum(dp[R-1][C-1][1])) % MOD\r\n\r\n# while True:\r\n#     R, C = random.randint(2, 22), random.randint(2, 22)\r\n#     # A = []\r\n#     # for i in range(R):\r\n#     #     # A.append([int(x) for x in input().split()])\r\n#     #     A.append([1 if random.randint(1, 10) > 2 else 0 for _ in range(C)])\r\n#\r\n#     A = [\r\n#         [1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1],\r\n#         [1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0],\r\n#         [0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],\r\n#         [1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1],\r\n#         [1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1],\r\n#         [0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1],\r\n#         [0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1],\r\n#         [1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1],\r\n#         [1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1],\r\n#         [1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1],\r\n#         [1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1],\r\n#         [1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0],\r\n#         [1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1],\r\n#         [0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1],\r\n#         [1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1],\r\n#         [1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1],\r\n#         [1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1],\r\n#         [1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1],\r\n#         [0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1],\r\n#         [1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1],\r\n#         [1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1],\r\n#         [1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],\r\n#     ]\r\n#\r\n#\r\n#     R, C = len(A), len(A[0])\r\n#     D = max(R, C) + 1\r\n#     print(solve2())\r\n#\r\n#     a, b = solve1(), solve2()\r\n#     print(a, b)\r\n#     if a != b:\r\n#         # print(R, C)\r\n#         # for row in A:\r\n#         #     print(row)\r\n#         # print(\'=\' * 40)\r\n#         # print(a, b)\r\n#         exit(0)\r\n#     exit(0)\r\n\r\nprint(solve2())'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: