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):
def main():
    h, w, k = map(int, input().split())
    MOD = 10 ** 9 + 7

    patterns = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
    x = [0] * (w - 1)
    for i in range(w-1):
        x[i] = patterns[i] * patterns[max(0, w-i-2)]

    y = [0] * w
    for i in range(w):
        y[i] = patterns[i] * patterns[max(0, w-i-1)]

    dp = [[0] * w for _ in range(h+1)]
    dp[0][0] = 1
    for j in range(h):
        for i in range(w):
            d = dp[j][i] * y[i]
            if i - 1 >= 0:
                d += dp[j][i-1] * x[i-1]
            if i + 1 < w:
                d += dp[j][i+1] * x[i]
            dp[j+1][i] = d % MOD
    print(dp[h][k-1])


main()

Solution (Python):
H, W, K = map(int, input().split())
dp = [[]]
for i in range(0, W):
	dp[0].append(0)
dp[0][0] = 1
for i in range(0, H):
	next = []
	for j in range(0, W):
		next.append(0)
	for j in range(0, 2**(W-1)):
		lst = []
		m = j
		for k in range(0, W-1):
			lst.append(m%2)
			m //= 2
		flag = True
		for k in range(0, W-2):
			if lst[k] == 1 and lst[k+1] == 1:
				flag = False
				break
		if flag:
			notswapped = []
			for k in range(0, W):
				notswapped.append(True)
			for k in range(0, W-1):
				if lst[k] == 1:
					next[k+1] += dp[-1][k]
					next[k] += dp[-1][k+1]
					notswapped[k] = False
					notswapped[k+1] = False
			for k in range(0, W):
				if notswapped[k]:
					next[k] += dp[-1][k]
	dp.append(next)
print(dp[H][K-1]%(10**9+7))

Solution (Python):



def ri():
    return int(input())

def rl():
    return list(input().split())

def rli():
    return list(map(int, input().split()))

p = [1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
def count(n):
    if n <= 0:
        return 1
    return p[n]

MOD = 1000000007

def main():
    H, W, K = rli()
    dp = [[0 for _ in range(W+2)] for _ in range(H+1)]
    dp[0][1] = 1
    for h in range(0, H):
        for w in range(1, W+1):
            dp[h+1][w] = dp[h][w-1]*count(w-3)*count(W-w-1)
            dp[h+1][w] += dp[h][w]*count(w-2)*count(W-w-1)
            dp[h+1][w] += dp[h][w+1]*count(w-2)*count(W-w-2)
            dp[h+1][w] %= MOD
    print(dp[H][K])


if __name__ == '__main__':
    main()

Solution (Python):
mod = 10**9+7
h, w, k = [ int(v) for v in input().split() ]

non_contiuous_list = [1,2]

end_0, end_1 = 1, 1
for i in range(8):
    end_1_new = end_0
    end_0_new = end_0 + end_1
    end_0, end_1 = end_0_new, end_1_new
    non_contiuous_list.append(end_0 + end_1)


def non_contiuous(x):
    global non_contiuous_list
    if x >= 0:
        return non_contiuous_list[x]
    else:
        return 1

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

for i in range(1,h+1):
    if w > 1:
        for j in range(w):
            a = max(0,w-2)
            b = max(0,w-3)
            if j == 0:
                reach[i][j] = reach[i-1][j] * non_contiuous(a) + reach[i-1][j+1] * non_contiuous(b)
            elif j == w - 1:
                reach[i][j] = reach[i-1][j] * non_contiuous(a) + reach[i-1][j-1] * non_contiuous(b)
            else:
                reach[i][j] = reach[i-1][j-1] * non_contiuous(j-2) * non_contiuous(w-j-2) + reach[i-1][j] * non_contiuous(j-1) * non_contiuous(w-j-2) + reach[i-1][j+1] * non_contiuous(j-1) * non_contiuous(w-j-3) 
    else:
        reach[i][0] = 1

    reach[i] = [ j % mod for j in reach[i] ] 

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

Solution (Python):
import sys

mod=10**9+7
fib=[1]*10
for i in range(2,10):
  fib[i]=fib[i-1]+fib[i-2]


H,W,K=map(int,input().split())
if W==1:
  print(1)
  sys.exit()

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

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

print(dp[H][K])

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


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


dp_H1[0][0] = 1
dp_H1[1][0] = 1

for i in range(2, W + 1):
	dp_H1[i][0] = dp_H1[i - 1][0] + dp_H1[i - 1][1]
	dp_H1[i][0] %= mod
	dp_H1[i][1] = dp_H1[i - 1][0]
	dp_H1[i][1] %= mod

dp_row_where[0][1] = 1

for i in range(1, H + 1):
	for j in range(1, W + 1):
		
		dp_row_where[i][j] += dp_row_where[i - 1][j] * sum(dp_H1[j - 1]) * sum(dp_H1[W - j])
		
		
		dp_row_where[i][j] += dp_row_where[i - 1][j - 1] * sum(dp_H1[j - 2]) * sum(dp_H1[W - j])
		
		
		dp_row_where[i][j] += dp_row_where[i - 1][j + 1] * sum(dp_H1[j - 1]) * sum(dp_H1[W - j - 1])
		
		dp_row_where[i][j] %= mod
		
print(dp_row_where[H][K])

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
fib = [1] * (W + 2)
for i in range(2,W+2) :
    fib[i] = fib[i - 1] + fib[i - 2]

def pat(w) :
    if w < 1 :
        return 1
    else :
        return fib[w + 1]

for i in range(H) :
    for j in range(W) :
        dp[i+1][j] = (dp[i+1][j] + dp[i][j] * pat(j - 1) * pat(W - j - 2)) % MOD
        if j > 0 :
            dp[i+1][j-1] = (dp[i+1][j-1] + dp[i][j] * pat(j - 2) * pat(W - j - 2)) % MOD
        if j <= W - 2 :
            dp[i+1][j+1] = (dp[i+1][j+1] + dp[i][j] * pat(j - 1) * pat(W - j - 3)) % MOD

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

Solution (Python):
fib = [None] * 11
fib[0], fib[1] = 1, 2
for i in range(2, 11):
    fib[i] = fib[i-1] + fib[i-2]
mod = 1000000007
H, W, K = map(int, input().split())
if W == 1:
    print(1)
    quit()
dp = [[0] * W for i in range(H+1)]
dp[0][0] = 1
for i in range(H):
    for j in range(W):
        if 1 < j < W-2:
            dp[i+1][j] += dp[i][j] * fib[j-1] * fib[W-j-2] % mod
            dp[i+1][j] += dp[i][j-1] * fib[j-2] * fib[W-j-2] % mod
            dp[i+1][j] += dp[i][j+1] * fib[j-1] * fib[W-j-3] % mod
        elif j == 1:
            dp[i+1][j] += dp[i][j] * fib[j-1] * fib[W-j-2] % mod
            dp[i+1][j] += dp[i][j-1] * fib[W-j-2] % mod
            dp[i+1][j] += dp[i][j+1] * fib[j-1] * fib[W-j-3] % mod
        elif j == W-2:
            dp[i+1][j] += dp[i][j] * fib[j-1] * fib[W-j-2] % mod
            dp[i+1][j] += dp[i][j-1] * fib[j-2] * fib[W-j-2] % mod
            dp[i+1][j] += dp[i][j+1] * fib[j-1] % mod
        elif j == 0:
            dp[i+1][0] = dp[i][0] * fib[W-2] + dp[i][1] * fib[W-3]
        elif j == W-1:
            dp[i+1][W-1] = dp[i][W-1] * fib[W-2] + dp[i][W-2] * fib[W-3]
        dp[i+1][j] %= mod
print(dp[H][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
fib = [1, 2, 3, 5, 8, 13, 21, 34]


def calc(w):
    if w < 0:
        return 1
    return fib[w]


for h in range(H):
    for w in range(W):
        dp[h + 1][w] = (dp[h + 1][w] + dp[h][w] * calc(w - 1) * calc(W - w - 2)) % MOD
        if w + 1 < W:
            dp[h + 1][w + 1] = (dp[h + 1][w + 1] + dp[h][w] * calc(w - 1) * calc(W - w - 3) % MOD)
        if w - 1 >= 0:
            dp[h + 1][w - 1] = (dp[h + 1][w - 1] + dp[h][w] * calc(w - 2) * calc(W - w - 2) % MOD)

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

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

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


def calc(w):
    if w <= 0:
        return 1
    ret = 0
    for pattern in product([0, 1], repeat=w):
        pattern = ''.join(list(map(str, pattern)))
        if '11' not in pattern:
            ret += 1
    return ret


for h in range(H):
    for w in range(W):
        dp[h + 1][w] = (dp[h + 1][w] + dp[h][w] * calc(w - 1) * calc(W - w - 2)) % MOD
        if w + 1 < W:
            dp[h + 1][w + 1] = (dp[h + 1][w + 1] + dp[h][w] * calc(w - 1) * calc(W - w - 3) % MOD)
        if w - 1 >= 0:
            dp[h + 1][w - 1] = (dp[h + 1][w - 1] + dp[h][w] * calc(w - 2) * calc(W - w - 2) % MOD)

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

Solution (Python):
from functools import lru_cache

mod = 10 ** 9 + 7

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


@lru_cache(maxsize=w + 10)
def fib(n):
    if n <= 1:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)
    
    


dp = [0] * w
dp[0] = 1
ndp = [0] * w

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

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

dp = [0] * w
dp[0] = 1
ndp = [0] * w

for _ in range(h):
    for bits in range(1 << w - 1):
        if '11' in bin(bits): continue
        to = list(range(w))
        for i in range(w - 1):
            if (bits >> i) & 1:
                to[i], to[i + 1] = to[i + 1], to[i]
        for i in range(w):
            ndp[to[i]] += dp[i]
            ndp[to[i]] %= mod
    dp = ndp
    ndp = [0] * w
print(dp[k])

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


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

dp[0][0] = 1

for h in range(1,H+1):
    for w in range(0,W):
        a = 0
        b = 0
        c = 0
        
        Q = W-1
        for bit in range(1<<Q):
            invalid = False
            cur_seq = False
            for i in range(Q):
                on = (bit >> i) & 1
                if on & cur_seq:
                    invalid = True
                    break
                cur_seq = on

            
            if invalid:
                continue

            connected = False
            
            
            for i in range(Q):
                on = (bit >> i) & 1
                if on:
                    x = i
                    y = i+1
                    if x == w-1:
                        connected = True
                        a += 1
                    elif y == w+1:
                        connected = True
                        c += 1
            if not connected:
                b += 1

        cnt = 0
        if a > 0:
            cnt += a * dp[h-1][w-1]
        if b > 0:
            cnt += b * dp[h-1][w]
        if c > 0:
            cnt += c * dp[h-1][w+1]

        dp[h][w] = cnt

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

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


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

dp[0][0] = 1

for h in range(1,H+1):
    for w in range(0,W):
        a = 0
        b = 0
        c = 0
        
        Q = W-1
        for bit in range(1<<Q):
            invalid = False
            cur_seq = False
            for i in range(Q):
                on = (bit >> i) & 1
                if on & cur_seq:
                    invalid = True
                    break
                cur_seq = on

            
            if invalid:
                continue

            connected = False
            
            
            for i in range(Q):
                on = (bit >> i) & 1
                if on:
                    x = i
                    y = i+1
                    if x == w-1:
                        connected = True
                        a += 1
                    elif y == w+1:
                        connected = True
                        c += 1
            if not connected:
                b += 1

        cnt = 0
        if a > 0:
            cnt += a * dp[h-1][w-1]
        if b > 0:
            cnt += b * dp[h-1][w]
        if c > 0:
            cnt += c * dp[h-1][w+1]

        dp[h][w] = cnt

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

Solution (Python):
from collections import deque
from copy import deepcopy

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

mod = int(1e9+7)


perm_lst = []
def bfs():
    dq = deque() 
    dq.append(([],0))
    while dq:
        post, line = dq.popleft()
        if line < W: 
          post_tmp = deepcopy(post) 
          post_tmp.append((line,line))
          dq.append( (post_tmp,line+1) )
        if line < W-1: 
          post_tmp = deepcopy(post) 
          post_tmp.append((line,line+1))
          dq.append( (post_tmp,line+2) )
        if line == W:
          perm_lst.append(post)
bfs()



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 perm in perm_lst:
    for j in range(len(perm)):
      if perm[j][0] != perm[j][1]:
        dp[i][perm[j][0]] += dp[i-1][perm[j][1]]
        dp[i][perm[j][1]] += dp[i-1][perm[j][0]]
      else:
        dp[i][perm[j][0]] += dp[i-1][perm[j][0]]
      


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

Solution (Python):
import numpy as np
H, W, K = map(int, input().split())

if W == 1:
    print (1)
    exit()
MOD = 10 ** 9 + 7


lst = [[0] * (W) for i in range(H+2)]
dp = np.array(lst)
dp[0][0] = 1

def check(h): 
    count = 0
    for i in range(2**(W-1)):
        flag2 = True
        flag = False 
        for j in range(W-1):
            if flag2: 
                
                if (i >> j) & 1: 
                    if flag: 
                        count += 1
                        
                        flag = True
                        flag2 = False
                        break
                    else: 
                        dp[H+1][j] += dp[h-1][j+1]%MOD
                        dp[H+1][j+1] += dp[h-1][j]%MOD
                        flag = True
                else:
                    if j == W-2: 
                        dp[H+1][j+1] = dp[h-1][j+1]%MOD
                    if not flag: 
                        dp[H+1][j] = dp[h-1][j]%MOD
                    else:
                        pass
                    flag = False
        if flag2: 
            dp[h][:] += dp[H+1][:]%MOD
            dp[h][:] = dp[h][:]%MOD
            
        dp[H+1][:] = 0
        
    
    
    return 0;

for i in range(H):
    check(i+1)


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

Solution (Python):
MOD = 1000000007

pattern = [0] * 10
pattern[0] = 1
pattern[1] = 1
for i in range(2, 8 + 1):
    pattern[i] = pattern[i-1] + pattern[i-2]


def single_down(idx_from, idx_to, W):
    if idx_from == idx_to:
        return pattern[idx_from - 1] * pattern[W - idx_from]
    else:
        left = min(idx_from, idx_to) - 1
        right = W - max(idx_from, idx_to)
        return pattern[left] * pattern[right]


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

    ptn = [[0] * W]
    ptn[0][0] = 1
    for h in range(1, H + 1):
        ptn.append([])
        ptn[h] = [0] * W
        for w in range(0, W):
            ptn[h][w] = ptn[h-1][w] * single_down(w+1, w+1, W) % MOD
            if w > 0:
                ptn[h][w] += ptn[h-1][w-1] * single_down(w, w+1, W) % MOD
            if w < W-1:
                ptn[h][w] += ptn[h-1][w+1] * single_down(w+2, w+1, W) % MOD
            ptn[h][w] %= MOD

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


if __name__ == '__main__':
    main()

Solution (Python):
mod = 10**9+7
H,W,K = map(int,input().split())
a = [0]*20
a[0]=1
a[1]=1
for i in range(10):
    a[i+2]=a[i+1]+a[i]
dp = [[0]*(W+1) for _ in range(H+1)]
dp[0][0] = 1
for h in range(H):
    for k in range(W):
        dp[h+1][k] += a[k]*a[W-k-1]*dp[h][k]
        dp[h+1][k] += a[k-1]*a[W-k-1]*dp[h][k-1]
        dp[h+1][k] += a[k]*a[W-k-2]*dp[h][k+1]
        dp[h+1][k] %= mod
print(dp[H][K-1])

Solution (Python):
mod=1000000007
H,W,K=map(int,input().split())
dp=[[0]*W for i in range(1+H)]
dp[0][0]=1
C=[0]*(W+1)
C[0]=1
c=[[0,0] for i in range(1+W)]
c[0][0]=1
for i in range(1,1+W):
    c[i][0]=c[i-1][0]+c[i-1][1]
    c[i][1]=c[i-1][0]
for w in range(1,1+W):
    C[w]=c[w][0]
for i in range(H):
    for k in range(W):
        for l in range(k-1,k+2):
            if l<0 or l>=W:
                continue
            x=dp[i][k]*C[min(k,l)]*C[W-1-max(k,l)]%mod
            dp[i+1][l]=(dp[i+1][l]+x)%mod
print(dp[H][K-1])

Solution (Python):
import sys
MOD = 1000000007


def main():
    h, w, k = [int(x) for x in input().split()]
    fibonacci = [1, 2]
    for i in range(w - 2):
        fibonacci.append(fibonacci[i] + fibonacci[i + 1])
    pattern = [0 for _ in range(w)]
    pattern[0] = 1
    for _ in range(h):
        nextp = [0 for _ in range(w)]
        for i in range(w):
            nextp[i] = (pattern[i] * (fibonacci[max(0, i - 1)] * fibonacci[max(0, w - (i + 2))])) % MOD
            if i > 0:
                nextp[i] += (pattern[i - 1] * (fibonacci[max(0, i - 2)] * fibonacci[max(0, w - (i + 2))])) % MOD
            if i < w - 1:
                nextp[i] += (pattern[i + 1] * (fibonacci[max(0, i - 1)] * fibonacci[max(0, w - (i + 3))])) % MOD
            nextp[i] %= MOD
        pattern = nextp
    print(pattern[k-1])


main()

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

dpW=[[1,0]for i in range(9)]
for i in range(1,9):
    dpW[i][0]=dpW[i-1][0]+dpW[i-1][1]
    dpW[i][1]=dpW[i-1][0]


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

for i in range(1,H+1):
    for j in range(1,W+1):
        
        dpH[i][j]+=dpH[i-1][j]*dpW[W-j][0]*dpW[j-1][0]
        if W-j-1>=0:
            dpH[i][j]+=dpH[i-1][j+1]*dpW[W-j-1][0]*dpW[j-1][0]
        if j-2>=0:
            dpH[i][j]+=dpH[i-1][j-1]*dpW[W-j][0]*dpW[j-2][0]
        dpH[i][j]%=(10**9+7)
print(dpH[H][K])

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

Solution (Python):
H,W,K=map(int,input().split())
mod=10**9+7
fib=[1,1,2,3,5,8,13,21]
memo=[[None]*W for _ in range(H+1)]
def dfs(cur,now):
    if cur==H:
        if now==K:
            return 1
        else:
            return 0
    elif now==1:
        if W==1:
            if memo[cur+1][0]==None:
                memo[cur+1][0]=dfs(cur+1,1)%mod
            return memo[cur+1][0]
        else:
            if memo[cur+1][0]==None:
                memo[cur+1][0]=dfs(cur+1,1)%mod
            if memo[cur+1][1]==None:
                memo[cur+1][1]=dfs(cur+1,2)%mod
            return (fib[W-1]*memo[cur+1][0]+fib[W-2]*memo[cur+1][1])%mod
    elif now==W:
        if memo[cur+1][W-2]==None:
            memo[cur+1][W-2]=dfs(cur+1,W-1)%mod
        if memo[cur+1][W-1]==None:
            memo[cur+1][W-1]=dfs(cur+1,W)%mod            
        return (fib[W-2]*memo[cur+1][W-2]+fib[W-1]*memo[cur+1][W-1])%mod
    else:
        if memo[cur+1][now-2]==None:
            memo[cur+1][now-2]=dfs(cur+1,now-1)%mod
        if memo[cur+1][now-1]==None:
            memo[cur+1][now-1]=dfs(cur+1,now)%mod     
        if memo[cur+1][now]==None:
            memo[cur+1][now]=dfs(cur+1,now+1)%mod  
        return (fib[W-now]*fib[now-2]*memo[cur+1][now-2]+fib[W-now]*fib[now-1]*memo[cur+1][now-1]+fib[W-now-1]*fib[now-1]*memo[cur+1][now])%mod
    
print(dfs(0,1))

Solution (Python):
H, W, K = map(int, input().split())
mod = 10**9 + 7
draw_array = [1, 1, 2, 3, 5, 8, 13, 21, 34]

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

ans_array = [[0] * W for i in range(H)]

ans_array[0][0] = draw_array[W - 1]
ans_array[0][1] = draw_array[W - 2]

for i in range(1, H):
    for w in range(W):
        if w == 0:
            ans_array[i][w] = (ans_array[i - 1][w] * draw_array[W - 1]) + (
                ans_array[i - 1][w + 1] * draw_array[W - 2])
            ans_array[i][w] = ans_array[i][w] % mod
        elif w == W - 1:
            ans_array[i][w] = (ans_array[i - 1][w] * draw_array[W - 1]) + (
                ans_array[i - 1][w - 1] * draw_array[W - 2])
            ans_array[i][w] = ans_array[i][w] % mod
        else:
            from_left = ans_array[i - 1][w - 1] * (
                draw_array[w - 1] * draw_array[W - w - 1])
            from_left = from_left % mod
            from_center = ans_array[i - 1][w] * (
                draw_array[w] * draw_array[W - w - 1])
            from_center = from_center % mod
            from_right = ans_array[i - 1][w + 1] * (
                draw_array[w] * draw_array[W - w - 2])
            from_right = from_right % mod
            ans_array[i][w] = (from_left+from_center+from_right) % mod


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

Solution (Python):
H,W,K=map(int,input().split())
mod=10**9+7
fib=[1,1,2,3,5,8,13,21]

from functools import lru_cache

@lru_cache(maxsize=None)
def dfs(cur,now):
    if cur==H:
        if now==K:
            return 1
        else:
            return 0
    elif now==1:
        if W==1:
            return dfs(cur+1,1)%mod
        else:
            return (fib[W-1]*dfs(cur+1,1)+fib[W-2]*dfs(cur+1,2))%mod
    elif now==W:
        return (fib[W-2]*dfs(cur+1,W-1)+fib[W-1]*dfs(cur+1,W))%mod
    else:
        return (fib[W-now]*fib[now-2]*dfs(cur+1,now-1)+fib[W-now]*fib[now-1]*dfs(cur+1,now)+fib[W-now-1]*fib[now-1]*dfs(cur+1,now+1))%mod
    
print(dfs(0,1))

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

mod = 10 ** 9 + 7


def Fib(n):
    a, b = 0, 1
    if n == 1:
        return a
    elif n == 2:
        return b
    else:
        for i in range(n - 2):
            a, b = b, a + b
        return b


dp = [[0 for j in range(W + 5)] for i in range(H + 5)]  
dp[0][1] = 1
for i in range(1, H + 1):
    for j in range(1, W + 1):
        for t in [-1, 0, 1]:
            if 1 <= j + t <= W:
                used = [0 for _ in range(W + 1)]
                for y in [j, j - 1, j + t, j + t - 1]:
                    if y >= 0:
                        used[y] = 1
                l = -(used[0] == 0)
                for x in used:
                    if x == 0:
                        l += 1
                    else:
                        break
                r = -(used[W] == 0)
                for x in used[::-1]:
                    if x == 0:
                        r += 1
                    else:
                        break
                dp[i][j] += Fib(l + 3) * Fib(r + 3) * dp[i - 1][j + t]
                dp[i][j] %= mod
print(dp[H][K])

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

mod = 10 ** 9 + 7


def Fib(n):
    a, b = 0, 1
    if n == 1:
        return a
    elif n == 2:
        return b
    else:
        for i in range(n - 2):
            a, b = b, a + b
        return b


dp = [[0 for j in range(W + 5)] for i in range(H + 5)]  
dp[0][1] = 1
for i in range(1, H + 1):
    for j in range(1, W + 1):
        for t in [-1, 0, 1]:
            if 1 <= j + t <= W:
                used = [0 for _ in range(W + 1)]
                for y in [j, j - 1, j + t, j + t - 1]:
                    if y >= 0:
                        used[y] = 1
                l = -(used[0] == 0)
                for x in used:
                    if x == 0:
                        l += 1
                    else:
                        break
                r = -(used[W] == 0)
                for x in used[::-1]:
                    if x == 0:
                        r += 1
                    else:
                        break
                dp[i][j] += Fib(l + 3) * Fib(r + 3) * dp[i - 1][j + t]
                dp[i][j] %= mod
print(dp[H][K])

Solution (Python):
mod = 10 ** 9 + 7
H, W, K = map(int, input().split())
K -= 1
dp = [0] * W
dp[0] = 1
ndp = [0] * W
for r in range(H):
    for i in range(1 << (W - 1)):
        if '11' in bin(i): continue
        perm = [i for i 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):
            next_line = perm[j]
            ndp[next_line] += dp[j]
            ndp[next_line] %= mod
    dp = ndp.copy()
    ndp = [0] * W
print(dp[K])

Solution (Python):

import sys
def input(): return sys.stdin.readline().rstrip()
def mi(): return map(int, input().split())


import itertools
H, W, K = mi()


def howmany(fr, h, w):
  global W
  
  if w+fr==0 or w+fr==W+1: return 0
  
  ans = 0
  
  for status in itertools.product(('0','1'),repeat=W-1):
    
    status = ''.join(('0',''.join(status),'0')) 
    
    
    if '11' in status: continue
    elif fr==0:
      if status[w-1]=='1' or status[w]=='1': continue
    elif fr==1:
      if status[w]=='0': continue
    else: 
      if status[w-1]=='0': continue
    
    ans += 1
  return ans % 1000000007


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

for h in range(1, H+1):
  for w in range(1, W+1):
  
  
    
    
    
    DP[h][w] = ((DP[h-1][w-1] * howmany(-1, h, w))%1000000007 + (DP[h-1][w] * howmany(0, h, w))%1000000007 + (DP[h-1][w+1] * howmany(1, h, w))%1000000007)%1000000007

print(DP[H][K])

Solution (Python):
import sys

from collections import deque

from collections import defaultdict

import heapq

import bisect





s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def getBitsL(n, L):
    bits = [0] * L
    for i in range(L):
        bits[i] = (n & 1) == 1
        n >>= 1
    return bits

def main():
    H, W, K = i2nn()
    if W == 1:
        print(1)
        return
    
    P = [[0] * W for _ in range(W)]
    for i in range(int(2**(W-1))):
        bits = getBitsL(i, W-1)
        ng = False
        for j in range(1, len(bits)):
            if bits[j-1] and bits[j]:
                ng = True
                break
        if ng:
            continue
        for j in range(W):
            if j == 0:
                if bits[j]:
                    P[j][j+1] += 1
                else:
                    P[j][j] += 1
            elif j == W-1:
                if bits[j-1]:
                    P[j][j-1] += 1
                else:
                    P[j][j] += 1
            else:
                if bits[j]:
                    P[j][j+1] += 1
                elif bits[j-1]:
                    P[j][j-1] += 1
                else:
                    P[j][j] += 1

    
    
    A = [[0] * W for i in range(H+1)]
    A[0][0] = 1
    MOD = int(1e+9) + 7
    for h in range(H):
        for w1 in range(W):
            for w2 in range(W):
                A[h+1][w2] = (A[h+1][w2] + A[h][w1] * P[w1][w2]) % MOD
    print(A[H][K-1])
    
    
    

main()

Solution (Python):
import itertools

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

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

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

for i in range(1, h + 1):
    for kuji_list in itertools.product([0, 1], repeat = w - 1):
        for l in range(len(kuji_list)-1):
            if kuji_list[l] == 1 and kuji_list[l+1] == 1:
                break
        else:
            for j in range(w):

                if j == 0:
                    if kuji_list[j] == 1:
                        dp[i][j] += dp[i - 1][j + 1]
                    else:
                        dp[i][j] += dp[i - 1][j]

                elif j == w - 1:
                    if kuji_list[j-1] == 1:
                        dp[i][j] += dp[i - 1][j - 1]
                    else:
                        dp[i][j] += dp[i - 1][j]

                else:
                    if kuji_list[j-1] == 1:
                        dp[i][j] += dp[i - 1][j - 1]
                    elif  kuji_list[j] == 1:
                        dp[i][j] += dp[i - 1][j + 1]
                    else:
                        dp[i][j] += dp[i - 1][j]

                dp[i][j] %= (10 ** 9 + 7)

ans = dp[-1][k - 1] % (10 ** 9 + 7)
print(ans)

Solution (Python):

import sys
from math import *
from itertools import *
from collections import *
from functools import *
try:
    from math import gcd
except Exception:
    from fractions import gcd

MOD = 1000000007  

def solve(H: int, W: int, K: int):
    dp = [[0] * (W + 2) for _ in range(H+1)]
    dp[0][1] = 1

    for h in range(H):
        for i in range(0, (1 << W), 2):
            f = True
            c = [0] * (W + 2)
            for w in range(1, W + 1):
                if ((i >> (w-1)) & 0x03) == 3:
                    f = False
                    break
                if i & (1 << (w - 1)):
                    c[w-1] += dp[h][w]
                elif i & (1 << w):
                    c[w+1] += dp[h][w]
                else:
                    c[w] += dp[h][w]
            if f:
                for j, cc in enumerate(c):
                    dp[h+1][j] += cc

    return dp[-1][K] % MOD


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))  
    result = solve(H, W, K)
    print(result)

if __name__ == '__main__':
    main()