Problem p03222 (python)

Fixed submission:
def count(length, on):
    """Count of possible amida patterns"""
    if length < 0:
        return 1
    if length == 0:
        return 1
    ret = count(length - 1, False)
    if not on:
        ret += count(length - 1, True)
    return ret


# for i in range(1, 9):
#     print(count(i, True) + count(i, False))


if __name__ == '__main__':
    H, W, K = map(int, input().split())

    # Count
    B = [0 for _ in range(W)]
    B[0] = 1
    for j in range(H):
        C = [0 for _ in range(W)]
        for i in range(W):
            left_off = count(i - 1, False)
            left_on = count(i - 1, True)
            right_off = count(W - i - 2, False)
            right_on = count(W - i - 2, True)
            # print(i, left_off, left_on, right_off, right_on)

            if B[i] > 0:
                C[i] += B[i] * (left_off * right_off)

            if i > 0 and B[i - 1] > 0:
                C[i] += B[i - 1] * (left_on * right_off)

            if i < W - 1 and B[i + 1] > 0:
                C[i] += B[i + 1] * (left_off * right_on)

        B = [ci for ci in C]
        # print(B)

    # MOD = 1_000_000_007  # Underscore is not supported until 3.6
    MOD = 1000000007
    ANS = C[K - 1] % MOD
    print(ANS)

Buggy submission (verdict: Runtime Error):
def count(length, on):
    """Count of possible amida patterns"""
    if length < 0:
        return 1
    if length == 0:
        return 1
    ret = count(length - 1, False)
    if not on:
        ret += count(length - 1, True)
    return ret


# for i in range(1, 9):
#     print(count(i, True) + count(i, False))


if __name__ == '__main__':
    H, W, K = map(int, input().split())

    # Count
    B = [0 for _ in range(W)]
    B[0] = 1
    for j in range(H):
        C = [0 for _ in range(W)]
        for i in range(W):
            left_off = count(i - 1, False)
            left_on = count(i - 1, True)
            right_off = count(W - i - 2, False)
            right_on = count(W - i - 2, True)
            # print(i, left_off, left_on, right_off, right_on)

            if B[i] > 0:
                C[i] += B[i] * (left_off * right_off)

            if i > 0 and B[i - 1] > 0:
                C[i] += B[i - 1] * (left_on * right_off)

            if i < W - 1 and B[i + 1] > 0:
                C[i] += B[i + 1] * (left_off * right_on)

        B = [ci for ci in C]
        # print(B)

    MOD = 1_000_000_007
    ANS = C[K - 1] % MOD
    print(ANS)

Buggy submission (verdict: Runtime Error):
def count(length, on):
    """Count of possible amida patterns"""
    if length < 0:
        return 1
    if length == 0:
        return 1
    ret = count(length - 1, False)
    if not on:
        ret += count(length - 1, True)
    return ret


# for i in range(1, 9):
#     print(count(i, True) + count(i, False))


if __name__ == '__main__':
    H, W, K = map(int, input().split())

    # Count
    B = [0 for _ in range(W)]
    B[0] = 1
    for j in range(H):
        C = [0 for _ in range(W)]
        for i in range(W):
            left_off = count(i - 1, False)
            left_on = count(i - 1, True)
            right_off = count(W - i - 2, False)
            right_on = count(W - i - 2, True)
            print(i, left_off, left_on, right_off, right_on)

            if B[i] > 0:
                C[i] += B[i] * (left_off * right_off)

            if i > 0 and B[i - 1] > 0:
                C[i] += B[i - 1] * (left_on * right_off)

            if i < W - 1 and B[i + 1] > 0:
                C[i] += B[i + 1] * (left_off * right_on)

        B = [ci for ci in C]
        # print(B)

    MOD = 1_000_000_007
    ANS = C[K - 1] % MOD
    print(ANS)