Problem:
 Score: 400 points    Problem Statement 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 [cm], and the endpoints of the horizontal lines must be at 1, 2, 3, ..., or H [cm] from the top of a vertical line.  A valid amidakuji is an amidakuji that satisfies the following conditions:   No two horizontal lines share an endpoint.  The two endpoints of each horizontal lines must be at the same height.  A horizontal line must connect adjacent vertical lines.    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.       Constraints  H is an integer between 1 and 100 (inclusive).  W is an integer between 1 and 8 (inclusive).  K is an integer between 1 and W (inclusive).         Input Input is given from Standard Input in the following format:  H  W  K       Output Print the number of the amidakuji that satisfy the condition, modulo 1\ 000\ 000\ 007 .        Sample Input 1 1 3 2      Sample Output 1 1  Only the following one amidakuji satisfies the condition:        Sample Input 2 1 3 1      Sample Output 2 2  Only the following two amidakuji satisfy the condition:        Sample Input 3 2 3 3      Sample Output 3 1  Only the following one amidakuji satisfies the condition:        Sample Input 4 2 3 1      Sample Output 4 5  Only the following five amidakuji satisfy the condition:        Sample Input 5 7 1 1      Sample Output 5 1  As there is only one vertical line, we cannot draw any horizontal lines. Thus, there is only one amidakuji that satisfies the condition: the amidakuji with no horizontal lines.       Sample Input 6 15 8 5      Sample Output 6 437760187  Be sure to print the answer modulo 1\ 000\ 000\ 007 .

Solution (Python):
MOD = 10 ** 9 + 7
h, w, k = map(int, input().split())
dp = [0] * w
dp[0] = 1

fdp = [[0, 0] for _ in range(w)]
fdp[0][0] = 1
for i in range(w - 1):
    fdp[i+1][0] += fdp[i][0]
    fdp[i+1][1] += fdp[i][0]
    fdp[i+1][0] += fdp[i][1]

def f(i):
    if i < 0:
        return 1
    return fdp[i][0] + fdp[i][1]

for _ in range(h):
    ndp = [0] * w
    for i in range(w):
        ndp[i] = (ndp[i] + dp[i] * f(i - 1) * f(w - i - 2))  % MOD
        if i + 1 < w:
            ndp[i+1] = (ndp[i+1] + dp[i] * f(i - 1) * f(w - i - 3)) % MOD
        if i - 1 >= 0:
            ndp[i-1] = (ndp[i-1] + dp[i] * f(i - 2) * f(w - i - 2)) % MOD
    dp = ndp
print(dp[k-1])

Solution (Python):
def resolve():
    H, W, K = list(map(int, input().split()))
    dp = [[0 for _ in range(W)] for __ in range(H+1)]
    dp[0][0] = 1
    mod = 10**9+7
    for h in range(H):
        for w in range(W):
            downleft = 0
            down = 0
            downright = 0
            for bits in range(1<<W-1):
                invalid = False
                for odr in range(W-2):
                    if (bits & (1<<odr)) and (bits & (1<<(odr+1))):
                        invalid = True
                if invalid:
                    continue
                if w > 0 and (bits & (1<<(w-1))):
                    downleft += 1
                elif w < W-1 and (bits & (1<<w)):
                    downright += 1
                else:
                    down += 1
            if w > 0 and downleft > 0:
                dp[h+1][w-1] += downleft*dp[h][w]
                dp[h+1][w-1] %= mod 
            if w < W-1 and downright > 0:
                dp[h+1][w+1] += downright*dp[h][w]
                dp[h+1][w+1] %= mod
            if down > 0:
                dp[h+1][w] += down*dp[h][w]
                dp[h+1][w] %= mod
    print(dp[H][K-1])


if '__main__' == __name__:
    resolve()

Solution (Python):
import sys

def S(): return sys.stdin.readline().rstrip()

H,W,K = map(int,S().split())
mod = 10**9+7

if W == 1:
    print(1)
    exit()

fib = [1,1,2,3,5,8,13,21]  

dp = [[0]*(W+1) for _ in range(H+1)]  

for i in range(H+1):
    for j in range(W+1):
        if i == 0:
            if j == 1:
                dp[i][j] = 1
        else:
            if j == 1:
                dp[i][j] = dp[i-1][j]*fib[W-1] + dp[i-1][j+1]*fib[W-2]
                dp[i][j] %= mod
            elif j == W:
                dp[i][j] = dp[i-1][j-1]*fib[W-2] + dp[i-1][j]*fib[W-1]
                dp[i][j] %= mod
            elif 2 <= j <= W-1:
                dp[i][j] = dp[i-1][j-1]*(fib[j-2]*fib[W-j]) + dp[i-1][j]*(fib[j-1]*fib[W-j]) + dp[i-1][j+1]*(fib[j-1]*fib[W-j-1])
                dp[i][j] %= mod

print(dp[H][K])

Solution (Python):

































    





def main():
    H, W, K = map(int, input().split())

    if W == 1:
        return 1

    dp = [[0]*W for _ in range(H)]
    dp[0][0] = 1

    bridges_list = []

    def preset(i, bridges, n_cand):
        if i == n_cand:
            bridges_list.append(bridges)
            return None

        if i-1 in bridges:
            preset(i+1, bridges, n_cand)
        else:
            bridges_1 = bridges[:]
            bridges_2 = bridges[:]
            bridges_1.append(i)

            preset(i+1, bridges_1, n_cand)
            preset(i+1, bridges_2, n_cand)

    preset(0, [], W-1)

    n_bridges = [0] * (W-1)
    for bridges in bridges_list:
        for x in bridges:
            n_bridges[x] += 1

    n_all_cands = len(bridges_list)

    
    

    dp[0][0] = (n_all_cands-n_bridges[0])
    dp[0][1] = n_bridges[0]

    for i in range(H-1):
        for j in range(W):
            if j == 0:
                dp[i+1][j] += dp[i][j] * (n_all_cands-n_bridges[j])
                dp[i+1][j+1] += dp[i][j] * n_bridges[j]
            elif j == W-1:
                dp[i+1][j] += dp[i][j] * (n_all_cands-n_bridges[j-1])
                dp[i+1][j-1] += dp[i][j] * n_bridges[j-1]
            else:
                dp[i+1][j] += dp[i][j] * (n_all_cands-n_bridges[j-1]-n_bridges[j])
                dp[i+1][j-1] += dp[i][j] * n_bridges[j-1]
                dp[i+1][j+1] += dp[i][j] * n_bridges[j]
    

    return dp[-1][K-1] % (10**9 + 7)


print(main())

Solution (Python):
MOD = 10**9+7
h,w,k = map(int, input().split())

patterns = [1,1,2,3,5,8,13,21]

dp = [ [0]*w for _ in range(h+1) ]
dp[0][0] = 1
for i in range(1,h+1):
    for wi in range(w):
        dp[i][wi] = dp[i-1][wi] * patterns[w-1-wi] * patterns[wi-0]
        if wi > 0:
            dp[i][wi] += dp[i-1][wi-1] * patterns[w-1-wi] * patterns[wi-1]
        if wi < w-1:
            dp[i][wi] += dp[i-1][wi+1] * patterns[w-1-wi-1] * patterns[wi-0]
        dp[i][wi] %= MOD

print(dp[h][k-1]%MOD)

Solution (Python):
def f():
    import sys
    input=sys.stdin.buffer.readline
    sys.setrecursionlimit(10**9)
    h,w,k=map(int,input().split())
    dp=[0]*w
    dp[k-1]=1
    ne=[0]*w
    mod=10**9+7
    table=[1,1,2,3,5,8,13,21,34]
    for c in range(h):
        for i in range(w):
            ne[i]=dp[i]*table[i]*table[w-i-1]
            if i>0:
                ne[i]+=dp[i-1]*table[i-1]*table[w-i-1]
            if i<w-1:
                ne[i]+=dp[i+1]*table[i]*table[w-i-2]
            ne[i]%=mod
        dp,ne=ne,dp
    print(dp[0])


if __name__ == "__main__":
    f()

Solution (Python):
import sys

readline = sys.stdin.buffer.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import deque

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

    if w == 1:
        print(1)
        sys.exit()

    que = deque("0")
    com = {i: {j: 0 for j in (-1, 0, 1)} for i in range(1, w + 1)}

    while que:
        cur = que.popleft()

        if len(cur) == w:
            cur += "0"
            for col in range(1, w + 1):
                if col >= 2 and cur[col - 1] == "1":
                    com[col][-1] += 1
                if col <= w - 1 and cur[col] == "1":
                    com[col][1] += 1
                if cur[col-1] == cur[col] == "0":
                    com[col][0] += 1
        else:
            if cur[-1] == "0":
                que.append(cur + "1")
            que.append(cur + "0")

    dp = [[0] * (w + 1) for _ in range(h + 1)]
    dp[0][1] = 1
    for row in range(h):
        for col in range(1, w + 1):
            if col >= 2:
                dp[row + 1][col - 1] += dp[row][col] * com[col][-1]
                dp[row + 1][col - 1] %= MOD
            if col <= w - 1:
                dp[row + 1][col + 1] += dp[row][col] * com[col][1]
                dp[row + 1][col + 1] %= MOD
            dp[row + 1][col] += dp[row][col] * com[col][0]
            dp[row + 1][col] %= MOD

    print(dp[-1][k] % MOD)


if __name__ == '__main__':
    main()

Solution (Python):
H, W, K = map(int, input().split())
MOD = 10**9 + 7

dp = [[0 for w in range(W)] for h in range(H + 1)]
dp[0][0] = 1


for h in range(H):
    for i in range(2 ** (W-1)):
        if '11' in bin(i):
            continue
        for w in range(W):  
            if w == 0:
                if (i >> w) & 1:
                    dp[h+1][w] += dp[h][w+1]
                else:
                    dp[h+1][w] += dp[h][w]
            elif 1 <= w < W-1:
                if (i >> (w-1)) & 1:
                    dp[h+1][w] += dp[h][w-1]
                elif (i >> w) & 1:
                    dp[h+1][w] += dp[h][w+1]
                else:
                    dp[h+1][w] += dp[h][w]
            else:
                if (i >> (w-1)) & 1:
                    dp[h+1][w] += dp[h][w-1]
                else:
                    dp[h+1][w] += dp[h][w]
            dp[h+1][w] %= MOD

print(dp[H][K-1])

Solution (Python):
H, W, K = map(int, input().split())
MOD = 10**9 + 7

if W == 1:
    print(1)
    exit()

dp = [[0 for w in range(W)] for h in range(H + 1)]
dp[0][0] = 1


for h in range(H):
    for i in range(2 ** (W-1)):
        if '11' in bin(i):
            continue
        for w in range(W):  
            if w == 0:
                if (i >> w) & 1:
                    dp[h+1][w] += dp[h][w+1]
                else:
                    dp[h+1][w] += dp[h][w]
            elif 1 <= w < W-1:
                if (i >> (w-1)) & 1:
                    dp[h+1][w] += dp[h][w-1]
                elif (i >> w) & 1:
                    dp[h+1][w] += dp[h][w+1]
                else:
                    dp[h+1][w] += dp[h][w]
            else:
                if (i >> (w-1)) & 1:
                    dp[h+1][w] += dp[h][w-1]
                else:
                    dp[h+1][w] += dp[h][w]
            dp[h+1][w] %= MOD



print(dp[H][K-1])

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

dp = [[0]*w for _ in range(h+1)] 

dp[0][0] = 1

d = {}
M = 10**9+7
def sub(i):
    
    if i in d:
        return d[i]
    if i<=1:
        ans = 1
    else:
        ans = sub(i-1) + sub(i-2)
    ans %= M
    d[i] = ans
    return ans
    

for i in range(1,h+1):
    for j in range(w):
        if j>=1:
            dp[i][j] += dp[i-1][j-1]*sub(j-1)*sub(w-j-1)
        if j<=w-2:
            dp[i][j] += dp[i-1][j+1]*sub(j)*sub(w-j-2)
        dp[i][j] += dp[i-1][j]*sub(j)*sub(w-j-1)
        dp[i][j] %= M
print(dp[h][k])

Solution (Python):
from itertools import product
H, W, K = map(int, input().split())
MOD = 10 ** 9 + 7

dp = [[0] * W for _ in range(H+1)]
dp[0][0] = 1
for h in range(H):
    for bit in range(1<<(W-1)):
        if "11" in bin(bit): continue
        for w in range(W):
            if w > 0 and (bit>>(w-1))&1:
                dp[h+1][w-1] += dp[h][w]
                dp[h+1][w-1] %= MOD
            elif (bit>>w)&1:
                dp[h+1][w+1] += dp[h][w]
                dp[h+1][w+1] %= MOD
            else:
                dp[h+1][w] += dp[h][w]
                dp[h+1][w] %= MOD

print(dp[-1][K-1] % MOD)

Solution (Python):
def split(word): 
    return [char for char in word] 
MOD=10**9+7
h,w,k1=map(int,input().split())
dp=[]
for i in range(h+1):
  dp.append([])
  for j in range(w):
    dp[-1].append(0)
dp[0][0]=1
connections=[0]*(w-1)
totallegal=0
for i in range(pow(2,w-1)):
  s='{0:b}'.format(i)
  k=split(s)
  k.reverse()
  for j in range(w-1-len(k)):
    k.append('0')
  k.reverse()
  failflag=0
  for j in range(1,w-1):
    if k[j]=='1' and k[j-1]=='1':
      failflag=1
  if failflag==1:
    continue
  for j in range(w-1):
    if k[j]=='1':
      connections[j]+=1
  totallegal+=1
for i in range(h):
  for j in range(w):
    used=0
    if j>0:
      dp[i+1][j-1]=(dp[i+1][j-1]+connections[j-1]*dp[i][j])%MOD
      used+=connections[j-1]
    if j<w-1:
      dp[i+1][j+1]=(dp[i+1][j+1]+connections[j]*dp[i][j])%MOD
      used+=connections[j]
    dp[i+1][j]=(dp[i+1][j]+(totallegal-used)*dp[i][j])%MOD
print(dp[h][k1-1])

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

mod = 10 ** 9 + 7

def dfs(idx, used):
    if idx == w - 1:
        return [[]]

    ret = dfs(idx + 1, False)
    if used == False:
        ret2 = dfs(idx + 1, True)
        for l in ret2:
            ret.append(l + [idx])
    return ret

combs = dfs(0, 0)

dp = [0] * w
dp[0] = 1
for i in range(h):
    dp_new = [0] * w
    for bars in combs:
        used = set()
        for start in bars:
            dp_new[start] += dp[start + 1]
            dp_new[start + 1] += dp[start]

            used.add(start)
            used.add(start + 1)

        for i in range(w):
            if i not in used:
                dp_new[i] += dp[i]

    dp = [x % mod for x in dp_new]

print(dp[k-1])

Solution (Python):












import sys
readline = sys.stdin.readline

DIV = 10 ** 9 + 7
H,W,K = map(int,readline().split())

P = [0] * max(W - 2 + 1,3)
P[1],P[2] = 2,3
for i in range(3, len(P)):
  P[i] = P[i - 1] + P[i - 2]
  





dp = [[0 for j in range(W)] for i in range(H + 1)]

dp[0][0] = 1 

def calc(L,R): 
  res = 1
  if 1 < L:
    
    res *= P[L - 1]
    res %= DIV
  if (W - 1) - (R + 1) >= 1:
    
    res *= P[(W - 1) - (R + 1)]
    res %= DIV
  return res
  

for i in range(H):
  for j in range(W):
    
    if j + 1 < W:
      dp[i + 1][j + 1] += dp[i][j] * calc(j, j + 1)
      dp[i + 1][j + 1] %= DIV
    
    if j - 1 >= 0:
      dp[i + 1][j - 1] += dp[i][j] * calc(j - 1,j)
      dp[i + 1][j - 1] %= DIV
    
    dp[i + 1][j] += dp[i][j] * calc(j,j) 
    dp[i + 1][j] % DIV
    

print(dp[H][K - 1] % DIV)

Solution (Python):












import sys
readline = sys.stdin.readline

DIV = 10 ** 9 + 7
H,W,K = map(int,readline().split())

P = [0] * max(W - 2 + 1,3)
P[1],P[2] = 2,3
for i in range(3, len(P)):
  P[i] = P[i - 1] + P[i - 2]
  





dp = [[0 for j in range(W)] for i in range(H + 1)]

dp[0][0] = 1 

def calc(L,R): 

  res = 1
  if 1 < L:
    
    res *= P[L - 1]

    res %= DIV
  if (W - 1) - (R + 1) >= 1:
    

    res *= P[(W - 1) - (R + 1)]

    res %= DIV

  return res
  

for i in range(H):
  for j in range(W):
    
    if j + 1 < W:

      dp[i + 1][j + 1] += dp[i][j] * calc(j, j + 1)
      dp[i + 1][j + 1] %= DIV

    
    if j - 1 >= 0:

      dp[i + 1][j - 1] += dp[i][j] * calc(j - 1,j)
      dp[i + 1][j - 1] %= DIV

    

    dp[i + 1][j] += dp[i][j] * calc(j,j) 
    dp[i + 1][j] % DIV




    

print(dp[H][K - 1] % DIV)

Solution (Python):
def check(amidakuji,w):
    before=0
    flag=True
    for _ in range(w-1):
        if amidakuji&1==1 and before==1:
            flag=False
            break
        elif amidakuji&1==1:
            before=1
            amidakuji>>=1
        else:
            before=0
            amidakuji>>=1
    return flag

from sys import stdin
def main():
    
    readline=stdin.readline
    mod=10**9+7
    h,w,k=map(int,readline().split())

    dp=[[0]*w for _ in range(h+1)]
    dp[0][0]=1
    for i in range(1,h+1):
        for bit in range(1<<(w-1)):
            if check(bit,w)==False:
                continue
            else:
                for j in range(w):
                    if j==0:
                        if bit&1==1:
                            dp[i][j+1]+=dp[i-1][j]
                        else:
                            dp[i][j]+=dp[i-1][j]
                    elif j==w-1:
                        if bit&1==1:
                            dp[i][j-1]+=dp[i-1][j]
                        else:
                            dp[i][j]+=dp[i-1][j]
                    else:
                        if bit&1==1:
                            dp[i][j-1]+=dp[i-1][j]
                            bit>>=1
                        else:
                            bit>>=1
                            if bit&1==1:
                                dp[i][j+1]+=dp[i-1][j]
                            else:
                                dp[i][j]+=dp[i-1][j]

                for j in range(w):
                    dp[i][j]%=mod

    print(dp[h][k-1])

if __name__=="__main__":
    main()

Solution (Python):
def main():
    h, w, k = map(int, input().split())

    bf = [0] * (w + 2)
    nx = [0] * (w + 2)
    bf[1] = 1

    c = [1, 1, 2, 3, 5, 8, 13, 21]

    for i in range(1, h + 1):
        for j in range(1, w + 1):
            nx[j] = c[j - 1] * c[w - j] * bf[j] + c[j - 1] * c[w - j - 1] * bf[j + 1] + c[j - 2] * c[w - j] * bf[j - 1]

        bf = nx
        nx = [0] * (w + 2)

    print(bf[k] % (10 ** 9 + 7))


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    h, w, k = map(int, input().split())

    dp = [[0] * (w + 2) for _ in range(h + 1)]
    dp[0][1] = 1

    c = [1, 1, 2, 3, 5, 8, 13, 21]

    for i in range(1, h + 1):
        for j in range(1, w + 1):
            dp[i][j] = c[j - 1] * c[w - j] * dp[i - 1][j] + c[j - 1] * c[w - j - 1] * dp[i - 1][j + 1] + c[j - 2] * c[w - j] * dp[i - 1][j - 1]

    print(dp[h][k] % (10 ** 9 + 7))


if __name__ == '__main__':
    main()

Solution (Python):
def fib():
    a = 1
    b = 0
    while 1:
        c = a + b
        yield c
        a = b
        b = c


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

    dp = [[0] * (w + 2) for _ in range(h + 1)]
    dp[0][1] = 1
    f = fib()
    c = [f.__next__() for _ in range(w + 1)]

    for i in range(1, h + 1):
        for j in range(1, w + 1):
            dp[i][j] = c[j - 1] * c[w - j] * dp[i - 1][j] + c[j - 1] * c[w - j - 1] * dp[i - 1][j + 1] + c[j - 2] * c[w - j] * dp[i - 1][j - 1]

    print(dp[h][k] % (10 ** 9 + 7))


if __name__ == '__main__':
    main()

Solution (Python):
def fib(n):
    a = 1
    b = 0
    i = 0
    while i < n:
        i += 1
        c = a + b
        yield c
        a = b
        b = c


def main():
    h, w, k = map(int, input().split())
    mod = 10 ** 9 + 7
    
    dp = [[0] * (w + 2) for _ in range(h + 1)]
    dp[0][1] = 1
    c = [i for i in fib(w + 1)]

    for i in range(1, h + 1):
        for j in range(1, w + 1):
            x = c[j - 1] * c[w - j]
            y = c[j - 1] * c[w - j - 1]
            z = c[j - 2] * c[w - j]

            dp[i][j] = (x * dp[i - 1][j] + y * dp[i - 1][j + 1] + z * dp[i - 1][j - 1]) % mod

    print(dp[h][k])


if __name__ == '__main__':
    main()

Solution (Python):
h,w,K = map(int,input().split())

mod = 10**9+7

num = 2**(w-1)

li = []

if w == 1:
    if K == 1:
        print(1)
        exit()
    else:
        print(0)
        exit()

for i in range(num):
    tmp = format(i, '0'+str(w-1)+'b')
    cnt = 0
    for j in range(w-1):
        if tmp[j] == '1':
            if cnt == 1:
                break
            else:
                cnt = 1
        else:
            cnt = 0
        if j == w-2:
            li.append(tmp)
    

dp = [[0 for i in range(w)] for j in range(h+1)]

dp[0][0] = 1

for i in range(h):
    
    for j in range(len(li)):
        for k in range(w):
            
            if k == 0:
                if li[j][k] == '1':
                    dp[i+1][k+1] += dp[i][k]
                    dp[i+1][k+1] %= mod
                else:
                    dp[i+1][k] += dp[i][k]
                    dp[i+1][k] %= mod
            elif k == w-1:
                if li[j][k-1] == '1':
                    dp[i+1][k-1] += dp[i][k]
                    dp[i+1][k-1] %= mod
                else:
                    dp[i+1][k] += dp[i][k]
                    dp[i+1][k] %= mod
            else:
                if li[j][k-1] == '1':
                    dp[i+1][k-1] += dp[i][k]
                    dp[i+1][k-1] %= mod
                elif li[j][k] == '1':
                    
                    dp[i+1][k+1] += dp[i][k]
                    
                    dp[i+1][k+1] %= mod
                else:
                    dp[i+1][k] += dp[i][k]
                    dp[i+1][k] %= mod
                    
print(dp[h][K-1])

Solution (Python):
h,w,k = [int(i) for i in input().split()]

mod = 10**9 + 7
   

dp = [[0 for _ in range(w)] for _ in range(h + 1)]
dp[0][0] = 1

for i in range(h):
    for bit in range(1<<(w-1)):
        if '11' in bin(bit) : continue
        for j in range(w):
            if j > 0 and bit & (1 << (j-1)):
                dp[i+1][j-1] += dp[i][j] % mod 
            elif bit & (1 << j):
                dp[i+1][j+1] += dp[i][j] % mod
            else:
                dp[i+1][j] += dp[i][j] % mod
                
print(dp[h][k-1]%mod)

Solution (Python):


"""
AtCoder Beginner Contest 113  D - Number of Amidakuji

愚直に考えると、
・それぞれの縦棒の間に、横棒があるかないかの2通り。これがある高さhだけで、2^(W-1)通りある（横棒が２連続で続かないので、厳密には違うが）。
・これが高さH（最大100個分）あるので、(2^7)^100 とか？とにかく全探索は間に合わない。

メタ視点だが、W<=8なので、bitDPとかやれそう。
愚直解の何がよくないかというと、たとえば H = 6,W = 4 みたいなあみだくじについて考えるとして、
・この中で上から3段目までが同じでそれより下が異なるあみだくじというのがあるが、同じ部分も毎回シミュレートしてしまうのが重複計算になって無駄。

なので、高さごとに取りうる横棒のパターンを確認して、それらについて移動先の場合の数を求めていけばいいか。

各高さについて毎回横棒のパターンをbitで探索するが何故か思いつかなかった。
"""

H,W,K = map(int, input().split())
MOD = 10**9 + 7


dp = [[0 for _ in range(W)] for _ in range(H+1)]
dp[0][0] = 1

ws = set()
for bit in range(1 << (W-1)):
    if "11" in bin(bit):
        continue
    ws.add(bit)


for i in range(H):
    for bit in ws:
        
        for j in range(W):
          

            
            if j != W-1 and bit & (1 << (W-2-j)): 
                    dp[i+1][j+1] += dp[i][j]
                    dp[i+1][j+1] %= MOD

            
            elif j != 0 and bit & (1 << (W-1-j)): 
                dp[i+1][j-1] += dp[i][j]
                dp[i+1][j-1] %= MOD

            else:
                  
                dp[i+1][j] += dp[i][j]
                dp[i+1][j] %= MOD
                



print(dp[-1][K-1])

Solution (Python):

H,W,K = map(int, input().split())
MOD = 10**9 + 7


dp = [[0 for _ in range(W)] for _ in range(H+1)]
dp[0][0] = 1

ws = set()
for bit in range(1 << (W-1)):
    if "11" in bin(bit):
        continue
    ws.add(bit)


for i in range(H):
    for bit in ws:
        
        for j in range(W):
          

            
            if j != W-1 and bit & (1 << (W-2-j)): 
                    dp[i+1][j+1] += dp[i][j]
                    dp[i+1][j+1] %= MOD

            
            elif j != 0 and bit & (1 << (W-1-j)): 
                dp[i+1][j-1] += dp[i][j]
                dp[i+1][j-1] %= MOD

            else:
                  
                dp[i+1][j] += dp[i][j]
                dp[i+1][j] %= MOD
                



print(dp[-1][K-1])

Solution (Python):

import sys
input = sys.stdin.readline









H,W,K = map(int,input().split())

mod = 10**9+7


j = [0,1,1,2,3,5,8,13];

m = [1,1,2,3,5,8,13,21];
 

dp = [[0 for _ in range(W)] for _ in range(H+1)]
dp[0][0] = 1
 
for h in range(H+1):
    for w in range(W):
        
        if w != 0:
            dp[h][w] += dp[h-1][w-1] * j[w] * m[W-1-w]
        
        if w != W-1:
            dp[h][w] += dp[h-1][w+1] * m[w] * j[W-1-w]
        
        dp[h][w] += dp[h-1][w] * m[w] * m[W-1-w]
        
        dp[h][w] %= mod;

    
print(dp[H][K-1])

Solution (Python):
h,w,K=map(int,input().split())
def two(x):
	return "0"*(w-1-len(bin(x)[2:]))+bin(x)[2:]
dp=[[0]*w for _ in range(h+1)]
dp[0][0]=1
mod=10**9+7
for i in range(h):
	for j in range(2**(w-1)):
		r=two(j)
		f=1
		for k in range(w-2):
			if r[k]==r[k+1]=="1":
				f=0
				break
		if f:
			for k in range(w):
				if k+1<w:
					if r[k]=="1":
						dp[i+1][k+1]+=dp[i][k]
						dp[i+1][k+1]%=mod
						continue
				if k>0:
					if r[k-1]=="1":
						dp[i+1][k-1]+=dp[i][k]
						dp[i+1][k-1]%=mod
						continue
				dp[i+1][k]+=dp[i][k]
				dp[i+1][k]%=mod
print(dp[h][K-1])

Solution (Python):
import itertools

H, W, K = map(int, input().split())
mod = 10**9+7
patterns = []
for p in itertools.product([0, 1], repeat=W-1):
    valid = True
    for i in range(W-2):
        if p[i] == p[i+1] == 1:
            valid = False
            break
    if valid:
        patterns += [p]

dp = [[0]*(W+1) for _ in range(H+1)]
dp[0][0] = 1
for i in range(H):
    for j in range(W):
        for pattern in patterns:
            if j > 0 and pattern[j-1] == 1:
                dp[i+1][j-1] += dp[i][j]
                dp[i+1][j-1] %= mod
            elif j < W-1 and pattern[j] == 1:
                dp[i+1][j+1] += dp[i][j]
                dp[i+1][j+1] %= mod
            else:
                dp[i+1][j] += dp[i][j]
                dp[i+1][j] %= mod
print(dp[H][K-1])

Solution (Python):
import math
import sys
MOD = 1000000007

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

if w == 1:
    print(1)
    sys.exit()

A = [[1]]


def bit(x, i):
    return (x >> i) & 1


def invalid(x):
    ans = False
    for j in range(w):
        if bit(x, j) == 1 and bit(x, j+1) == 1:
            ans = True
    return ans


for i in range(w-1):
    A[0].append(0)

for i in range(1, h+1):
    A.append([])
    for j in range(w):
        A[i].append(0)
    for x in range(2**(w-1)):
        if(invalid(x)):
            continue
        
        
        if bit(x, 0) == 1:
            A[i][0] = (A[i][0] + A[i-1][1]) % MOD
        else:
            A[i][0] = (A[i][0] + A[i-1][0]) % MOD
        if bit(x, w-2) == 1:
            A[i][w-1] = (A[i][w-1] + A[i-1][w-2]) % MOD
        else:
            A[i][w-1] = (A[i][w-1] + A[i-1][w-1]) % MOD
        
        for j in range(1, w-1):
            if bit(x, j-1) == 1:
                A[i][j] = (A[i][j] + A[i-1][j-1]) % MOD
            elif bit(x, j) == 1:
                A[i][j] = (A[i][j] + A[i-1][j+1]) % MOD
            else:
                A[i][j] = (A[i][j] + A[i-1][j]) % MOD



print(A[h][k-1])

Solution (Python):
import sys
from functools import lru_cache
def input(): return sys.stdin.readline().strip()
mod = 1000000007

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        
        
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

@lru_cache(maxsize=None)
def calc(n):
    """
    n個のものから隣り合わないように物をいくつか選択する場合の数(何も選ばないケースも許す)
    これは実はフィボナッチ数列になる
    """
    if n == -1: return 1
    if n == 0: return 1
    if n == 1: return 2
    return (calc(n - 1) + calc(n - 2)) % mod

@lru_cache(maxsize=None)
def func(h, w, k):
    if h == 0 and k == 1: return 1
    if h == 0: return 0
    if k == 1:
        val1 = func(h - 1, w, 1) * calc(w - 2) % mod
        val2 = func(h - 1, w, 2) * calc(w - 3) % mod
        return (val1 + val2) % mod
    if k == w:
        val1 = func(h - 1, w, w) * calc(w - 2) % mod
        val2 = func(h - 1, w, w - 1) * calc(w - 3) % mod
        return (val1 + val2) % mod
    val1 = func(h - 1, w, k - 1) * calc(k - 3) * calc(w - (k + 1)) % mod
    val2 = func(h - 1, w, k) * calc(k - 2) * calc(w - (k + 1)) % mod
    val3 = func(h - 1, w, k + 1) * calc(k - 2) * calc(w - (k + 2)) % mod
    return (val1 + val2 + val3) % mod

def main():
    H, W, K = map(int, input().split())
    if W == 1:
        print(1)
        return
    if W == 2:
        comb = Combination(H)
        if K == 1:
            ans = 0
            for i in range(H // 2 + 1): ans += comb(H, i * 2)
            print(ans)
        else:
            ans = 0
            for i in range(1, (H + 1) // 2 + 1): ans += comb(H, i * 2 - 1)
            print(ans)
        return
    print(func(H, W, K))
    

    




if __name__ == "__main__":
    main()

Solution (Python):


H, W, K = map(int, input().split())
MOD = 10**9 + 7

comb = []
def dfs(n, p):
    if len(n) == (W-1):
        if len(n) == 0:
            n = [0]
        comb.append(tuple(n))
        return
    for i in (0, 1):
        if p == 1 and i == 1:
            continue
        n.append(i)
        dfs(n, i)
        n.pop()  

dfs([], 0)

dp = [[0] * W for _ in range(H+1)]
dp[0][0] = 1
for h in range(H):
    for w in range(W):
        
        tmp = 0
        for i in comb:
            if w == 0 and i[w] == 0:
                tmp += 1
            elif w == (W-1) and i[w-1] == 0:
                tmp += 1
            elif i[w-1] == 0 and i[w] == 0:
                tmp += 1
        dp[h+1][w] += dp[h][w] * tmp

        
        if w != 0:
            tmp = 0
            for i in comb:
                if i[w-1] == 1:
                    tmp += 1
            dp[h+1][w] += dp[h][w-1] * tmp        

        
        if w != (W-1):
            tmp = 0
            for i in comb:
                if i[w] == 1:
                    tmp += 1
            dp[h+1][w] += dp[h][w+1] * tmp  

print(dp[H][K-1]%MOD)

Solution (Python):

from itertools import product


def patterns(w):
    res = []
    for pt in product([0, 1], repeat=w):
        valid = True
        for i in range(w - 1):
            if pt[i] == pt[i + 1] == 1:
                valid = False
                break
        if valid:
            res.append(pt)
    return res


def submit():
    h, w, k = [int(e) for e in input().split()]
    dp = [[0 for _ in range(w)] for _ in range(h + 1)]
    dp[0][0] = 1
    modp = 10 ** 9 + 7

    pts = patterns(w - 1)

    for i in range(1, h + 1):
        for j in range(w):
            for pt in pts:
                if j > 0 and pt[j - 1] == 1: 
                    dp[i][j - 1] += dp[i - 1][j]
                    dp[i][j - 1] %= modp
                elif j < w - 1 and pt[j] == 1:  
                    dp[i][j + 1] += dp[i - 1][j]
                    dp[i][j + 1] %= modp
                else:
                    dp[i][j] += dp[i - 1][j]
                    dp[i][j] %= modp


    print(dp[h][k - 1])


submit()