Problem p03222 (python)

Fixed submission:
def fib(W):
    a, b = 1, 1
    n = [a, b]
    while W > len(n):
        a, b = b, b + a
        n.append(b)
    return n
H, W, K = map(int, input().split())
f = fib(W)
r = [1] + [0] * (W - 1)
for i in range(H):
    tmp = [0] * W
    for j in range(W):
        if j == 0:
            tmp[j] = r[j] * f[W - j - 1] + r[j + 1] * f[W - j - 2] if W != 1 else 1
        elif j == W - 1:
            tmp[j] = r[j] * f[j] + r[j - 1] * f[j - 1]
        else:
            tmp[j] = r[j] * f[j] * f[W - j - 1] + r[j + 1] * f[W - j - 2] * f[j] + r[j - 1] * f[W - j - 1] * f[j - 1]
    r = tmp
print(r[K - 1] % 1000000007)

Buggy submission (verdict: Runtime Error):
def fib(W):
    a, b = 1, 1
    n = [a, b]
    while W > len(n):
        a, b = b, b + a
        n.append(b)
    return n
H, W, K = map(int, input().split())
f = fib(W)
r = [1] + [0] * (W - 1)
for i in range(H):
    tmp = [0] * W
    for j in range(W):
        if j == 0:
            tmp[j] = r[j] * f[W - j - 1] + r[j + 1] * f[W - j - 2]
        elif j == W - 1:
            tmp[j] = r[j] * f[j] + r[j - 1] * f[j - 1]
        else:
            tmp[j] = r[j] * f[j] * f[W - j - 1] + r[j + 1] * f[W - j - 2] * f[j] + r[j - 1] * f[W - j - 1] * f[j - 1]
    r = tmp
print(r[K - 1] % 1000000007)

Buggy submission (verdict: Runtime Error):
def fib(W):
    a, b = 1, 1
    n = [a, b]
    while W > len(n):
        a, b = b, b + a
        n.append(b)
    return n
H, W, K = map(int, input().split())
f = fib(W)
r = [1] + [0] * (W - 1)
for i in range(H):
    tmp = [0] * W
    for j in range(W):
        if j == 0:
            tmp[j] = r[j] * f[W - j - 1] + r[j + 1] * f[W - j - 2]
        elif j == W - 1:
            tmp[j] = r[j] * f[j] + r[j - 1] * f[j - 1]
        else:
            tmp[j] = r[j] * f[j] * f[W - j - 1] + r[j + 1] * f[W - j - 2] * f[j] + r[j - 1] * f[W - j - 1] * f[j - 1]
    r = tmp
print(r[K - 1] % 1_000_000_007)

Buggy submission (verdict: Runtime Error):
H, W, K = map(int, input().split())
r = []
tmp = []
for i in range(W):
    r.append(0)
    tmp.append(0)
r[0] = 1
p = [1, 2, 4, 7, 12, 20]
ans = 0
for j in range(H):
    if W == 1 and K == 1:
        ans = 1
        break
    for i in range(W):
        u = i
        v = (W - 1) - i
        a, b, c, d = 1, 1, 1, 1
        if u >= 2:
            a += p[u - 2] 
        if v >= 2:
            b += p[v - 2]
        if u - 1 >= 2:
            c += p[u - 3]
        if v - 1 >= 2:
            d += p[v - 3]
        if i == 0:
            tmp[i] = r[i] * a * b + r[i + 1] * a * d
        elif i == (W - 1):
            tmp[i] = r[i - 1] * c * b + r[i] * a * b
        else:
            tmp[i] = r[i - 1] * c * b  + r[i] * a * b + r[i + 1] * a * d
    for i in range(len(tmp)):
        r[i] = tmp[i]
ans = r[K - 1] % 1_000_000_007
print(ans)

Buggy submission (verdict: Runtime Error):
H, W, K = map(int, input().split())
r = []
tmp = []
for i in range(W):
    r.append(0)
    tmp.append(0)
r[0] = 1
p = [1, 2, 4, 7, 12, 20]
ans = 0
for j in range(H):
    if W == 1 and K == 1:
        ans = 1
        break
    for i in range(W):
        u = i
        v = (W - 1) - i
        a, b, c, d = 1, 1, 1, 1
        if u >= 2:
            a += p[u - 2] 
        if v >= 2:
            b += p[v - 2]
        if u - 1 >= 2:
            c += p[u - 3]
        if v - 1 >= 2:
            d += p[v - 3]
        if i == 0:
            tmp[i] = r[i] * a * b + r[i + 1] * a * d
        elif i == (W - 1):
            tmp[i] = r[i - 1] * c * b + r[i] * a * b
        else:
            tmp[i] = r[i - 1] * c * b  + r[i] * a * b + r[i + 1] * a * d
    for i in range(len(tmp)):
        r[i] = tmp[i]
ans = r[K - 1] % 1_000_000_007
print(ans)