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):
# -*- coding: utf-8 -*-

h, w, k = map(int, input().split())


def f(x):
    lst = [1, 2, 3, 5, 7, 13, 19]
    if 0 <= x < 7:
        return lst[x]
    else:
        return 1


ptn = [[0] * (w + 2) for _ in range(w + 2)]
for i in range(w + 2):
    for j in range(w + 2):
        if i == 0 or i == w+1 or j == 0 or j == w+1:
            continue
        elif i == j:
            ptn[i][j] = f(i-2)*f(w-i-1)
        elif i == j + 1:
            ptn[i][j] = f(i-3)*f(w-i-1)
        elif i == j -1:
            ptn[i][j] = f(i-2)*f(w-i-2)
print(ptn)


for _ in range(h - 1):
    temp = [[0] * (w + 2) for _ in range(w + 2)]
    for i in range(w + 2):
        for j in range(w + 2):
            if i == 0 or i == w+1 or j == 0 or j == w+1:
                continue
            else:
                temp[i][j] = ptn[i-1][j]*f(i-3)*f(w-i-1) + ptn[i][j]*f(i-2)*f(w-i-1) + ptn[i+1][j]*f(i-2)*f(w-i-2)

    ptn = temp; print(ptn)

print(ptn[1][k] % 1000000007)


# -*- coding: utf-8 -*-

h, w, k = map(int, input().split())


def f(x):
    lst = [1, 2, 3, 5, 8, 13, 21]
    if 0 <= x < 7:
        return lst[x]
    else:
        return 1


ptn = [[0] * (w + 2) for _ in range(w + 2)]
for i in range(w + 2):
    for j in range(w + 2):
        if i == 0 or i == w + 1 or j == 0 or j == w + 1:
            continue
        elif i == j:
            ptn[i][j] = f(i-2)*f(w-i-1)
        elif i == j + 1:
            ptn[i][j] = f(i-3)*f(w-i-1)
        elif i == j - 1:
            ptn[i][j] = f(i-2)*f(w-i-2)
print(ptn)


for _ in range(h - 1):
    temp = [[0] * (w + 2) for _ in range(w + 2)]
    for i in range(w + 2):
        for j in range(w + 2):
            if i == 0 or i == w + 1 or j == 0 or j == w + 1:
                continue
            else:
                temp[i][j] = ptn[i-1][j]*f(i-3)*f(w-i-1) + ptn[i][j]*f(i-2)*f(w-i-1) + ptn[i+1][j]*f(i-2)*f(w-i-2)

    ptn = temp; print(ptn)

print(ptn[1][k] % 1000000007)


# -*- coding: utf-8 -*-

h, w, k = map(int, input().split())


def f(x):
    lst = [1, 2, 3, 5, 8, 13, 21]
    if 0 <= x < 7:
        return lst[x]
    else:
        return 1


ptn = [[0] * (w + 2) for _ in range(w + 2)]
for i in range(w + 2):
    for j in range(w + 2):
        if i == 0 or i == w + 1 or j == 0 or j == w + 1:
            continue
        elif i == j:
            ptn[i][j] = f(i-2)*f(w-i-1)
        elif i == j + 1:
            ptn[i][j] = f(i-3)*f(w-i-1)
        elif i == j - 1:
            ptn[i][j] = f(i-2)*f(w-i-2)

for _ in range(h - 1):
    temp = [[0] * (w + 2) for _ in range(w + 2)]
    for i in range(w + 2):
        for j in range(w + 2):
            if i == 0 or i == w + 1 or j == 0 or j == w + 1:
                continue
            else:
                temp[i][j] = ptn[i-1][j]*f(i-3)*f(w-i-1) + ptn[i][j]*f(i-2)*f(w-i-1) + ptn[i+1][j]*f(i-2)*f(w-i-2)

    ptn = temp

print(ptn[1][k] % 1000000007)


Verdicts: Wrong Answer

Wrong Answer

Accepted