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):
'''
自宅用PCでの解答
'''
import math

import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

def main():
    h,w,k = map(int,ipt().split())
    nm = [1,1,2,3,5,8,13,21,34]
    dp = [0]*(w+2)
    dp[1] = 1
    for i in range(h):
        ndp = [0]*(w+2)
        for j in range(1,w+1):
            ndp[j] = dp[j]*nm[j-1]*nm[w-j]+dp[j-1]*nm[j-2]*nm[w-j]+dp[j+1]*nm[j-1]*nm[w-j-1]
            ndp[j] %= mod
        dp = ndp*1


    print(dp[k])


    return None

if __name__ == '__main__':
    main()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    H, W, K = map(int, input().split())
    K -= 1
    dp = [[0] * W for _ in range(H + 1)]
    dp[0][0] = 1
    for i in range(H):
        for j in range(W):
            for bit in range(1 << (W - 1)):
                flg = True
                for mask in range(W - 2):
                    if (bit & (1 << mask)) and (bit & (1 << (mask + 1))):
                        flg = False
                if flg:
                    next_j = j
                    if bit & (1 << j):
                        next_j = j + 1
                    elif j > 0 and (bit & (1 << (j - 1))):
                        next_j = j - 1
                    dp[i + 1][next_j] = (dp[i + 1][next_j] + dp[i][j]) % mod
    print(dp[H][K])


if __name__ == '__main__':
    resolve()

Solution (Python):
import sys
import math
import collections
import bisect
import copy



sys.setrecursionlimit(10 ** 7)
INF = 10 ** 16
MOD = 10 ** 9 + 7


ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))





def main():
    h, w, k = ns()
    dp = [[0 for _ in range(w)] for __ in range(h + 1)]
    dp[0][0] = 1
    fibo = [1, 2]
    for i in range(10):
        fibo.append(fibo[-1] + fibo[-2])

    for y in range(1, h + 1):
        for x in range(w):
            if x == 0:
                
                dp[y][x] += dp[y - 1][x] * fibo[max(0, w - 1 - 1)]
                if w > 1:
                    
                    dp[y][x] += dp[y - 1][x + 1] * fibo[max(0, w - 1 - 2)]
            elif x == w - 1:
                
                dp[y][x] += dp[y - 1][x] * fibo[max(0, w - 1 - 1)]
                if w > 1:
                    
                    dp[y][x] += dp[y - 1][x - 1] * fibo[max(0, w - 1 - 2)]
            else:
                
                dp[y][x] += dp[y - 1][x] * fibo[x - 1] * fibo[max(0, w - 1 - x - 1)]
                
                dp[y][x] += dp[y - 1][x - 1] * fibo[max(0, x - 1 - 1)] * fibo[max(0, w - 1 - x - 1)]
                
                dp[y][x] += dp[y - 1][x + 1] * fibo[x - 1] * fibo[max(0, w - 1 - x - 2)]
            dp[y][x] %= MOD

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


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import math
import collections
import bisect
import copy



sys.setrecursionlimit(10 ** 7)
INF = 10 ** 16
MOD = 10 ** 9 + 7


ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))





def main():
    h, w, k = ns()
    dp = [[0 for _ in range(w)] for __ in range(h + 1)]
    dp[0][0] = 1
    fibo = [1, 2]
    for i in range(10):
        fibo.append(fibo[-1] + fibo[-2])

    for y in range(1, h + 1):
        for x in range(w):
            if x == 0:
                
                dp[y][x] += dp[y - 1][x] * fibo[max(0, w - 1 - 1)]
                if w > 1:
                    
                    dp[y][x] += dp[y - 1][x + 1] * fibo[max(0, w - 1 - 2)]
            elif x == w - 1:
                
                dp[y][x] += dp[y - 1][x] * fibo[max(0, w - 1 - 1)]
                if w > 1:
                    
                    dp[y][x] += dp[y - 1][x - 1] * fibo[max(0, w - 1 - 2)]
            else:
                
                dp[y][x] += dp[y - 1][x] * fibo[x - 1] * fibo[max(0, w - 1 - x - 1)]
                
                dp[y][x] += dp[y - 1][x - 1] * fibo[max(0, x - 1 - 1)] * fibo[max(0, w - 1 - x - 1)]
                
                dp[y][x] += dp[y - 1][x + 1] * fibo[x - 1] * fibo[max(0, w - 1 - x - 2)]
            dp[y][x] %= MOD

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


if __name__ == '__main__':
    main()

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

WW = [0]*(W+1)
WW[0] = 1
WW[1] = 1
for i in range(2, W+1):
    WW[i] = WW[i-1] + WW[i-2]
DP = [[0]*W for i in range(H+1)]
DP[0][0] = 1
mod = 10**9+7
for i in range(1, H+1):
    for j in range(W):
        if j == 0:
            DP[i][j] = DP[i-1][j]*WW[W-1]
            if W > 1:
                DP[i][j] += DP[i-1][j+1]*WW[W-2]
        elif j == W-1:
            DP[i][j] = DP[i-1][j]*WW[W-1]
            if W > 1:
                DP[i][j] += DP[i-1][j-1]*WW[W-2]
        else:
            DP[i][j] = DP[i-1][j]*WW[j]*WW[W-1-j]+DP[i-1][j-1] * \
                WW[j-1]*WW[W-1-j]+DP[i-1][j+1]*WW[j]*WW[W-2-j]

        DP[i][j] %= mod

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

Solution (Python):
from itertools import combinations

H,W,K=map(int,input().split())
dp=[[0 for i in range(W)] for j in range(H+1)]

mod=10**9+7

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

memo={}
def is_separate(c):
  for i in range(len(c)-1):
    if c[i+1]-c[i] == 1:
      return False
  return True

def n_select(occupied):
  if memo.get(occupied):
    return memo[occupied]
  else:
    count=1
    if len(occupied)==1:
      for r in range(1,W//2+1):
        for c in combinations(range(W-1),r=r):
          if occupied[0]-1 not in c and occupied[0] not in c:
            if is_separate(c):
              count += 1
    if len(occupied)==2:
      for r in range(1,W//2+1):
        for c in combinations(range(W-1),r=r):
          if occupied[0]-1 not in c and occupied[0] not in c and occupied[0]+1 not in c:
            if is_separate(c):count += 1
  memo[occupied] = count
  return count

dp[0][0]=1
for i in range(1,H+1):
  for j in range(W):
    if j==0:
      dp[i][j] = dp[i-1][j]*n_select((j,))+dp[i-1][j+1]*n_select((j,j+1))
    elif j==W-1:
      dp[i][j] = dp[i-1][j]*n_select((j,))+dp[i-1][j-1]*n_select((j-1,j))
    else:
      dp[i][j] = dp[i-1][j]*n_select((j,))+dp[i-1][j+1]*n_select((j,j+1))+dp[i-1][j-1]*n_select((j-1,j))

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

Solution (Python):
def f(i):
  if i == W-1:
    for j in range(W-2):
      if s[j] == s[j+1] == 1:
        return
    global x
    for j in range(W):
      if j == 0:
        if s[0] == 1:
          x[0][1] += 1
        else:
          x[0][0] += 1
      elif j == W - 1:
        if s[W-2] == 1:
          x[W-1][W-2] += 1
        else:
          x[W-1][W-1] += 1
      else:
        if s[j-1] == 1:
          x[j][j-1] += 1
        elif s[j] == 1:
          x[j][j+1] += 1
        else:
          x[j][j] += 1 
    return
  s[i] = 1
  f(i + 1)
  s[i] = 0
  f(i + 1)

H,W,K=map(int, input().split())
MOD = pow(10, 9) + 7
s = [0] * (W - 1)
x = [[0] * W for _ in range(W)]
if not W == 1:
  f(0)
else:
  print(1)
  exit()
dp = [[0] * W for _ in range(H+1)]
dp[0][0] = 1
for i in range(1,H+1):
  for j in range(W):
    for l in range(W):
      dp[i][j]+=dp[i-1][l]*x[l][j]
      dp[i][j]%=MOD
print(dp[H][K-1])

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

goal = [0 for i in range(W)]
goal[0] = 1
oldGoal = [0 for i in range(W)]
oldGoal[0] = 1
fib = [1, 1, 2, 3, 5, 8, 13, 21, 34]

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

for i in range(H):
    for j in range(W):
        if j == 0:
            a1 = oldGoal[j] * fib[W-1]
            a2 = oldGoal[j+1] * fib[W-2]
            a1 = a1 % 1000000007
            a2 = a2 % 1000000007
            goal[j] = a1 + a2
        elif j == W - 1:
            a1 = oldGoal[j-1] * fib[W-2]
            a2 = oldGoal[j] * fib[W-1]
            a1 = a1 % 1000000007
            a2 = a2 % 1000000007
            goal[j] = a1 + a2
        else:
            a1 = oldGoal[j-1] * fib[j-1] * fib[W-j-1]
            a2 = oldGoal[j] * fib[j] * fib[W-j-1]
            a3 = oldGoal[j+1] * fib[j] * fib[W-j-2]
            a1 = a1 % 1000000007
            a2 = a2 % 1000000007
            a3 = a3 % 1000000007
            goal[j] = a1 + a2 + a3
    for k in range(W):
        oldGoal[k] = goal[k]
print(goal[K-1] % 1000000007)

Solution (Python):
H,W,K=map(int,input().split())
dp=[[0]*W for i in range(H+1)]
dp[0][0]=1
if W==1:
  print(1)
  exit()
  
import itertools
A=list(itertools.product([0,1], repeat=W-1))

B=[]
for i in A:
  x=0
  for j in range(W-2):
    if i[j]==1 and i[j+1]==1:
      x=1
  if x==0:
    B.append(i)

D=[[0,0,0] for i in range(W)]
for i in B:
  for j in range(W-1):
    if i[j]==1:
      D[j+1][0]+=1
      D[j][2]+=1
    if j==0 and i[j]==0:
      D[j][1]+=1
    if j==W-2 and i[j]==0:
      D[j+1][1]+=1
    if j<W-2:
      if i[j]==0 and i[j+1]==0:      
        D[j+1][1]+=1
dp=[[0]*W for i in range(H+1)]
mod=10**9+7
dp[0][0]=1
for i in range(H):
  for j in range(W):
    if j==0:
      dp[i+1][j]=dp[i][j]*D[j][1]+dp[i][j+1]*D[j][2]
    elif j==W-1:
      dp[i+1][j]=dp[i][j]*D[j][1]+dp[i][j-1]*D[j][0]
    else:
      dp[i+1][j]=dp[i][j]*D[j][1]+dp[i][j-1]*D[j][0]+dp[i][j+1]*D[j][2]
    dp[i+1][j]%=mod
print(dp[-1][K-1])

Solution (Python):
H,W,K=map(int,input().split())
dp=[[0]*W for i in range(H+1)]
dp[0][0]=1
if W==1:
  print(1)
  exit()
  
import itertools
A=list(itertools.product([0,1], repeat=W-1))

B=[]
for i in A:
  x=0
  for j in range(W-2):
    if i[j]==1 and i[j+1]==1:
      x=1
  if x==0:
    B.append(i)

D=[[0,0,0] for i in range(W)]
for i in B:
  for j in range(W-1):
    if i[j]==1:
      D[j+1][0]+=1
      D[j][2]+=1
    if j==0 and i[j]==0:
      D[j][1]+=1
    if j==W-2 and i[j]==0:
      D[j+1][1]+=1
    if j<W-2:
      if i[j]==0 and i[j+1]==0:      
        D[j+1][1]+=1
dp=[[0]*W for i in range(H+1)]
mod=10**9+7
dp[0][0]=1
for i in range(H):
  for j in range(W):
    if j==0:
      dp[i+1][j]=dp[i][j]*D[j][1]+dp[i][j+1]*D[j][2]
    elif j==W-1:
      dp[i+1][j]=dp[i][j]*D[j][1]+dp[i][j-1]*D[j][0]
    else:
      dp[i+1][j]=dp[i][j]*D[j][1]+dp[i][j-1]*D[j][0]+dp[i][j+1]*D[j][2]
    dp[i+1][j]%=mod
print(dp[-1][K-1])

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

def poss_of_ok_spaces(idx,straight):
    if straight:
        ok_spaces_l = max(idx - 1 - 1, 0)
        ok_spaces_r = max(w - idx - 1, 0)
        return sum(dp[ok_spaces_l])%MOD * sum(dp[ok_spaces_r])%MOD
    else:
        
        ok_spaces_l = max(idx - 1 - 2, 0)
        ok_spaces_r = max(w - idx - 1, 0)
        return sum(dp[ok_spaces_l])%MOD * sum(dp[ok_spaces_r])%MOD

def rc(n,idx):
    if memo[n][idx] != 0:
        return memo[n][idx]
    if n == 1:
        if idx == k:
            return poss_of_ok_spaces(idx,True)%MOD
        elif k == idx + 1:
            return poss_of_ok_spaces(k,False)%MOD
        elif k == idx - 1:
            return poss_of_ok_spaces(idx,False)%MOD
        else:
            return 0
    ret = rc(n-1,idx)%MOD*poss_of_ok_spaces(idx,True)%MOD
    if idx + 1 <= w:
        ret += rc(n-1,idx+1)%MOD*poss_of_ok_spaces(idx+1,False)%MOD
    if idx - 1 >= 1:
        ret += rc(n-1,idx-1)%MOD*poss_of_ok_spaces(idx,False)%MOD
    ret %= MOD
    memo[n][idx] = ret
    return ret
print(rc(h,1))

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

dp=[[0]*(h+2) for _ in range(w+2)]
comb=[1]*(w+5)
comb[2]=2
for i in range(3,w+1):
    for j in range(1,i):
        comb[i]+=comb[i-j-1]

dp[1][0]=1


mod=10**9+7

for hh in range(1,h+1):
    for ww in range(1,w+1):
        dp[ww][hh]+=comb[ww-1]*comb[w-ww]*dp[ww][hh-1]
        dp[ww][hh]+=comb[ww-2]*comb[w-ww]*dp[ww-1][hh-1]
        dp[ww][hh]+=comb[ww-1]*comb[w-ww-1]*dp[ww+1][hh-1]
        dp[ww][hh]%=mod

print(dp[k][h])

Solution (Python):
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    H, W, K = NMI()
    dp = make_grid(H+1, W, 0)
    move = make_grid(W, W, 0)

    dp[0][0] = 1

    for case in range(2**(W-1)):
        bad_case = False
        prev_bit = -1
        for i in range(W-1):
            now_bit = (case >> i) & 1
            if now_bit == prev_bit == 1:
                bad_case = True
            prev_bit = now_bit
        if bad_case:
            continue

        for b in range(W):

            if b == 0:
                if (case >> 0) & 1:
                    move[0][1] += 1
                else:
                    move[0][0] += 1

            elif b == W - 1:
                if (case >> b - 1) & 1:
                    move[b][b - 1] += 1
                else:
                    move[b][b] += 1

            else:
                if (case >> b - 1) & 1:
                    move[b][b - 1] += 1
                elif (case >> b) & 1:
                    move[b][b + 1] += 1
                else:
                    move[b][b] += 1

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

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


if __name__ == "__main__":
    main()

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

H, W, K = MAP()

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

for i in range(H):
    for j in range(W):
        for S in range(1<<(W-1)):
            for k in range(W-2):
                if (S>>k)&1==1 and (S>>(k+1))&1==1:
                    break
            else:
                if j >= 1 and (S>>(j-1))&1:
                    dp[i+1][j-1] += dp[i][j]
                    dp[i+1][j-1] %= mod
                elif j <= W-2 and (S>>j)&1:
                    dp[i+1][j+1] += dp[i][j]
                    dp[i+1][j+1] %= mod
                else:
                    dp[i+1][j] += dp[i][j]
                    dp[i+1][j] %= mod

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

Solution (Python):
H, W, K = map(int, input().split())
dp = [[0]*(W+2) for _ in range(H+1)]
dp[0][1] = 1
mod = 10**9+7
for i in range(H):
    for j in range(1, W+1):
        t_1 = 0
        t_2 = 0
        t_3 = 0
        for k in range(2**(W-1)):
            s = format(k, "b")
            p = 0
            if len(s) != W-1:
                s = "0"*(W-1-len(s)) + s
            for l in range(1, len(s)):
                if s[l-1] == "1" and s[l] == "1":
                    p = 1
                    break
            q = 0
            if p == 0:
                if 0 <= j - 2 < len(s):
                    if s[j-2] == "1":
                        t_1 += 1
                        q = 1
                if j-1 < len(s):
                    if s[j-1] == "1":
                        t_3 += 1
                        q = 1
                if q == 0:
                    t_2 += 1
        dp[i+1][j-1] += dp[i][j]*t_1
        dp[i+1][j] += dp[i][j]*t_2
        dp[i+1][j+1] += dp[i][j]*t_3
        dp[i+1][j-1] %= mod
        dp[i+1][j] %= mod
        dp[i+1][j+1] %= mod

print(dp[H][K])

Solution (Python):
def f(i):
    if i == w - 1:
        for j in range(w - 2):
            if s[j] == s[j + 1] == 1:
                return
        global x
        for j in range(w):
            if j == 0:
                if s[0] == 1:
                    x[0][1] += 1
                else:
                    x[0][0] += 1
            elif j == w - 1:
                if s[w - 2] == 1:
                    x[w - 1][w - 2] += 1
                else:
                    x[w - 1][w - 1] += 1
            else:
                if s[j - 1] == 1:
                    x[j][j - 1] += 1
                elif s[j] == 1:
                    x[j][j + 1] += 1
                else:
                    x[j][j] += 1 
        return
    s[i] = 1
    f(i + 1)
    s[i] = 0
    f(i + 1)

h, w, k = map(int, input().split())
mod = pow(10, 9) + 7
s = [0] * (w - 1)
x = [[0] * w for _ in range(w)]
if not w == 1:
    f(0)
else:
    print(1)
    exit()
dp = [[0] * w for _ in range(h + 1)]
dp[0][0] = 1
for i in range(1, h + 1):
    for j in range(w):
        for l in range(w):
            dp[i][j] += dp[i - 1][l] * x[l][j]
            dp[i][j] %= mod
print(dp[h][k - 1])

Solution (Python):


import math

import itertools
from collections import deque
from collections import Counter




Mod=10**9+7
h,w,K=map(int,input().split())
dp=[[0]*w for _ in range(h+1)]
dp[0][0]=1
n=2**(w-1)
for i in range(h):
    for j in range(w):
        for m in range(n):
            ok=True
            for k in range(w-2):
                if (m&(1<<k)) and (m&(1<<(k+1))):
                    ok=False
            if not ok:
                continue
            nj=j
            if (m & (1<<j)):
                nj=j+1
            elif j>0 and (m&(1<<(j-1))):
                nj=j-1
            dp[i+1][nj]+=dp[i][j]
            dp[i+1][nj]%=Mod
print(dp[h][K-1])

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7






H, W, K = getNM()

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


bridge_right = [0] * W
bridge_left = [0] * W
not_bridge = [0] * W

for bit in range(1 << (W - 1)):
    flag = True
    for i in range(1, (W - 1)):
        if bit & (1 << i) and bit & (1 << (i - 1)):
            flag = False
    if flag:
        for i in range(W):
            if i == 0:
                if bit & (1 << i):
                    bridge_right[i] += 1
                else:
                    not_bridge[i] += 1
            elif i == W - 1:
                if bit & (1 << (i - 1)):
                    bridge_left[i] += 1
                else:
                    not_bridge[i] += 1
            else:
                if bit & (1 << i):
                    bridge_right[i] += 1
                elif bit & (1 << (i - 1)):
                    bridge_left[i] += 1
                else:
                    not_bridge[i] += 1

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

dp[0][0] = 1
for i in range(1, W):
    dp[0][i] = 0


for i in range(1, H + 1):
    for j in range(W):
        dp[i][j] += dp[i - 1][j] * not_bridge[j]
        if j == 0:
            dp[i][j + 1] += dp[i - 1][j] * bridge_right[j]
        elif j == W - 1:
            dp[i][j - 1] += dp[i - 1][j] * bridge_left[j]
        else:
            dp[i][j + 1] += dp[i - 1][j] * bridge_right[j]
            dp[i][j - 1] += dp[i - 1][j] * bridge_left[j]

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

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

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

dp = [[0]*w for _ in range(h+1)]
dp[0][0] = 1
for i in range(1, h+1):
    for p in range(2**(w-1)):
        L = [0]*(w-1)
        for q in range(w-1):
            if (p >> q) & 1:
                L[q] = 1
        flag = True
        for q in range(w-2):
            if L[q] == 1 and L[q+1] == 1:
                flag = False
        if not flag:
            continue
        for j in range(w):
            if j == 0:
                if L[j] == 1:
                    dp[i][j] += dp[i-1][1]
                else:
                    dp[i][j] += dp[i-1][0]
            elif j == w-1:
                if L[j-1] == 1:
                    dp[i][j] += dp[i-1][w-2]
                else:
                    dp[i][j] += dp[i-1][w-1]
            else:
                if L[j-1] == 1:
                    dp[i][j] += dp[i-1][j-1]
                elif L[j] == 1:
                    dp[i][j] += dp[i-1][j+1]
                else:
                    dp[i][j] += dp[i-1][j]
            dp[i][j] %= mod


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

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

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

dp = [[0]*w for _ in range(h+1)]
dp[0][0] = 1
for i in range(1, h+1):
    for p in range(2**(w-1)):
        L = [0]*(w-1)
        for q in range(w-1):
            if (p >> q) & 1:
                L[q] = 1
        flag = True
        for q in range(w-2):
            if L[q] == 1 and L[q+1] == 1:
                flag = False
        if not flag:
            continue
        for j in range(w):
            if j == 0:
                if L[j] == 1:
                    dp[i][j] += dp[i-1][1]
                else:
                    dp[i][j] += dp[i-1][0]
            elif j == w-1:
                if L[j-1] == 1:
                    dp[i][j] += dp[i-1][w-2]
                else:
                    dp[i][j] += dp[i-1][w-1]
            else:
                if L[j-1] == 1:
                    dp[i][j] += dp[i-1][j-1]
                elif L[j] == 1:
                    dp[i][j] += dp[i-1][j+1]
                else:
                    dp[i][j] += dp[i-1][j]
            dp[i][j] %= mod


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

Solution (Python):


import itertools
mod = 1000000007

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

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

dp[0][0] = 1

for h_ in range(1, h+1):
    for bridges in itertools.product([0, 1], repeat=w-1):
        flag = 0
        for j in range(len(bridges)-1):
            if bridges[j] == 1 and bridges[j+1] == 1:
                flag = 1
                continue
        if flag == 1:
            continue
        
        for w_ in range(w):
            if w_ > 0:
                if bridges[w_-1] == 1:
                    dp[h_][w_] += dp[h_-1][w_-1] % mod
                    continue
            if w_ < w-1:
                if bridges[w_] == 1:
                    dp[h_][w_] += dp[h_-1][w_+1] % mod
                    continue
            dp[h_][w_] += dp[h_-1][w_] % mod



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

Solution (Python):
h,w,k_=map(int,input().split())
mod=pow(10,9)+7
if w==1:
  print(1)
  exit()

sen=[[0]*3 for _ in range(w)]
for j in range(2**(w-1)):
  yoko=[0]*(w-1)
  for k in range(w-1):
    if (j>>k) & 1:
      yoko[k]=1
  flg=True
  for k in range(w-2):
    if yoko[k]==1 and yoko[k+1]==1:
      flg=False
      break
  if not flg:continue
  for k in range(w):
    if k==0:
      if yoko[k]==1:
        sen[k+1][0]+=1
      else:
        sen[k][2]+=1
    elif k<w-1:
      if yoko[k]==1:
        sen[k+1][0]+=1
      elif yoko[k-1]==1:
        sen[k-1][1]+=1
      else:
        sen[k][2]+=1
    else:
      if yoko[k-1]==1:
        sen[k-1][1]+=1
      else:
        sen[k][2]+=1

import numpy as np 
dp=np.zeros((h+1,w),int)
dp[0,0]=1
for i in range(h):
  dp[i+1,0]=sen[0][2]*dp[i,0]+sen[0][1]*dp[i,1]
  for j in range(1,w-1):
    dp[i+1,j]=sen[j][2]*dp[i,j]+sen[j][1]*dp[i,j+1]+sen[j][0]*dp[i,j-1]
  dp[i+1,w-1]=sen[w-1][2]*dp[i,w-1]+sen[w-1][0]*dp[i,w-2]
  dp[i+1]%=mod
print(dp[h,k_-1])

Solution (Python):


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

h,w,k=MI()
dp=[[0]*w for i in range(h+1)]
dp[0][0]=1
a=0
b=1
weight=[]
for i in range(100):
    weight.append(a+b)
    a,b=b,a+b

for i in range(h):
    for j in range(w):
        if 0<=j+1<w:
            left=max(j-1,0)
            right=max(w-j-3,0)
            dp[i+1][j+1]+=(dp[i][j]*weight[left]*weight[right])%mod
        if 0<=j<w:
            left=max(j-1,0)
            right=max(w-j-2,0)
            dp[i+1][j]+=(dp[i][j]*weight[left]*weight[right])%mod
        if 0<=j-1<w:
            left=max(j-2,0)
            right=max(w-j-2,0)
            dp[i+1][j-1]+=(dp[i][j]*weight[left]*weight[right])%mod
print(dp[-1][k-1]%mod)

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

def isvalid(bit):
    for t in range(W-2):
        if (bit>>t&1) and (bit>>(t+1)&1):
            return False
    return True

H,W,K=map(int,input().split())
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):
        l,c,r=0,0,0
        for bit in range(2**(W-1)):
            if not isvalid(bit):
                continue
            if ((k>0 and not(bit>>(k-1)&1)) or k==0) and ((k<W-1 and not(bit>>k&1))or k==W-1):
                c+=1
            if (k>0) and (bit>>(k-1)&1):
                l+=1
            if (k<W-1) and (bit>>k&1):
                r+=1
        dp[i][k]=(dp[i][k]+dp[i-1][k]*c)%MOD
        if k>0:
            dp[i][k]=(dp[i][k]+dp[i-1][k-1]*l)%MOD
        if k<W-1:
            dp[i][k]=(dp[i][k]+dp[i-1][k+1]*r)%MOD
print(dp[H][K-1])

Solution (Python):
MOD=10**9+7
H,W,K=map(int,input().split())
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):
        l,c,r=0,0,0
        for bit in range(2**(W-1)):
            ok=True
            for t in range(W-2):
                if (bit>>t&1) and (bit>>(t+1)&1):
                    ok=False
                    break
            if not ok:
                continue
            if ((k>0 and not(bit>>(k-1)&1)) or k==0) and ((k<W-1 and not(bit>>k&1))or k==W-1):
                c+=1
            if (k>0):
                if ((k>1 and not(bit>>(k-2)&1)) or k==1) and ((k<W-1 and not(bit>>k&1))or k==W-1) and (bit>>(k-1)&1):
                    l+=1
            if (k<W-1):
                if ((k>0 and not(bit>>(k-1)&1)) or k==0) and ((k<W-2 and not (bit>>(k+1)&1))or k==W-2) and (bit>>k&1):
                    r+=1
        dp[i][k]=(dp[i][k]+dp[i-1][k]*c)%MOD
        if k>0:
            dp[i][k]=(dp[i][k]+dp[i-1][k-1]*l)%MOD
        if k<W-1:
            dp[i][k]=(dp[i][k]+dp[i-1][k+1]*r)%MOD
print(dp[H][K-1])

Solution (Python):
h,w,K = map(int,input().split())
if w == 1:
    print(1)
    exit()
K -= 1
mod = 1000000007
dp = [[0]*(w) for _ in range(h+1)]
for i in range(w): dp[0][0] = 1

for i in range(h):
    for j in range(1<<(w-1)):
        invalid = False
        for k in range(w-1):
            if j>>k & 1 and j>>(k+1) & 1:
                invalid = True
                break
        if invalid: continue
        used = [False]*w
        for k in range(w):
            if used[k]: continue
            if j>>k & 1:
                dp[i+1][k] = (dp[i+1][k]+dp[i][k+1])%mod
                dp[i+1][k+1] = (dp[i+1][k+1]+dp[i][k])%mod
                used[k] = True
                used[k+1] = True
            else:
                dp[i+1][k] = (dp[i+1][k]+dp[i][k])%mod
                used[k] = True

print(dp[h][K])

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