CodeEff/ECCO huggingface dataset:
# Original solution
H,W,K=list(map(int,input().split()))

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

mod=1000000007
    
def f(H,K):
    if H==0:
        if K==1:
            return 1
        else:
            return 0
    else:
        if K==0 or K==W+1:
            return 0
        else:
            return (f(H-1,K)*fibo[K-1]*fibo[W-K]\
                    +f(H-1,K-1)*fibo[K-2]*fibo[W-K]\
                    +f(H-1,K+1)*fibo[K-1]*fibo[W-K-1])%mod
            
print(f(H,K))

# Optimized solution
H,W,K=list(map(int,input().split()))

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

mod=1000000007
    
f=[[1 if i==1 else 0 for i in range(W+2)]]
for i in range(H):
    for j in range(W):
        f.append([(f[-1][j]*fibo[j-1]*fibo[W-j]+f[-1][j-1]*fibo[j-2]*fibo[W-j]\
                  +f[-1][j+1]*fibo[j-1]*fibo[W-j-1])% mod\
                     if (j>=1 and j<=W) else 0 for j in range(W+2)])     

print(f[H][K])
# Original solution
import sys

MOD = 10 ** 9 + 7

h, w, k = list(map(int, sys.stdin.readline().split()))

def main():
    ok = []
    for i in range(2 ** (w - 1)):
        prev = False
        for j in range(w-1):
            if i >> j & 1:
                if prev:
                    break
                else:
                    prev = True
            else:
                prev = False
        else:
            ok.append(i)
        
    res = [0] * w
    res[0] = 1
    for _ in range(h):
        nex = [0] * w
        for i in ok:
            j = 0
            while j < w:
                if i >> j & 1:
                    nex[j] += res[j+1]
                    nex[j+1] += res[j] 
                    j += 2
                else:
                    nex[j] += res[j]
                    j += 1
        for j in range(w):
            nex[j] %= MOD
        res = nex
    
    return res[k-1]
    
if __name__ == '__main__':
    ans = main()
    print(ans)

# Optimized solution
import sys

MOD = 10 ** 9 + 7

h, w, k = list(map(int, sys.stdin.readline().split()))

def main():
    if w == 1:
        return 1
        
    ok = []
    for i in range(2 ** (w - 1)):
        prev = False
        for j in range(w-1):
            if i >> j & 1:
                if prev:
                    break
                else:
                    prev = True
            else:
                prev = False
        else:
            ok.append(i)

    lcr = [(letter, 0) for letter in 'lcr']
    a = [dict(lcr) for _ in range(w)]
    for i in ok:
        j = 0
        while j < w:
            if i >> j & 1:
                a[j]['r'] += 1
                a[j+1]['l'] += 1
                j += 2
            else:
                a[j]['c'] += 1
                j += 1

    res = [0] * w
    res[0] = 1
    for _ in range(h):
        nex = [0] * w
        for j in range(w):
            if j == 0:
                nex[j] = res[j] * a[j]['c'] + res[j+1] * a[j]['r']
            elif j < w - 1:
                nex[j] = res[j-1] * a[j]['l'] + res[j] * a[j]['c'] + res[j+1] * a[j]['r']
            else:
                nex[j] = res[j-1] * a[j]['l'] + res[j] * a[j]['c']
        for j in range(w):
            nex[j] %= MOD
        res = nex

    return res[k-1]
    
if __name__ == '__main__':
    ans = main()
    print(ans)
# Original solution
MOD = 10**9 + 7

H, W, K = list(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]))


# Optimized solution
MOD = 10**9 + 7

H, W, K = list(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]))
# Original solution
H, W, K = list(map(int, input().split()))
W2 = W-1
c = [0] * (W2+1)
cnt = 0
MOD = 10**9 + 7
for bit in range(1 << W2):
    s0 = bit&1
    flg=True
    for i in range(1, W2):
        if (bit>>i)&1 and s0 == 1:
            flg = False
            break
        s0 = (bit>>i)&1
    if flg:
        cnt += 1
        for i in range(W2):
            if (bit >> i)&1:
                c[i] += 1
dp = [[0]*W for _ in range(H+1)]
dp[0][0] = 1
for h in range(H):
    for i in range(W):
        if i != 0:
            dp[h+1][i-1] += dp[h][i]*c[i-1]
            dp[h+1][i-1] %= MOD
        if i != W-1:
            dp[h+1][i+1] += dp[h][i]*c[i]
            dp[h+1][i+1] %= MOD
        dp[h+1][i] += dp[h][i]*(cnt-c[i-1]-c[i])
        dp[h+1][i] %= MOD
print((dp[H][K-1]))

# Optimized solution
H, W, K = list(map(int, input().split()))
MOD, p, cnt = 10**9+7, [0]*W, 0
for bit in range(1<<(W-1)):
    s0 = bit&1
    flg=True
    for w in range(1, W-1):
        if (bit>>w)&1 and s0 == 1:flg=False; break
        s0 = (bit>>w)&1
    if flg:
        cnt += 1
        for w in range(W - 1):
            if (bit >> w)&1:p[w] += 1
dp = [[0]*W for _ in range(H+1)]
dp[0][0] = 1
for h in range(H):
    for w in range(W):
        if w:
            dp[h+1][w-1] += dp[h][w]*p[w-1]
            dp[h+1][w-1] %= MOD
        if w-(W - 1):
            dp[h+1][w+1] += dp[h][w]*p[w]
            dp[h+1][w+1] %= MOD
        dp[h+1][w]+=dp[h][w]*(cnt-p[w-1]-p[w])
        dp[h+1][w]%=MOD
print((dp[H][K-1]))
# Original solution
mod = 10**9+7

h,w,k = list(map(int,input().split()))
k = k-1
dp = [0]*1000 #dp[i]=i個縦棒がある時の横棒の引き方
dp[0]=1
dp[1]=1
dp[2]=2

for i in range(3,1000):
  dp[i] = (dp[i-1]+dp[i-2])%mod
  #i-1とi番目に横棒を引かないとき、横棒の置き方は1からi-1番目の置き方と同じ
  #i-1とi番目に横棒を引くとき、横棒の置き方は1からi-2番目の置き方と同じ（i-1とi-2の間には置けないから）
  #→iの横棒の置き方はf(i-1)+f(i-2) ※場合わけにおける組み合わせ総数

dp2=[[0 for j in range(w)] for i in range(h+1)] #上からi下がったところでj番目にいく縦線を引くようなあみだくじの総数

dp2[0][0] = 1
for i in range(h):
  for j in range(w):
    #dp[i][j]からdp[i+1][j]への遷移が起こる条件は
    #j-1とjの間、jとj+1の間に横棒がない
    #このような横棒の置き方は
    #（縦棒1から縦棒j-1の置き方）*（縦棒j+1からwまでの棒の置き方）

    dp2[i+1][j] = (dp2[i+1][j]+dp2[i][j]*dp[j]%mod*dp[w-j-1]%mod)%mod

    #dp[i][j]からdp[i+1][j-1]に遷移する条件
    #jとj-1の間に横棒がある
    #j-1とj-2の間、j+1とjの間に横棒がない
    #この置き方は
    #（縦棒1から縦棒j-2までの横棒の置き方）* （縦棒jから縦棒wまでの横棒の置き方置き方）
    if (j-1>=0):
      dp2[i+1][j-1]=(dp2[i+1][j-1]+dp2[i][j]*dp[j-1]%mod*dp[w-j-1]%mod)%mod

    #dp[i][j]からdp[i+1][j+1]への遷移が起こる条件は
    #j+1とjの間に横棒がある
    #jとj-1の間、j+2とj+1の間に横棒がない
    #この置き方は
    #(縦棒1から縦棒j-1の置き方)*(縦棒j+2*wまでの横棒の置き方)

    if (j+1<w):
      dp2[i+1][j+1]=(dp2[i+1][j+1]+dp2[i][j]*dp[j]%mod*dp[w-j-2]%mod)%mod


print((dp2[h][k]))



# Optimized solution
mod = 10**9+7

h,w,k = list(map(int,input().split()))
fibonacchi =[1, 1, 2, 3, 5, 8, 13, 21, 34]
dp = [[0] * (w + 1) for _ in range(h + 1)]
dp[0][1] = 1
for i in range(h):
  for j in range(w+1):
    #dp[i][j]からdp[i+1][j-1]に遷移する条件
    #jとj-1の間に横棒がある&j-1とj-2の間、j+1とjの間に横棒がない
    #この置き方は
    #（縦棒1から縦棒j-2までの横棒の置き方）* （縦棒j+1から縦棒wまでの横棒の置き方置き方）
    if j >= 2:
      dp[i+1][j-1] += (fibonacchi[j-2]*fibonacchi[w-j])*dp[i][j]
      dp[i+1][j-1]%=mod

    #dp[i][j]からdp[i+1][j+1]への遷移が起こる条件は
    #j+1とjの間に横棒がある&jとj-1の間、j+2とj+1の間に横棒がない
    #この置き方は
    #(縦棒1から縦棒j-1の置き方)*(縦棒j+2*wまでの横棒の置き方)
    if j <= w-1:
      dp[i+1][j+1] += (fibonacchi[j-1]*fibonacchi[w-j-1])*dp[i][j]
      dp[i+1][j+1]%=mod

    #dp[i][j]からdp[i+1][j]への遷移が起こる条件は
    #j-1とjの間、jとj+1の間に横棒がない
    #このような横棒の置き方は
    #（縦棒1から縦棒j-1の置き方）*（縦棒j+1からwまでの棒の置き方）
    dp[i+1][j] += (fibonacchi[j-1]*fibonacchi[w-j])*dp[i][j]
    dp[i+1][j] %=mod

print((dp[h][k]))
# Original solution
import itertools


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

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

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

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

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

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

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

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

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


# Optimized solution
import itertools


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

DP = [0] * w
DP[0] = 1
mod = 10**9 + 7

patterns = []

for line_count in range(w):
    candidates = itertools.combinations(list(range(w-1)), line_count)

    for pattern in candidates:
        usable = True
        prev = 10

        for num in pattern:
            if num == prev + 1:
                usable = False
                break
            else:
                prev = num

        if usable:
            patterns.append(pattern)

for i in range(h):
    next_DP = [0] * w

    for pattern in patterns:
        straight = set(range(w))
        for line in pattern:
            next_DP[line] += DP[line+1]
            next_DP[line] %= mod
            next_DP[line+1] += DP[line]
            next_DP[line+1] % mod
            straight.discard(line)
            straight.discard(line+1)

        for line in straight:
            next_DP[line] += DP[line]
            next_DP[line] %= mod

    DP = next_DP.copy()

ans = DP[k-1]
print((ans%mod))
# Original solution
l=[[] for i in range(9)]
l[1]=[""]
l[2]=["0","1"]
for i in range(3,9):
    for s in l[i-1]:
        l[i].append("0"+s)
        if s[0]!="1":
            l[i].append("1"+s)

mod=1000000007
s=input().split()
h,w,k=int(s[0]),int(s[1]),int(s[2])
res=[[0]*(w) for i in range(h+1)]
res[0][0]=1
for i in range(h):
    for s in l[w]:
        s="0"+s+"0" #どの縦棒から見ても左右が参照できるように両端に0をつけておく
        for j in range(w):
            if s[j]=="0" and s[j+1]=="0": #直進
                res[i+1][j]+=res[i][j]
                res[i+1][j]%=mod
            if s[j]=="0" and s[j+1]=="1": #左列に移る
                res[i+1][j+1]+=res[i][j]
                res[i+1][j+1]%=mod
            if s[j]=="1" and s[j+1]=="0": #右列に移る
                res[i+1][j-1]+=res[i][j]
                res[i+1][j-1]%=mod
print((res[h][k-1]))

# Optimized solution
l=[[] for i in range(9)]
l[1]=[""]
l[2]=["0","1"]
for i in range(3,9):
    for s in l[i-1]:
        l[i].append("0"+s)
        if s[0]!="1":
            l[i].append("1"+s)

mod=1000000007
s=input().split()
h,w,k=int(s[0]),int(s[1]),int(s[2])
dp=[[0]*(w) for i in range(h+1)]
dp[0][0]=1
for i in range(h):
    for s in l[w]:
        s="0"+s+"0" #どの縦棒から見ても左右が参照できるように両端に0をつけておく
        for j in range(w):
            if s[j]=="0" and s[j+1]=="0": #直進
                dp[i+1][j]+=dp[i][j]
                dp[i+1][j]%=mod
            if s[j]=="0" and s[j+1]=="1": #左列に移る
                dp[i+1][j+1]+=dp[i][j]
                dp[i+1][j+1]%=mod
            if s[j]=="1" and s[j+1]=="0": #右列に移る
                dp[i+1][j-1]+=dp[i][j]
                dp[i+1][j-1]%=mod
print((dp[h][k-1]))
# Original solution
H,W,K=list(map(int,input().split()))
mod=10**9+7
fib=[1,1,2,3,5,8,13,21]

from functools import lru_cache

@lru_cache(maxsize=None)
def dfs(cur,now):
    if cur==H:
        if now==K:
            return 1
        else:
            return 0
    elif now==1:
        if W==1:
            return dfs(cur+1,1)%mod
        else:
            return (fib[W-1]*dfs(cur+1,1)+fib[W-2]*dfs(cur+1,2))%mod
    elif now==W:
        return (fib[W-2]*dfs(cur+1,W-1)+fib[W-1]*dfs(cur+1,W))%mod
    else:
        return (fib[W-now]*fib[now-2]*dfs(cur+1,now-1)+fib[W-now]*fib[now-1]*dfs(cur+1,now)+fib[W-now-1]*fib[now-1]*dfs(cur+1,now+1))%mod
    
print((dfs(0,1)))

# Optimized solution
H,W,K=list(map(int,input().split()))
mod=10**9+7
fib=[1,1,2,3,5,8,13,21]
memo=[[None]*W for _ in range(H+1)]
def dfs(cur,now):
    if cur==H:
        if now==K:
            return 1
        else:
            return 0
    elif now==1:
        if W==1:
            if memo[cur+1][0]==None:
                memo[cur+1][0]=dfs(cur+1,1)%mod
            return memo[cur+1][0]
        else:
            if memo[cur+1][0]==None:
                memo[cur+1][0]=dfs(cur+1,1)%mod
            if memo[cur+1][1]==None:
                memo[cur+1][1]=dfs(cur+1,2)%mod
            return (fib[W-1]*memo[cur+1][0]+fib[W-2]*memo[cur+1][1])%mod
    elif now==W:
        if memo[cur+1][W-2]==None:
            memo[cur+1][W-2]=dfs(cur+1,W-1)%mod
        if memo[cur+1][W-1]==None:
            memo[cur+1][W-1]=dfs(cur+1,W)%mod            
        return (fib[W-2]*memo[cur+1][W-2]+fib[W-1]*memo[cur+1][W-1])%mod
    else:
        if memo[cur+1][now-2]==None:
            memo[cur+1][now-2]=dfs(cur+1,now-1)%mod
        if memo[cur+1][now-1]==None:
            memo[cur+1][now-1]=dfs(cur+1,now)%mod     
        if memo[cur+1][now]==None:
            memo[cur+1][now]=dfs(cur+1,now+1)%mod  
        return (fib[W-now]*fib[now-2]*memo[cur+1][now-2]+fib[W-now]*fib[now-1]*memo[cur+1][now-1]+fib[W-now-1]*fib[now-1]*memo[cur+1][now])%mod
    
print((dfs(0,1)))
# Original solution
MOD = 10 ** 9 + 7

H, W, K = list(map(int, input().split()))
K -= 1
# 0-indexed

dp = [[0 for _ in range(W)] for _ in range(H + 1)]
dp[0][0] = 1
# dp[h][k]
# h段のあみだくじで横線kに到達する本数

for h in range(H):
    # h: 移動前の高さ
    for b in range(1 << (W - 1)):
        # 各段はW - 1箇所の横線配置位置をもつ

        if '11' in bin(b): continue
        # 横線同士がつながっているケースは不適

        goto = [i for i in range(W)]
        # goto[i]: 縦線iからの移動先

        for j in range(W - 1):
            # j: 横線の番号 かつ 横線の左側の縦線の番号
            if (b >> j) & 1 == 1:
                # 横線が存在する場合
                goto[j], goto[j + 1] = goto[j + 1], goto[j]
        # gotoで横線配置bによる移動を表現する

        for i in range(W):
            # i: 移動前の縦線
            dp[h + 1][goto[i]] += dp[h][i]
            dp[h + 1][goto[i]] %= MOD

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


# Optimized solution
def f(n):
    # 縦線n本で構成できる横線の組み合わせ
    if n <= 1: return 1
    return f(n - 1) + f(n - 2)


MOD = 10 ** 9 + 7

H, W, K = list(map(int, input().split()))
K -= 1
# 0-indexed

dp = [[0 for _ in range(W)] for _ in range(H + 1)]
dp[0][0] = 1
# dp[h][k]
# h段のあみだくじで横線kに到達する本数

for h in range(H):
    # h: 移動前の高さ
    for i in range(W):
        # i: 移動前の縦線
        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]))
# Original solution
mod = 10 ** 9 + 7
H, W, K = list(map(int, input().split()))
K -= 1
dp = [0] * W
dp[0] = 1
ndp = [0] * W
for r in range(H):
    for i in range(1 << (W - 1)):
        if '11' in bin(i): continue
        perm = [i for i in range(W)]
        for j in range(W - 1):
            if (i >> j) & 1:
                perm[j], perm[j + 1] = perm[j + 1], perm[j]
        for j in range(W):
            next_line = perm[j]
            ndp[next_line] += dp[j]
            ndp[next_line] %= mod
    dp = ndp.copy()
    ndp = [0] * W
print((dp[K]))


# Optimized solution
mod = 10 ** 9 + 7
h, w, k = list(map(int, input().split()))
k -= 1

dp = [0] * w
dp[0] = 1
ndp = [0] * w

for _ in range(h):
    for bits in range(1 << w - 1):
        if '11' in bin(bits): continue
        to = list(range(w))
        for i in range(w - 1):
            if (bits >> i) & 1:
                to[i], to[i + 1] = to[i + 1], to[i]
        for i in range(w):
            ndp[to[i]] += dp[i]
            ndp[to[i]] %= mod
    dp = ndp
    ndp = [0] * w
print((dp[k]))
# Original solution
h,w,kk = list(map(int,input().split()))
dp = [[[] for j in range(w)] for i in range(h+1)]
# dp[i][j]
# 高さiにおいて点jに行き得る通り数
for i in range(h+1):
        for j in range(w):
                dp[i][j] = 0
dp[0][0]=1
mod = 1000000007

for i in range(1,h+1):
        for j in range(1<<(w-1)):
                yoko = [False for loo in range(w)]
                for k in range((w-1)):
                        yoko[k] = True if ((j>>k)&1) else False
                
                ok = True
                for l in range(w-2):
                        if(yoko[l]==True and yoko[l+1]==True):
                                ok = False
                if(not ok):
                        continue
                
                for l in range(w):
                        if(l==0):
                                if(yoko[l]):
                                        dp[i][l] += dp[i-1][l+1]
                                else:
                                        dp[i][l] += dp[i-1][l]
                                dp[i][l]%=mod
                                continue
                        if(l==w-1):
                                if(yoko[l-1]):
                                        dp[i][l] += dp[i-1][l-1]
                                else:
                                        dp[i][l] += dp[i-1][l]
                                dp[i][l]%=mod                                
                                continue

                        if(yoko[l-1] or yoko[l]):
                                if(yoko[l-1]):
                                        dp[i][l]+= dp[i-1][l-1]
                                else:
                                        dp[i][l]+= dp[i-1][l+1]
                        else:
                                dp[i][l] += dp[i-1][l]
                        dp[i][l]%=mod
                        
print((dp[h][kk-1]))

# Optimized solution
mod = 10**9+7
h,w,k = list(map(int,input().split()))
dp =[[0]*w for _ in range(h+1)]
dp[0][0]=1
fibo=[1]*10
for i in range(2,10):
        fibo[i] = fibo[i-2]+fibo[i-1]
for i in range(1,h+1):
        for j in range(w):
                dp[i][j] = dp[i-1][j]*fibo[j]*fibo[w-j-1]%mod
                if(j>0):
                        dp[i][j] += dp[i-1][j-1]*fibo[j-1]*fibo[w-j-1]%mod
                        dp[i][j] %= mod
                if(j<w-1):
                        dp[i][j] += dp[i-1][j+1]*fibo[j]*fibo[w-j-2]%mod
                        dp[i][j]%=mod
print((dp[h][k-1]))
# Original solution
# -*- coding: utf-8 -*-

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

fibonacci = [1,1,2,3,5,8,13,21] # W <= 8なのでこれだけでいい

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

for h in range(H+1):
	if W == 1:
		break
	for w in range(W):
		if h == 0:
			if w == 0:
				Amida[h][w] = 1
			else:
				break
		elif w == 0:
			Amida[h][w] = fibonacci[W-2] * Amida[h-1][w+1] + fibonacci[W-1] * Amida[h-1][w]
		elif w == W-1:
			Amida[h][w] = fibonacci[W-2] * Amida[h-1][w-1] + fibonacci[W-1] * Amida[h-1][w]
		else:
			Amida[h][w] += (fibonacci[w-1] * fibonacci[W-w-1] * Amida[h-1][w-1])
			Amida[h][w] += (fibonacci[w] * fibonacci[W-w-1] * Amida[h-1][w])
			Amida[h][w] += fibonacci[w] * fibonacci[W-w-2] * Amida[h-1][w+1]

		Amida[h][w] = Amida[h][w] % 1000000007

if W == 1:
	if K == 1:
		print((1))
	else:
		print((0))
else:
	print((Amida[H][K-1]))

# Optimized solution
H, W, K = list(map(int,input().split()))

mod = 1000000007

fibonacci = [1,1,2,3,5,8,13,21] # W <= 8なのでこれだけでいい

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

for h in range(H+1):
	if W == 1:
		break
	for w in range(W):
		if h == 0:
			if w == 0:
				Amida[h][w] = 1
			else:
				break
		elif w == 0:
			Amida[h][w] = fibonacci[W-2] * Amida[h-1][w+1] + fibonacci[W-1] * Amida[h-1][w]
		elif w == W-1:
			Amida[h][w] = fibonacci[W-2] * Amida[h-1][w-1] + fibonacci[W-1] * Amida[h-1][w]
		else:
			Amida[h][w] += (fibonacci[w-1] * fibonacci[W-w-1] * Amida[h-1][w-1])
			Amida[h][w] += (fibonacci[w] * fibonacci[W-w-1] * Amida[h-1][w])
			Amida[h][w] += fibonacci[w] * fibonacci[W-w-2] * Amida[h-1][w+1]

		Amida[h][w] = Amida[h][w] % mod

if W == 1:
	if K == 1:
		print((1))
	else:
		print((0))
else:
	print((Amida[H][K-1]))
# Original solution
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

H, W, K = lr()
MOD = 10 ** 9 + 7
dp = [[0] * W for _ in range(H+1)]
dp[0][0] = 1
ladder = [[0] * 2 for _ in range(15)] #あえて多めに用意
ladder[1][0] = 1
for i in range(2, 9):
    ladder[i][0] = ladder[i-1][0] + ladder[i-1][1]
    ladder[i][1] = ladder[i-1][0]

ladder = [max(1, x+y) for x, y in ladder]

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

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

# Optimized solution
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 10 ** 9 + 7
H, W, K = lr()
cases = [1] * 10  # 縦棒i本で何通りの横棒の書き方があるか(0本含む)
cases[-1] = 0 
for i in range(2, 9):
    cases[i] = cases[i-2] + cases[i-1]

dp = [0] * W
dp[0] = 1
for i in range(H):
    prev = dp[:]
    for j in range(W):
        left = j; right = W-(j+1)
        dp[j] *= cases[left] * cases[right]
        if j > 0:
            dp[j] += prev[j-1] * cases[left-1] * cases[right]
        if j < W-1:
            dp[j] += prev[j+1] * cases[left] * cases[right-1]
        dp[j] %= MOD
        
answer = dp[K-1] % MOD
print(answer)
# 19
# Original solution
a,b,c=list(map(int,input().split()))
e=0
f=[[1,1]]
k=[[1,1,1],[2,1,1,1,2],[3,2,2,1,2,2,3],[5,3,3,2,4,2,3,3,5],[8,5,5,3,6,4,6,3,5,5,8],[12,8,8,5,10,6,9,6,10,5,8,8,12],[21,13,13,8,16,10,15,9,15,10,16,8,13,13,21]]
if b==1:
    print((1))
else:
    d=k[b-2]
    for i in range(0,a):
        l=len(f)
        for j in range(0,l):
            f.append([f[j][0],f[j][1]*d[2*(f[j][0]-1)]])
            if f[j][0]-1>0 and f[j][0]-1>=c-(a-i):
                f.append([f[j][0]-1,f[j][1]*d[1+2*(f[j][0]-2)]])
            if f[j][0]+1<=b and f[j][0]+1<=c+(a-i):
                f.append([f[j][0]+1,f[j][1]*d[2*(f[j][0]-1)+1]])
            j+=1
        else:
            del f[:l]
    else:
        for i in range(0,len(f)):
            if f[i][0]==c:
                e+=f[i][1]
        print((e%(10**9+7)))

# Optimized solution
a,b,c=list(map(int,input().split()))
s=[[0]*b for i in range(a+1)]
s[0][0]=1
k=[[1,1,1],[2,1,1,1,2],[3,2,2,1,2,2,3],[5,3,3,2,4,2,3,3,5],[8,5,5,3,6,4,6,3,5,5,8],[13,8,8,5,10,6,9,6,10,5,8,8,13],[21,13,13,8,16,10,15,9,15,10,16,8,13,13,21]]
if b==1:
    print((1))
elif c-a>=2:
    print((0))    
else:
    d=k[b-2]
    for i in range(1,a+1):
        s[i][b-1]=s[i-1][b-1]*d[2*(b-1)]+s[i-1][b-2]*d[2*(b-1)-1]
        for j in range(0,b-1):
            if j==0:
                s[i][0]=s[i-1][0]*d[0]+s[i-1][1]*d[1]
            else:    
                s[i][j]=s[i-1][j-1]*d[2*j-1]+s[i-1][j]*d[2*j]+s[i-1][j+1]*d[2*j+1]
    print((s[a][c-1]%(10**9+7)))