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):

from collections import defaultdict


def main():
    high, width, goal = map(int, input().split())

    move_dic = [defaultdict(int) for i in range(width + 2)]
    for i in range(2 ** (width - 1)):
        data = bin(i)[2:]
        if '11' in data:
            continue
        data = [0 for j in range(width - 1 - len(data))] + list(map(int, list(data)))
        
        for j in range(width - 1):
            if data[j]:
                move_dic[j + 1][j + 2] += 1
                move_dic[j + 2][j + 1] += 1
            elif j < width - 2:
                if data[j + 1] == 0:
                    move_dic[j + 2][j + 2] += 1
                if j == 0:
                    move_dic[j + 1][j + 1] += 1
            else:
                move_dic[j + 2][j + 2] += 1
            

    dp = [[0 for i in range(width + 2)] for j in range(high + 2)]
    dp[1][1] = 1

    for i in range(2, high + 2):
        for j in range(1, width + 1):
            dp[i][j] = dp[i - 1][j - 1] * move_dic[j - 1][j] + dp[i - 1][j] * move_dic[j][j] + dp[i - 1][j + 1] * move_dic[j + 1][j]

    if width == 1:
        dp[high + 1][goal] = 1
    mod = 10 ** 9 + 7
    print(dp[high + 1][goal] % mod)



if __name__ == '__main__':
    main()

Solution (Python):
from itertools import chain
import numpy as np

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

def gen_row_pattern(i):
  
  if i>W:
    return [[]]
  
  result = [[(i,i)] + x for x in gen_row_pattern(i+1)]
  
  if i <= W-1:
    result += [[(i,i+1)] + x for x in gen_row_pattern(i+2)]
  return result

patterns = gen_row_pattern(1)

import numpy as np
A = np.zeros((W+1,W+1),dtype=np.int64)
for x,y in chain(*patterns):
  A[x,y] += 1
  if x != y:
    A[y,x] += 1


v = np.zeros(W+1,dtype=np.int64)
v[1] = 1

MOD = 10**9 + 7

for _ in range(H):
  v = np.mod(np.dot(A,v),MOD)

answer = v[K]
print(answer)

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

f = [1, 1]
while len(f)<=W:
  f.append(f[-2]+f[-1])

A = {(0,k):(1 if k==1 else 0) for k in range(1, W+1)}

for h in range(1, H+1):
  for x in range(1, W+1):
    pat = f[x-1]*f[W-x]*A[(h-1, x)]
    if x > 1:
      pat += f[x-2]*f[W-x]*A[(h-1, x-1)]
    if x < W:
      pat += f[x-1]*f[W-x-1]*A[(h-1, x+1)]
    A[(h, x)] = pat

print(A[(H, K)]%1000000007)

Solution (Python):
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

h,w,k = li()
k -= 1
MOD = 10**9 + 7


if w > 1:
    matrix = [[0]*w for _ in range(w)]
    for num in range(1 << (w-1)):
        if "11" in bin(num):
            continue

        ex = False
        for i, bit in enumerate(bin(num)[2:].zfill(w-1)):
            if bit == "1":
                ex = True
                matrix[i][i+1] += 1
                matrix[i+1][i] += 1

            elif ex:
                ex = False

            else:
                matrix[i][i] += 1

        if not ex:
            matrix[w-1][w-1] += 1

    
    dp = [1] + [0]*(w-1)
    for hi in range(h):
        nex = [0]*w
        for wj in range(w):
            for wk in range(w):
                nex[wj] += matrix[wj][wk] * dp[wk]
                nex[wj] %= MOD

        dp = nex

    print(dp[k])

else:
    print(1)

Solution (Python):
from functools import lru_cache
H, W, K = map(int, input().split())
mod = 1000000007
def amida(start, end):
    if end <= start:
        return 1
    if end > W-1:
        return 1
    return count(end-start+1)
@lru_cache(maxsize=None)
def count(n):
    res = 0
    if n <= 0:
        return 0
    if n == 1:
        return 1
    if n == 2:
        return 2
    res += count(n-1)
    res += count(n-2)
    return res

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

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

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

if (W==1):
    print (1)
else:
    import itertools as tool
    amd = [ it  for it in  tool.product( *([[0,1]]*(W-1)) ) if sum([ 1 if it[i]+it[i+1]==2 else 0 for i in range(W-2)] ) == 0   ]

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


    for h in range(H):
        _dp = [0]*W
        for it in amd:
            w = 0
            for i in range(W):
                if w >= W-1 :
                    break
                if (it[w]==1):
                    _dp[w]+=dp[w+1]
                    _dp[w+1]+=dp[w]
                    w+=2
                else:
                    _dp[w]+=dp[w]
                    w+=1
            if (w==W-1):
                _dp[w]+=dp[w]
                w+=1
        dp = [ it%MOD for it in _dp]
    print (dp[K-1]%MOD)

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 cur in range(h):
    for bits in range(1 << (w - 1)):
        if '11' in bin(bits): continue
        
        for i in range(w):
            
            if i < (w - 1) and (bits >> i) & 1:
                ndp[i + 1] += dp[i]
                ndp[i + 1] %= MOD
            elif i >= 1 and (bits >> (i - 1)) & 1:
                ndp[i - 1] += dp[i]
                ndp[i - 1] %= MOD
            else:
                ndp[i] += dp[i]
                ndp[i] %= MOD
    dp = ndp.copy()
    ndp = [0] * w
print(dp[k])

Solution (Python):

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

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






def fib(n):
    fibonacci = [1,1,2,3,5,8,13,21,34]
    return fibonacci[n]

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

    dp[0][0] = 1
    for h in range(1,H+1):
        for k in range(W):
            if 0 < k < W-1: 
                num1 = dp[h-1][k-1]*fib(W-k-1)*fib(k-1)
                num2 = dp[h-1][k]  *fib(W-k-1)*fib(k)
                num3 = dp[h-1][k+1]*fib(W-k-2)*fib(k)
            if k == 0: 
                num1 = 0
                num2 = dp[h-1][k]  *fib(W-k-1)*fib(k)
                num3 = dp[h-1][k+1]*fib(W-k-2)*fib(k)
                
            if k == W-1: 
                num1 = dp[h-1][k-1]*fib(W-k-1)*fib(k-1)
                num2 = dp[h-1][k]  *fib(W-k-1)*fib(k)
                num3 = 0
            
            dp[h][k] = num1+num2+num3
    mod = 10**9+7
    print(dp[-1][K-1]%mod)

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

horz_pattern = 0
horz_pattern_fromleft = [0] * W
horz_pattern_fromright = [0] * W
for i in range(2**(W-1)):
  horz = bin(i+2**(W-1))[3:]
  ok = 1
  for j in range(W-2):
    if int(horz[j]) * int(horz[j+1]) == 1:
      ok = 0
      break
  if ok:
    horz_pattern += 1
    for bar in range(W-1):
      if horz[bar] == "1":
        horz_pattern_fromleft[bar+1] += 1
        horz_pattern_fromright[bar] += 1

dp = [[0 for w in range(W+2)] for h in range(H+1)]
dp[0][1] = 1
for h in range(1,H+1):
  for w in range(1,W+1):
    fromleft = horz_pattern_fromleft[w-1]
    fromright = horz_pattern_fromright[w-1]
    no_move = horz_pattern - fromleft - fromright
    dp[h][w] = (dp[h-1][w] * no_move
    		  + dp[h-1][w-1] * fromleft
      		  + dp[h-1][w+1] * fromright) % mod
print(dp[H][K])

Solution (Python):
import sys
from collections import defaultdict
input = sys.stdin.readline
H, W, K = list(map(int, input().split()))

mod = 1000000007

c = defaultdict(lambda: 1)
c.update({0: 1, 1: 2, 2: 3, 3: 5, 4: 8, 5: 13, 6: 21})

dp = [{0: 0, 1: 1, 2: 0, 3: 0, 4: 0, 5: 0, 6: 0, 7: 0, 8: 0, 9: 0}, ]

for i in range(1, H+2):
    dp_i = {0: 0, W+1: 0}
    for j in range(1, W+1):
        dp_i[j] = dp[i-1][j-1]*c[j-3]*c[W-j-1] % mod + \
            dp[i-1][j]*c[j-2]*c[W-j-1] % mod + \
            dp[i-1][j+1]*c[j-2]*c[W-j-2] % mod
    dp.append(dp_i)


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

Solution (Python):
from collections import defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

H,W,K = inpl()

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

a_to_b = [[0]*W for i in range(W)]
for a in range(W):
    for b in range(W):
        if a > b:
            a_to_b[a][b] = a_to_b[b][a]
        else:
            if abs(a-b) > 1:
                a_to_b[a][b] = 0
            else:
                a_to_b[a][b] = num[a]*num[W-b-1]

cnt = [0]*W
cnt[0] = 1
for h in range(H):
    next_cnt = [0]*W
    for a in range(W):
        for b in range(W):
            next_cnt[b] += a_to_b[a][b] * cnt[a]
    cnt = next_cnt[:]

print(cnt[K-1]%mod)

Solution (Python):
H,W,K=[int(a) for a in input().split(" ")]
wp = [0]*(W-1)
wv = [0]*W
curr, prev = [0]*W, [0]*W
prev[0] = 1
mod = 1000000007

def comb(n):
    prev, curr = [1,1], [0,0]
    if n<1: return 1
    for i in range(n-1):
        curr[0] = prev[1]
        curr[1] = prev[0]+prev[1]
        prev,curr = curr,prev
    return sum(prev)

for i in range(W):
    nl, nr = max(0,i-1), max(0, W-i-2)
    wv[i] = comb(nl)*comb(nr)

for i in range(W-1):
    nl, nr = max(0, i-1), max(0, W-i-3)
    wp[i] = comb(nl)*comb(nr)

for i in range(H):
    for i in range(W):
        curr[i]=0
    for i in range(W):
        curr[i] = (curr[i] + (wv[i]*prev[i])%mod)%mod
        if i>=1:
            curr[i-1] = (curr[i-1]+(wp[i-1]*prev[i])%mod)%mod
        if i<=W-2:
            curr[i+1] = (curr[i+1]+(wp[i]*prev[i])%mod)%mod
    prev, curr = curr, prev
print(prev[K-1]%mod)

Solution (Python):
h,w,k=map(int,input().split())
pattern=[]
n_pattern=[]
pattern.append(1)
n_pattern.append(0)
for i in range(w-1):
    pattern.append(0)
    n_pattern.append(0)
def f(x):
    if x==0:
        return 1
    elif x==1:
        return 1
    elif x==2:
        return 2
    elif x==3:
        return 3
    elif x==4:
        return 5
    elif x==5:
        return 8
    elif x==6:
        return 13
    elif x==7:
        return 21
for i in range(h):
    for j in range(w):
        a=f(w-1-j)*f(j)*pattern[j]
        if j>=1:
            b=f(w-1-j)*f(j-1)*pattern[j-1]
        else:
            b=0
        if j<=w-2:
            c=f(w-2-j)*f(j)*pattern[j+1]
        else:
            c=0
        n_pattern[j]=a+b+c
    for j in range(w):
        pattern[j]=n_pattern[j]
print(pattern[k-1]%(10**9+7))

Solution (Python):
from itertools import product

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

mod = 10 ** 9 + 7

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

for i, j, k in product(range(H), range(W), range(1 << (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 >= 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

import heapq
import re
import bisect
import random
import math
import itertools
from collections import defaultdict, deque
from copy import deepcopy
from decimal import *

h, w, k = map(int, input().split())
memo = defaultdict(lambda:defaultdict(int))

def dfs(x, y):
    if y == h:
        if x == k - 1:
            return 1
        else:
            return 0
    if y in memo[x]:
        return memo[x][y]

    ans = 0
    for i in range(1 << w - 1):
        flg = True
        for j in range(w - 2):
            if i & (1 << j) and i & (1 << j + 1):
                flg = False
                break
        if flg:
            nx = x
            if x > 0 and i & (1 << x - 1):
                nx = x - 1
            elif i & (1 << x):
                nx = x + 1
            ans += dfs(nx, y + 1)
            ans %= 1000000000 + 7
    memo[x][y] = ans
    return ans
print(dfs(0, 0))

Solution (Python):


from bisect import bisect_left as binl

def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return map(int, input_tuple)


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def lcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x





def calc_bincount(w):
    bincount = {}
    for i in range(w - 1):
        bincount[i] = 2**i
        for j in range(2**i):
            while j:
                if j & 3 == 3:
                    bincount[i] -= 1
                    break
                j >>= 1
    bincount[-4] = bincount[-3] = bincount[-2] = bincount[-1] = 1
    return bincount


def main():
    h, w, k = intin()
    mod = 1000000007

    bincount = calc_bincount(w)

    counts_first = {}
    for i in range(1, w + 1):
        counts_first[i] = 0
    counts_first[1] = 1
    h_to_counts = {0: counts_first}

    for i in range(1, h + 1):
        prev_counts = h_to_counts[i - 1]
        h_to_counts[i] = {}
        for j in range(1, w + 1):
            h_to_counts[i][j] = 0

            
            if j > 1:
                incr = ((bincount[j-3] * bincount[((w+1)-j)-2]) * prev_counts[j-1]) % mod
                h_to_counts[i][j] += incr
                h_to_counts[i][j] %= mod

            
            incr = ((bincount[j-2] * bincount[((w+1)-j)-2]) * prev_counts[j]) % mod
            h_to_counts[i][j] += incr
            h_to_counts[i][j] %= mod

            
            if j < w:
                incr = ((bincount[j-2] * bincount[((w+1)-j)-3]) * prev_counts[j+1]) % mod
                h_to_counts[i][j] += incr
                h_to_counts[i][j] %= mod

    print(h_to_counts[h][k])


if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np

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

valids = []
for i in range(2 ** (W - 1)):
    f0, f1 = False, False
    for bit in range(W - 1):
        if i >> bit & 1 == 0:
            f0 = True
            f1 = False
        else:
            if f1 == True:
                break
            f1 = True
            f0 = False
    else:
        valids.append(i)

M = np.zeros((W, W))

for valid in valids:
    m = np.eye(W)
    for bit in range(W - 1):
        if valid >> bit & 1 == 1:
            end = W - bit
            m[end-2:end, end-2:end] = np.array([[0, 1], [1, 0]])
    M += m

state = np.zeros((W,))
state[0] = 1
for i in range(H):
    state = M.dot(state)
    state %= int(1e9 + 7)

print(int(state[K - 1] % (int(1e9) + 7)))

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

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

dp = [[0]*(W+2) for _ in range(H+1)]
dp[0][K] = 1
for i in range(1,H+1):
    for j in range(1,W+1):
        dp[i][j] += (dp[i-1][j] * f[max(0,j-2)] * f[max(0,W-j-1)]
                     + dp[i-1][j-1] * f[max(0,j-3)] * f[max(0,W-j-1)]
                     + dp[i-1][j+1] * f[max(0,j-2)] * f[max(0,W-j-2)] )
        dp[i][j] %= mod
print(dp[-1][1])

Solution (Python):
mod=10**9+7
def add(a,b):
    return (a+b)%mod
def sub(a,b):
    return (a-b)%mod
def mul(a,b):
    return ((a%mod)*(b%mod))%mod
def pow(x,y):
    if y==0:
        return 1
    elif y==1:
        return x%mod
    elif y%2==0:
        return pow(x,y//2)**2 % mod
    else:
        return pow(x,y//2)**2 * x % mod
def div(a,b):
    return mul(a,pow(b,mod-2))

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

p=[1,1,1+1,1+2,1+3+1,1+4+3,1+5+6+1,1+6+10+4]

for i in range(w):
    a[0][i][i]=p[w-1-i]*p[i]
    if i<w-1:
        a[0][i][i+1]=a[0][i+1][i]=p[w-2-i]*p[i]

for r in range(1,h):
    for i in range(w):
        for j in range(w):
            a[r][i][j]=mul(a[r-1][i][j],p[w-1-j]*p[j])
            if j>0:
                a[r][i][j]+=mul(a[r-1][i][j-1],p[w-2-(j-1)]*p[j-1])
            if j<w-1:
                a[r][i][j]+=mul(a[r-1][i][j+1],p[w-2-j]*p[j])
                
print(a[h-1][0][k-1]%mod)

Solution (Python):
import collections
cd = collections.defaultdict
dp = cd(lambda: cd(int))
dp[0][1] = 1

H, W, K = [int(_) for _ in input().split()]
mod = 10**9 + 7

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

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

print(dp[H][K])

Solution (Python):
import collections
cd = collections.defaultdict
memo = cd(lambda: cd(int))
memo[0][1] = 1

H, W, K = [int(_) for _ in input().split()]
mod = 10**9 + 7

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


def count(h, w):
    if memo[h][w]:
        return memo[h][w]
    elif h == 0 or w == 0 or w == W + 1:
        return 0
    else:
        ret = count(h - 1, w) * fib[w - 1] * fib[W - w]
        ret += count(h - 1, w - 1) * fib[w - 2] * fib[W - w]
        ret += count(h - 1, w + 1) * fib[w - 1] * fib[W - w - 1]
        ret %= mod
        memo[h][w] = ret
        return ret


print(count(H, K))

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

draw_line = [0 for _ in range(W)]
draw_line[0] = 1
if W > 1:
    draw_line[1] = 1
for i in range(2, W):
    draw_line[i] = draw_line[i-1] + draw_line[i-2]

dp = [[0 for _ in range(W)] for _ in range(H+1)]
dp[0][0] = 1
for h in range(1, H+1):
    for w in range(W):
        
        if w > 0:
            dp[h][w] += dp[h-1][w-1] * draw_line[w-1] * draw_line[W-w-1]
        
        dp[h][w] += dp[h-1][w] * draw_line[w] * draw_line[W-w-1]
        
        if w < W-1:
            dp[h][w] += dp[h-1][w+1] * draw_line[w] * draw_line[W-w-2]

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

Solution (Python):

import sys

MOD = 1000000007  

def solve(H: int, W: int, K: int):
    
    t = [[0 for i in range(W)] for j in range(H+1)]
    t[0][0] = 1
    
    
    d = [0 for i in range(W+1)]
    d[0] = 1
    d[1] = 1
    for w in range(2, W+1):
        d[w] += d[w-1] 
        d[w] += d[w-2] 

    for h in range(1, H+1):
        for k in range(W):
            if k > 0:
                
                t[h][k] += t[h-1][k-1] * d[k-1] * d[W-k-1]
                t[h][k] %= MOD
            if k < W-1:
                
                t[h][k] += t[h-1][k+1] * d[k] * d[W-k-2]
                t[h][k] %= MOD
            
            t[h][k] += t[h-1][k] * d[k] * d[W-k-1]
            t[h][k] %= MOD

    print(t[H][K-1])
    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):
import sys,collections as cl
Max = sys.maxsize
def l():
	return list(map(int,input().split()))
def m():
	return map(int,input().split())
def s(x):
	a = []
	aa = x[i]
	su = 1
	for i in range(len(x)-1):
		if aa == x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a

h,w,k = m()

a = [1,1]

for i in range(98):
	a.append(a[-1] + a[-2])

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

for i in range(h):
	for j in range(w):
		l[i+1][j+1] = (l[i][j]*(a[max(0,j-1)] * a[w - 1 - j]) +l[i][j+1]*(a[j] * a[w - 1 - j]) + l[i][j+2]*(a[j] * a[max(0,w - 2 - j)]))%(10**9+7)
print(l[h][k])

Solution (Python):
from functools import lru_cache


def solve(string):
    h, w, k = map(int, string.split())
    c = [1, 1]
    for _ in range(1, 7):
        i, j = c[-2:]
        c.append(i + j)

    @lru_cache(h * w)
    def rec(pos, depth):
        if depth == h:
            return 1 if pos == 1 else 0
        ans = rec(pos, depth + 1) * c[pos - 1] * c[w - pos]
        if pos < w:
            ans += rec(pos + 1, depth + 1) * c[pos - 1] * c[w - pos - 1]
        if pos > 1:
            ans += rec(pos - 1, depth + 1) * c[pos - 2] * c[w - pos]
        return ans

    return str(rec(k, 0) % (10**9 + 7))


if __name__ == '__main__':
    print(solve(input()))

Solution (Python):
import sys
ns = lambda: sys.stdin.readline().rstrip()
ni = lambda: int(ns())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
nsl = lambda: map(str, sys.stdin.readline().split())

h, w, k = nm()
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):
        for m in range(2 ** (w - 1)):
            count1 = 0
            count2 = 0
            count3 = 0
            mm = bin(m)[2:].zfill(w - 1)
            if '11' in mm:
                continue
            if j > 0:
                if mm[j - 1] == '1':
                    count1 += 1
                else:
                    if j < w - 1:
                        if mm[j] == '1':
                            count3 += 1
                        else:
                            count2 += 1
                    else:
                        count2 += 1
            else:
                if j < w - 1:
                    if mm[j] == '1':
                        count3 += 1
                    else:
                        count2 += 1
                else:
                    count2 += 1
            if j > 0:
                dp[i + 1][j - 1] += (dp[i][j] * count1) % mod
            if j < w - 1:
                dp[i + 1][j + 1] += (dp[i][j] * count3) % mod
            dp[i + 1][j] += (dp[i][j] * count2) % mod

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

Solution (Python):
H,W,K=map(int,input().split())
if W==1:
    print(1)
    quit()

INF=1e9+7
dp=[[0]*W for i in range(H+1)]
dp[0][0]=1
d=W-1
a=max(0,d-1)
b=max(0,d-2)
f=max(0,d-3)
dic={0:0,1:1,2:2,3:4,4:7,5:12,6:20}
a=dic[a]+1
b=dic[b]+1
f=dic[f]+1
def func(w):
    c=dic[w-1]+1
    e=dic[d-w-1]+1
    return c*e
def func1(w):
    c=dic[w-1-1]+1
    e=dic[d-w-1]+1
    return c*e
def func2(w):
    c=dic[w-1]+1
    e=dic[d-w-1-1]+1
    return c*e
for i in range(H):
    for w in range(W):
        if w==0:
            dp[i+1][w]=(dp[i][w]*a)+(dp[i][w+1]*b)
            dp[i+1][w]%=INF
        elif w==W-1:
            dp[i+1][w]=(dp[i][w]*a)+(dp[i][w-1]*b)
            dp[i+1][w]%=INF
        elif w==1 :
            dp[i+1][w]=(dp[i][w]*b)+(dp[i][w-1]*b)+(dp[i][w+1]*f)
            dp[i+1][w]%=INF
        elif w==W-2:
            dp[i+1][w]=(dp[i][w]*b)+(dp[i][w-1]*f)+(dp[i][w+1]*b)
            dp[i+1][w]%=INF
        else:
            dp[i+1][w]=(dp[i][w]*func(w))+(dp[i][w-1]*func1(w))+(dp[i][w+1]*func2(w))
            dp[i+1][w]%=INF

print(int(dp[H][K-1]%INF))

Solution (Python):
h,w,k=map(int,input().split())
dp=[[0]*(w+1) for i in range(h+2)]
dp[1][1]=1
p=10**9+7
line=[1]*(101)
line[2]=2
for i in range(3,101):
  line[i]=line[i-1]+line[i-2]
for i in range(1,h+1):
  for j in range(1,w+1):
    dp[i+1][j]+=dp[i][j]*line[j-1]*line[w-j]
    dp[i+1][j]%=p
    if 2<=j:
      dp[i+1][j]+=dp[i][j-1]*line[j-2]*line[w-j]
      dp[i+1][j]%=p
    if j+1<=w:
      dp[i+1][j]+=dp[i][j+1]*line[j-1]*line[w-j-1]
      dp[i+1][j]%=p
print(dp[h+1][k])

Solution (Python):



import itertools 
from collections import defaultdict

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


w = [[0] * 3 for _ in range(W)]
patterns = itertools.product([0, 1], repeat=W-1)

if W > 1:
    for i in range(W):
        for k, j in enumerate([-1, 0, 1]):
            if i - j < 0 or i - j > W - 1:
                continue
            
            num_use_pattern = 0
            for pattern in itertools.product([0, 1], repeat=W-1):
                if j == -1:
                    if i - 1 < 0: 
                        if pattern[i] == 0:
                            continue
                    else:
                        if not (pattern[i-1] == 0 and pattern[i] == 1):
                            continue
                elif j == 1:
                    if i >= W - 1:
                        if pattern[i-1] == 0:
                             continue
                    else:
                        if not (pattern[i-1] == 1 and pattern[i] == 0):
                            continue
                else:
                    if i - 1 < 0: 
                        if pattern[i] == 1:
                            continue
                    elif i >= W - 1:
                        if pattern[i-1] == 1:
                             continue
                    else:
                        if pattern[i] == 1 or pattern[i-1] == 1:
                            continue
                   
                if sum([pattern[l] * pattern[l-1] for l in range(1, W-1)]) > 0:
                    continue
                
                num_use_pattern += 1
                
            w[i][k] += num_use_pattern
     
    memo = defaultdict(lambda: defaultdict(lambda: -1))
    def recursive(h, k, num_p):
        if 0 > k or k >= W:
            return 0
        if memo[h][k] != -1:
            return memo[h][k] * num_p
        if h == H:
            if k == K - 1:
                return num_p
            else:
                return 0
             
        temp1 = 0
        temp2 = 0
        temp3 = 0
        temp1 = recursive(h + 1, k, w[k][1])
        if k > 0:
            temp2 = recursive(h + 1, k - 1, w[k][2])
        if k <= W - 1:
            temp3 = recursive(h + 1, k + 1, w[k][0])
            
        temp = temp1 + temp2 + temp3
        memo[h][k] = temp
        
        return temp * num_p
     
    print(recursive(0, 0, 1) % 1000000007)
else:
    print(1)

Solution (Python):
import itertools

import numpy as np

height, width, k = map(int, input().split())
k -= 1

MOD = 1000000007


patterns = []
for r in range(width - 1):
    for pattern in itertools.combinations(range(width - 1), r):
        
        if all(abs(a - b) != 1 for a, b in zip(pattern[:-1], pattern[1:])):
            patterns.append(pattern)


counts = np.zeros((width, width))
for pattern in patterns:
    for w in range(width):
        if w in pattern:
            counts[w][w + 1] += 1
        elif w - 1 in pattern:
            counts[w][w - 1] += 1
        else:
            counts[w][w] += 1
if width == 1:
    counts[0][0] = 1



dp = np.zeros((height, width))
dp[0] = counts[0].copy()
for h in range(height - 1):
    dp[h + 1] = np.dot(dp[h], counts) % MOD

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

Solution (Python):
import itertools

height, width, k = map(int, input().split())
k -= 1

MOD = 1000000007


patterns = []
for r in range(width - 1):
    for pattern in itertools.combinations(range(width - 1), r):
        
        if all(abs(a - b) != 1 for a, b in zip(pattern[:-1], pattern[1:])):
            patterns.append(pattern)


counts = [[0 for _ in range(width)] for _ in range(width)]
for pattern in patterns:
    for w in range(width):
        if w in pattern:
            counts[w][w + 1] += 1
        elif w - 1 in pattern:
            counts[w][w - 1] += 1
        else:
            counts[w][w] += 1



dp = [[0 for _ in range(width)] for _ in range(height)]
dp[0] = counts[0].copy()
for h in range(height - 1):
    for w in range(width):
        
        dp[h + 1][w] = sum([dp[h][v] * counts[v][w] for v in range(width)]) % MOD

if width == 1:
    print(1)
else:
    print(dp[-1][k])

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


def barcnt(n):
    if n == 0:
        return 1
    elif n == 1:
        return 1
    elif n == 2:
        return 2
    elif n == 3:
        return 3
    elif n == 4:
        return 5
    elif n == 5:
        return 8
    elif n == 6:
        return 13
    elif n == 7:
        return 21
    else:
        return 0
    
def f(H, K):
    if K < 1 or K > W:
        return 0
    else:
        if dp[H][K] != -1:
            return dp[H][K]
        elif H == 1:
            if K == 1:
                dp[H][K] = barcnt(W-1)
                return dp[H][K]
            elif K == 2:
                dp[H][K] = barcnt(W-2)
                return dp[H][K]
            else:
                dp[H][K] = 0
                return 0
        else:
            dp[H][K] = f(H-1, K-1)*barcnt(max(0, K-2))*barcnt(max(0, W-K))
            dp[H][K] += f(H-1, K)*barcnt(max(0, K-1))*barcnt(max(0, W-K))
            dp[H][K] += f(H-1, K+1)*barcnt(max(0, K-1))*barcnt(max(0, W-K-1))
            dp[H][K] %= 10**9+7
            return dp[H][K]

print(f(H, K))

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

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


def check(l):
    for i in range(len(l)-1):
        if l[i+1]+l[i]==2:
            return False
    return True

for i in range(1,H+1):
    for w in range(W):
        X,Y,Z=0,0,0
        for j in range(2**(W-1)):
            tmp=[]
            for k in range(W-1):
                tmp.append(j>>k&1)
            if check(tmp):
                if w-1>=0 and (j>>(w-1))&1==1:
                    dp[i][w-1]+=dp[i-1][w]
                    dp[i][w-1]%=P
                elif w<=W-2 and j>>w&1==1:
                    dp[i][w+1]+=dp[i-1][w]
                    dp[i][w+1]%=P
                else:
                    dp[i][w]+=dp[i-1][w]
                    dp[i][w]%=P
print(dp[H][K-1])