Problem: Amidakuji is a traditional method of lottery in Japan.  To make an amidakuji, we first draw W parallel vertical lines, and then draw horizontal lines that connect them. The length of each vertical line is H+1   Find the number of the valid amidakuji that satisfy the following condition, modulo 1\ 000\ 000\ 007: if we trace the path from the top of the leftmost vertical line to the bottom, always following horizontal lines when we encounter them, we reach the bottom of the K-th vertical line from the left.  For example, in the following amidakuji, we will reach the bottom of the fourth vertical line from the left.  

Submission attempts (in order):
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)

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)

Verdicts: Runtime Error

Accepted