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):
H, W, K = map(int, input().split())

fib = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
mod = 10 ** 9 + 7
'''
端にいてそのまま下にいくときfib[W+1]
端にいて右か左にいくときfib[W]
中にいて下に行くとき
'''
if W == 1:
    print(1)
    exit()

dp = [[0] * W for _ in range(H + 1)]
dp[0][0] = 1
for h in range(1, H + 1):
    for w in range(W):
        if w == 0:
            
            dp[h][w] = dp[h - 1][w] * fib[W - 1] + dp[h - 1][w + 1] * fib[W - 2]
        elif w == W - 1:
            dp[h][w] = dp[h - 1][w] * fib[W - 1] + dp[h - 1][w - 1] * fib[W - 2]
        else:
            dp[h][w] = dp[h - 1][w] * fib[w] * fib[W - 1 - w] + dp[h - 1][w + 1] * fib[W - w - 2] * fib[w] + dp[h - 1][
                w - 1] * fib[
                           w - 1] * fib[W - 1 - w]
        dp[h][w] %= mod

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

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

mod = 10**9+7
dp = [["0"]*(W+2) for _ in range(H+1)]
for h in range(H+1):
    dp[h][0] = 0
    dp[h][W+1] = 0
for w in range(W+2):
    dp[0][w] = 0
dp[0][1] = 1

cmb = [1, 2, 3, 5, 8, 13, 21, 34]
def f(h, w):
    if dp[h][w] != "0":
        return dp[h][w]
    dp[h][w] = 0
    dp[h][w] += f(h-1, w-1)*cmb[max(0, w-3)]*cmb[max(0, W-w-1)]
    dp[h][w] += f(h-1, w)*cmb[max(0, w-2)]*cmb[max(0, W-w-1)]
    dp[h][w] += f(h-1, w+1)*cmb[max(0, w-2)]*cmb[max(0, W-w-2)]
    dp[h][w] %= mod
    return dp[h][w]

print(f(H, K))

Solution (Python):
import itertools


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

DP = [0] * w
DP[0] = 1
mod = 10**9 + 7

patterns = []

for line_count in range(w):
    candidates = itertools.combinations(range(w-1), line_count)

    for pattern in candidates:
        usable = True
        prev = 10

        for num in pattern:
            if num == prev + 1:
                usable = False
                break
            else:
                prev = num

        if usable:
            patterns.append(pattern)

for i in range(h):
    next_DP = [0] * w

    for pattern in patterns:
        straight = set(range(w))
        for line in pattern:
            next_DP[line] += DP[line+1]
            next_DP[line] %= mod
            next_DP[line+1] += DP[line]
            next_DP[line+1] % mod
            straight.discard(line)
            straight.discard(line+1)

        for line in straight:
            next_DP[line] += DP[line]
            next_DP[line] %= mod

    DP = next_DP.copy()

ans = DP[k-1]
print(ans%mod)

Solution (Python):
mod = 10 ** 9 + 7
fib = [1, 1, 2, 3, 5, 8, 13, 21, 34]

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

dp = [0] * W
dp[0] = 1

for _ in range(H):

    T = [0] * W

    for i in range(W):
        if 0 < i:
            T[i] += dp[i - 1] * fib[i - 1] * fib[W - i - 1]

        T[i] += dp[i] * fib[i] * fib[W - i - 1]

        if i < W - 1:
            T[i] += dp[i + 1] * fib[i] * fib[W - i - 2]

        T[i] %= mod

    dp = T

print(dp[K - 1])

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

MOD = 10**9 + 7
k -= 1

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

for i in range(h):
    for j in range(w):
        for bit in range(1<<(w-1)):
            ok = True
            for _ in range(w-2):
                if not (bit + (bit<<1) == bit ^ (bit<<1)):
                    ok = False
            if not ok:
                continue
            ni = i+1; nj = j
            if (bit>>j) & 1:
                nj = j+1
            elif j > 0 and (bit>>(j-1)) & 1:
                nj = j-1
            dp[ni][nj] += dp[i][j]
            dp[ni][nj] %= MOD           

ans = dp[h][k]
ans %= MOD
print(ans)

Solution (Python):
MOD = 10**9+7
h, w, K = map(int, input().split())
n = w-1
dp = [[0] * w for _ in range(h+1)]
dp[0][0] = 1

def judge(edge):
    for i in range(1, n):
        if edge[i] and edge[i-1]: return False
    return True

for i in range(1, h+1):
    for j in range(w):
        for k in range(2**n):
            edge = [1 & (k >> l) for l in range(n)]
            if not judge(edge): continue
            if j < w-1 and edge[j]: dp[i][j] += dp[i-1][j+1]
            if j > 0 and edge[j-1]: dp[i][j] += dp[i-1][j-1]
            edge.append(0)
            if not edge[j] and not edge[j-1]:
                dp[i][j] += dp[i-1][j]

            dp[i][j] %= MOD

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

Solution (Python):
h,w,k=map(int,input().split())
mod=10**9+7
fib=[1,1]
for i in range(6):
  fib.append(fib[-2]+fib[-1])
dp=[[0]*w for i in range(h+1)]
dp[0][0]=1
for i in range(h):
  for j in range(w):
    if w==1:
      dp[i+1][j]=dp[i][j]
    elif j==0:
      dp[i+1][j]=(dp[i][j]*fib[j]*fib[w-j-1]+dp[i][j+1]*fib[j]*fib[w-j-2])%(mod)
    elif j==w-1:
      dp[i+1][j]=(dp[i][j-1]*fib[j-1]*fib[w-j-1]+dp[i][j]*fib[j]*fib[w-j-1])%(mod)
    else:
      dp[i+1][j]=(dp[i][j-1]*fib[j-1]*fib[w-j-1]+dp[i][j]*fib[j]*fib[w-j-1]+dp[i][j+1]*fib[j]*fib[w-j-2])%(mod)
print(dp[h][k-1])

Solution (Python):
H, W, K = [int(_) for _ in input().split()]

pat = set()


def make_pat(v):
    if v in pat: return
    a = v
    while a > 0:
        if a & 1 and a & 2:
            return
        a = a >> 1

    pat.add(v)
    for i in range(W - 1):
        a = 1 << i
        if a & v: continue
        make_pat(a | v)


make_pat(0)


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

dp[0][0] = 1
MOD = 10 ** 9 + 7

for i in range(H):
    for line in pat:
        for j in range(W):
            
            if line & (1 << j):  
                dp[i + 1][j + 1] += dp[i][j] % MOD
            elif j > 0 and line & (1 << (j - 1)):  
                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):


import itertools

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

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


move = [[0]*W for _ in range(W)]
for horizontal_line_pattern in list(itertools.product([0,1], repeat=W-1)):
    for i in range(W-2):
        if horizontal_line_pattern[i] == 1 and horizontal_line_pattern[i+1] == 1:
            break
    else:
        for i in range(W-1):
            if horizontal_line_pattern[i] == 1:
                move[i][i+1] += 1
                move[i+1][i] += 1
            else:
                if i == 0:
                    move[0][0] += 1
                elif i == W-2:
                    move[W-1][W-1] += 1
                try:
                    if horizontal_line_pattern[i+1] == 0:
                        move[i+1][i+1] += 1
                except IndexError:
                    pass


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

for i in range(1, H+1):
    for j in range(W):
        for k in [-1, 0, 1]:
            try:
                dp[i][j] += dp[i-1][j+k] * move[j][j+k]
                dp[i][j] %= MOD
            except IndexError:
                pass

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

Solution (Python):


import itertools

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


def check(L):
    n=len(L)
    for i in range(1,n):
        if L[i]==1 and L[i-1]==1:
            return False
    return True
        



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

for i in range(H):
    for ite in itertools.product([0,1], repeat=(W-1)):
        ite=list(ite)
        ite.append(0)
        if check(ite):
            flag=0
            for j in range(W):
                if flag==1:
                    dp[i+1][j-1]+=dp[i][j]
                    dp[i+1][j-1]%=mod
                    flag=0
                elif ite[j]==1:
                    dp[i+1][j+1]+=dp[i][j]
                    dp[i+1][j+1]%=mod
                    flag=1
                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())


a=[1]*max((W-1),1)
for i in range(W-1):
    a[i]+=i
    if i-2>0:
        a[i]+=((i-1)*(i-2))//2
        if i==5:
            a[i]+=1
        elif i==6:
            a[i]+=4
    
mod=10**9+7    


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

for i in range(H):
    for j in range(W):
        for k in range(-1,2,1):
            if j+k>=0 and j+k<W:
                l=min(j,j+k)
                r=max(j,j+k)
                dp[i+1][j+k]+=dp[i][j]*a[max(0,l-1)]*a[max(0,(W-1)-r-1)]
                dp[i+1][j+k]%=mod
                
print(dp[-1][K-1])

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

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

root = []
for i in range(2 ** (W - 1)):
  flag = 1
  for j in range(1, W - 1):
    if ((i >> j) & 1) & (i >> (j - 1) & 1):
      flag = 0
      break
  if flag:
    root.append(i)

swap = [[j for j in range(W)] for _ in range(len(root))]
for i in range(len(root)):
  for j in range(W - 1):
    if (root[i] >> j) & 1:
      swap[i][j], swap[i][j + 1] =  swap[i][j + 1], swap[i][j]


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

for i in range(H):
  for s in swap:
    for j in range(W):
      dp[i + 1][s[j]] = (dp[i + 1][s[j]] + dp[i][j]) % MOD



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

Solution (Python):
def pow(x,m):
    if m==0:
        return 1
    if m==1:
        return x
    if m%2==0:
        return (pow(x,m//2)**2)%p
    else:
        return (x*(pow(x,(m-1)//2)**2)%p)%p
def V(n):
    if n<=0:return 1
    if n==1:return 2
    if n==2:return 3
    cnt = n+1
    for k in range(2,(n+1)//2+1):
        cnt = (cnt+((A[n-k+1]*B[k])%p*B[n-2*k+1])%p)%p
    return cnt
        
p = 10**9+7
H,W,K = map(int,input().split())
A = [1 for _ in range(W+1)]
for i in range(2,W+1):
    A[i] = (A[i-1]*i)%p
B = [1 for _ in range(W+1)]
B[W] = pow(A[W],p-2)
for i in range(W-1,1,-1):
    B[i] = ((i+1)*B[i+1])%p
dp = [[0 for _ in range(W+2)] for _ in range(H+1)]
dp[1][1] = V(W-2)
if W>=2:
    dp[1][2] = V(W-3)
for h in range(2,H+1):
    for k in range(1,W+1):
        dp[h][k] = ((dp[h-1][k-1]*V(k-3)*V(W-k-1))%p+(dp[h-1][k]*V(k-2)*V(W-k-1))%p+(dp[h-1][k+1]*V(k-2)*V(W-k-2))%p)%p
print(dp[H][K])

Solution (Python):
MOD = 10**9+7
h, w, k = map(int, input().split())
ans = 0
dp = [ [0]*w for _ in range(h+1)]
dp[0][0] = 1
for i in range(h):
  for j in range(2**(w-1)):
    s = bin(j)[2:]
    s = "0"*(w-1-len(s)) + s
    for t in range(w-2):
      if s[t] == s[t+1] == "1":
        break
    else:
      s = "0" + s + "0"
      for t in range(w):
        if s[t] == "0" and s[t+1] == "0":
          dp[i+1][t] += dp[i][t]
        else:
          if s[t] == "1":
            dp[i+1][t] += dp[i][t-1]
          else:
            dp[i+1][t] += dp[i][t+1]
        dp[i+1][t] %= MOD
print(dp[h][k-1])

Solution (Python):
import sys
H,W,K=map(int,input().split())
if W==1:
    print(1)
    sys.exit()
L=[1,1,2,3,5,8,13,21,34]
mod=10**9+7
dp=[[0]*W for i in range(H+1)]
dp[0][0]=1
for i in range(H):
    for j in range(W):
        if j==0:
            dp[i+1][j]+=dp[i][j]*L[W-1]
            dp[i+1][j]+=dp[i][j+1]*L[W-2]
            dp[i+1][j]%=mod
        elif j==W-1:
            dp[i+1][j]+=dp[i][j]*L[W-1]
            dp[i+1][j]+=dp[i][j-1]*L[W-2]
            dp[i+1][j]%=mod
        else:
            dp[i+1][j]+=dp[i][j-1]*L[j-1]*L[W-j-1]
            dp[i+1][j]+=dp[i][j]*L[j]*L[W-j-1]
            dp[i+1][j]+=dp[i][j+1]*L[j]*L[W-j-2]
            dp[i+1][j]%=mod
print(dp[H][K-1])

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

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

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

for i in range(H):
    for j in range(W):
        dp[i][j] %= MOD
        here = dp[i][j]
        for d in range(2 ** (W - 1)):
            d = format(d, '0' + str(W - 1) + 'b')
            if not d.count('11'):
                if j == 0:
                    if d[j] == '1':
                        dp[i + 1][j + 1] += here
                    else:
                        dp[i + 1][j] += here
                elif j == W - 1:
                    if d[j - 1] == '1':
                        dp[i + 1][j - 1] += here
                    else:
                        dp[i + 1][j] += here
                else:
                    if d[j - 1] == '1':
                        dp[i + 1][j - 1] += here
                    elif d[j] == '1':
                        dp[i + 1][j + 1] += here
                    else:
                        dp[i + 1][j] += here

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

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

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

pat = [0] * W
for i in range(2 ** (W - 1)):
    j = bin(i)
    if not str(j).count('11'):
        pat[len(j) - 2] += 1
for i in range(W - 1):
    pat[i + 1] += pat[i]
pat[0] = 1

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

for i in range(H):
    for j in range(W):
        k = j + 1
        if k == 1:
            dp[i + 1][j] += dp[i][j] * pat[max(0, W - 1 - 1)]
            dp[i + 1][j] += dp[i][j + 1] * pat[max(0, W - 1 - 2)]
        elif 1 < k < W:
            dp[i + 1][j] += dp[i][j] * pat[max(0, j - 1)] * pat[max(0, W - k - 1)]
            dp[i + 1][j] += dp[i][j - 1] * pat[max(0, j - 2)] * pat[max(0, W - k - 1)]
            dp[i + 1][j] += dp[i][j + 1] * pat[max(0, j - 1)] * pat[max(0, W - k - 2)]
        else:
            dp[i + 1][j] += dp[i][j] * pat[max(0, W - 1 - 1)]
            dp[i + 1][j] += dp[i][j - 1] * pat[max(0, W - 1 - 2)]

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

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

Solution (Python):
MOD = 10**9+7

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

F = [1,1,2,3,5,8,13,21,34]

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

for i in range(1,H+1):
    for j in range(W):
        dp[i][j] += dp[i-1][j]*F[j]*F[W-j-1]
        if j != W-1:
            dp[i][j] += dp[i-1][j+1]*F[j]*F[W-j-2]
        if j != 0:
            dp[i][j] += dp[i-1][j-1]*F[j-1]*F[W-j-1]
        dp[i][j] %= MOD
        
print(dp[H][K-1])

Solution (Python):
mod = 10**9+7
H, W, K = map(int, input().split())
if W == 1:
    print(1)
    exit()
dp = [[0] * W for _ in range(H+1)]
dp[0][K-1] = 1
factor = [0] * (W-1)
for i in range(W-1):
    for j in range(1 << i):
        for k in range(i-1):
            if (j >> k) & (j >> (k+1)):
                break
        else:
            factor[i] += 1
for i in range(1, H+1):
    for j in range(W):
        for k in [-1, 0, 1]:
            if 0 <= j+k < W:
                left = max(min(j, j+k)-1, 0)
                right = max(W-max(j, j+k)-2, 0)
                dp[i][j] += dp[i-1][j+k] * factor[left] * factor[right]
        dp[i][j] %= mod
print(dp[H][0])

Solution (Python):
def p_d():
    H, W, K = map(int, input().split())
    mod = 10 ** 9 + 7
    dp = [0] * W
    dp[0] = 1
    fib = [1, 1]
    for i in range(2, W):
        fib.append(fib[i - 2] + fib[i - 1])
    some = [0] * W
    for i in range(W):
        some[i] = fib[i] * fib[W - i - 1]
    some_2 = [0] * (W - 1)
    for i in range(W - 1):
        some_2[i] = fib[i] * fib[W - i - 2]
    for i in range(1, H + 1):
        w = 0
        NEXT = [0] * W
        for j in range(W):
            if j > 0:
                NEXT[j - 1] += dp[j] * some_2[j - 1]
                NEXT[j - 1] %= mod
            if j < W - 1:
                NEXT[j + 1] += dp[j] * some_2[j]
                NEXT[j + 1] %= mod
            if dp[j] > 0:
                NEXT[j] += dp[j] * some[j]
                NEXT[j] %= mod
            w += 1
        dp = NEXT
    print(dp[K - 1] % mod)


if __name__ == '__main__':
    p_d()

Solution (Python):
h,w,k=map(int,input().split())
ws=[0]*10
ws[0]=1
ws[1]=1
for i in range(2,10):
    ws[i]=ws[i-1]+ws[i-2]
dp=[[0 for i in range(h+1)] for j in range(w)]
dp[0][0]=1
mod=10**9+7
if w==1:
    print(1)
    exit()
for i in range(h):
    for j in range(w):
        if j==0:
            dp[0][i+1]=dp[0][i]*ws[w-1]+dp[1][i]*ws[max(0,w-2)]
            dp[0][i+1]%=mod
        elif j==w-1:
            dp[w-1][i+1]=dp[w-1][i]*ws[w-1]+dp[w-2][i]*ws[max(0,w-2)]
            dp[w-1][i+1]%=mod
        else:
            dp[j][i+1]=dp[j][i]*ws[max(0,j)]*ws[max(0,w-j-1)]+dp[j-1][i]*ws[max(0,j-1)]*ws[max(0,w-j-1)]+dp[j+1][i]*ws[max(0,j)]*ws[max(0,w-j-2)]
            dp[j][i+1]%=mod
print(dp[k-1][h]%mod)

Solution (Python):
import sys

MOD = 10 ** 9 + 7

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

def main():
    if w == 1:
        return 1
        
    ok = []
    for i in range(2 ** (w - 1)):
        prev = False
        for j in range(w-1):
            if i >> j & 1:
                if prev:
                    break
                else:
                    prev = True
            else:
                prev = False
        else:
            ok.append(i)

    lcr = [(letter, 0) for letter in 'lcr']
    a = [dict(lcr) for _ in range(w)]
    for i in ok:
        j = 0
        while j < w:
            if i >> j & 1:
                a[j]['r'] += 1
                a[j+1]['l'] += 1
                j += 2
            else:
                a[j]['c'] += 1
                j += 1

    res = [0] * w
    res[0] = 1
    for _ in range(h):
        nex = [0] * w
        for j in range(w):
            if j == 0:
                nex[j] = res[j] * a[j]['c'] + res[j+1] * a[j]['r']
            elif j < w - 1:
                nex[j] = res[j-1] * a[j]['l'] + res[j] * a[j]['c'] + res[j+1] * a[j]['r']
            else:
                nex[j] = res[j-1] * a[j]['l'] + res[j] * a[j]['c']
        for j in range(w):
            nex[j] %= MOD
        res = nex

    return res[k-1]
    
if __name__ == '__main__':
    ans = main()
    print(ans)

Solution (Python):
import sys

MOD = 10 ** 9 + 7

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

def main():
    ok = []
    for i in range(2 ** (w - 1)):
        prev = False
        for j in range(w-1):
            if i >> j & 1:
                if prev:
                    break
                else:
                    prev = True
            else:
                prev = False
        else:
            ok.append(i)
        
    res = [0] * w
    res[0] = 1
    for _ in range(h):
        nex = [0] * w
        for i in ok:
            j = 0
            while j < w:
                if i >> j & 1:
                    nex[j] += res[j+1]
                    nex[j+1] += res[j] 
                    j += 2
                else:
                    nex[j] += res[j]
                    j += 1
        for j in range(w):
            nex[j] %= MOD
        res = nex
    
    return res[k-1]
    
if __name__ == '__main__':
    ans = main()
    print(ans)

Solution (Python):
h,w,k = map(int,input().split())
mod = 10**9+7
am = [1,1,2,3,5,8,13,21]
DP = [[0 for i in range(w+1)] for j in range(h+1)]
DP[0][1] = 1
for i in range(1,h+1):
  for j in range(1,w+1):
    DP[i][j] = (DP[i-1][j]*am[j-1]*am[w-j])%mod
    if j > 1:
      DP[i][j] += (DP[i-1][j-1]*am[j-2]*am[w-j])%mod
    if j < w:
      DP[i][j] += (DP[i-1][j+1]*am[j-1]*am[w-j-1])%mod
print((DP[h][k])%mod)

Solution (Python):
H,W,K = map(int,input().split())
mod = 10**9+7
dp = [[0 for i in range(W)] for j in range(H+1)]
dp[0][0] = 1
dp_x = [[0,0] for i in range(W)]
dp_o = [[0,0] for i in range(W)]
dp_x[0][0] = 1
dp_x[0][1] = 1
for i in range(W-1):
    dp_x[i+1][0] = dp_x[i][0]+dp_x[i][1]
    dp_x[i+1][1] =dp_x[i][0]
dp_o[0][0] = 1
dp_o[0][1] = 0
for i in range(W-1):
    dp_o[i+1][0] = dp_o[i][0] + dp_o[i][1]
    dp_o[i+1][1] =dp_o[i][0]
dp_o = [sum(e) for e in dp_o]
dp_x = [sum(e) for e in dp_x]
dp_o = [1]+dp_o
dp_x = [1]+dp_x
if W == 1:
    print(1)
    exit()
for h in range(0,H):
    for w in range(W):
        if w == 0:
            dp[h+1][0] += dp[h][0]*dp_x[W-1-1]%mod
            dp[h+1][0] += dp[h][1]*dp_o[W-1-1]%mod
        elif w == W-1:
            dp[h+1][w] += dp[h][w]*dp_x[W-1-1]%mod
            dp[h+1][w] += dp[h][w-1]*dp_o[W-1-1]%mod
        else:
            
            dp[h+1][w] += dp[h][w]*dp_x[w-1]*dp_x[W-w-2]%mod
            
            dp[h+1][w] += dp[h][w+1]*dp_x[w-1]*dp_o[W-w-2]%mod
            
            dp[h+1][w] += dp[h][w-1]*dp_o[w-1]*dp_x[W-w-2]%mod
print(dp[H][K-1]%mod)

Solution (Python):











import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,hypot,log 
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')

class ModInt:
    def __init__(self, x):
        self.x = x % mod
    
    def __str__(self):
        return str(self.x)
    
    __repr__ = __str__

    def __add__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x + other.x)
        else:
            return ModInt(self.x + other)

    __radd__ = __add__
        
    def __sub__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x - other.x)
        else:
            return ModInt(self.x - other)

    def __rsub__(self, other):
        if isinstance(other, ModInt):
            return ModInt(other.x - self.x)
        else:
            return ModInt(other - self.x)

    def __mul__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x * other.x)
        else:
            return ModInt(self.x * other)

    __rmul__ = __mul__

    def __truediv__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x * pow(other.x, mod-2,mod))
        else:
            return ModInt(self.x * pow(other, mod - 2, mod))
            
    def __rtruediv(self, other):
        if isinstance(other, self):
            return ModInt(other * pow(self.x, mod - 2, mod))
        else:
            return ModInt(other.x * pow(self.x, mod - 2, mod))
            

    def __pow__(self, other):
        if isinstance(other, ModInt):
            return ModInt(pow(self.x, other.x, mod))
        else:
            return ModInt(pow(self.x, other, mod))
            

    def __rpow__(self, other):
        if isinstance(other, ModInt):
            return ModInt(pow(other.x, self.x, mod))
        else:
            return ModInt(pow(other, self.x, mod))

def main():
    H,W,K = MI()
    K-=1

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

    max_bit = 1<<(W-1)
    for h in range(H):
        for mask in range(max_bit):
            before = 0
            ng = False
            for i in range(W):
                if before&(mask>>i):
                    ng = True
                    break
                before = mask>>i&1
            if ng:
                continue
            for i in range(W):
                if 1&mask>>i:
                    dp[h+1][i]+=dp[h][i+1]                
                    dp[h+1][i+1]+=dp[h][i]
                elif i==0 or not 1&mask>>(i-1):
                    dp[h+1][i]+=dp[h][i]
    print(dp[-1][K])


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque
import time
import bisect
def input():
    return sys.stdin.readline()[:-1]
mod=1000000007
h,w,k=map(int,input().split())
n=2**(w-1)
if w==1:
    print(1)
    exit()

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



for l in range(h):
    for i in range(1<<w-1):
        a = str(bin(i))[2:].zfill(w-1)
        if a.count('11') >= 1:
            continue
        for j in range(w):
            if j==0:
                if i & (1<<w-2):
                    dp[l+1][j+1]+=dp[l][j]
                else:
                    dp[l+1][j]+=dp[l][j]
            elif j==w-1:
                if i & 1:
                    dp[l+1][j-1]+=dp[l][j]
                else:
                    dp[l+1][j]+=dp[l][j]
            else:
                if i & (1<<j-1):
                    dp[l+1][j-1]+=dp[l][j]
                elif i & (1<<j):
                    dp[l+1][j+1]+=dp[l][j]
                else:
                    dp[l+1][j]+=dp[l][j]
            

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

Solution (Python):
H, W, K = map(int, input().split())
MOD = 10**9 + 7
if W == 1:
    print(1)
    exit()
MR = [0] * W
ML = [0] * W
MS = [0] * W
for i in range(1 << (W-1)):
    S = bin(i)[2:]
    S = "0"*(W-1-len(S)) + S
    if S.find("11") >= 0:
        continue
    for j, s in enumerate(S):
        if s == "1":
            MR[j] += 1
            ML[j+1] += 1
    for j, (s1, s2) in enumerate(zip("0"+S, S+"0")):
        if s1 == s2 == "0":
            MS[j] += 1

DP = [[0] * W for _ in range(H+1)]
DP[0][0] = 1
for h in range(H):
    for w in range(W-1):
        DP[h+1][w+1] += DP[h][w] * MR[w] % MOD
        DP[h+1][w] += DP[h][w+1] * ML[w+1] % MOD
    for w in range(W):
        DP[h+1][w] += DP[h][w] * MS[w] % MOD

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

Solution (Python):
import sys
input = sys.stdin.readline
H, W, K = map(int, input().split())
mod = 10 ** 9 + 7
dp = [[0] * W for _ in range(H + 1)]
dp[0][0] = 1
for i in range(H):
  for j in range(W):
    for b in range(pow(2, W - 1)):
      f = 0
      t = 0
      bb = []
      for k in range(W - 2, -1, -1):
        bb.append(int(b >= pow(2, k)))
        if b >= pow(2, k): b -= pow(2, k)
      for k in range(len(bb) - 1):
        if bb[k] and (bb[k + 1]):
          f = 1
          break
      if f: continue
      
      if j > 0:
        if bb[j - 1]:
          dp[i + 1][j - 1] += dp[i][j]
          dp[i + 1][j - 1] %= mod
          f = 1
      if j < W - 1:
        if bb[j]:
          dp[i + 1][j + 1] += dp[i][j]
          dp[i + 1][j + 1] %= mod
          f = 1
      if f == 0:
        dp[i + 1][j] += dp[i][j]
        dp[i + 1][j] %= mod
print(dp[-1][K - 1])

Solution (Python):
import itertools
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


H, W, K = list(map(int, sys.stdin.buffer.readline().split()))
K -= 1

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

valid_patterns = []
for pattern in itertools.product([True, False], repeat=W - 1):
    ok = True
    for a, b in zip(pattern, pattern[1:]):
        ok &= not (a and b)
    if ok:
        valid_patterns.append(pattern)
through = [0] * W
for pattern in valid_patterns:
    through[0] += pattern[0] is False
    through[-1] += pattern[-1] is False
    for i, (l, r) in enumerate(list(zip(pattern, pattern[1:]))):
        through[i + 1] += not l and not r


dp = np.zeros((H + 1, W), dtype=int)
dp[0][0] = 1
for h in range(1, H + 1):
    dp[h] = dp[h - 1] * through % MOD
    for pattern in valid_patterns:
        for w, p in enumerate(pattern):
            if p:
                dp[h][w] += dp[h - 1][w + 1]
                dp[h][w + 1] += dp[h - 1][w]
        dp[h] %= MOD
print(dp[-1][K] % MOD)

Solution (Python):
h,w,k = map(int, input().split())
mod = 10 ** 9 + 7
dp = [[0] * w for i in range(h+1)]
dp[0][0] = 1
b0,b1 = 1,0
c = [1]
for i in range(w-1):
  b0, b1 = b0+b1, b0
  c.append(b0+b1)
if w == 1:
  print(1)
  exit()
for i,v_i in enumerate(dp[:h]):
  for j,now in enumerate(v_i):
    if j == 0:
      dp[i+1][j] += (now * (c[max(0,w-2)])) % mod
      dp[i+1][j+1] += (now * (c[max(0,w-3)])) % mod
    elif j == w-1:
      dp[i+1][j] += (now * (c[max(0,w-2)])) % mod
      dp[i+1][j-1] += (now * (c[max(0,w-3)])) % mod
    else:
      dp[i+1][j-1] += (now * c[max(0,j-2)]*c[max(0,w-j-2)]) % mod
      dp[i+1][j] += (now * c[max(0,j-1)]*c[max(0,w-j-2)]) % mod
      dp[i+1][j+1] += (now * c[max(0,j-1)]*c[max(0,w-j-3)]) % mod
ans = dp[h][k-1] % mod
print(ans)

Solution (Python):
h,w,k = map(int, input().split())
mod = 10 ** 9 + 7
dp = [[0] * w for i in range(h+1)]
dp[0][0] = 1
b0,b1 = 1,0
c = [1]
for i in range(w-1):
  b0, b1 = b0+b1, b0
  c.append(b0+b1)
d = [0] + c[1:]
if w == 1:
  print(1)
  exit()
for i,v_i in enumerate(dp[:h]):
  for j,now in enumerate(v_i):
    if j == 0:
      dp[i+1][j] += (now * (c[max(0,w-2)])) % mod
      dp[i+1][j+1] += (now * (c[max(0,w-3)])) % mod
    elif j == w-1:
      dp[i+1][j] += (now * (c[max(0,w-2)])) % mod
      dp[i+1][j-1] += (now * (c[max(0,w-3)])) % mod
    else:
      dp[i+1][j-1] += (now * c[max(0,j-2)]*c[max(0,w-j-2)]) % mod
      dp[i+1][j] += (now * c[max(0,j-1)]*c[max(0,w-j-2)]) % mod
      dp[i+1][j+1] += (now * c[max(0,j-1)]*c[max(0,w-j-3)]) % mod
ans = dp[h][k-1] % mod
print(ans)