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):
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:
                    X+=1
                elif w<=W-2 and j>>w&1==1:
                    Z+=1
                else:
                    Y+=1
            else:
                continue

        if w-1>=0: dp[i][w-1]=(dp[i][w-1]+dp[i-1][w]*X)%P
        dp[i][w]=(dp[i][w]+dp[i-1][w]*Y)%P
        if w+1<=W-1: dp[i][w+1]=(dp[i][w+1]+dp[i-1][w]*Z)%P

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

Solution (Python):

import sys
import functools
INF = float("inf")

MOD = 1000000007  


@functools.lru_cache(maxsize=None)
def f(x):
    if x <= 0:
        return 1
    elif x == 1:
        return 2
    else:
        return f(x-1) + f(x-2)


def solve(H: int, W: int, K: int):

    dp = [0]*(W+2)
    dp[1] = 1                   
    for h in range(H):
        buf = [0]*(W+2)
        for i in range(1, W+1):
            
            buf[i] += dp[i-1]*f(i-3)*f(W-i-1)
            buf[i] %= MOD
            
            buf[i] += dp[i]*f(i-2)*f(W-i-1)
            buf[i] %= MOD
            
            buf[i] += dp[i+1]*f(i-2)*f(W-i-2)
            buf[i] %= MOD
        for i in range(1, W+1):
            dp[i] = buf[i]
    print(dp[K])

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  
    W = int(next(tokens))  
    K = int(next(tokens))  
    solve(H, W, K)


if __name__ == '__main__':
    main()

Solution (Python):
h,w,k = map(int, input().split())
memo = [[0]*w for i in range(h+1)]
for i in range(0, w):
    memo[0][i] = 0
memo[0][0] = 1

for i in range(1, h+1):
    for j in range(0, 1 << (w-1)):
        skip = False
        for l in range(w-2):
            skip = skip or ((j >> l) & 1 and (j >> (l+1)) & 1)
        if not skip:
            for l in range(w):
                if l-1 >= 0 and (j >> (l-1)) & 1:
                    memo[i][l] += memo[i-1][l-1]
                elif l+1 < w and (j >> l) & 1:
                    memo[i][l] += memo[i-1][l+1]
                else:
                    memo[i][l] += memo[i-1][l]
                memo[i][l] = memo[i][l] % 1000000007

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

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

memo = [[0]*w for i in range(h+1)]
for i in range(0, w):
    memo[0][i] = 0
memo[0][0] = 1



for i in range(1, h+1):
    for j in range(0, 1 << (w-1)):
        skip = False
        for l in range(w-2):
            skip = skip or ((j >> l) & 1 and (j >> (l+1)) & 1)
        
        if not skip:
            for l in range(w):
                if l-1 >= 0 and (j >> (l-1)) & 1:
                    memo[i][l] += memo[i-1][l-1]
                elif l+1 < w and (j >> l) & 1:
                    memo[i][l] += memo[i-1][l+1]
                else:
                    memo[i][l] += memo[i-1][l]
                memo[i][l] = memo[i][l] % 1000000007


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

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

r = 10**9 + 7

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

dp[0][0]=1

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

if W!=1:
    for i in range(H):
        for j in range(W):
            if j==0:
                dp[i+1][j]=(num[W-1]*dp[i][j]+num[W-2]*dp[i][j+1])%r
            elif j==W-1:
                dp[i+1][j]=(num[W-1]*dp[i][j]+num[W-2]*dp[i][j-1])%r
            else:
                dp[i+1][j]=(num[j]*num[W-j-1]*dp[i][j]+num[j-1]*num[W-j-1]*dp[i][j-1]+num[j]*num[W-j-2]*dp[i][j+1])%r
    print(dp[H][K-1])
else:
    print(1)

Solution (Python):
h, w, k = map(int, input().split())
M = 1000000007
x = [ 0 for i in range(w)]
x[0] = 1
for i in range(1, w):
    for j in range((1<<i)):
        f = 0
        for l in range(i-1):
            if ((j>>l)&1) == 1 and ((j>>(l+1))&1) == 1:
                f = 1
                break
        if f == 0:
            x[i] += 1
    x[i] %= M
    

def g(a):
    if a < 0: return 1
    return x[a]

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]   * g(j-1) * g(w-j-2)
        if j-1 >= 0:dp[i][j] += dp[i-1][j-1] * g(j-2) * g(w-j-2)
        if j+1 <  w:dp[i][j] += dp[i-1][j+1] * g(j-1) * g(w-j-3)
        dp[i][j] %= M
        

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

Solution (Python):
from itertools import product
H,W,K = list(map(int, input().split()))
mod=int(1e9+7)

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


from itertools import product
def one_row(W):
    one_row_amida={i:{i:0 for i in range(W)} for i in range(W)}

    for p in product([0,1], repeat=W-1):
        if any([p[i]==1 and p[i+1]==1 for i in range(W-2)]):
            continue
        after = [i for i in range(W)]
        for i in range(W-1):
            if p[i]:
                after[i], after[i+1] = after[i+1], after[i]
        for i, a in enumerate(after):
            one_row_amida[i][a] += 1
    return one_row_amida

one_row_amida = one_row(W)

for h in range(H):
    for w in range(W):
        for j in range(W):
            memo[h+1][j] += memo[h][w] * one_row_amida[w][j]
    memo[h+1] = [x%mod for x in memo[h+1]]

answer = memo[H][K-1]

print(answer)

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

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

dp[0][0] = 1


for h in range(H):
    for x in range(W):
        for b in range(2**(W-1)):
            if not '11' in bin(b):
                if x >= 1 and (b>>(x-1)) & 1:
                    dp[h+1][x-1] += dp[h][x]
                    dp[h+1][x-1] %= MOD
                elif x <= W-2 and (b>>x) & 1:
                    dp[h+1][x+1] += dp[h][x]
                    dp[h+1][x+1] %= MOD
                else:
                    dp[h+1][x] += dp[h][x]
                    dp[h+1][x] %= MOD

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

Solution (Python):
from itertools import product

mod = 1000000007
H, W, K = map(int, input().split())
dp = {}
dp[0] = [1] + [0]*(W-1)

for h in range(1, H+1):
    dp[h] = [0] * W
    for pattern in product([0, 1], repeat=W-1):
        c = 0
        for p in pattern:            
            c = ((c + 1) if p == 1 else 0)
            if c >= 2:
                break            
        if c >= 2:
            continue
        for i in range(0, W):
            if i <= W-2 and pattern[i] == 1:
                dp[h][i] = (dp[h][i] + dp[h-1][i+1]) % mod
            elif i >= 1 and pattern[i-1] == 1:
                dp[h][i] = (dp[h][i] + dp[h-1][i-1]) % mod
            else:
                dp[h][i] = (dp[h][i] + dp[h-1][i]) % mod
print(dp[H][K-1])

Solution (Python):
def way(h, w, k):
    if w == 1:
        return 1
    if [h, k] == [1, 1] or [h, k] == [1, 2]:
        return fibo[w - k]
    if h == 1:
        return 0
    if memo[h][k] != -1:
        return memo[h][k]
    re = way(h - 1, w, k) * fibo[k - 1] * fibo[w - k]
    if k != 1:
        re += way(h - 1, w, k - 1) * fibo[max(k - 2, 0)] * fibo[w - k]
    if k != w:
        re += way(h - 1, w, k + 1) * fibo[k - 1] * fibo[max(w - k - 1, 0)]
    memo[h][k] = re
    return re

h, w, k = map(int, input().split())
fibo = [1, 1]
for i in range(2, w):
    fibo += [fibo[i - 1] + fibo[i - 2]]
memo = [[-1] * (w + 1) for _ in range(h + 1)]

print(way(h, w, k) % 1000000007)

Solution (Python):

import sys

MOD = 1000000007  

def solve(H: int, W: int, K: int):
    comb_ = [[] for _ in range(W)]
    comb_[0] = [0, 1] 
    for i in range(1, W):
        comb_[i] = [comb_[i - 1][1], sum(comb_[i - 1])]
    comb = []
    for c in comb_:
        comb.append(c[0] + c[1])
    
    
    dp = [[[0] * 2 for i in range(W)] for _ in range(H + 1)]
    dp[0][0][1] = 1
    for h in range(1, H + 1):
        for w in range(W):
            dp[h][w][0] = dp[h - 1][w][1]
        
        for w in range(W):
            dp[h][w][1] += dp[h][w][0] * comb[max(0, w - 1)] * comb[max(0, W - w - 2)]
            if w > 0:
                dp[h][w][1] += dp[h][w - 1][0] * comb[max(0, w - 2)] * comb[max(0, W - w - 2)]
            if w < W - 1:
                dp[h][w][1] += dp[h][w + 1][0] * comb[max(0, w - 1)] * comb[max(0, W - w - 3)]
    
    ret = dp[H][K - 1][1] % MOD
    print(ret)
    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

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

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

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

for i in range(1,H+1):
    a[i][0] = a[i-1][0]*dic[W-2] + a[i-1][1]*dic[W-3]
    for j in range(1,W-1):
        a[i][j]=a[i-1][j-1]*dic[j-2]*dic[W-j-2] + a[i-1][j]*dic[j-1]*dic[W-j-2] + a[i-1][j+1]*dic[j-1]*dic[W-j-3]
    a[i][W-1] = a[i-1][W-1]*dic[W-2] + a[i-1][W-2]*dic[W-3]


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

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
from functools import partial, reduce
from operator import mul
prod = partial(reduce, mul)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

fibo = [1, 1]
for i in range(2, 9):
    fibo.append(fibo[i - 1] + fibo[i - 2])

def main():
    H, W, K = LI()
    K -= 1
    dp = [0] * W
    dp[0] = 1
    for _ in range(H):
        pre = dp
        dp = [0] * W
        for w in range(W):
            
            cnt = fibo[max(0, w - 0)] * fibo[max(0, W - w - 1)]
            dp[w] += pre[w] * cnt
            dp[w] %= MOD
            
            cnt = fibo[max(0, w - 1)] * fibo[max(0, W - w - 1)]
            if w - 1 >= 0:
                dp[w - 1] += pre[w] * cnt
                dp[w - 1] %= MOD
            
            cnt = fibo[max(0, w - 0)] * fibo[max(0, W - w - 2)]
            if w + 1 < W:
                dp[w + 1] += pre[w] * cnt
                dp[w + 1] %= MOD
    ans = dp[K]
    return ans

print(main())

Solution (Python):
def valid(x):
    even_mask = 85  
    odd_mask = 170  
    return (x & odd_mask) >> 1 & (x & even_mask) == 0 and (x & odd_mask) << 1 & (x & even_mask) == 0

def yoko(x):
    a, b, c = 0, 0, 0
    for bit in range(1<<(W-1)):
        if not valid(bit):
            continue
        if bit >> (W - x - 1) & 1:
            a += 1
        elif W - x - 2 >= 0 and bit >> (W - x - 2) & 1:
            c += 1
        else:
            b += 1
    return a, b, c

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

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

for i in range(H):
    for j in range(W):
        a, b, c = yoko(j)
        if j - 1 >= 0:
            dp[i+1][j-1] += a * dp[i][j]
            dp[i+1][j-1] %= BIG
        dp[i+1][j] += b * dp[i][j]
        dp[i+1][j] %= BIG
        if j + 1 < W:
            dp[i+1][j+1] += c * dp[i][j]
            dp[i+1][j+1] %= BIG
print(dp[H][K-1])

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007


def A():
    return


def B():
    return


def C():
    n,m = LI()
    v = LIR(m)
    for i in range(m):
        v[i] = [v[i][0],v[i][1],i]
    v.sort(key = lambda x:x[1])
    f = [0 for i in range(n+1)]
    ans = [None for i in range(m)]
    for p,y,i in v:
        f[p] += 1
        s = "{:0>6}".format(p)
        t = "{:0>6}".format(f[p])
        ans[i] = s+t
    for i in ans:
        print(i)

def D():
    h,w,k = LI()
    dp = [[0 for i in range(w)] for j in range(h+1)]
    dp[0][0] = 1
    p = [1 for i in range(w+1)]
    for i in range(w):
        p[i+1] = p[i]*2
    l = [i for i in range(p[w-1])]
    i = 0
    while i < len(l):
        a = l[i]
        for j in range(w):
            if a&p[j] and a&p[j+1]:
                l.pop(i)
                i -= 1
                break
        i += 1
    d = [[0 for i in range(3)] for j in range(w)]
    for j in range(w):
        for s in l:
            if 0 < j < w-1:
                if p[j]&s:
                    d[j][2] += 1
                elif p[j-1]&s:
                    d[j][0] += 1
                else:
                    d[j][1] += 1
            elif j == 0:
                if p[j]&s:
                    d[j][2] += 1
                else:
                    d[j][1] += 1
            else:
                if p[j-1]&s:
                    d[j][0] += 1
                else:
                    d[j][1] += 1
    for i in range(h):
        for j in range(w):
            dp[i+1][j] += d[j][1]*dp[i][j]
            dp[i+1][j] %= mod
            if j > 0:
                dp[i+1][j-1] += d[j][0]*dp[i][j]
                dp[i+1][j-1] %= mod
            if j < w-1:
                dp[i+1][j+1] += d[j][2]*dp[i][j]
                dp[i+1][j+1] %= mod
    print(dp[h][k-1])

def E():
    return


def F():
    return


def G():
    return


def H():
    return


if __name__ == "__main__":
    D()

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007


def A():
    return


def B():
    return


def C():
    n,m = LI()
    v = LIR(m)
    for i in range(m):
        v[i] = [v[i][0],v[i][1],i]
    v.sort(key = lambda x:x[1])
    f = [0 for i in range(n+1)]
    ans = [None for i in range(m)]
    for p,y,i in v:
        f[p] += 1
        s = "{:0>6}".format(p)
        t = "{:0>6}".format(f[p])
        ans[i] = s+t
    for i in ans:
        print(i)

def D():
    h,w,k = LI()
    dp = [[0 for i in range(w)] for j in range(h+1)]
    dp[0][0] = 1
    p = [1 for i in range(w+1)]
    for i in range(w):
        p[i+1] = p[i]*2
    l = [i for i in range(p[w-1])]
    i = 0
    while i < len(l):
        a = l[i]
        for j in range(w):
            if a&p[j] and a&p[j+1]:
                l.pop(i)
                i -= 1
                break
        i += 1
    for i in range(h):
        for j in range(w):
            a = 0
            b = 0
            c = 0
            for s in l:
                if 0 < j < w-1:
                    if p[j]&s:
                        c += 1
                    elif p[j-1]&s:
                        a += 1
                    else:
                        b += 1
                elif j == 0:
                    if p[j]&s:
                        c += 1
                    else:
                        b += 1
                else:
                    if p[j-1]&s:
                        a += 1
                    else:
                        b += 1
            dp[i+1][j] += b*dp[i][j]
            dp[i+1][j] %= mod
            if j > 0:
                dp[i+1][j-1] += a*dp[i][j]
                dp[i+1][j-1] %= mod
            if j < w-1:
                dp[i+1][j+1] += c*dp[i][j]
                dp[i+1][j+1] %= mod
    print(dp[h][k-1])

def E():
    return


def F():
    return


def G():
    return


def H():
    return


if __name__ == "__main__":
    D()

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


def transition(w):
    X = [1, 2, 3, 5, 8, 13, 21, 34]
    if w >= 0:
        return X[w]
    else:
        return 1



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

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

        
        if w + 1 < W:
            dp[h + 1][w + 1] += dp[h][w] * (transition(w - 1) * transition(W - w - 3))
            dp[h + 1][w + 1] %= MOD

        
        if w - 1 >= 0:
            dp[h + 1][w - 1] += dp[h][w] * (transition(w - 2) * transition(W - w - 2))
            dp[h + 1][w - 1] %= MOD

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

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

dp[0][0] = 1
for i in range(H):
    for j in range(W):
        for k in range(1 << (W - 1)):
            flag = True
            if '11' in bin(k):
                flag = False
            if flag:
                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 - 1 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[-1][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(H):
    for j in range(W):
        for k in range(1 << (W - 1)):
            ok = True
            if '11' in bin(k):
                ok = False
            if ok:
                if j >= 1 and ((k >> (j - 1)) & 1):
                    dp[i + 1][j - 1] += dp[i][j]
                    dp[i + 1][j - 1] %= mod
                    
                    
                elif j <= W -2 and ((k >> j) & 1):
                    dp[i + 1][j + 1] += dp[i][j]
                    dp[i + 1][j + 1] %= mod
                    
                    
                else:
                    dp[i + 1][j] += dp[i][j]
                    dp[i + 1][j] %= mod
                    
            
print(dp[H][K - 1])

Solution (Python):


H,W,K = [int(n) for n in input().split()]
memo = [[0 for _ in range(W)] for __ in range(H+1)]
memo[0][0] = 1
MOD = 10**9 + 7
for h in range(1,H+1):
    for pt in range((1 << W-1)):
        
        
        if "11" in bin(pt): continue
        
        goto = [i for i in range(W)]
        for i in range(W):
            if (1 << i) & pt:
                goto[i], goto[i + 1] = goto[i + 1], goto[i]
        for i in range(W):
            memo[h][goto[i]] += memo[h-1][i]
            memo[h][goto[i]] %= MOD


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

Solution (Python):
H,W,K = map(int,input().split())
dp = []
for i in range(H+1):
  L = [0]*W
  dp.append(L)
fb = [1,1]
for i in range(W-2):
  fb.append(fb[i]+fb[i+1])
dp[0][0] = 1
if W != 1:
  for i in range(1,H+1):
    for j in range(W):
      if 1 <= j <= W-2:
        dp[i][j] = dp[i-1][j-1]*fb[j-1]*fb[W-j-1]+dp[i-1][j]*fb[j]*fb[W-j-1]+dp[i-1][j+1]*fb[j]*fb[W-j-2]
      elif j == 0:
        dp[i][j] = dp[i-1][j]*fb[W-1]+dp[i-1][j+1]*fb[W-2]
      else:
        dp[i][j] = dp[i-1][j]*fb[W-1]+dp[i-1][j-1]*fb[W-2]
else:
  dp[H][0] = 1
print(dp[H][K-1]%(10**9+7))

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

mo=10**9 +7
p=[-1]*(w+1)
p[0]=1
p[1]=2
def pat(x):
    if x<0 or x>=w:
        return 1
    else:
        if p[x]!=-1:
            return p[x]
        else:
            return pat(x-2)+pat(x-1)

a=[[0 for i in range(w)] for i in range(h+1)]
a[0]=[1]+[0]*(w-1)
for i in range(1,h+1):
    for j in range(0,w):
        if j>0: a[i][j]+=a[i-1][j-1]*pat(j-2)*pat(w-j-2)
        a[i][j]+=a[i-1][j]*pat(j-1)*pat(w-1-j-1)
        if j<w-1: a[i][j]+=a[i-1][j+1]*pat(j-1)*pat(w-j-3)
print(a[h][k-1] % mo)

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

p=[-1]*(w+1)
p[0]=1
p[1]=2
def pat(x):
    if x<0 or x>=w:
        return 1
    else:
        if p[x]!=-1:
            return p[x]
        else:
            return pat(x-2)+pat(x-1)
        
for j in range(1):
    0
mo=10**9 +7

a=[[0 for i in range(w)] for i in range(h+1)]
a[0]=[1]+[0]*(w-1)
for i in range(1,h+1):
    
    
    for j in range(0,w):
        if j>0: a[i][j]+=a[i-1][j-1]*pat(j-2)*pat(w-j-2)
        a[i][j]+=a[i-1][j]*pat(j-1)*pat(w-1-j-1)
        if j<w-1: a[i][j]+=a[i-1][j+1]*pat(j-1)*pat(w-j-3)
print(a[h][k-1] % mo)

Solution (Python):
h, w, K = [int(item) for item in input().split()]

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

def layer_pattern(w, pat):
  if w == 0:
    for i in range(len(pat) -1):
      if pat[i] == 1 and pat[i+1] == 1:
        return False
    pats.append([0] + pat + [0])
    return True
  layer_pattern(w-1, pat + [0])
  layer_pattern(w-1, pat + [1])

layer_pattern(w-1, [])

for i in range(h+1):
  if i == 0:
    ans[0][0] = 1
  else:
    for pat in pats:
      for k in range(len(pat)):
        if k == len(pat)-1:
          continue
        elif pat[k] == 0 and pat[k+1] == 0:
          ans[i][k] += ans[i-1][k]
        elif pat[k] == 1 and pat[k+1] == 0:
          ans[i][k] += ans[i-1][k-1]
        elif pat[k] == 0 and pat[k+1] == 1:
          ans[i][k] += ans[i-1][k+1]
        else:
          print("cannot be happen")
          break

print(ans[h][K-1] % 1000000007)

Solution (Python):
H, W, K = map(int, input().split())
mod = 10 ** 9 + 7
A = [[0] * (W + 2) for i in range(H + 1)]
A[0][1] = 1
def multiple(N):
    temp = [1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
    return (temp[N + 1])


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

Solution (Python):
H,W,K = tuple(map(int,input().split()))
m = 1000000007
def get (bou_no_kazu):
    if bou_no_kazu == 2 or bou_no_kazu ==3:
        return bou_no_kazu
    else:
        return get(bou_no_kazu-1) + get(bou_no_kazu-2)

def n(nodes,from_idx,to_idx):
    ret = nodes[from_idx]
    
    if min(from_idx,to_idx) > 1:
        
        ret *= get(min(from_idx,to_idx))
    if max(from_idx,to_idx) < W-2:
        
        ret *= get(W-max(from_idx,to_idx)-1)
    return ret
    
prev_node = [1]*1+[0]*(W-1)
next_node = [1]*W

for i in range(H):
    for j in range(W):
        
        next_node[j] = n(prev_node,j,j)
        if j-1 >= 0:
            next_node[j] += n(prev_node,j-1,j)
        if j+1 <= W-1:
            next_node[j] += n(prev_node,j+1,j)
    
        
    prev_node = [int(i)%m for i in next_node.copy()]

print(int(prev_node[K-1]))

Solution (Python):
def f(n):
    
    if n <= 1: return 1
    return f(n - 1) + f(n - 2)


MOD = 10 ** 9 + 7

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


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



for h in range(H):
    
    for i in range(W):
        
        if i >= 1:
            dp[h + 1][i - 1] += dp[h][i] * f(i - 1) * f(W - 1 - i)
            dp[h + 1][i - 1] %= MOD
        dp[h + 1][i] += dp[h][i] * f(i) * f(W - 1 - i)
        dp[h + 1][i] %= MOD
        if i < W - 1:
            dp[h + 1][i + 1] += dp[h][i] * f(i) * f(W - 2 - i)
            dp[h + 1][i + 1] %= MOD

print(dp[H][K])

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

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


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



for h in range(H):
    
    for b in range(1 << (W - 1)):
        

        if '11' in bin(b): continue
        

        goto = [i for i in range(W)]
        

        for j in range(W - 1):
            
            if (b >> j) & 1 == 1:
                
                goto[j], goto[j + 1] = goto[j + 1], goto[j]
        

        for i in range(W):
            
            dp[h + 1][goto[i]] += dp[h][i]
            dp[h + 1][goto[i]] %= MOD

print(dp[H][K])

Solution (Python):


MOD = 10 ** 9 + 7

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

K -= 1


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



for h in range(1, H + 1):
    
    for b in range(1 << (W - 1)):
        if '11' in bin(b): continue

        perm = [i for i in range(W)]
        

        for i in range(W - 1):
            if (b >> i) & 1:
                perm[i], perm[i + 1] = perm[i + 1], perm[i]

        for i in range(W):
            dp[h][perm[i]] += dp[h - 1][i]
            dp[h][perm[i]] %= MOD

print(dp[H][K])

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


def baai(L):
    if L == []:
        return 1
    elif L == [0]:
        return 2
    elif L == [1]:
        return 1
    elif L == [0, 0]:
        return 3
    elif len(L) == 2:
        return 1

    if L[0:2] == [1, 0]:
        return baai(L[2:])
    elif L[0:2] == [0, 1]:
        return baai(L[1:])
    elif L[0:2] == [0, 0]:
        return baai(L[2:])+baai(L[1:])
    else:
        print("hoge", L)
        return 0


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


for i in range(H):
    for j in range(W):
        
        if j-1 > i:
            break
        elif i == 0:
            if j == 0:
                dp[i][j] = baai([0]*(W-2))
            else:
                buf = [0] * (W-1)
                buf[0] = 1
                dp[i][j] = baai(buf)
            dp[i][j] = dp[i][j] % div
            continue

        buf = [0]*W
        buf[j] = 1
        dp[i][j] += dp[i-1][j]*baai(buf)
        if j-1 >= 0:
            buf = [0]*(W-1)
            buf[j-1] = 1
            dp[i][j] += dp[i-1][j-1]*baai(buf)
        if j+1 < W:
            buf = [0]*(W-1)
            buf[j] = 1
            dp[i][j] += dp[i-1][j+1]*baai(buf)
        dp[i][j] = dp[i][j] % div

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

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

dp = [1] + [0] * (w - 1)
 

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

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

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

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

fibs = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
def getFib(i):
    return fibs[i+2]

numLs, numCs, numRs = [0]*W, [0]*W, [0]*W
for j in range(W):
    numCs[j] = getFib(j-1) * getFib(W-1-j-1)
    numLs[j] = getFib(j-2) * getFib(W-1-j-1)
    numRs[j] = getFib(j-1) * getFib(W-1-j-2)

dp = [[0]*W for _ in range(H+1)]
dp[0][0] = 1
for i in range(H):
    for j in range(W):
        dp[i+1][j] += dp[i][j] * numCs[j]
        if j > 0:
            dp[i+1][j-1] += dp[i][j] * numLs[j]
        if j < W-1:
            dp[i+1][j+1] += dp[i][j] * numRs[j]
    for j in range(W):
        dp[i+1][j] %= MOD

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

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

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

pats = []
for pat in range(1<<(W-1)):
    for i in range(W-2):
        if pat & (1<<i) and pat & (1<<(i+1)):
            break
    else:
        pats.append(pat*2)

dp = [[0]*W for _ in range(H+1)]
dp[0][0] = 1
for i in range(H):
    for j in range(W):
        for pat in pats:
            L = pat & (1<<j)
            R = pat & (1<<(j+1))
            if L == 0 and R == 0:
                dp[i+1][j] += dp[i][j]
            elif L != 0 and R == 0:
                dp[i+1][j-1] += dp[i][j]
            elif L == 0 and R != 0:
                dp[i+1][j+1] += dp[i][j]
    for j in range(W):
        dp[i+1][j] %= MOD

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