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):
height, width, k = map(int, input().split())

start_w = 1
end_w = width

if end_w <= 1:
    print(1)
    exit()


def enum_no_relation_cases(n, m=0):
    front = n - (start_w + 1) - (m * (m - 1)) // 2
    rear = end_w - (n + 1) - (m * (m + 1)) // 2
    return int(enum_amida_all_cases(front) * enum_amida_all_cases(rear))


def enum_amida_all_cases(n):
    if n < 1:
        return 1
    return fibonacci(n + 2)


f = [1, 1, 1] + ([0] * (end_w - 1))


def fibonacci(n):
    if f[n] == 0:
        f[n] = fibonacci(n - 1) + fibonacci(n - 2)
    return f[n]


ans = [[0] * (1 + end_w + 1) for i in range(height + 1)]
ans[0][start_w] = 1
search_range = start_w + 1
for h in range(1, height + 1):
    for w in range(1, search_range + 1):
        from_just_above = ans[h - 1][w] * enum_no_relation_cases(w)
        from_upper_left = ans[h - 1][w - 1] * enum_no_relation_cases(w, -1)
        from_upper_right = ans[h - 1][w + 1] * enum_no_relation_cases(w, 1)
        ans[h][w] = from_just_above + from_upper_left + from_upper_right

    if search_range < end_w:
        search_range += 1

print(ans[height][k] % 1000000007)

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

if w == 1:
    print(1)
else:
    acr = []
    for p in range(2**(w-1)):
        det = 0
        pp = p
        exist = [0] * (w-1)
        for i in range(w-1):
            exist[i] = pp % 2
            pp = pp // 2
        for ii in range(w-2):
            if exist[ii] == 1 and exist[ii+1] == 1:
                det = 1
        if det == 0:
            acr.append(exist[:])
    

    cur = [0] * w
    cur[0] = 1
    

    for t in range(h):
        n = [0] * w
        for x in range(len(acr)):
            n[0] = (n[0] + cur[1] * acr[x][0] + cur[0] * (1-acr[x][0]))%MOD
            for j in range(1,w-1):
                n[j] = (n[j] + cur[j-1] * acr[x][j-1] + cur[j+1] * acr[x][j] + cur[j] * (1-acr[x][j-1])*(1-acr[x][j]))%MOD
            n[w-1] = (n[w-1] + cur[w-2] * acr[x][w-2] + cur[w-1] * (1-acr[x][w-2])) % MOD
        
        cur = n[:]
        
    print(cur[k-1])

Solution (Python):
def main():
    MOD = 1000000007
    
    H, W, K = map(int, input().split())
    table = [[0, 0, 0] for i in range(9)]
    
    for i in range(2**(W-1)):
        n = [i & 2**j for j in range(8)]
        
        for i in range(7):
            if n[i] and n[i+1]:
                break
        else:
            i = 0
            while i < W:
                if not n[i]:
                    table[i+1][1] += 1
                    i += 1
                else:
                    table[i+1][2] += 1
                    table[i+2][0] += 1
                    i += 2
                    
    dp = [[0 for i in range(W+2)] for j in range(H+1)] 
    dp[0][1] = 1
    
    for i in range(1, H+1):
        for j in range(1, W+1):
            a = dp[i-1][j-1] * table[j][0]
            b = dp[i-1][j] * table[j][1]
            c = dp[i-1][j+1] * table[j][2]
            dp[i][j] = (a+b+c) % MOD
        
    print(dp[H][K])
    
if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import itertools
    mod = 10**9+7
    H,W,K = map(int, input().split())
    zero = [0,1]
    dp = [[[0]*W for i in range(W)] for j in range(H+1)]
    for i in range(W):
        dp[0][i][i] = 1
    
    for h in range(1,H+1):
        
        for v in itertools.product(zero, repeat = W-1):
            flag = 0
            for i in range(len(v)-1):
                if v[i] == v[i+1] == 1:
                    flag = 1
            if flag == 0:
                goto = []
                for i in range(W):
                    goto.append(i)
                for i in range(len(v)):
                    if v[i] == 1:
                        tmp = goto[i]
                        goto[i] = goto[i+1]
                        goto[i+1] = tmp
                
                for i in range(W):
                    for j in range(W):
                        dp[h][i][goto[j]] += dp[h-1][i][j]
                        dp[h][i][goto[j]] %= mod
        
    print(dp[H][0][K-1])
            
    
main()

Solution (Python):
H, W, K = map(int,input().split())
dp = [[0]*W for _ in range(H+1)]
dp[0][0] = 1

ck = [0]*9
ck[0] = 1
for i in range(1,9):
  for j in range(2**(i-1)):
    for k in range(i-1):
      if (j>>k)&(j>>(k+1))==True:
        break
    else:
      ck[i] += 1

mod = 10**9+7
for i in range(1,H+1):
  for j in range(W):
    if (j == 0)&(j == W-1):
      dp[i][j] = dp[i-1][j]*(ck[j]*ck[W-1-j])
    elif j == 0:
      dp[i][j] = dp[i-1][j+1]*(ck[j]*ck[W-j-2])+dp[i-1][j]*(ck[j]*ck[W-1-j])
    elif j == W-1:
      dp[i][j] = dp[i-1][j]*(ck[j]*ck[W-1-j])+dp[i-1][j-1]*(ck[j-1]*ck[W-j-1])
    else:
      dp[i][j] = dp[i-1][j+1]*(ck[j]*ck[W-j-2])+dp[i-1][j]*(ck[j]*ck[W-1-j])+dp[i-1][j-1]*(ck[j-1]*ck[W-j-1])

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

Solution (Python):

def genP(W):
    P = []
    D = [0]*(W-1)
    P.append(D[:])
    for i in range(2**(W-1)-1):
        d = 0
        while D[d] == 1:
            D[d] = 0
            d+=1
        D[d] = 1
        if any(D[i] == 1 and D[i+1] == 1 for i in range(W-2)):
            continue
        P.append(D[:])
    return P 


def make_swap(p, W):
    base = [x for x in range(0,W)]
    b = base[:] 
    for w in range(len(p)):
        if p[w] == 1:
            b[w], b[w+1] = b[w+1], b[w]
    return b


def solve(H, W, K):
    swaps = []
    for p in genP(W):
        s = make_swap(p, W)
        swaps.append(s)

    count = [[0]*W for i in range(H+1)]
    count[0][0] = 1

    for h in range(0,H):
        for w in range(0, W):
            for swap in swaps:
                count[h+1][w] += count[h][swap[w]]
                count[h+1][w] %= 1000000007
    
    print(count[H][K-1])

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

Solution (Python):
def genP(W):
    P = []
    D = [0]*(W-1)
    P.append(D[:])
    for i in range(2**(W-1)-1):
        d = 0
        while D[d] == 1:
            D[d] = 0
            d+=1
        D[d] = 1
        if any(D[i] == 1 and D[i+1] == 1 for i in range(W-2)):
            continue
        P.append(D[:])
    return P 

def make_swap(p, W):
    base = [x for x in range(0,W)]
    b = base[:] 
    for w in range(len(p)):
        if p[w] == 1:
            b[w], b[w+1] = b[w+1], b[w]
    return b

if 0==1:
    W = 4
    base = [x-1 for x in range(1,W+1)]
    for p in genP(W):
        print(*base)
        print("", *p)
        print(*make_swap(p, W))
        print()

def solve(H, W, K):
    swaps = []
    for p in genP(W):
        s = make_swap(p, W)
        swaps.append(s)

    count = [[0]*W for i in range(H+1)]
    count[0][0] = 1

    for h in range(0,H):
        for w in range(0, W):
            for swap in swaps:
                count[h+1][w] += count[h][swap[w]]
                count[h+1][w] %= 1000000007
    
    print(count[H][K-1])

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

Solution (Python):
F = [1, 1]
for i in range(7):
  F.append(F[i]+F[i+1])

h, w, k = map(int, input().split())
mod = 10**9 + 7
a = [[0 for i in range(w)] for i in range(h+1)]
a[0][0] = 1

if w == 1:
  print(1)
else:
  for i in range(h):
    for j in range(w):
      if j == 0:
        a[i+1][j] += F[w-1] * a[i][j] % mod
        a[i+1][j+1] += F[w-2] * a[i][j] % mod
      elif j==w-1:
        a[i+1][j] += F[w-1] * a[i][j] % mod
        a[i+1][j-1] += F[w-2] * a[i][j] % mod
      else:
        a[i+1][j] += F[j] * F[w-j-1] * a[i][j] % mod
        a[i+1][j+1] += F[j] * F[w-j-2] * a[i][j] % mod
        a[i+1][j-1] += F[j-1] * F[w-j-1] * a[i][j] % mod
        
  print(a[-1][k-1]%mod)

Solution (Python):
def calc(num):
    a, b, c = 0, 0, 0
    for i in range(2 ** (w - 1)):
        kk = 0
        kkk = 0
        t = "0" * (w - 1 - len(bin(i)[2:])) + bin(i)[2:]
        if ("11" not in t):
            if (num <= w - 2):
                if (t[num] == "1"):
                    c += 1
                    kk = 1
            if (num - 1 >= 0):
                if (t[num - 1] == "1"):
                    b += 1
                    kkk = 1
            if (kk + kkk) == 0:
                a += 1
    return a, b, c


h, w, k = map(int, input().split())
k -= 1
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 j in range(w):
        a, b, c = calc(j)
        dp[i + 1][j] = ((dp[i][j] * a) + dp[i + 1][j]) % mod
        if j - 1 >= 0:
            dp[i + 1][j - 1] = ((dp[i][j] * b) + dp[i + 1][j - 1]) % mod
        if j + 1 < w:
            dp[i + 1][j + 1] = ((dp[i][j] * c) + dp[i + 1][j + 1]) % mod
print(dp[h][k])

Solution (Python):

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

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

lis = [0] * W

lis[0] += 1

for j in range(H):

    nlis = [0] * W

    for i in range(W):

        if i > 0:

            if i == 1:
                nlis[i-1] += lis[i] * amari[W-2]

            else:
                nlis[i-1] += lis[i] * amari[i-1] * amari[W-1-i]

        nlis[i] += lis[i] * amari[i] * amari[W-1-i]

        if i < W-1:

            if i == W-2:
                nlis[i+1] += lis[i] * amari[W-2]

            else:
                nlis[i+1] += lis[i] * amari[i] * amari[W-i-2]

    for i in range(W):

        lis[i] = nlis[i] % (10 ** 9+ 7)

print (lis[K-1] % (10**9 + 7))

Solution (Python):
h,w,K=map(int,input().split())
mod=10**9+7
dp=[[0]*(w+1) for _ in range(h+1)]
dp[0][0]=1
for i in range(h):
    for j in range(w):
        for k in range(2**(w-1)):
            ok=True
            for l in range(w-2):
                if (k>>l)&1 and (k>>(l+1))&1:
                    ok=False
            if ok:
                if j>=1 and (k>>(j-1))&1:
                    dp[i+1][j-1]+=dp[i][j]
                    dp[i+1][j-1]%=mod
                elif j<=w-2 and (k>>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):
H, W, K = map(int, input().split())

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

B = [format(i, 'b').zfill(W - 1) for i in range(2 ** (W - 1)) if '11' not in format(i, 'b')]

for h in range(H):
  for w in range(W):
    for b in B:
      if w > 0 and b[w - 1] == '1':
      	dp[h + 1][w - 1] += dp[h][w]
      elif w < W - 1 and b[w] == '1':
        dp[h + 1][w + 1] += dp[h][w]
      else:
        dp[h + 1][w] += dp[h][w]

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

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

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

B = [i for i in range(2 ** (W - 1)) if '11' not in format(i, 'b')]

for h in range(H):
  for w in range(W):
    for b in B:
      if w > 0 and (b >> (w - 1)) & 1:
      	dp[h + 1][w - 1] += dp[h][w]
      elif w < W - 1 and (b >> w) & 1:
        dp[h + 1][w + 1] += dp[h][w]
      else:
        dp[h + 1][w] += dp[h][w]

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

Solution (Python):
H, W, K = map(int, input().split())
mod = 10 ** 9 + 7
dp = [[0 for _ in range(W + 2)] for _ in range(H + 2)]
dp[0][1] = 1

fib = [0] * (W + 1)
fib[1] = 1
for i in range(2, W + 1):
    fib[i] = fib[i - 1] + fib[i - 2]

for i in range(1, H + 1):
    for j in range(1, W + 1):
        dp[i][j] = (dp[i - 1][j - 1] * fib[j - 1] * fib[W - j + 1] +
                    dp[i - 1][j] * fib[j] * fib[W - j + 1] +
                    dp[i - 1][j + 1] * fib[j] * fib[W - j]) % mod
print(dp[H][K])

Solution (Python):
h,w,k=map(int,input().split())
mod=10**9+7
dp=[[0]*w for _ in range(h)]
D=[[0]*w for _ in range(w)]
for i in range(2**(w-1)):
    s='0'+bin(i)[2:].rjust(w-1,'0')+'0'
    if '11' in s:continue
    for i in range(w-1):
        if s[i+1]=='1':
            D[i][i+1]+=1
            D[i+1][i]+=1
    for i in range(w):
        if s[i:i+2]=='00':
            D[i][i]+=1
dp[0]=D[0]
for i in range(1,h):
    for j in range(1,w):
        dp[i][j]+=dp[i-1][j-1]*D[j-1][j]
    for j in range(w-1):
        dp[i][j]+=dp[i-1][j+1]*D[j+1][j]
    for j in range(w):
        dp[i][j]+=dp[i-1][j]*D[j][j]
        dp[i][j]%=mod
print(dp[-1][k-1])

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

H, W, K = map(int, input().split())
if W == 1:
    print(1)
    exit()
dp = [[0 for x in range(W)] for h in range(H+1)]
dp[0][0] = 1


for h in range(H):
    X, Y, Z = 0, 0, 0

    
    for i in range(2 ** (W-1)):
        
        if bin(i).count('11') >= 1:
            continue
        perm = [k for k in range(W)]
        for j in range(W-1):
            if ((i >> j) & 1):
                perm[j], perm[j+1] = perm[j+1], perm[j]

        for j in range(W):
            dp[h+1][perm[j]] += dp[h][j]
            dp[h+1][perm[j]] %= MOD



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

Solution (Python):
h,w,k = (int(x) for x in input().split())
MOD = 1000000007

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


fib[1] = 1
dp[0][1] = 1

for i in range(2,w+1):
  fib[i] = fib[i-1] + fib[i-2]
  
for i in range(1, h+1):
  for j in range(1, w+1):
    dp[i][j] = (dp[i - 1][j - 1]*fib[j - 1]*fib[w - j + 1]+dp[i - 1][j]*fib[j]*fib[w - j + 1]+dp[i - 1][j + 1]*fib[j]*fib[w - j])%MOD
                                                                                                                          
print(dp[h][k])

Solution (Python):

import sys, math, fractions, itertools

MOD = 1000000007  

def solve(h: int, w: int, k: int):
    wc = [1] * 9

    for i in range(2, 9):
        wc[i] = wc[i-1] + wc[i-2]

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

    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  
    W = int(next(tokens))  
    K = int(next(tokens))  
    solve(H, W, K)

if __name__ == '__main__':
    main()

Solution (Python):
H,W,K = map(int,input().split())
move= [0]*(W-1)
count = 0
MOD = 10**9+7

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

for i in range(2**(W-1),2**W):
    b = bin(i)[3:]
    flag = True
    for j in range(W-2):
        if b[j] == '1' and b[j+1] == '1':
            flag = False
    if flag :
        count += 1
        for j in range(W-1):
            move[j] += int(b[j])

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]*(count - move[0]) + DP[i][j+1]*move[0])%MOD
        elif j == W-1:
            DP[i+1][j] = (DP[i][j-1] * move[j-1] + DP[i][j]*(count - move[j-1])) % MOD
        else:
            DP[i+1][j] = (DP[i][j-1] * move[j-1] + DP[i][j]*(count - move[j] - move[j-1]) + DP[i][j+1]*move[j]) % MOD
print(DP[-1][K-1])

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

for i in range(2, 9):
    wc[i] = wc[i-1] + wc[i-2]

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

Solution (Python):

import sys
import math
from collections import defaultdict


sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]


mod = 10**9 + 7


def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))



H,W,K = II()
from itertools import product

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


dp = [[0]*W for _ in range(H+1)]
dp[0][0] = 1
for i in range(1,H+1):
  for j in range(W):
    if 0<=j-1:
      a = list(product(['+','-'],repeat=W-1))
      counter = 0
      for a1 in a:
        if a1[j-1]!= '+':
          continue
        else:
          for k in range(1,W-1):
            if a1[k] == '+' and a1[k-1] == '+':
              break
            else:
              if k == W-2:
                counter += 1
      dp[i][j] += dp[i-1][j-1]*counter
      dp[i][j] %= mod
      
    if W-1>=j+1:
      a = list(product(['+','-'],repeat=W-1))
      counter = 0
      for a1 in a:
        if a1[j]!= '+':
          continue
        else:
          for k in range(1,W-1):
            if a1[k] == '+' and a1[k-1] == '+':
              break
            else:
              if k == W-2:
                counter += 1
      dp[i][j] += dp[i-1][j+1]*counter
      dp[i][j] %= mod

    a = list(product(['+','-'],repeat=W-1))
    counter = 0
    for a1 in a:
      if j <= W-2:
        if a1[j] == '+':
          continue
      if j-1>=0:
        if a1[j-1] == '+':
          continue
      for k in range(1,W-1):
        if a1[k] == '+' and a1[k-1] == '+':
          break
        else:
          if k==W-2:
            counter += 1
    dp[i][j] += dp[i-1][j]*counter
    dp[i][j] %= mod

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

Solution (Python):
H, W, K = map(int, input().split())
mod = int(1E9+7)

if W == 1:
    print(1)
else:
    dp = [[0 for _ in range(W)] for _ in range(H+1)]

    P = [1, 1, 2, 3, 5, 8, 13, 21]
    dp[0][0] = 1

    for h in range(1, H+1):
        for k in range(W):
            if k == 0:
                dp[h][k] = (P[k]*P[W-k-1]*dp[h-1][k] + P[k]*P[W-k-2]*dp[h-1][k+1]) % mod
            elif k == W-1:
                dp[h][k] = (P[k-1]*P[W-k-1]*dp[h-1][k-1] + P[k]*P[W-k-1]*dp[h-1][k]) % mod
            else:
                dp[h][k] = (P[k-1]*P[W-k-1]*dp[h-1][k-1] + P[k]*P[W-k-1]*dp[h-1][k] + P[k]*P[W-k-2]*dp[h-1][k+1]) % mod
    print(dp[H][K-1])

Solution (Python):
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque

from itertools import product

from itertools import permutations

from itertools import combinations

from itertools import accumulate
from bisect import bisect_left, bisect_right

import re







def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e50)
MOD = int(1e9)+7 


def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]



def main():
    H, W, K = l_inpl()
    dp = create_grid(H+1, W)
    for i in range(W):
        dp[0][i] = 0
    dp[0][0] = 1

    for i in range(H):
        for j in range(W):
            for k in range(0, 2**(W-1)): 
                ok = True
                for l in range(W-2):
                    if (k >> l) & 1 and (k >> (l+1)) & 1:
                        
                        ok = False
                if not ok:
                    continue
                if j > 0 and (k >> (j-1)) & 1:
                    
                    dp[i+1][j-1] += dp[i][j]
                    dp[i+1][j-1] %= MOD
                elif j < W-1 and (k >> 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])

if __name__ == "__main__":
    main()

Solution (Python):
from functools import lru_cache

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

MOD = 10**9 + 7


class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

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

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

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

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

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

    def __radd__(self, other):
        return ModInt(other + self.x)

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

    def __rmul__(self, other):
        return ModInt(other * self.x)

    def __rtruediv__(self, other):
        return ModInt(other * pow(self.x, MOD - 2, MOD))

    def __rpow__(self, other):
        return ModInt(pow(other, self.x, MOD))



@lru_cache(maxsize=None)
def f(i):
    return (
        ModInt(1) if i <= 0 else
        ModInt(2) if i == 1 else
        f(i - 1) + f(i - 2)
    )



@lru_cache(maxsize=None)
def g(i, j):
    return (
        ModInt(0) if i == 0 and j >= 2 or j == 0 or j == W + 1 else
        ModInt(1) if i == 0 and j == 1 else
        (
            g(i - 1, j - 1) * f(j - 3) * f(W - j - 1) +
            g(i - 1, j) * f(j - 2) * f(W - j - 1) +
            g(i - 1, j + 1) * f(j - 2) * f(W - j - 2)
        )
    )


ans = g(H, K)

print(ans)

Solution (Python):
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(1,h+1):
  for j in range(2**(w-1)):
    tmp=format(j,'b')
    if len(tmp)!=w-1:
      tmp=(w-1-len(tmp))*'0'+tmp
    flag=True
    for l in range(1,w-1):
      if tmp[l]=='1' and tmp[l-1]=='1':
        flag=False
        break
    if flag==False:
      continue
    else:
      arr=[i for i in range(1,w+1)]
      for m in range(w-1):
        if tmp[m]=='1':
          arr[m],arr[m+1]=arr[m+1],arr[m]
      for m in range(w):
        dp[i][m]+=dp[i-1][arr[m]-1]%mod
print(dp[h][k-1]%mod)

Solution (Python):



import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7

h,w,K = map(int,input().split())
if w == 1:
    print(1)
    quit()
dp = [[0]*(w) for _ in range(h+1)]
dp[0][0] = 1
for i in range(h):
    for j in range(w):
        x,y,z = 0,0,0
        for k in range(2**(w-1)):
            b = [0]*(w-1)
            for l in range(w-1):
                if (k>>l) & 1:
                    if b[l-1] == 1:
                        break
                    b[l] = 1
            else:
                if j > 0 and j < w-1:
                    if b[j-1] == 1 and b[j] == 0:
                        x += 1
                    elif b[j-1] == 0 and b[j] == 0:
                        y += 1
                    elif b[j-1] == 0 and b[j] == 1:
                        z += 1
                elif j == 0:
                    if b[j] == 0:
                        y += 1
                    elif b[j] == 1:
                        z += 1
                elif j == w-1:
                    if b[j-1] == 0:
                        y += 1
                    elif b[j-1] == 1:
                        x += 1
        if j > 0:
            dp[i+1][j-1] += x*dp[i][j]
            dp[i+1][j-1] %= mod
        if j + 1 < w:
            dp[i+1][j+1] += z*dp[i][j]
            dp[i+1][j+1] %= mod
        dp[i+1][j] += y*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]*w for i in range(h+1)]
dp[0][0] = 1


for i in range(1, h+1):
    if w == 1:
        dp[i][0] = dp[i-1][0]
        continue

    for bits in range(1<<(w-1)):
        if bits & (bits>>1) != 0:
            continue
        

        for j in range(w-1):
            if (bits>>j) & 1 == 1:
                dp[i][j+1] += dp[i-1][j]
                dp[i][j+1] %= MOD
                dp[i][j] += dp[i-1][j+1]
                dp[i][j] %= MOD
            else:
                if j == 0 or (bits>>(j-1)) & 1 == 0:
                    dp[i][j] += dp[i-1][j]
                    dp[i][j] %= MOD

                if j == w-2:
                    dp[i][w-1] += dp[i-1][w-1]
                    dp[i][w-1] %= MOD
    

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

Solution (Python):
from collections import defaultdict
MOD = 10 ** 9 + 7

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

fib = {-2: 0, -1: 1, 0: 1}
for i in range(1, W):
    fib[i] = fib[i - 1] + fib[i - 2]

dp = defaultdict(int)

dp[(0, 1)] = 1
for i in range(1, H + 1):
    for j in range(1, W + 1):
        dp[(i, j)] \
            = fib[j - 3] * fib[W - j - 1] * dp[(i - 1, j - 1)] \
            + fib[j - 2] * fib[W - j - 1] * dp[(i - 1, j)] \
            + fib[j - 2] * fib[W - j - 2] * dp[(i - 1, j + 1)]
        dp[(i, j)] %= MOD

print(dp[(H, K)])

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

S=[1, 1]
for i in range(W-1):
    S.append(S[-1]+S[-2])

dp = [0]*W
dp[0] = 1
for h in range(H):
    dp_new=[0]*W
    for w in range(W):
        dp_new[w] = S[w]*S[W-1-w]*dp[w]
	
    for w in range(W-1):
        dp_new[w  ] += S[w]*S[W-2-w]*dp[w+1]
        dp_new[w+1] += S[w]*S[W-2-w]*dp[w  ]

    dp = [d%1000000007 for d in dp_new]

print(dp[K-1])

Solution (Python):
import numpy as np


h,w,k = map(int,input().split())
connect = [[0 for i in range(w)] for j in range(w)]

if w == 1:
    print(1)
else:
    allstate = [""]
    befstate = [""]
    for i in range(w-1):
        for s in befstate:
            if s == "":
                allstate.append(s+str(i))
            else:
                last = int(s[-1])
                if (i-last)!=1:
                    allstate.append(s+str(i))
        befstate = allstate.copy()
        
    
    tot = len(allstate)
    for s in allstate:
        for c in s:
            temp = int(c)
            connect[temp][temp+1] += 1
            connect[temp+1][temp] += 1
    for i in range(w):
        temp = sum(connect[i])
        connect[i][i] = tot-temp
    buf = [0 for i in range(w)]
    buf[0] = 1
    for i in range(h):
        nbuf = [0 for i in range(w)]
        for j in range(w):
            for l in range(w):
                nbuf[l] += buf[j]*connect[j][l]
                nbuf[l]%=10**9+7
        buf = nbuf.copy()
    
    print(buf[k-1])

Solution (Python):


import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 

h,w,k = [int(i) for i in readline().split()]
MOD = 10**9+7

num =[0]*(w-1)
total = 0
for i in range(1<<(w-1)):
    for j in range(w-2):
        if ((i>>j)&1) & ((i>>(j+1))&1): break
    else:
        total += 1
        for j in range(w-1):
            if ((i>>j)&1): num[j] += 1




dp = [[0]*(w) for i in range(h+1)]
dp[0][0] = 1
for i in range(h):
    for j in range(w):
        r=l=0
        if j < w-1: r = num[j]
        if j: l = num[j-1]

        if r:
            dp[i+1][j+1] += r*dp[i][j]
            dp[i+1][j+1] %= MOD
        dp[i+1][j  ] += (total-r-l)*dp[i][j]
        dp[i+1][j  ] %= MOD
        if l:
            dp[i+1][j-1] += l*dp[i][j]
            dp[i+1][j-1] %= MOD



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

Solution (Python):
import itertools

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

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

bits = []
for r in range(w + 1):
    for bit in itertools.combinations(range(w - 1), r):
        if all(y - x > 1 for x, y in zip(bit, bit[1:])):
            bits.append(bit)

mod = 10 ** 9 + 7

for i in range(h):
    for j in range(w):
        for bit in bits:
            if j in bit:
                dp[i + 1][j + 1] += dp[i][j]
                dp[i + 1][j + 1] %= mod
            elif (j - 1) in bit:
                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):
h, w, K = map(int, raw_input().split())
dp = [[0]*w for i in range(h+1)]
dp[0][0] = 1
MOD = 10**9+7
def valid_mask():
    res = []
    for mask in range(1 << (w-1)):
        invalid = False
        for k in range(w-2):
            if (mask & 1 << k) > 0 and (mask & 1 << (k+1)) > 0:
                invalid = True
                break
        if not invalid:
            res.append(mask)
    return res

masks = valid_mask()

for i in range(h):
    for j in range(w):
        for mask in masks:
            if j < w-1 and (mask & 1 << j) > 0:
                dp[i+1][j+1] = (dp[i][j] + dp[i+1][j+1]) % MOD
            elif j - 1 >= 0 and (mask & (1 << (j-1))) > 0:
                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] % MOD