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

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap



def C(n, r):
    c = 1
    for i in range(1, r+1):
        c *= n
        c //= i
        n -= 1

    return c

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

    
    L = [0] * (W+2)
    C = [0] * (W+2)
    R = [0] * (W+2)
    for c in product(range(2), repeat=W-1):
        for i in range(W-2):
            if c[i] * c[i+1] != 0:
                break
        else:
            for j in range(1, W+1):
                if j != 1 and c[j-2] == 1:
                    L[j] += 1
                elif j != W and c[j-1] == 1:
                    R[j] += 1
                else:
                    C[j] += 1

    dp[0][1] = 1
    mod = 10**9 + 7
    for h in range(0, H):
        for w in range(1, W+1):
            dp[h+1][w-1] += dp[h][w] * L[w]
            dp[h+1][w-1] %= mod
            dp[h+1][w] += dp[h][w] * C[w]
            dp[h+1][w] %= mod
            dp[h+1][w+1] += dp[h][w] * R[w]
            dp[h+1][w+1] %= mod


    return dp[H][K]


def main():
    H, W, K = read_int_n()
    
    print(slv(H, W, K))


if __name__ == '__main__':
    main()

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

def gen_pattern(curr, result):
    if len(curr) == W - 1:
        result.append(curr)
        return
    if len(curr) == 0:
        gen_pattern([0], result)
        gen_pattern([1], result)
    else:
        gen_pattern(curr + [0], result)
        if curr[-1] == 0:
            gen_pattern(curr + [1], result)
bridge = []
gen_pattern([], bridge)

MOD = 1000000007

di = []
for y in range(H + 1):
    ret = []
    for x in range(W):
        ret.append(0)
    di.append(ret)
di[0][0] = 1

for y in range(1, H + 1):
    for x in range(W):
        left = 0
        center = 0
        right = 0
        if W == 1:
            center = 1
        else:
            for b in bridge:
                if x == 0:
                    if b[x] == 0:
                        center += 1
                    if b[x] > 0:
                        right += 1
                elif x == W - 1:
                    if b[x - 1] > 0:
                        left += 1
                    if b[x - 1] == 0:
                        center += 1
                else:
                    if b[x - 1] > 0:
                        left += 1
                    if b[x - 1] == 0 and b[x] == 0:
                        center += 1
                    if b[x] > 0:
                        right += 1
        t = (di[y - 1][x] * center) % MOD
        if x > 0:
            t += (di[y - 1][x - 1] * left) % MOD
        if x < W - 1:
            t += (di[y - 1][x + 1] * right) % MOD
        di[y][x] = t % MOD

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

Solution (Python):

"""
Created on Sat Jan  5 10:49:47 2019

@author: Yamazaki Kenichi
"""

H,W,K = map(int, input().split())
mod = 10**9 +7
a = [1,1,2,3,5,8,13,21]
T = [[-1 for i in range(9)] for i in range(H+1) ]
def n(h,k):
    if T[h][k] != -1:
        return T[h][k]
    res = 0
    if h == 1:
        if k == 1 or k == 2:
            T[h][k] = a[W-k]
            return a[W-k]
        else:
            T[h][k] = 0
            return 0
    res += n(h-1,k)*(a[k-1] * a[W-k])
    if k != 1:
        res += n(h-1,k-1)*(a[k-1-1] * a[W-k])
    if k != W:
        res += n(h-1,k+1)*(a[k-1] * a[W-k-1])
    T[h][k] = res
    return res % mod
ans = n(H,K)
print(ans)

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

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

    

for i in range(1,H+1):
    for x in range(2**(W-1)):           
        Alloc = [0]*9
        tmp = x
        for y in range(1,8):  
            Alloc[y] = tmp%2
            tmp //= 2 
        for y in range(0,9):
            if Alloc[y] == 1 and Alloc[y+1] == 1:
                break
        else:   
            for j in range(1,9):  
                if Alloc[j-1] == 1: 
                    dp[i][j] += dp[i-1][j-1]
                elif Alloc[j] == 1:
                    dp[i][j] += dp[i-1][j+1]
                else:
                    dp[i][j] += dp[i-1][j]
                dp[i][j] %= 1000000007

print(dp[H][K])

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

mat = [[0]*W for _ in range(W)]

def dfs(bar_partial):
    if len(bar_partial) == W-1:
        perm = list(range(W))
        for i,w in enumerate(bar_partial):
            if w == 1:
                perm[i] = i+1
                perm[i+1] = i
        for i in range(W):
            mat[i][perm[i]] += 1
        return
    bar_partial.append(0)
    dfs(bar_partial)
    bar_partial.pop()
    if len(bar_partial) == 0 or bar_partial[-1] == 0:
        bar_partial.append(1)
        dfs(bar_partial)
        bar_partial.pop()

dfs([])
dp_hw = [[0]*W for _ in range(H+1)]
dp_hw[0][0] = 1
for i in range(1, H+1):
    dp_prev = dp_hw[i-1]
    dp_current = dp_hw[i]
    for j in range(W):
        for k in range(W):
            dp_current[j] += dp_prev[k]*mat[j][k]
        dp_current[j] = dp_current[j] % 1000000007

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

Solution (Python):

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


def noborder_both_side(cw: int, W: int) -> int:
    """縦線 cw の両隣に横線が存在しない場合の数
    """
    
    return border_num[cw-1] * border_num[W-cw]


def border_only_leftside(cw: int, W: int) -> int:
    """縦線 cw の左側のみに横線が存在する場合の数
    """
    
    if cw == 1:
        return 0

    
    
    
    return border_num[cw-2] * border_num[W-cw]


def border_only_rightside(cw: int, W: int) -> int:
    """縦線 cw の右側のみに縦線が存在する場合の数
    """
    
    if cw == W:
        return 0

    
    
    
    return border_num[cw-1] * border_num[W-cw-1]


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

    for h in range(H):
        for w in range(1, W+1):
            
            
            
            dp[h+1][w] += dp[h][w] * noborder_both_side(w, W)

            
            
            
            dp[h+1][w-1] += dp[h][w] * border_only_leftside(w, W)

            
            
            
            dp[h+1][w+1] += dp[h][w] * border_only_rightside(w, W)

    return dp[H][K]


if __name__ == "__main__":
    H, W, K = map(int, input().split())
    ans = number_of_amidakuji(H, W, K)
    print(ans % 1000000007)

Solution (Python):
ri = lambda: int(input())
rl = lambda: list(map(int,input().split()))
rr = lambda N: [ri() for _ in range(N)]
YN = lambda b: print('YES') if b else print('NO')
INF = 10**18

H,W,K=rl()
DIV =  1000000007

rc = K-1
dp = [[0 for _ in range(W)] for _ in range(H+1)]
dp[0][0]=1
bar = [1, 1+0, 1+1, 2+1, 3+2, 5+3, 8+5, 13+8, 21+13]

for h in range(1,H+1):
    for w in range(W):
        if w != 0:
            dp[h][w] += dp[h-1][w-1]*bar[w-1]*bar[W-w-1]
        dp[h][w] += dp[h-1][w]*bar[w]*bar[W-w-1]
        if w != W-1:
            dp[h][w] += dp[h-1][w+1]*bar[w]*bar[W-w-2]

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

Solution (Python):
md = 1000000000 + 7

def fi(n):
  if n < 0:
    return 0
  elif n <= 1:
    return 1
  elif n == 2:
    return 2
  else:
    return ( fi(n-1) + fi(n-2) ) % md


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

li[0] = 1

li_prev = []
li_next = []

li_prev[:] = li[:]
li_next[:] = li[:]

for j in range(h):
  for i in range(w):
    li_next[i] = (li_prev[max(0,i-1)] * fi(i-1) * fi(w-i-1)
               + li_prev[i] * fi(i) * fi(w-i-1)
               + li_prev[min(w-1,i+1)] * fi(i) * fi(w-i-2)) % md
  li_prev[:] = li_next[:]

print(li_prev[k-1])

Solution (Python):
from itertools import combinations
mod = 10**9 + 7
h, w, k = map(int, input().split())
edge = [[0]*w for i in range(w)]

for r in range(w//2+1):
    for c in combinations(range(w-1),r):
        
        flag = True
        if len(c) > 1:
            for i in range(len(c)-1):
                if c[i+1] - c[i] == 1:
                    flag = False
                    break
        if not flag:continue
        for i in range(w):
            if i in c: continue
            if i-1 in c:
                edge[i-1][i] += 1
                edge[i][i-1] += 1
            else:
                edge[i][i] += 1


DP = [[0]*w for i in range(h+1)]
DP[0][0] = 1
for i in range(h):
    for j in range(w):
        for l in range(w):
            DP[i+1][j] = (DP[i+1][j] + DP[i][l]*edge[l][j]) % mod

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

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

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

for h in range(H):
  cnt = 0
  while cnt < (1<<(W-1)):
    if '11' not in format(cnt, 'b'):
      for w in range(W):
        if w>0 and (cnt>>(w-1)) & 1:
          dp[h+1][w-1] += dp[h][w]
        elif w<W-1 and (cnt>>w) & 1:
          dp[h+1][w+1] += dp[h][w]
        else:
          dp[h+1][w] += dp[h][w]
    cnt += 1

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

Solution (Python):
H, W, K = map(int, input().split())
MOD = 10 ** 9 + 7
rec = []
for i in range(1 << (W - 1)):
    for j in range(W - 1):
        if i & 1 << j and i & 1 << (j + 1):
            break
    else:
        rec.append(i)

dp = [[0] * W for i in range(H + 1)]
dp[0][0] = 1
for i in range(1, H + 1):
    for k in range(W):
        for j in range(len(rec)):
            if k > 0 and (rec[j] & 1 << (k - 1)):
                dp[i][k - 1] += dp[i - 1][k]
                dp[i][k - 1] %= MOD
            elif k <= W - 2 and rec[j] & 1 << k:
                dp[i][k + 1] += dp[i - 1][k]
                dp[i][k + 1] %= MOD
            else:
                dp[i][k] += dp[i - 1][k]
                dp[i][k] %= MOD

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

Solution (Python):
H,W,K = map(int,input().split())
L = [-1]*W
def line(n):
  if(n<2):
    return 1
  else:
    if(L[n]!=-1):
      return L[n]
    else:
      a = 0
      for i in range(n-1):
        a += line(n-i-2)
      return a+1

arr = [[-1 for i in range(H)] for j in range(W)]
def ans(h,k):
  if(k<1 or k>W):
    return 0
  elif(h==0):
    if(k==1):
      return 1
    else:
      return 0
  else:
    if(arr[k-1][h-1]!=-1):
      return arr[k-1][h-1]
    else:
      arr[k-1][h-1]= ans(h-1,k)*(line(k-1)*line(W-k))+ans(h-1,k-1)*line(k-2)*line(W-k)+ans(h-1,k+1)*line(k-1)*line(W-k-1)
      arr[k-1][h-1] %= 1000000007
      return arr[k-1][h-1]
    
print(ans(H,K))

Solution (Python):
def memorize(func):
    memo = {}
    def wrapper(*args):
        if args not in memo:
            memo[args] = func(*args)
        return memo[args]
    return wrapper

@memorize
def amida(W):   
    if W<2:
        return 1
    else:
        return amida(W-1)+amida(W-2)

@memorize
def amida2(H, W, x):
    if H==0:
        return 1 if x==1 else 0
    a = 0 if x==1 else amida(x-2)*amida(W-x)*amida2(H-1, W, x-1)
    b = amida(x-1)*amida(W-x)*amida2(H-1, W, x)
    c = 0 if x==W else amida(x-1)*amida(W-x-1)*amida2(H-1, W, x+1)
    return (a+b+c)%1000000007
print(amida2(*map(int, input().split())))

Solution (Python):
h,w,k = map(int, input().split())
mod = 1000000000+7

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

dp[0][0] = 1

onerow_t = [0]*(w-1) 
onerow_sum = 0

for i in range(1<<(w-1)):
    tf = [None]*(w-1)
    valid = True
    for d in range(w-1):
        if (i>>d)&1 != 0:
            tf[d] = True
        if d>0 and tf[d-1] and tf[d]:
            valid = False
            break
    
    if valid:
        onerow_sum += 1
        for d in range(w-1):
            if tf[d]:
                onerow_t[d] += 1

for i in range(1,h+1):
    for j in range(w):
        tmp = onerow_sum
        if 0<=j-1:
            dp[i][j] += onerow_t[j-1]*dp[i-1][j-1]
            tmp -= onerow_t[j-1]
        if j+1<w:
            dp[i][j] += onerow_t[j]*dp[i-1][j+1]
            tmp -= onerow_t[j]
        
        dp[i][j] += tmp*dp[i-1][j]
        dp[i][j] = dp[i][j]%mod



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

Solution (Python):

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

def fibonatti(N):
  fibonatti_seq=[1,1]
  for i in range(1,N):
    fibonatti_seq.append(fibonatti_seq[i-1]+fibonatti_seq[i])
  return fibonatti_seq

fibonatti_seq=fibonatti(8)

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

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

Solution (Python):
h, w, k= map(int,input().split())
MOD = 10**9+7
dp, fib = [[0]*10 for i in range(h+1)], [1,1,2,3,5,8,13,21]
dp[0][1] = 1
if w == 1:
    print(1)
else:
    for i in range(1,h+1):
        for j in range(1, w+1):
            fromleft, fromabove, fromright = 0, 0, 0
            if j == 1: 
                fromabove = dp[i-1][j]*fib[w-1]
                fromright = dp[i-1][j+1]*fib[w-2]
            elif j == w: 
                fromleft = dp[i-1][j-1]*fib[w-2]
                fromabove = dp[i-1][j]*fib[w-1]
            else: 
                fromleft = dp[i-1][j-1]*fib[j-2]*fib[w-j]
                fromabove = dp[i-1][j]*fib[j-1]*fib[w-j]
                fromright = dp[i-1][j+1]*fib[j-1]*fib[w-j-1]
            dp[i][j] = (fromleft+fromabove+fromright)%MOD
            
    print(dp[h][k])

Solution (Python):



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

    if W == 1:
        print(1)
        return

    division = 1000000007
     
    amida = [[] for i in range(W+1)]
    amida[1] = ['0', '1']
    for x in range(2, W):
        for b in amida[x-1]:
            if b[-1] == '0':
                amida[x].append(b + '1')
            amida[x].append(b + '0')

    all_count = len(amida[W-1])
    bar = [0] * (W+1)
    for i in range(W-1):
        bar[i+1] = len(list(filter(lambda t:t[i] == '1', amida[W-1])))

    dp = [[0 for i in range(W+2)] for j in range(H+1)]
    dp[0][1] = 1
    for y in range(1,H+1):
        for x in range(1,W+1):
            dp[y][x] = dp[y-1][x-1] * bar[x-1] \
                     + dp[y-1][x+1] * bar[x] \
                     + dp[y-1][x] * (all_count - bar[x] - bar[x-1])

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

main()

Solution (Python):
h, w, k = map(int, input().split())
dp = [[0 for _ in range(w)] for _ in range(h+1)]
perm = [1, 2, 3, 5, 8, 13, 21, 34]
law = 1000000007
for row in range(h+1):
    for col in range(w):
        if row == 0:
            dp[row][col] = int(col == 0)
        else:
            if col > 0:
                dp[row][col] = (dp[row][col] + dp[row-1][col-1] * perm[max(0,col-2)] * perm[max(0, w-col-2)]) % law
            if col < w - 1:
                dp[row][col] = (dp[row][col] + dp[row-1][col+1] * perm[max(0,col-1)] * perm[max(0, w-col-3)]) % law
            dp[row][col] = (dp[row][col] + dp[row-1][col] * perm[max(0,col-1)] * perm[max(0,w-col-2)]) % law
print(dp[h][k-1])

Solution (Python):


import math
import sys
import heapq
from operator import itemgetter
import itertools
input = sys.stdin.readline












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


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


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

def get_patnum(i):
	if i <= 0:
		return 1
	else:
		return patnum[i]

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

		
		move_left = dp[i][j+1] * get_patnum(j-2) * get_patnum(W-j-2)

		
		move_right = dp[i][j-1] * get_patnum(j-3) * get_patnum(W-j-1)

		dp[i+1][j] = (move_down + move_left + move_right) % 1000000007
		
print(dp[H][K])

Solution (Python):
c = [1, 2, 3, 5, 8, 13, 21, 34, 55]

def count(n):
    if n < 0:
        return 1
    else:
        return c[n]
    
h, w, k = [int(i) for i in input().split(" ")]

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

def ul(i, j):
    if j == 0:
        return 0
    else:
        return count(j - 2) * count(w - j - 2) * p[i - 1][j - 1]

def uu(i, j):
    return count(j - 1) * count(w - j - 2) * p[i - 1][j]

def ur(i, j):
    if j == w - 1:
        return 0
    else:
        return count(j - 1) * count(w - j - 3) * p[i - 1][j + 1]

for i in range(1, h + 1):
    for j in range(0, w):
        p[i][j] = ul(i, j) + uu(i, j) + ur(i, j)
    
print(p[-1][k - 1] % 1000000007)

Solution (Python):
h,w,k=map(int,input().split())
DP=[[0 for i in range(w)] for j in range(h+1)]
DP[0][0]=1
mod=1000000007
for i in range(h):
    for j in range(w):
        for p in range(1<<w-1):
            flag=True
            for q in range(w-2):
                if (p>>q)&1==1 and (p>>q+1)&1==1:
                    flag=False
            if flag:
                if j>=1 and (p>>j-1)&1==1:
                    DP[i+1][j-1]+=DP[i][j]
                    DP[i+1][j-1]%=mod
                elif j<=w-2 and (p>>j)&1==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):
def f(n):
    memo = {}
    def compute(n):
        if n in memo:
            return memo[n]
        if n == 2:
            return 2
        if n <= 1:
            return 1
        ret = compute(n-1) + compute(n-2)
        memo[n] = ret
        return ret
    return compute(n)


memo = {}

def gen_patterns(c, h, w, k):
    if (c, h) in memo:
        return memo[(c,h)]
    elif h == 1:
        if c == k:
            return f(c-1) * f(w-c) % 1000000007
        elif c+1 == k:
            return f(c-1)* f(w-c-1) % 1000000007
        elif c-1 == k:
            return f(c-2)*f(w-c) % 1000000007
        else:
            return 0
    else:
        ret = 0
        ret += f(c-1) * f(w-c) * gen_patterns(c,h-1,w,k)
        ret = ret % 1000000007
        if c != 1:
            ret += f(c-2)*f(w-c)*gen_patterns(c-1,h-1,w,k)
            ret = ret % 1000000007
        if c != w:
            ret += f(c-1)*f(w-c-1)*gen_patterns(c+1,h-1,w,k)
            ret = ret % 1000000007
        memo[(c,h)] = ret
        return ret


def main():
    H, W, K = list(map(int, input().split(' ')))
    print(gen_patterns(1, H, W, K))



if __name__ == '__main__':
    main()

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


def pattern(n):
    if n < 1:
        return 1
    elif n == 1:
        return 2
    elif n == 2:
        return 3
    else:
        return pattern(n-2) + pattern(n-1)


def memorize(func):
    cache = {}

    def inner(*args):
        if args in cache:
            return cache[args]
        else:
            ret = func(*args)
            cache[args] = ret
            return ret

    return inner


@memorize
def count(h, W, K):
    if h == 0:
        if K == 1:
            return 1
        else:
            return 0
    ret = 0
    if 1 < K:
        ret += count(h-1, W, K-1) * pattern(K-3) * pattern(W-K-1)
    ret += count(h-1, W, K) * pattern(K-2) * pattern(W-K-1)
    if K < W:
        ret += count(h-1, W, K+1) * pattern(K-2) * pattern(W-K-2)
    return ret


print(count(H, W, K) % 1000000007)

Solution (Python):
f = [0,1,1,2,3,5,8,13,21,34,55,89]
h,w,k = map(int,input().split())
a = [0]*(w+2)
b = [0]*(w+2)
a[1] =     1
for i in range(h):
  for j in range(1,w+1):
    b[j] =(f[j-1]*f[w-j+1]*a[j-1] + f[j]*f[w-j+1]*a[j] + f[j]*f[w-j]*a[j+1])%1000000007
  for j in range(1,w+1):
    a[j] = b[j]   

    
    
print(a[k])

Solution (Python):
H, W, K = map(int, input().split())
K -= 1
fibbonacci = [1, 1]
for i in range(8):
    fibbonacci.append(fibbonacci[-1] + fibbonacci[-2])
dp = [[0] * W for i 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] * fibbonacci[j] * fibbonacci[W - j - 1]
        if j > 0:
            dp[i + 1][j - 1] += dp[i][j] * fibbonacci[j - 1] * fibbonacci[W - j - 1]
        if j < W - 1:
            dp[i + 1][j + 1] += dp[i][j] * fibbonacci[j] * fibbonacci[W - j - 2]
print(dp[H][K]%(10**9 + 7))

Solution (Python):
import sys

def fib(n):
  if n == 0:
    return 1
  elif n == 1:
    return 1
  else:
    return fib(n-1) + fib(n-2)

def main():
  input = sys.stdin.readline
  H, W, K = map(int, input().split())
  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):
      if (j-1) >= 0:
        X = fib(j-1) * fib(W-(j+1))
        DP[i+1][j-1] += X * DP[i][j]

      if (j+1) <= (W-1):
        Z = fib(j) * fib(W-(j+2))
        DP[i+1][j+1] += Z * DP[i][j]

      Y = fib(j) * fib(W-(j+1))
      DP[i+1][j] += Y * DP[i][j]

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


if __name__ == '__main__':
  main()

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

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

dp[0][1]=1

for i in range(h+1):
    for j in range(1,w+1):
        for l in range(2**(w-1)):
            p=bin(l)
            q=len(p)
            r=p.replace("11","")
            if q==len(r):
                r=p.replace("0b","")
                r="0"*(w-1-len(r))+r
                if j==1:
                    if r[0]=="0":
                        dp[i+1][j]+=dp[i][j]
                    else:
                        dp[i+1][j+1]+=dp[i][j]
                elif j==w:
                    if r[-1]=="0":
                        dp[i+1][j]+=dp[i][j]
                    else:
                        dp[i+1][j-1]+=dp[i][j]
                else:
                    if r[j-1]=="1":
                        dp[i+1][j+1]+=dp[i][j]
                    elif r[j-2]=="1":
                        dp[i+1][j-1]+=dp[i][j]
                    else:
                        dp[i+1][j]+=dp[i][j]
                   
print(dp[h][k]%1000000007)

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











patternSize=[1for _ in range(w+2)]
patternSize[1]=2
for i in range(2,w):
    patternSize[i]=patternSize[i-1]+patternSize[i-2]



a=[[0for _ in range(w)]for _ in range(h+1)]
a[0][0]=1
for i in range(1,h+1):
    for j in range(0,w):
        
        if j!=0:
            a[i][j-1]+=a[i-1][j]*patternSize[j-2]*patternSize[w-1-j-1]
        a[i][j]+=a[i-1][j]*patternSize[j-1]*patternSize[w-1-j-1]
        if j!=w-1:
            a[i][j+1]+=a[i-1][j]*patternSize[j-1]*patternSize[w-1-j-2]



print(a[h][k-1]%1000000007)

Solution (Python):
fib = [1,1,2,3,5,8,13,21,34]
mod = 1000000007
H,W,K = list(map(int,input().split()))

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

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

print(dp[-1][K])

Solution (Python):
MOD = 1000000000 + 7


class DP2D(object):

    def __init__(self, item_n: int, border: int, initializer: int = 0):
        self.item_n = item_n
        self.border = border
        self.table = [[initializer for _ in range(self.item_n + 1)] for _ in range(self.border + 1)]

    def __str__(self):
        return "\n".join(list(map(lambda l:
                                  " ".join(list(map(str, l)))
                                  , self.table)))

    def __repr__(self):
        return "DynamicProgramming object:\n" + \
               "item_n: " + str(self.item_n) + ", border: " + str(self.border) + "\n" + \
               "table:\n" + self.__str__()

    def solve(self, expr: callable) -> list:
        raise NotImplementedError

    def fill_0_idx_with(self, value: int) -> "DP2D":
        self.table[0] = [value for _ in range(self.item_n + 1)]
        for i in range(1, self.border + 1):
            self.table[i][0] = value
        return self


class BitDP2D(DP2D):
    def __init__(self, item_n: int, border: int, bit_n: int):
        super(BitDP2D, self).__init__(item_n, border)
        self.bit_n = bit_n

    def solve(self, expr: callable) -> list:
        for sbj_i in range(1, self.border+1):
            for bit in range(2 ** self.bit_n):

                for item_idx in range(1, self.item_n):
                    if (bit >> item_idx) & 1 and (bit >> (item_idx-1)) & 1:
                        break
                else:

                    for item_idx in range(1, self.item_n + 1):
                        if item_idx > 1 and (bit >> (item_idx-2)) & 1:  
                            self.table[sbj_i][item_idx] += self.table[sbj_i - 1][item_idx - 1]
                            self.table[sbj_i][item_idx] %= MOD
                        elif (bit >> (item_idx-1)) & 1:  
                            self.table[sbj_i][item_idx] += self.table[sbj_i - 1][item_idx + 1]
                            self.table[sbj_i][item_idx] %= MOD
                        else:  
                            self.table[sbj_i][item_idx] += self.table[sbj_i - 1][item_idx]
                            self.table[sbj_i][item_idx] %= MOD
        return self.table


if __name__ == '__main__':
    H, W, K = map(int, input().split())
    dp = BitDP2D(W, H, W-1)
    dp.table[0][1] = 1
    print(dp.solve(None)[H][K])

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

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

f = {} 
for x in range(w-1):
    if(x in [0,w-2]):
        f[x] = fib[w-2]
    else:
        f[x] = fib[x]*fib[w-x-2]

g = {} 
for x in range(w):
    if(x in [0,w-1]):
        g[x] = fib[w-1]
    else:
        g[x] = fib[x]*fib[w-x-1]


d = [[0 for _ in range(w)] for _ in range(h+1)]
d[0][0] = 1
for m in range(1,h+1):
    for n in range(w):
        d[m][n] = d[m-1][n]*g[n]
        if(n!=0):
            d[m][n] += d[m-1][n-1]*f[n-1]
        if(n!=w-1):
            d[m][n] += d[m-1][n+1]*f[n]
        d[m][n] %= 1000000007
print(d[h][k-1])

Solution (Python):
from functools import lru_cache

input_lst = list(map(int, input().split()))
h, w, k = input_lst[0], input_lst[1], input_lst[2]

def row_comb(w):
    if w < 0:
        return 0
    elif w <= 1:
        return 1
    elif w == 2:
        return 2
    else:
        return row_comb(w-2)+row_comb(w-1)

@lru_cache(maxsize=1000)
def trio(h,w):
    if h == 0:
        return [1] + [0 for i in range(10)]
    else:
        lst = []
        for i in range(1, w+1):
            if i == 1:
                lst.append(trio(h-1,w)[0] * row_comb(w-1) + trio(h-1,w)[1] * row_comb(w-2))
            elif i == w:
                lst.append(trio(h-1,w)[w-1] * row_comb(w-1) + trio(h-1,w)[w-2] * row_comb(w-2))
            elif i == 2:
                lst.append(trio(h-1,w)[0] * row_comb(w-2) + trio(h-1,w)[2] * row_comb(w-3) + trio(h-1,w)[1] * row_comb(w-2))
            elif i == w-1:
                lst.append(trio(h-1,w)[w-1] * row_comb(w-2) + trio(h-1,w)[w-3] * row_comb(w-3) + trio(h-1,w)[w-2] * row_comb(w-2))
            elif i > 2 and i < w-1:
                a = row_comb(i-2) * row_comb(w-i)
                b = row_comb(i-1) * row_comb(w-i-1)
                c = row_comb(i-1) * row_comb(w-i)
                lst.append(trio(h-1,w)[i-2] * a + trio(h-1,w)[i] * b + trio(h-1,w)[i-1] * c)
        lst = lst + [0 for i in range(10)]
        return lst
    
print(trio(h, w)[k-1] % 1000000007)

Solution (Python):
H,W,K = map(int,input().split())
if W == 1:
    print(1)
    exit()
def serch(yokobou=[[None]*(W-1)],depth=0):
    queue = []
    for arrange in yokobou:
        for b in [0,1]:
            if b == 0:
                copy = arrange[:]
                copy[depth] = 0
                queue.append(copy)
            elif b == 1:
                copy = arrange[:]
                if depth == 0:
                    copy[depth] = 1
                elif arrange[depth-1] != 1:
                    copy[depth] = 1
                else:
                    continue
                queue.append(copy)
    yokobou = queue[:]
    if depth == W-2:
        return yokobou
    return serch(yokobou,depth+1)

def possibility(j):
    X,Y,Z = 0,0,0
    for e in serch():
        if j == 0:
            if e[j] == 1:
                Z += 1
            elif e[j] == 0:
                Y += 1
            continue
        elif j == W-1:
            if e[j-1] == 1:
                X += 1
            elif e[j-1] == 0:
                Y += 1 
            continue
        if e[j-1] == 1:
            X += 1
        if e[j] == 1:
            Z += 1
        if e[j-1] == 0 and e[j] == 0:
            Y += 1
    return (X,Y,Z)

dp = [[0]*(W) for i in range(H+1)]
dp[0][0] = 1
for i in range(H):
    for j in range(W):
        (X,Y,Z) = possibility(j)
        if j != 0:
            dp[i+1][j] += X*dp[i][j-1]
        if j != W-1:
            dp[i+1][j] += Z*dp[i][j+1]
        dp[i+1][j] += Y*dp[i][j]

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