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 examA():
    X, Y = LI()
    ans = X + Y//2
    print(ans)
    return

def examB():
    N = I()
    T, A = LI()
    H = LI()
    cur = 10**9; ans = 0
    for i in range(N):
        now = abs(A - (T - H[i]*0.006))
        if cur>now:
            cur = now
            ans = i
    print(ans+1)
    return

def examC():
    N, M = LI()
    PY = [[]for _ in range(M)]
    d = defaultdict(int)
    ans = [[]for _ in range(M)]
    for i in range(M):
        PY[i] = LI()
        PY[i].append(i)
    PY.sort(key=lambda x:x[1])
    for p,y,s in PY:
        d[p] +=1
        cur = str(p).zfill(6) + str(d[p]).zfill(6)
        ans[s] = cur
    for v in ans:
        print(v)
    return

def examD():
    global mod
    H, W, K = LI()
    fibo = [1]*(W+1)
    for i in range(W-1):
        fibo[i+2] = fibo[i+1] + fibo[i]
    dp = [[0]*(W) for _ in range(H+1)]
    dp[0][0] = 1

    for i in range(H):
        for j in range(W):
            dp[i+1][j] += dp[i][j]*fibo[j]*fibo[W-j-1]%mod
            dp[i+1][j] %=mod
            if j-1>=0:
                dp[i+1][j-1] += dp[i][j]*fibo[j-1]*fibo[W-j-1]%mod
                dp[i+1][j-1] %=mod
            if j+1<W:
                dp[i+1][j+1] += dp[i][j]*fibo[j]*fibo[W-j-2]%mod
                dp[i+1][j+1] %=mod
    ans = dp[H][K-1]
    print(ans)

    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examD()

Solution (Python):
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
import itertools
A=list(itertools.product([1,0],repeat=W-1))

B=[]

for a in A:
    flg=True
    for i in range(len(a)-1):
        if a[i+1]==1 and a[i]==1:
            flg=False
    if flg:
        B.append(a)

for h in range(1,H+1):
    for b in B:
        for w in range(W):
            if w==0:
                dp[h][w]+=dp[h-1][w]*(1-b[w])+dp[h-1][w+1]*b[w]
            elif w==W-1:
                dp[h][w]+=dp[h-1][w]*(1-b[w-1])+dp[h-1][w-1]*b[w-1]
            else:
                dp[h][w]+=dp[h-1][w]*(1-b[w-1])*(1-b[w])+dp[h-1][w-1]*b[w-1]+dp[h-1][w+1]*b[w]


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

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007




h, w, k = LI()
fib_list = [1] * w
for i in range(2, w):
    fib_list[i] = fib_list[i - 1] + fib_list[i - 2]


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




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

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

H, W, K = MAP()


def check(S):
    for i in range(W-1):
        
        if S & 1<<i and S & 1<<(i+1):
            return False
    return True


dp = list3d(H+1, 1<<W, W+1, 0)
dp[0][0][1] = 1
for i in range(H):
    for S1 in range(1<<W):
        
        if S1 & 1:
            continue
        
        if not check(S1):
            continue
        for S2 in range(1<<W):
            if S2 & 1:
                continue
            if not check(S2):
                continue
            for j in range(1, W+1):
                
                if S2 & 1<<(j-1):
                    dp[i+1][S2][j-1] += dp[i][S1][j]
                    dp[i+1][S2][j-1] %= MOD
                
                elif S2 & 1<<j:
                    dp[i+1][S2][j+1] += dp[i][S1][j]
                    dp[i+1][S2][j+1] %= MOD
                
                else:
                    dp[i+1][S2][j] += dp[i][S1][j]
                    dp[i+1][S2][j] %= MOD
ans = 0
for S in range(1<<W):
    ans += dp[H][S][K]
    ans %= MOD
print(ans)

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

H, W, K = MAP()


def check(S):
    for i in range(W-1):
        
        if S & 1<<i and S & 1<<(i+1):
            return False
    return True


dp = list3d(H+1, 1<<W, W+1, 0)
dp[0][0][1] = 1
for i in range(H):
    for S1 in range(1<<W):
        
        if S1 & 1:
            continue
        
        if not check(S1):
            continue
        for S2 in range(1<<W):
            if S2 & 1:
                continue
            if not check(S2):
                continue
            for j in range(1, W+1):
                
                if S2 & 1<<(j-1):
                    dp[i+1][S2][j-1] += dp[i][S1][j]
                    dp[i+1][S2][j-1] %= MOD
                
                elif S2 & 1<<j:
                    dp[i+1][S2][j+1] += dp[i][S1][j]
                    dp[i+1][S2][j+1] %= MOD
                
                else:
                    dp[i+1][S2][j] += dp[i][S1][j]
                    dp[i+1][S2][j] %= MOD
ans = 0
for S in range(1<<W):
    ans += dp[H][S][K]
    ans %= MOD
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
L = [1, 2, 3, 5, 8, 13, 21]
for i in range(H):
    for j in range(W):
        if j > 0:
            dp[i+1][j] += dp[i][j-1]*L[max(0, j-2)]*L[max(0, W-2-j)]
        if j < W-1:
            dp[i+1][j] += dp[i][j+1]*L[max(0, j-1)]*L[max(0, W-3-j)]
        dp[i+1][j] += dp[i][j]*L[max(0, j-1)]*L[max(0, W-2-j)]
        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+2)
dp[1] = 1


ref = [1,2,3,5,8,13,21]
pat = lambda l,r:ref[max(l,0)] * ref[max(r,0)]

for i in range(h):
	_dp = [0]*(w + 2)
	for j in range(1,w+1):
		_dp[j] = dp[j-1]*pat(j-3,w-j-1) + dp[j]*pat(j-2,w-j-1) + dp[j+1]*pat(j-2,w-j-2)
		_dp[j] %= mod
	dp = _dp
print(dp[k])

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


ref = [1,2,3,5,8,13,21]
pat = lambda l,r:ref[max(l,0)]*ref[max(r,0)]

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

Solution (Python):
def main():
    H, W, K = map(int, input().split())
    dp = [[0] * W for _ in range(H + 5)]
    dp[0][0] = 1
    MOD = 10 ** 9 + 7
    for h 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 w in range(W):
                if w == 0:
                    if a[w] == '1':
                        dp[h+1][w+1] += dp[h][w]
                        dp[h+1][w+1] %= MOD
                    elif a[w] == '0':
                        dp[h+1][w] += dp[h][w]
                        dp[h+1][w] %= MOD
                elif w == W - 1:
                    if a[w-1] == '1':
                        dp[h+1][w-1] += dp[h][w]
                        dp[h+1][w-1] %= MOD
                    elif a[w-1] == '0':
                        dp[h+1][w] += dp[h][w]
                        dp[h+1][w] %= MOD
                else:
                    if a[w-1] == '1':
                        dp[h+1][w-1] += dp[h][w]
                        dp[h+1][w-1] %= MOD
                    elif a[w] == '1':
                        dp[h+1][w+1] += dp[h][w]
                        dp[h+1][w+1] %= MOD
                    else:
                        dp[h+1][w] += dp[h][w]
                        dp[h+1][w] %= MOD

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







if __name__ == "__main__":
    main()

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,W):
    dp[0][i] = 0

for h in range(H):
    for w in range(W):
        
        for j in range((1<<W-1)):
            ok = True
            for k in range(1,W-1):
                if (j>>k)%2 == 1 and (j>>k-1)%2 == 1:
                    ok = False 
                    break
            if ok :
                
                if w < W-1 and (j>>w)%2 == 1:
                    dp[h+1][w+1] += dp[h][w]
                    dp[h+1][w+1] = dp[h+1][w+1]%mod
                
                elif w > 0 and (j>>w-1)%2 == 1:
                    dp[h+1][w-1] += dp[h][w]
                    dp[h+1][w-1] = dp[h+1][w-1]%mod
                else:
                    dp[h+1][w] += dp[h][w]
                    dp[h+1][w] = dp[h+1][w]%mod

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

Solution (Python):



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

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


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

dp[0][0] = 1

MOD = 10**9+7
for i in range(H):
    
    
    for yoko in range(2**(W-1)):
        if "11" in bin(yoko):
            continue
        
        yoko = bin(yoko)[2:].zfill(W-1)

        for j in range(W):
            
            
            
            if j != 0 and  yoko[j-1] == "1":
                dp[i+1][j-1] += dp[i][j]
                dp[i+1][j-1] = dp[i+1][j-1] % MOD

            
            
            elif j != W-1 and yoko[j] == "1":
                dp[i+1][j+1] += dp[i][j]
                dp[i+1][j+1] = dp[i+1][j+1] % MOD

            
            else:
                dp[i+1][j] += dp[i][j]
                dp[i+1][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+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):
import sys
from math import factorial
MOD = 10**9+7
h, w, k = [int(i) for i in sys.stdin.readline().split()]

memo_ls2 = [[0 for x in range(2)] for y in range(8)]
memo_ls2[1][0] = 1
for i in range(2,8):
    memo_ls2[i][0] = memo_ls2[i-1][1] + memo_ls2[i-1][0]
    memo_ls2[i][1] = memo_ls2[i-1][0]
memo_ls = [sum(i) for i in memo_ls2]

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

Solution (Python):

import sys

MOD = 1000000007  


def solve(H: int, W: int, K: int):
    if W == 1:
        print(1)
        return 
    
    
    dp1 = [[0]*W for _ in range(W)]

    for i in range(2): 
        for j in range(W):
            
            
            tmp = [[-1]*2 for _ in range(W-1)]
            if i == 0 or j == W-1: 
                tmp[0][0] = 1
                if j == 0:
                    tmp[0][1] = 0
                else: 
                    if j != W-1: tmp[j][1] = 0
                    tmp[j-1][1] = 0
                    if tmp[0][1] != 0: tmp[0][1] = 1

                for k in range(0,W-2):
                    tmp[k+1][0] = tmp[k][0] + tmp[k][1] 
                    if tmp[k+1][1] == -1: 
                        tmp[k+1][1] = tmp[k][0] 
                
                dp1[j][j] = sum(tmp[-1])

            else: 
                if j == 0: 
                    tmp[0][1] = 1
                    tmp[0][0] = 0                    
                else:
                    tmp[j][0] = 0 
                    if j < W-2: tmp[j+1][1] = 0
                    tmp[j-1][1] = 0
                    if tmp[0][1] != 0:
                        tmp[0][1] = 1
                    tmp[0][0] = 1

                for k in range(0,W-2):
                    if tmp[k+1][0] == -1:
                        tmp[k+1][0] = tmp[k][0] + tmp[k][1] 
                    if tmp[k+1][1] == -1: 
                        tmp[k+1][1] = tmp[k][0] 
                dp1[j][j+1] = sum(tmp[-1])


    
    dp2 = [[0]*W for _ in range(H+1)]
    dp2[1] = dp1[0]
    for h in range(1,H):
        for k in range(W):
            if k >= 1 and k < W-1:
                dp2[h+1][k] = dp1[k-1][k]*dp2[h][k-1] + dp1[k][k]*dp2[h][k] + dp1[k][k+1]*dp2[h][k+1]
            elif k>=1:
                dp2[h+1][k] = dp1[k-1][k]*dp2[h][k-1] + dp1[k][k]*dp2[h][k]
            elif k <W-1:
                dp2[h+1][k] = dp1[k][k]*dp2[h][k] + dp1[k][k+1]*dp2[h][k+1]


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

    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 = [int(str) for str in input().strip().split()]

MOD = 1000000007

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

for h in range(H):
    for w in range(W):
        for bit in range(2 ** (W - 1)):
            if bit & (bit << 1):
                continue

            
            if w > 0 and bit & (1 << (w - 1)):
                dp[h + 1][w - 1] += dp[h][w]
                dp[h + 1][w - 1] %= MOD
            
            elif w < W - 1 and bit & (1 << w):
                dp[h + 1][w + 1] += dp[h][w]
                dp[h + 1][w + 1] %= MOD

            else:
                dp[h + 1][w] += dp[h][w]
                dp[h + 1][w] %= MOD

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

Solution (Python):
import itertools


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

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

mod = 10**9 + 7
path = [[i, i+1] for i in range(w-1)]
DP = [[0]*(h+1) for _ in range(w)]
DP[0][0] = 1

for height in range(h):
    for pos in range(w):
        down_unable = {pos}
        left_unable = {pos-1, pos}
        right_unable = {pos, pos+1}

        down_count = 1
        left_count = 1
        right_count = 1
        for pick in range(1, 1 + w//2):
            all_pattern = list(itertools.combinations(path, pick))

            for pattern in all_pattern:
                check = set()
                possible = True
                for a, b in pattern:
                    if check & {a, b}:
                        possible = False
                        break
                    check |= {a, b}
                if not possible:
                    continue
                if not check & down_unable:
                    down_count += 1
                if not check & left_unable:
                    left_count += 1
                if not check & right_unable:
                    right_count += 1

        if pos == 0:
            DP[pos][height+1] += DP[pos][height] * down_count % mod
            DP[pos+1][height+1] += DP[pos][height] * right_count % mod

        elif pos == w-1:
            DP[pos][height+1] += DP[pos][height] * down_count % mod
            DP[pos-1][height+1] += DP[pos][height] * left_count % mod
        else:
            DP[pos][height+1] += DP[pos][height] * down_count % mod
            DP[pos+1][height+1] += DP[pos][height] * right_count % mod
            DP[pos-1][height+1] += DP[pos][height] * left_count % mod

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

Solution (Python):
import itertools


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

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

mod = 10**9 + 7
path = [[i, i+1] for i in range(w-1)]
DP = [[0]*(h+1) for _ in range(w)]
DP[0][0] = 1

for height in range(h):
    for pos in range(w):
        down_unable = {pos}
        left_unable = {pos-1, pos}
        right_unable = {pos, pos+1}

        down_count = 1
        left_count = 1
        right_count = 1
        for pick in range(1, 1 + w//2):
            all_pattern = list(itertools.combinations(path, pick))

            for pattern in all_pattern:
                check = set()
                possible = True
                for a, b in pattern:
                    if check & {a, b}:
                        possible = False
                        break
                    check |= {a, b}
                if not possible:
                    continue
                if not check & down_unable:
                    down_count += 1
                if not check & left_unable:
                    left_count += 1
                if not check & right_unable:
                    right_count += 1

        if pos == 0:
            DP[pos][height+1] += DP[pos][height] * down_count % mod
            DP[pos+1][height+1] += DP[pos][height] * right_count % mod

        elif pos == w-1:
            DP[pos][height+1] += DP[pos][height] * down_count % mod
            DP[pos-1][height+1] += DP[pos][height] * left_count % mod
        else:
            DP[pos][height+1] += DP[pos][height] * down_count % mod
            DP[pos+1][height+1] += DP[pos][height] * right_count % mod
            DP[pos-1][height+1] += DP[pos][height] * left_count % mod

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

Solution (Python):
import sys
import itertools


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    h, w, K = list(map(int, readline().split()))
    if w == 1:
        print(1)
    else:
        pt = [[0] * w for _ in range(w)]
        pf = [0] * w
        for it in itertools.product([True, False], repeat=w-1):
            b = True
            for i in range(1, len(it)):
                if it[i] and it[i-1]:
                    b = False
                    break
            if b:
                for i in range(len(it)):
                    if it[i]:
                        pt[i][i+1] += 1
                        pt[i+1][i] += 1
                    else:
                        if i == 0:
                            pf[i] += 1
                        elif i == w - 2:
                            pf[i+1] += 1
                for i in range(1, w - 1):
                    if not it[i-1] and not it[i]:
                        pf[i] += 1
        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 range(w):
                    if j != k:
                        dp[i][j] += dp[i-1][k] * pt[j][k]
                    else:
                        dp[i][j] += dp[i-1][k] * pf[j]
                    dp[i][j] %= mod
        print(dp[-1][K-1])


if __name__ == '__main__':
    solve()

Solution (Python):
def main():
    h,w,k=map(int,input().split())
    mod = 10**9+7
    b = [1,1,2,3,5,8,13,21,34]
    dp=[[0 for _ in range(w)]for j in range(h+1)]
    dp[0][0] = 1
    if w == 1:
        return 1

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

print(main())

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
ls = []
for h in range(2**(W-1)):
  log = ''
  flag = True
  for x in range(W-1):
    if h%2==1 and flag:
      log += '1'
      flag = False
    else:
      log += '0'
      flag = True
    h >>= 1
  ls += [log]
if W==1:
  ls = ['0']
ls = set(ls)
for i in range(H):
  for j in range(W):

    for log in ls:
      if j==0:
        if log[j]=='1':
          dp[i+1][j+1] += dp[i][j]%MOD
        else:
          dp[i+1][j] += dp[i][j]%MOD
      elif j==W-1:
        if log[j-1]=='1':
          dp[i+1][j-1] += dp[i][j]%MOD
        else:
          dp[i+1][j] += dp[i][j]%MOD
      else:
        if log[j-1]=='1':
          dp[i+1][j-1] += dp[i][j]%MOD
        elif log[j]=='1':
          dp[i+1][j+1] += dp[i][j]%MOD
        else:
          dp[i+1][j] += dp[i][j]%MOD
print(dp[-1][K-1]%MOD)

Solution (Python):

from collections import defaultdict
import copy


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

INF = 10 ** 9 + 7


def main():
	H, W, K = getlist()
	A = [0] * W
	A[0] = 1
	if W == 1:
		print(1)
	else:		
		for i in range(H):
			B = [0] * W
			for j in range(1 << (W - 1)):
				output = [0] * (W - 1)
				for k in range(W - 1):
					if ((j >> k) & 1) == 1:
						output[k] = 1
				judge = "Yes"
				for k in range(W - 2):
					if output[k] == 1 and output[k + 1] == 1:
						judge = "No"
				if judge == "Yes":
					if output[0] == 1:
						B[0] += A[1]
					else:
						B[0] += A[0]
					for k in range(1, W - 1):
						if output[k - 1] == 1:
							B[k] += A[k - 1]
						elif output[k] == 1:
							B[k] += A[k + 1]
						else:
							B[k] += A[k]
					if output[W - 2] == 1:
						B[W - 1] += A[W - 2]
					else:
						B[W - 1] += A[W - 1]

			for i in range(W):
				B[i] %= INF
			A = copy.deepcopy(B)
		print(A[K - 1] % INF)
	
if __name__ == '__main__':
	main()

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

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

preCnt = [0] * (W + 1)  
for w in range(1, W + 1):
    cnt = 0
    for bit in range(1 << w):
        if bin(bit).count('11') == 0:
            cnt += 1
    preCnt[w] = cnt

def left(w):
    ret = 1
    ret *= preCnt[w - 3] if w - 3 > 0 else 1
    ret *= preCnt[W - w - 1] if W - w - 1 > 0 else 1
    return ret % MOD

def right(w):
    ret = 1
    ret *= preCnt[w - 2] if w - 2 > 0 else 1
    ret *= preCnt[W - w - 2] if W - w - 2 > 0 else 1
    return ret % MOD

def mid(w):
    ret = 1
    ret *= preCnt[w - 2] if w - 2 > 0 else 1
    ret *= preCnt[W - w - 1] if W - w - 1 > 0 else 1
    return ret % MOD

for h in range(1, H + 1):
    for w in range(1, W + 1):
        dp[h][w] += dp[h - 1][w - 1] * left(w)
        dp[h][w] += dp[h - 1][w] * mid(w)
        dp[h][w] += dp[h - 1][w + 1] * right(w)
        dp[h][w] %= MOD

print(dp[H][K])

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

D = [[0]*W for _ in range(W)]
for S in range(1<<W-1):
    if S & S<<1 != 0:
        continue
    
    S <<= 1
    for i in range(W):
        if S>>i&1:
            D[i][i-1] += 1
        elif S>>i+1&1:
            D[i][i+1] += 1
        else:
            D[i][i] += 1
    
    

E = [[0]*W for _ in range(W)]
for i in range(W):
    E[i][i] = 1

for i in range(H):
    A = [[0]*W for _ in range(W)]
    for x in range(W):
        for y in range(W):
            A[x][y] = sum(E[x][z] * D[z][y] % mod for z in range(W)) % mod
    E = A

print(A[0][K-1])

Solution (Python):
"""
21:12:30
"""
mod = 10**9 + 7
H, W, K = map(int, input().split())

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

if W == 1:
    print(1)
    exit()
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] * bs[W-1-(j+1)] + dp[i][j+1] * bs[W-1-(j+2)]        
        
        elif j == W-1:
            dp[i+1][j] = dp[i][j-1] * bs[j-2] + dp[i][j] * bs[j-1]   
        
        else:
            dp[i+1][j] = dp[i][j-1]*bs[max(0,j-2)]*bs[W-1-(j+1)] + dp[i][j]*bs[j-1]*bs[W-1-(j+1)] + dp[i][j+1]*bs[j-1]*bs[max(0,W-1-(j+2))]
        
        dp[i+1][j] %= mod
print(dp[H][K-1])

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



bits = []
for i in range(2**(w-1)):
    bit = [0] * (w-1)
    for j in range(w-1):
        if ((i >> j) & 1):
            bit[j] = 1
    for j in range(w-2):
        if bit[j] == 1 and bit[j+1] == 1:
            break
    else:
        bits.append(bit)

path = [[0 for i in range(w)] for i in range(w)]

for bit in bits:
    for ww in range(w):
        flag = True
        if ww != w-1:
            if bit[ww] == 1:
                flag = False
                path[ww][ww+1] += 1
        if ww != 0:
            if bit[ww-1] == 1:
                flag = False
                path[ww][ww-1] += 1
        if flag:
            path[ww][ww] += 1

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

dp[0][0] = 1

for hh in range(h):
    for ww in range(w):
        for ww2 in range(w):
            dp[hh+1][ww2] += dp[hh][ww] * path[ww][ww2] 
            dp[hh+1][ww2] %= 1000000007
            
print(dp[-1][k-1])

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def check(x):
    n=x.bit_length()
    for i in range(n-1):
        if((x>>i)&1 and (x>>(i+1))&1):
            return False
    return True

def resolve():
    H,W,K=map(int,input().split())
    K-=1
    dp=[0]*W
    dp[0]=1
    for _ in range(H):
        ndp=[0]*W
        
        for V in range(2**(W-1)):
            if(not check(V)): continue
            for w in range(W):
                if(w<W-1 and (V>>w)&1): 
                    ndp[w+1]+=dp[w]
                    ndp[w+1]%=MOD
                elif(w>0 and (V>>(w-1))&1): 
                    ndp[w-1]+=dp[w]
                    ndp[w-1]%=MOD
                else: 
                    ndp[w]+=dp[w]
                    ndp[w]%=MOD
        dp=ndp
    print(dp[K])
resolve()

Solution (Python):
MOD = 1000000007
 
def get_fibonatti_table(n):
    table = [1,1]
    for i in range(2, n+1):
        table.append(table[i-1]+table[i-2])
    return table

def solve():
    H,W,K = map(int, input().split())
    fib_table = get_fibonatti_table(W)
    dp_table = [[0 for _ in range(W+1)] for _ in range(H+1)]
    dp_table[0][1] = 1
    for h in range(1, H+1):
        for w in range(1,W+1):
            weight = fib_table[w-1]*fib_table[W-w]
            dp_table[h][w] = dp_table[h-1][w] * weight
            if 1 < w:
                
                weight = fib_table[w-2]*fib_table[W-w]
                
                dp_table[h][w] += dp_table[h-1][w-1] * weight
            if w < W:
                
                weight = fib_table[w-1]*fib_table[W-w-1]
                dp_table[h][w] += dp_table[h-1][w+1] * weight
                
    
    print(dp_table[H][K] % MOD)
    
solve()