Problem p03222 (python)

Fixed submission:
from functools import lru_cache

input_lst = list(map(int, input().split()))
h, w, k = input_lst[0], input_lst[1], input_lst[2]

def row_comb(w):
    if w < 0:
        return 0
    elif w <= 1:
        return 1
    elif w == 2:
        return 2
    else:
        return row_comb(w-2)+row_comb(w-1)

@lru_cache(maxsize=1000)
def trio(h,w):
    if h == 0:
        return [1] + [0 for i in range(10)]
    else:
        lst = []
        for i in range(1, w+1):
            if i == 1:
                lst.append(trio(h-1,w)[0] * row_comb(w-1) + trio(h-1,w)[1] * row_comb(w-2))
            elif i == w:
                lst.append(trio(h-1,w)[w-1] * row_comb(w-1) + trio(h-1,w)[w-2] * row_comb(w-2))
            elif i == 2:
                lst.append(trio(h-1,w)[0] * row_comb(w-2) + trio(h-1,w)[2] * row_comb(w-3) + trio(h-1,w)[1] * row_comb(w-2))
            elif i == w-1:
                lst.append(trio(h-1,w)[w-1] * row_comb(w-2) + trio(h-1,w)[w-3] * row_comb(w-3) + trio(h-1,w)[w-2] * row_comb(w-2))
            elif i > 2 and i < w-1:
                a = row_comb(i-2) * row_comb(w-i)
                b = row_comb(i-1) * row_comb(w-i-1)
                c = row_comb(i-1) * row_comb(w-i)
                lst.append(trio(h-1,w)[i-2] * a + trio(h-1,w)[i] * b + trio(h-1,w)[i-1] * c)
        lst = lst + [0 for i in range(10)]
        return lst
    
print(trio(h, w)[k-1] % 1000000007)

Buggy submission (verdict: Runtime Error):
from functools import lru_cache

input_lst = list(map(int, input().split()))
h, w, k = input_lst[0], input_lst[1], input_lst[2]

def row_comb(w):
    if w <= 0:
        return 0
    if w == 1:
        return 1
    if w == 2:
        return 2
    else:
        return row_comb(w-2)+row_comb(w-1)

@lru_cache(maxsize=1000)
def trio(h,w):
    if h == 0:
        return [1] + [0 for i in range(w)]
    else:
        lst = []
        for i in range(1, w+1):
            if i == 1:
                lst.append(trio(h-1,w)[0] * row_comb(w-1) + trio(h-1,w)[1] * row_comb(w-2))
            elif i == w:
                lst.append(trio(h-1,w)[w-1] * row_comb(w-1) + trio(h-1,w)[w-2] * row_comb(w-2))
            elif i == 2:
                lst.append(trio(h-1,w)[0] * row_comb(w-2) + trio(h-1,w)[2] * row_comb(w-3) + trio(h-1,w)[1] * row_comb(w-2))
            elif i == w-1:
                lst.append(trio(h-1,w)[w-1] * row_comb(w-2) + trio(h-1,w)[w-3] * row_comb(w-3) + trio(h-1,w)[w-2] * row_comb(w-2))
            elif i > 2 and i < w-1:
                a = row_comb(i-2) * row_comb(w-i)
                b = row_comb(i-1) * row_comb(w-i-1)
                c = row_comb(i-1) * row_comb(w-i)
                lst.append(trio(h-1,w)[i-2] * a + trio(h-1,w)[i] * b + trio(h-1,w)[i-1] * c)
        return lst
    
print(trio(h, w)[k-1] % 1000000007)

Buggy submission (verdict: Runtime Error):
input_lst = list(map(int, input().split()))
h, w, k = input_lst[0], input_lst[1], input_lst[2]

def row_comb(w):
    if w <= 0:
        return 0
    if w == 1:
        return 1
    if w == 2:
        return 2
    else:
        return row_comb(w-2)+row_comb(w-1)

@lru_cache(maxsize=1000)
def trio(h,w):
    if h == 0:
        return [1] + [0 for i in range(w)]
    else:
        lst = []
        for i in range(1, w+1):
            if i == 1:
                lst.append(trio(h-1,w)[0] * row_comb(w-1) + trio(h-1,w)[1] * row_comb(w-2))
            elif i == w:
                lst.append(trio(h-1,w)[w-1] * row_comb(w-1) + trio(h-1,w)[w-2] * row_comb(w-2))
            elif i == 2:
                lst.append(trio(h-1,w)[0] * row_comb(w-2) + trio(h-1,w)[2] * row_comb(w-3) + trio(h-1,w)[1] * row_comb(w-2))
            elif i == w-1:
                lst.append(trio(h-1,w)[w-1] * row_comb(w-2) + trio(h-1,w)[w-3] * row_comb(w-3) + trio(h-1,w)[w-2] * row_comb(w-2))
            elif i > 2 and i < w-1:
                a = row_comb(i-2) * row_comb(w-i)
                b = row_comb(i-1) * row_comb(w-i-1)
                c = row_comb(i-1) * row_comb(w-i)
                lst.append(trio(h-1,w)[i-2] * a + trio(h-1,w)[i] * b + trio(h-1,w)[i-1] * c)
        return lst
    
print(trio(h, w)[k-1] % 1000000007)