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 3 2

-----Sample Output-----
1

Only the following one amidakuji satisfies the condition:

Difficulty: interview

Starter code:

Solutions:
def check(amidakuji,w):
    before=0
    flag=True
    for _ in range(w-1):
        if amidakuji&1==1 and before==1:
            flag=False
            break
        elif amidakuji&1==1:
            before=1
            amidakuji>>=1
        else:
            before=0
            amidakuji>>=1
    return flag

from sys import stdin
def main():
    #入力
    readline=stdin.readline
    mod=10**9+7
    h,w,k=map(int,readline().split())

    dp=[[0]*w for _ in range(h+1)]
    dp[0][0]=1
    for i in range(1,h+1):
        for bit in range(1<<(w-1)):
            if check(bit,w)==False:
                continue
            else:
                for j in range(w):
                    if j==0:
                        if bit&1==1:
                            dp[i][j+1]+=dp[i-1][j]
                        else:
                            dp[i][j]+=dp[i-1][j]
                    elif j==w-1:
                        if bit&1==1:
                            dp[i][j-1]+=dp[i-1][j]
                        else:
                            dp[i][j]+=dp[i-1][j]
                    else:
                        if bit&1==1:
                            dp[i][j-1]+=dp[i-1][j]
                            bit>>=1
                        else:
                            bit>>=1
                            if bit&1==1:
                                dp[i][j+1]+=dp[i-1][j]
                            else:
                                dp[i][j]+=dp[i-1][j]

                for j in range(w):
                    dp[i][j]%=mod

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

def __starting_point():
    main()
__starting_point()

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

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

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)
print((dp[h][k-1]))


h,w,k_=list(map(int,input().split()))
mod=pow(10,9)+7
if w==1:
  print((1))
  return
# 遷移の仕方
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]))
#print(dp)


import sys
input = sys.stdin.readline
MOD = 10 ** 9 + 7


def main():
    H, W, K = map(int, input().split())
    dp = [[0] * W for _ in range(H + 1)]  # 数え上げ問題なので0で初期化する
    dp[0][0] = 1  # 初期条件
    for h in range(H):
        for bit in range(1 << (W - 1)):  # 左ビットシフトで2 ** (W-1)と同じ
            if '11' in bin(bit): continue  # ある頂点から左右方向に棒が伸びているケースはスルー
            for w in range(W):
                # w番目の棒を考える
                if w and bit & (1 << (w - 1)):  # leftを見るので1<<w-1と確認, w=0の時はleftにいけないことに注意する
                    dp[h + 1][w - 1] += dp[h][w] % MOD
                elif bit & (1 << w):  # rightを見るので1<<w確認
                    dp[h + 1][w + 1] += dp[h][w] % MOD
                else:  # down, 左右どちらにもいかない時
                    dp[h + 1][w] += dp[h][w] % MOD
    # for i in dp:
    #     print(*i)
    print(dp[H][K - 1] % MOD)


def __starting_point():
    main()
__starting_point()

# 解説と下記を参考に作成
# https://atcoder.jp/contests/abc113/submissions/15821617
# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque
# from decorator import stop_watch
# 
# 
# @stop_watch
def solve(H, W, K):
    mod = 10 ** 9 + 7
    dp = [[0] * W for _ in range(H + 1)]
    dp[0][0] = 1
    for h in range(H):
        for w in range(W):
            if dp[h][w] == 0:
                continue
            for i in range(3):
                new_w = w - 1 + i
                if not 0 <= new_w < W:
                    continue

                def cnt_tmp(n, r, l, flg):
                    re = 0
                    if n >= W - 2:
                        if r <= n <= l:
                            return 1
                        if flg:
                            return 1
                        else:
                            return 2
                    if r <= n <= l:
                        return cnt_tmp(n + 1, r, l, False)
                    re += cnt_tmp(n + 1, r, l, False)
                    re += cnt_tmp(n + 1, r, l, True) if not flg else 0
                    return re

                tmp = cnt_tmp(0, min(w, new_w) - 1, max(w, new_w), False)
                dp[h + 1][new_w] += dp[h][w] * tmp
                dp[h + 1][new_w] %= mod
    # for dpi in dp:
    #     print(dpi)
    print((dp[-1][K - 1]))


def __starting_point():
    H, W, K = list(map(int, input().split()))
    solve(H, W, K)

    # # test
    # from random import randint
    # from func import random_str
    # solve()

__starting_point()

import sys
mod = 7 + 10 ** 9

def solve():
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    DP = [[0] * W for _ in range(H + 1)]
    pattern = [1, 2, 3, 5, 8, 13, 21]
    DP[0][0] = 1
    for h in range(H):
        for w in range(W):
            if w == 0:
                DP[h+1][w] += (DP[h][w] * pattern[max(0, W - 2)]) % mod
                if W > 1: DP[h+1][w] += (DP[h][w+1] * pattern[max(0, W - 3)]) % mod
            elif w == W - 1:
                DP[h+1][w] += (DP[h][w] * pattern[max(0, W - 2)]) % mod
                if W > 1: DP[h+1][w] += (DP[h][w-1] * pattern[max(0, W - 3)]) % mod
            else:
                DP[h+1][w] += (DP[h][w]  * pattern[max(0, w - 1)] * pattern[max(0, W - w - 2)]) % mod
                DP[h+1][w] += (DP[h][w+1] * pattern[max(0, w - 1)] * pattern[max(0, W - w - 3)]) % mod
                DP[h+1][w] += (DP[h][w-1] * pattern[max(0, w - 2)] * pattern[max(0, W - w - 2)]) % mod
            DP[h+1][w] %= mod
    print(DP[H][K - 1])

    return 0

def __starting_point():
    solve()
__starting_point()

# coding: utf-8

# https://atcoder.jp/contests/abc113
# 12:01-12:49 give up -> kaisetsu
# 11:57-12:25 try again

# from pprint import pprint as ppr


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

#     v = "v"
#     h = "h"
#     dp = [[{"v": 0, "h": 0} for _ in range(W)] for _ in range(H)]
#     dp[0][0][v] = 1

#     for i in range(H):

#         for j in range(W):
#             # horizontal computation
#             if j == 0:
#                 dp[i][j+1][h] += dp[i][j][v]
#             elif j == W-1:
#                 dp[i][j-1][h] += dp[i][j][v]
#             else:
#                 dp[i][j+1][h] += dp[i][j][v]
#                 dp[i][j-1][h] += dp[i][j][v]

#         if i < H-1:
#             for j in range(W):
#                 # vertical computation
#                 dp[i+1][j][v] += dp[i][j][v] + dp[i][j][h]
    
#     ppr(dp)

#     return dp[H-1][K-1][v] + dp[H-1][K-1][h]


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

    if W == 1:
        return 1

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

    bridges_list = []

    def preset(i, bridges, n_cand):
        if i == n_cand:
            bridges_list.append(bridges)
            return None

        if i-1 in bridges:
            preset(i+1, bridges, n_cand)
        else:
            bridges_1 = bridges[:]
            bridges_2 = bridges[:]
            bridges_1.append(i)

            preset(i+1, bridges_1, n_cand)
            preset(i+1, bridges_2, n_cand)

    preset(0, [], W-1)

    n_bridges = [0] * (W-1)
    for bridges in bridges_list:
        for x in bridges:
            n_bridges[x] += 1

    n_all_cands = len(bridges_list)

    # ppr(bridges_list)
    # ppr(n_bridges)

    dp[0][0] = (n_all_cands-n_bridges[0])
    dp[0][1] = n_bridges[0]

    for i in range(H-1):
        for j in range(W):
            if j == 0:
                dp[i+1][j] += dp[i][j] * (n_all_cands-n_bridges[j])
                dp[i+1][j+1] += dp[i][j] * n_bridges[j]
            elif j == W-1:
                dp[i+1][j] += dp[i][j] * (n_all_cands-n_bridges[j-1])
                dp[i+1][j-1] += dp[i][j] * n_bridges[j-1]
            else:
                dp[i+1][j] += dp[i][j] * (n_all_cands-n_bridges[j-1]-n_bridges[j])
                dp[i+1][j-1] += dp[i][j] * n_bridges[j-1]
                dp[i+1][j+1] += dp[i][j] * n_bridges[j]
    # ppr(dp)

    return dp[-1][K-1] % (10**9 + 7)


print((main()))


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)


def __starting_point():
    main()
__starting_point()

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

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

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

from itertools import product

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

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


def check_valid_bridge(bridge):
    for i in range(1, w-1):
        if bridge[i-1] and bridge[i]:
            return False
    return True

for t in range(1, h + 1):
    for i in range(1, w + 1):
        X, Y, Z = 0, 0, 0
        if w != 1:
            p = product([True, False], repeat=w-1)            
            for bridge in p:
                if check_valid_bridge(bridge):
                    if i > 1 and bridge[i-2]:
                        X += 1
                    elif i < w and bridge[i-1]:
                        Y += 1
                    elif (i == 1 and not bridge[i-1]) or (i == w and not bridge[i-2]) or (1 < i < w and not bridge[i-2] and not bridge[i-1]):
                        Z += 1
        else:
            Z = 1
        # print(f"{X} {Y} {Z}")
        pattern_1 = dp[t-1][i-1] * X if i > 1 else 0
        pattern_2 = dp[t-1][i+1] * Y if i < w else 0
        pattern_3 = dp[t-1][i] * Z
        dp[t][i] = (pattern_1 + pattern_2 + pattern_3) % mod

# for line in dp:
#     print(*line)
print((dp[h][k]))


# D - Number of Amidakuji

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

comb = []
def dfs(n, p):
    if len(n) == (W-1):
        if len(n) == 0:
            n = [0]
        comb.append(tuple(n))
        return
    for i in (0, 1):
        if p == 1 and i == 1:
            continue
        n.append(i)
        dfs(n, i)
        n.pop()  

dfs([], 0)

dp = [[0] * W for _ in range(H+1)]
dp[0][0] = 1
for h in range(H):
    for w in range(W):
        # まっすぐ降りてくるケース
        tmp = 0
        for i in comb:
            if w == 0 and i[w] == 0:
                tmp += 1
            elif w == (W-1) and i[w-1] == 0:
                tmp += 1
            elif i[w-1] == 0 and i[w] == 0:
                tmp += 1
        dp[h+1][w] += dp[h][w] * tmp

        # 左からくるケース
        if w != 0:
            tmp = 0
            for i in comb:
                if i[w-1] == 1:
                    tmp += 1
            dp[h+1][w] += dp[h][w-1] * tmp        

        # 右からくるケース
        if w != (W-1):
            tmp = 0
            for i in comb:
                if i[w] == 1:
                    tmp += 1
            dp[h+1][w] += dp[h][w+1] * tmp  

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


import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

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

    for _ in range(H):
        dp, dp_prev = [0] * W, dp
        for mask in range(1 << (W - 1)):
            ok = True
            for i in range(W - 2):
                if mask & (1 << i) and mask & (1 << (i + 1)):
                    ok = False
            if not ok:
                continue
            for i in range(W):
                if i > 0 and mask & (1 << (i - 1)):
                    dp[i - 1] = (dp[i - 1] + dp_prev[i]) % MOD
                elif i < W - 1 and mask & (1 << i):
                    dp[i + 1] = (dp[i + 1] + dp_prev[i]) % MOD
                else:
                    dp[i] = (dp[i] + dp_prev[i]) % MOD

    print((dp[K - 1]))

    return


def __starting_point():
    main()

__starting_point()

import sys
readline = sys.stdin.readline
MOD = 10 ** 9 + 7

def main():
    H, W, K = map(int, readline().rstrip().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 k in range(2**(W-1)):
                b = bin(k)[2:].zfill(W-1)
                # 近接する2つの横線がつながってるか判定
                flg = True
                for l in range(W-2):
                    if b[l] == b[l+1] == '1':
                        flg = False
                        break
                if not flg:
                    continue
                if j >= 1 and b[j-1] == '1':
                    # 左方向に横線を辿るケース
                    dp[i+1][j-1] += dp[i][j]
                    dp[i+1][j-1] %= MOD
                elif j <= W-2 and b[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])
    

def __starting_point():
    main()
__starting_point()

import sys

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


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


def __starting_point():
    resolve()

__starting_point()

h, w, k = list(map(int, input().split()))
# h, w, k = 15, 8, 5
# h, w, k = 2, 3, 1
# h, w, k = 2, 3, 3
# h, w, k = 1, 3, 2
p = 10**9+7
# DP[i][j]=i段目まで見て0からjに着くパターン数
# 最終的にDP[h][k-1]を求める
DP = [[0 for j in range(w+1)] for i in range(h+1)]
DP[0][0] = 1
F = [1, 1, 2, 3, 5, 8, 13, 21]
for i in range(h):
    for j in range(w):
        a = DP[i][j-1]*F[j-1]*F[w-1-j]
        b = DP[i][j+1]*F[j]*F[w-2-j]
        c = DP[i][j]*F[j]*F[w-1-j]
        DP[i+1][j] = (a+b+c) % p
print((DP[h][k-1]))


h,w,k = list(map(int,input().split()))
k -= 1
dp = [[0]*w for _ in range(h+1)]
dp[0][0] = 1
mod = 10**9 + 7
def cnt(n):
    if n < 0:
        return 1
    if 0 <= n < 3:
        return n + 1
    return n + (n-1)*(n-2)//2 + (n-2)*(n-3)*(n-4)//6 + 1

for i in range(h):
    for j in range(w):
        if j > 0:
            dp[i+1][j-1] += dp[i][j] * cnt(j-2) * cnt(w-2-j)
            dp[i+1][j-1] %= mod
        if j < w-1:
            dp[i+1][j+1] += dp[i][j] * cnt(j-1) * cnt(w-3-j)
            dp[i+1][j+1] %= mod
        dp[i+1][j] += dp[i][j] * cnt(j-1) * cnt(w-2-j)
        dp[i+1][j] %= mod
print((dp[h][k]))


def main():
    MOD = 10 ** 9 + 7

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

    dp = [[0] * W for _ in range(H + 1)]
    dp[0][0] = 1
    # 横線[0,H)
    # H->終着点

    for h in range(H):
        for bit in range(1 << (W - 1)):
            if '11' in bin(bit): continue
            toes = list(range(W))
            for j in range(W - 1):
                if (bit >> j) & 1:
                    toes[j], toes[j + 1] = toes[j + 1], toes[j]
            for frm, to in enumerate(toes):
                dp[h + 1][to] = (dp[h + 1][to] + dp[h][frm]) % MOD
    ans = dp[H][K - 1]
    print(ans)


def __starting_point():
    main()

# import sys
# input = sys.stdin.readline
# 
# sys.setrecursionlimit(10 ** 7)
# 
# (int(x)-1 for x in input().split())
# rstrip()

__starting_point()

h, w, k = list(map(int, input().split()))
dp = [0] * w
mod = 10 ** 9 + 7

dp[0] = 1
for i in range(h):
    next = [0] * w
    for bit in range(1 << w - 1):
        ok = True
        for j in range(w - 2):
            if bit >> j & 1 and bit >> j + 1 & 1:
                ok = False
        if ok:
            moved = [False] * w
            for j in range(w):
                if bit >> j & 1:
                    next[j + 1] += dp[j]
                    next[j] += dp[j + 1]
                    moved[j] = moved[j + 1] = True
                elif not moved[j]:
                    next[j] += dp[j]
    dp = next
print((dp[k - 1] % mod))


h,w,K = map(int,input().split())
if w == 1:
    print(1)
    return
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
# for i in range(h+1): print(dp[i])
print(dp[h][K])

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)
  return
  
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])

import sys
import math
import collections
import bisect
import copy

# import numpy as np

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

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


# ===CODE===


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:
                # from U
                dp[y][x] += dp[y - 1][x] * fibo[max(0, w - 1 - 1)]
                if w > 1:
                    # from R
                    dp[y][x] += dp[y - 1][x + 1] * fibo[max(0, w - 1 - 2)]
            elif x == w - 1:
                # from U
                dp[y][x] += dp[y - 1][x] * fibo[max(0, w - 1 - 1)]
                if w > 1:
                    # from L
                    dp[y][x] += dp[y - 1][x - 1] * fibo[max(0, w - 1 - 2)]
            else:
                # from U
                dp[y][x] += dp[y - 1][x] * fibo[x - 1] * fibo[max(0, w - 1 - x - 1)]
                # from L
                dp[y][x] += dp[y - 1][x - 1] * fibo[max(0, x - 1 - 1)] * fibo[max(0, w - 1 - x - 1)]
                # from R
                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]))


def __starting_point():
    main()

__starting_point()

#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
#import heapq
#from fractions  import gcd
#input=sys.stdin.readline
#import bisect
Mod=10**9+7
h,w,K=list(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]))


"""
    dp[h][w]: h番目のrow(h: 0~H(終着))で棒w(w: 0~W-1)にいる状態になるための横線(0~h)の組合せ数
    dp[h][w] = A*dp[h-1][w-1] + B*dp[h-1][w] + C*dp[h-1][w+1] O(100*8)
    A, B, Cはなんかうまいこと決めれそう。(全探索でもO(7*7*3))
    o(10**6)には入りそう
    """
def main():
    import sys
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    dp = [[0]*W for _ in range(H+1)]
    dp[0][0] = 1
    for h in range(1, H+1):
        for w in range(W):
            A, B, C = 0, 0, 0
            for i in range(2 ** (W-1)):
                lines = []
                for j in range(W-1):
                    if ((i >> j) & 1):
                        if lines and lines[-1]:
                            break
                        lines.append(True)
                    else:
                        lines.append(False)
                else:
                    if w-1 >= 0 and lines[w-1]:
                        A += 1
                    elif w <= W-2 and lines[w]:
                        C += 1
                    else:
                        B += 1
            if w-1 >= 0:
                dp[h][w] += dp[h-1][w-1] * A
            dp[h][w] += dp[h-1][w] * B
            if w+1 <= W-1:
                dp[h][w] += dp[h-1][w+1] * C
    print(dp[H][K-1] % (10**9+7))
    

def __starting_point():
    main()
__starting_point()

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

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)

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

    bf = [0] * (w + 2)
    nx = [0] * (w + 2)
    bf[1] = 1

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

    for i in range(1, h + 1):
        for j in range(1, w + 1):
            nx[j] = c[j - 1] * c[w - j] * bf[j] + c[j - 1] * c[w - j - 1] * bf[j + 1] + c[j - 2] * c[w - j] * bf[j - 1]

        bf = nx
        nx = [0] * (w + 2)

    print((bf[k] % (10 ** 9 + 7)))


def __starting_point():
    main()

__starting_point()

import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

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

    for _ in range(H):
        dp, dp_prev = [0] * W, dp
        for mask in range(1 << (W - 1)):
            ok = True
            for i in range(W - 2):
                if mask & (1 << i) and mask & (1 << (i + 1)):
                    ok = False
                    break
            if not ok:
                continue
            for i in range(W):
                if i > 0 and mask & (1 << (i - 1)):
                    dp[i - 1] = (dp[i - 1] + dp_prev[i]) % MOD
                elif i < W - 1 and mask & (1 << i):
                    dp[i + 1] = (dp[i + 1] + dp_prev[i]) % MOD
                else:
                    dp[i] = (dp[i] + dp_prev[i]) % MOD

    print((dp[K - 1]))

    return


def __starting_point():
    main()

__starting_point()

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

if w == 1:
    print(1)
    return

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

l = [[0]*3 for i in range(w)]

for i in range(2**(w-1)):
    if "11" in bin(i):
        continue

    for j in range(w-1):
        if (i >> j) & 1:        
            l[j][2] += 1
            l[j+1][0] += 1

fib = [1,1]
for i in range(10):
    fib.append(fib[-1]+fib[-2])
for i in l:
    i[1] = fib[w] - sum(i)

for i in range(h):
    for j in range(w):
        dp[i+1][j] += dp[i][j]*l[j][1]%mod
        if j != 0:
            dp[i+1][j] += dp[i][j-1]*l[j][0]%mod
        if j != w-1:
            dp[i+1][j] += dp[i][j+1]*l[j][2]%mod
        dp[i+1][j] %= mod

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

import sys
readline = sys.stdin.readline
MOD = 10 ** 9 + 7

def main():
    H, W, K = map(int, readline().rstrip().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 k in range(2**(W-1)):
                b = bin(k)[2:].zfill(W-1)
                # 2つの横線がつながってないか調べる
                flg = True
                for l in range(W-2):
                    if b[l] == b[l+1] == '1':
                        flg = False
                        break
                if not flg:
                    continue
                if j >= 1 and b[j-1] == '1':
                    # 左方向に横線を辿るケース
                    dp[i+1][j-1] += dp[i][j]
                    dp[i+1][j-1] %= MOD
                elif j <= W-2 and b[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])
    

def __starting_point():
    main()
__starting_point()

import sys

input = sys.stdin.readline


def main():
    H, W, K = [int(x) for x in input().split()]
    MOD = 10 ** 9 + 7

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

    cnt = [0] * (W - 1)
    cntz = [0] * W
    for i in range(2 ** (W - 1)):
        tmp = [0] * (W - 1)
        for j in range(W - 1):
            if i >> j & 1:
                tmp[j] += 1
        # 2辺連続で引かれていないかをチェック
        for j, k in zip(tmp, tmp[1:]):
            if j == k == 1:
                break
        else:
            # チェックをパスした状態をカウント
            for j in range(W - 1):
                cnt[j] += tmp[j]
            for j in range(W):
                if j == 0:
                    if tmp[j] == 0:
                        cntz[j] += 1
                elif j == W - 1:
                    if tmp[j - 1] == 0:
                        cntz[j] += 1
                else:
                    if tmp[j] == tmp[j - 1] == 0:
                        cntz[j] += 1

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

    for j in range(H):
        for i in range(W):
            if i == 0:
                dp[j + 1][i] += dp[j][i] * cntz[i]
                dp[j + 1][i + 1] += dp[j][i] * cnt[i]
                dp[j + 1][i] %= MOD
                dp[j + 1][i + 1] %= MOD
            elif i == W - 1:
                dp[j + 1][i] += dp[j][i] * cntz[i]
                dp[j + 1][i - 1] += dp[j][i] * cnt[i - 1]
                dp[j + 1][i] %= MOD
                dp[j + 1][i - 1] %= MOD
            else:
                dp[j + 1][i] += dp[j][i] * cntz[i]
                dp[j + 1][i + 1] += dp[j][i] * cnt[i]
                dp[j + 1][i - 1] += dp[j][i] * cnt[i - 1]
                dp[j + 1][i] %= MOD
                dp[j + 1][i + 1] %= MOD
                dp[j + 1][i - 1] %= MOD

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


def __starting_point():
    main()

__starting_point()

def fib(n):
    a = 1
    b = 0
    i = 0
    while i < n:
        i += 1
        c = a + b
        yield c
        a = b
        b = c


def main():
    h, w, k = list(map(int, input().split()))
    mod = 10 ** 9 + 7
    
    dp = [[0] * (w + 2) for _ in range(h + 1)]
    dp[0][1] = 1
    c = [i for i in fib(w + 1)]

    for i in range(1, h + 1):
        for j in range(1, w + 1):
            x = c[j - 1] * c[w - j]
            y = c[j - 1] * c[w - j - 1]
            z = c[j - 2] * c[w - j]

            dp[i][j] = (x * dp[i - 1][j] + y * dp[i - 1][j + 1] + z * dp[i - 1][j - 1]) % mod

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


def __starting_point():
    main()

__starting_point()

from itertools import product

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

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

pats = [pat for pat in product([1, 0], repeat=w-1)]

for i in range(1, h + 1):
	for j in range(w):
		for pat in pats:
			valid = True
			for e1, e2 in zip(pat, pat[1:]):
				if e1 and e2:
					valid = False

			if not valid:
				continue

			if j - 1 >= 0 and pat[j-1]:
				dp[i][j] += dp[i-1][j-1]

			elif j <= w - 2 and pat[j]:
				dp[i][j] += dp[i-1][j+1]

			else:
				dp[i][j] += dp[i-1][j]

			dp[i][j] %= mod

ans = dp[h][k-1]
print(ans)
#print(*dp, sep="\n")


def main():
    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
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    mod = 10**9 + 7

    h,w,k = map(int, input().split())
    dp = [[0]*w for _ in range(h+1)]
    dp[0][0] = 1

    pattern = []
    if w > 2:
        for i in range(1<<(w-1)):
            for j in range(w-2):
                if ((i>>j) & 1) and ((i>>(j+1)) & 1):
                    break
            else:
                pattern.append(i)
    else:
        print(1)
        return
    
    for i in range(h):
        for j in range(w):
            for p in pattern:
                if j == 0:
                    if p & 1:
                        dp[i+1][j+1] += dp[i][j] % mod
                    else:
                        dp[i+1][j] += dp[i][j] % mod
                elif j == w-1:
                    if (p>>(w-2)) & 1:
                        dp[i+1][j-1] += dp[i][j] % mod
                    else:
                        dp[i+1][j] += dp[i][j] % mod
                else:
                    if (p>>(j-1)) & 1:
                        dp[i+1][j-1] += dp[i][j] % mod
                    elif (p>>j) & 1:
                        dp[i+1][j+1] += dp[i][j] % mod
                    else:
                        dp[i+1][j] += dp[i][j] % mod
    print(dp[-1][k-1] % mod)


def __starting_point():
    main()
__starting_point()

MOD = 10 ** 9 + 7
h, w, k = list(map(int, input().split()))
dp = [0] * w
dp[0] = 1

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

def f(i):
    if i < 0:
        return 1
    return fdp[i][0] + fdp[i][1]

for _ in range(h):
    ndp = [0] * w
    for i in range(w):
        ndp[i] = (ndp[i] + dp[i] * f(i - 1) * f(w - i - 2))  % MOD
        if i + 1 < w:
            ndp[i+1] = (ndp[i+1] + dp[i] * f(i - 1) * f(w - i - 3)) % MOD
        if i - 1 >= 0:
            ndp[i-1] = (ndp[i-1] + dp[i] * f(i - 2) * f(w - i - 2)) % MOD
    dp = ndp
print((dp[k-1]))


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

MOD = 10 ** 9 + 7
h, w, k = [int(x) for x in input().split()]
dp = [[0] * w for _ in range(h+1)]
dp[0][0] = 1
for i in range(h):
    for b in range(1 << (w-1)):
        ok = True
        for s in range(w-2):
            if b >> s & 1 and b >> (s+1) & 1:
                ok = False
        if ok:            
            for j in range(w):
                if j > 0 and b >> (j-1) & 1:
                    dp[i+1][j-1] = (dp[i+1][j-1] + dp[i][j]) % MOD
                elif j+1 < w and b >> j & 1:
                    dp[i+1][j+1] = (dp[i+1][j+1] + dp[i][j]) % MOD
                else:
                    dp[i+1][j] = (dp[i+1][j] + dp[i][j]) % MOD

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

'''3/18 AtCoder（漸化式dp）
一番左の棒からスタートして、K番目の棒に到達するようなあみだくじは
何通り作れますかという趣旨の問題
まず、この問題を解くうえで一番重要なのは、
「ある高さh、棒jに至る経路の総数を求める漸化式が立てられる」ということ
高さh、棒jに至る経路の総数をdp[h][j]とすれば、
高さh-1からこの位置に至ることができるのは、
棒j-1,j,j+1のいずれかしかない
さらに、そこに至る経路数というのは結局
「ほかの棒にどんな風に架け橋（横棒）がかかっているか」の場合の数なので、
それをdp[h-1][j-1],dp[h-1][j],dp[h-1][j+1]にかけていく必要がある
例えば、dp[h-1][j]を見てみる　これは、同じ棒から下ってくることを
意味しているが、換言すれば「高さi-1とiには、棒jから伸びる横棒はない」
ということである
つまり、この高さにおける横棒の架かり方というのは
「棒1~j-1までの架かり方」と「棒j+1~棒Wまでの架かり方」の
二パターンしかないということになる
ある高さにおける横棒のかかり方も漸化式で求められる　
高さhにおける(横一列にかけ橋が並んでいる状況を考える）、
n本の棒の間にかかる橋の場合の数の総数をf(n)と置くと、
f(n) = f(n-1)+f(n-2)と書くことができる
これは、f(n)が
①n本目とn-1本目の棒の間に橋が架かっていない→場合の数はf(n-2)と同じ
②n本目とn-1本目の棒の間に橋が架かっている→場合の数はf(n-1)と同じ
の二パターンの合計だからである
だから、dp[h-1][j]に掛ける数はいくつかということを考えたら、
j-1本の棒の間にかかる橋の場合の数f(j-1)と、
W-j本の棒の間にかかる橋の場合の数f(W-j)本ということになる　
これと同様に、残り二本に対してもいくつかければよいかを考えて、
dp[h][j]]に対する漸化式を立てればよい
'''
H,W,K = map(int,input().split())
dp = []
for i in range(H+1): #高さ0の分を余分に持っておく
  L = [0]*W
  dp.append(L)
fb = [1,1] #フィボナッチ（f(n)=f(n-1)+f(n-2)）
for i in range(W-2):
  fb.append(fb[i]+fb[i+1])
dp[0][0] = 1 #左端の棒の高さ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)) #高さH（一番下）、K-1番目の棒を調べる

H, W, K = list(map(int, input().split()))
h_lines = (1, 1, 2, 3, 5, 8, 13, 21, 34)
MOD = 10 ** 9 + 7

dp = [[0] * 8 for _ 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] * h_lines[w] * h_lines[W - w - 1]
        if w > 0:
            dp[h + 1][w] += dp[h][w - 1] * h_lines[w - 1] * h_lines[W - w - 1]
        if w < W - 1:
            dp[h + 1][w] += dp[h][w + 1] * h_lines[w] * h_lines[W - w - 2]
        dp[h + 1][w] %= MOD
print((dp[H][K - 1]))


def is_valid(k):
    n = k.bit_length()

    for i in range(n - 1):
        if (k >> i) & 1 and (k >> i + 1) & 1:
            return False

    return True

p = 10**9+7

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

dp = [[0]*W for _ in range(H + 1)]
# dp[i][j] : i段目までみたときjにいくようなあみだくじの本数

dp[0][0] = 1

for i in range(H):
    for j in range(1 << (W - 1)):
        if not is_valid(j): continue
        for k in range(W):
            if k < W - 1 and (j >> k) & 1:
                dp[i + 1][k + 1] += dp[i][k]
                dp[i + 1][k + 1] %= p
            elif k > 0 and (j >> (k - 1)) & 1:
                dp[i + 1][k - 1] += dp[i][k]
                dp[i + 1][k - 1] %= p
            else:
                dp[i + 1][k] += dp[i][k]
                dp[i + 1][k] %= p

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

# 解説と下記を参考に作成
# https://atcoder.jp/contests/abc113/submissions/15821617
# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque
# from decorator import stop_watch
#
#
# @stop_watch
def solve(H, W, K):
    mod = 10 ** 9 + 7
    dp = [[0] * W for _ in range(H + 1)]
    dp[0][0] = 1
    fibo = [1, 2, 3, 5, 8, 13, 21]
    for h in range(H):
        for w in range(W):
            if dp[h][w] == 0:
                continue
            for i in range(3):
                new_w = w - 1 + i
                if not 0 <= new_w < W:
                    continue
                l, r = min(w, new_w), max(w, new_w)
                tmp = fibo[max(l - 1, 0)] * fibo[max(W - 1 - (r + 1), 0)]
                dp[h + 1][new_w] += dp[h][w] * tmp
                dp[h + 1][new_w] %= mod
    print((dp[-1][K - 1]))


def __starting_point():
    H, W, K = list(map(int, input().split()))
    solve(H, W, K)

    # # test
    # from random import randint
    # from func import random_str
    # solve()

__starting_point()

"""
    dp[h][w]: h番目のrow(h: 0~H(終着))で棒w(w: 0~W-1)にいる状態になるための横線(0~h)の組合せ数
    dp[h][w] = A*dp[h-1][w-1] + B*dp[h-1][w] + C*dp[h-1][w+1] O(100*8)
    A, B, Cはなんかうまいこと決めれそう。(全探索でもO(7*7*7))
    """
def main():
    import sys
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    dp = [[0]*W for _ in range(H+1)]
    dp[0][0] = 1
    for h in range(1, H+1):
        for w in range(W):
            A, B, C = 0, 0, 0
            for i in range(2 ** (W-1)):
                lines = []
                for j in range(W-1):
                    if ((i >> j) & 1):
                        if lines and lines[-1]:
                            break
                        lines.append(True)
                    else:
                        lines.append(False)
                else:
                    if w-1 >= 0 and lines[w-1]:
                        A += 1
                    elif w <= W-2 and lines[w]:
                        C += 1
                    else:
                        B += 1
            if w-1 >= 0:
                dp[h][w] += dp[h-1][w-1] * A
            dp[h][w] += dp[h-1][w] * B
            if w+1 <= W-1:
                dp[h][w] += dp[h-1][w+1] * C
    print(dp[H][K-1] % (10**9+7))
    

def __starting_point():
    main()
__starting_point()

MOD = 10**9+7
H, W, K = list(map(int, input().split()))
dp = [[0]*W for _ 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)):
            # 2つの横線がつながっていないか調べる
            ok = True
            for l in range(W-2):
                if (k>>l)&1 and (k>>(l+1))&1:
                    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-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[H][K-1]))


h, w, k = list(map(int, input().split()))
dp = [0] * w
mod = 10 ** 9 + 7

comb = []
for bit in range(1 << w - 1):
    ok = True
    for j in range(w - 2):
        if bit >> j & 1 and bit >> j + 1 & 1:
            ok = False
    if ok:
        comb.append(bit)

dp[0] = 1
for i in range(h):
    next = [0] * w
    for bit in comb:
        moved = [False] * w
        for j in range(w):
            if bit >> j & 1:
                next[j + 1] += dp[j]
                next[j] += dp[j + 1]
                moved[j] = moved[j + 1] = True
            elif not moved[j]:
                next[j] += dp[j]
    dp = next
print((dp[k - 1] % mod))


h, w, k = map(int, input().split())
p = 10**9+7
DP = [[0 for j in range(w+1)] for i in range(h+1)]
DP[0][0] = 1
F = [1, 2, 3, 5, 8, 13, 21][:w]+[1]
for i in range(h):
    for j in range(w):
        a = DP[i][j-1]*F[j-2]*F[w-2-j]
        b = DP[i][j]*F[j-1]*F[w-2-j]
        c = DP[i][j+1]*F[j-1]*F[w-3-j]
        DP[i+1][j] = (a+b+c) % p
print(DP[h][k-1])

H,W,K = map(int,input().split())
dp = [[0]*W for i in range(H+1)]
dp[0][0] = 1
MOD = 10**9+7
for i in range(H):
    for b in range(1<<(W-1)):
        if '11' in bin(b): continue
        for k in range(W):
            if k and b&(1<<(k-1)):
                dp[i+1][k-1] += dp[i][k]
            elif b&(1<<k):
                dp[i+1][k+1] += dp[i][k]
            else:
                dp[i+1][k] += dp[i][k]
print(dp[-1][K-1] % MOD)

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

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

OK = [0, 1, 1, 2, 3, 5, 8, 13]
NG = [0, 1, 2, 3, 5, 8, 13, 21]

if W == 1:
  print(dp[K-1])
else:
  for _ in range(H):
    temp = dp[:]
    for i in range(W):
      if i == 0:
        dp[i] = temp[i] * NG[W-1-i] + temp[i+1] * OK[W-1-i]
      elif i == W-1:
        dp[i] = temp[i-1] * OK[i] + temp[i] * NG[i]
      else:  
        dp[i] = temp[i-1] * OK[i] * NG[W-1-i] + temp[i] * NG[i] * NG[W-1-i] + temp[i+1] * NG[i] * OK[W-1-i]
      dp[i] %= mod
  print(dp[K-1])

fib = [1, 1, 2, 3, 5, 8, 13, 21]
mod = 1000000007
h, w, k = list(map(int, input().split()))
k -= 1
p = [0] * w
p[0] = 1
for i in range(h):
  q = [0] * w
  for j in range(w):
    if j > 0:
      q[j] += p[j - 1] * fib[j - 1] * fib[w - 1 - j]
    if j < w - 1:
      q[j] += p[j + 1] * fib[j] * fib[w - j - 2]
    if 0 < j < w - 1:
      q[j] += p[j] * fib[j] * fib[w - j - 1]
    elif j > 0:
      q[j] += p[j] * fib[j]
    elif j < w - 1:
      q[j] += p[j] * fib[w - j - 1]
    else:
      q[j] += p[j]
    q[j] %= mod
  p = q
print((p[k]))


h,w,k=map(int,input().split())
mod=10**9+7
dp=[0]*w
dp[0]=1
fib=[1,1,2,3,5,8,13,21,34,55,89]
for _ in range(h):
  t=[0]*w
  for i in range(w):
    if i>0:
      t[i]+=dp[i-1]*fib[i-1]*fib[w-i-1]
    t[i]+=dp[i]*fib[i]*fib[w-i-1]
    if i<w-1:
      t[i]+=dp[i+1]*fib[i]*fib[w-i-2]
    t[i]%=mod
  dp=t
print(dp[k-1])

h,w,k=map(int,input().split())
dp=[0]*(w)
l=[1,1,2,3,5,8,13,21,34]#n本の縦線に高さ1のvalidな横棒を引く通り、フィボナッチ数列になる
#a_n:=n本の縦線にvalidな横棒を引く通りの総数、とすれば
#n+1本の時は1.1と2本目に横棒を引く（2と3の間に引けないのでa_n-1通り）
#          2.                引かない（a_n通り）
#よって漸化式a_n+1=a_n+a_n-1が成立。
dp[0]=1
mod=10**9+7
r=[0]*w
for i in range(h):
    for i in range(w):
        r[i]=dp[i]*l[i]*l[w-1-i]#左右に横棒を引かない
        if i>=1:
            r[i]+=dp[i-1]*l[i-1]*l[w-1-i]#左にのみ横棒を引く
        if i<=w-2:
            r[i]+=dp[i+1]*l[i]*l[w-2-i]#右にのみ横棒を引く
        r[i]%=mod
    dp,r=r,dp

print(dp[k-1])

def fib():
    a = 1
    b = 0
    while 1:
        c = a + b
        yield c
        a = b
        b = c


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

    dp = [[0] * (w + 2) for _ in range(h + 1)]
    dp[0][1] = 1
    f = fib()
    c = [f.__next__() for _ in range(w + 1)]

    for i in range(1, h + 1):
        for j in range(1, w + 1):
            dp[i][j] = c[j - 1] * c[w - j] * dp[i - 1][j] + c[j - 1] * c[w - j - 1] * dp[i - 1][j + 1] + c[j - 2] * c[w - j] * dp[i - 1][j - 1]

    print((dp[h][k] % (10 ** 9 + 7)))


def __starting_point():
    main()

__starting_point()

from itertools import product

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

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

pats = [pat for pat in product([1, 0], repeat=w-1)]

for i in range(h):
	for j in range(w):
		for pat in pats:
			valid = True
			for e1, e2 in zip(pat, pat[1:]):
				if e1 and e2:
					valid = False

			if not valid:
				continue

			if j - 1 >= 0 and pat[j-1]:
				dp[i+1][j-1] += dp[i][j]
				dp[i+1][j-1] %= mod

			elif j <= w - 2 and pat[j]:
				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

ans = dp[h][k-1]
print(ans)
#print(*dp, sep="\n")


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

mod = 10**9 + 7
   

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

for i in range(h):
    for bit in range(1<<(w-1)):
        if '11' in bin(bit) : continue
        for j in range(w):
            if j > 0 and bit & (1 << (j-1)):
                dp[i+1][j-1] += dp[i][j] % mod 
            elif bit & (1 << j):
                dp[i+1][j+1] += dp[i][j] % mod
            else:
                dp[i+1][j] += dp[i][j] % mod
                
print(dp[h][k-1]%mod)

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

def check(bit):
  pre_b = '0'
  for b in bit:
    if b == '1' and pre_b == '1':
      return False
    pre_b = b
  return True

# dp[h][w]:上からh段目での操作を終了した時点でw番目のあみだにいる場合の数
dp = [[0]*(W+2) for h in range(H+1)]
dp[0][1] = 1

# ある段における横線の配置を全探索してw-1 <-> wに横線がある数
lines = [0] * (W+1)
c = 0
for i in range(2**(W-1)):
  if not check(bin(i)[2:]):
    continue
  c += 1
  for w in range(W-1):
    lines[w+1] += (i & 1<<w) > 0


# 配るDP
for h in range(H):
  for w in range(1, W+1):
    x, z = lines[w-1], lines[w]
    y = c - x - z
    dp[h+1][w-1] = (dp[h+1][w-1] + dp[h][w]*x % MOD) % MOD
    dp[h+1][w] = (dp[h+1][w] + dp[h][w]*y % MOD) % MOD
    dp[h+1][w+1] = (dp[h+1][w+1] + dp[h][w]*z % MOD) % MOD

print(dp[-1][K])

import sys

h, w, k = map(int, input().split())
mod = 10 ** 9 + 7
if w == 1:
    print(1)
    return
row = [0 for i in range(w + 1)]
row[0] = 1
row[1] = 1
for i in range(w - 1):
    row[i + 2] = row[i + 1] + row[i]

dp = [[0 for i in range(w)] for j in range(h + 1)]
dp[0][0] = 1
for i in range(h):
    for j in range(w):
        if j == 0:
            dp[i + 1][j] = dp[i][j] * row[w - 1] + dp[i][j + 1] * row[w - 2]
            dp[i + 1][j] %= mod
        elif j == w - 1:
            dp[i + 1][j] = dp[i][j] * row[w - 1] + dp[i][j - 1] * row[w - 2]
            dp[i + 1][j] %= mod
        else:
            dp[i + 1][j] = dp[i][j - 1] * row[j - 1] * row[w - j - 1] + dp[i][j] * row[j] * row[w - j - 1] + dp[i][j + 1] * row[j] * row[w - j - 2]
            dp[i + 1][j] %= mod
print(dp[h][k - 1])

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

mod = 10 ** 9 + 7

if w == 1:
    print(1)
    return

n_join = [0 for i in range(w-1)]
n_unjoin = [0 for i in range(w-1)]
cnt = 0

for i in range(2 ** (w-1)):
    p = 0
    f = 1
    tmp_join = []
    tmp_unjoin = []
    for j in range(w-1):
        c = i & (1 << j)
        if c:
            tmp_join.append(j)
        if not (c or p):
            tmp_unjoin.append(j)
        if p and c:
            f = 0
            break
        p = c
    if f:
        cnt += 1
        for j in tmp_join:
            n_join[j] += 1
        for j in tmp_unjoin:
            n_unjoin[j] += 1

n_unjoin.append(cnt - n_join[-1])

dp = [[0 for j in range(w)] for i in range(h)]
dp[0][0] = n_unjoin[0]
dp[0][1] = n_join[0]

for i in range(1,h):
    for j in range(w):
        dp[i][j] += dp[i-1][j] * n_unjoin[j] % mod
        dp[i][j] %= mod
        if j > 0:
            dp[i][j] += dp[i-1][j-1] * n_join[j-1] % mod
            dp[i][j] %= mod
        if j < w - 1:
            dp[i][j] += dp[i-1][j+1] * n_join[j] % mod
            dp[i][j] %= mod
        
print(dp[h-1][k-1])

#float型を許すな
#numpyは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 list(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
#print(weight)    
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))




H,W,K = map(int,input().split())
mod = 10**9+7
dp = W*[0]
dp[0] = 1
fib = [1,1,2,3,5,8,13,21,34,55,89]

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

print(dp[K-1])


from itertools import product


def patterns(w):
    res = []
    for pt in product([0, 1], repeat=w):
        valid = True
        for i in range(w - 1):
            if pt[i] == pt[i + 1] == 1:
                valid = False
                break
        if valid:
            res.append(pt)
    return res


def submit():
    h, w, k = [int(e) for e in input().split()]
    dp = [[0 for _ in range(w)] for _ in range(h + 1)]
    dp[0][0] = 1
    modp = 10 ** 9 + 7

    pts = patterns(w - 1)

    for i in range(1, h + 1):
        for j in range(w):
            for pt in pts:
                if j > 0 and pt[j - 1] == 1: # j -> j - 1に遷移する
                    dp[i][j - 1] += dp[i - 1][j]
                    dp[i][j - 1] %= modp
                elif j < w - 1 and pt[j] == 1:  # j -> j + 1に遷移する
                    dp[i][j + 1] += dp[i - 1][j]
                    dp[i][j + 1] %= modp
                else:
                    dp[i][j] += dp[i - 1][j]
                    dp[i][j] %= modp


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


submit()

from itertools import product
H, W, K = list(map(int, input().split()))
mod = 10 ** 9 + 7

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

up = [0] * W
right = [0] * W
left = [0] * W

for b in range(1 << (W - 1)):
    bridge = bin(b)[2:].zfill(W - 1)
    if "11" in bridge:
        continue

    # 左の棒
    if bridge[0] == "0":
        up[0] += 1
    else:
        right[0] += 1

    # 右の棒
    if bridge[-1] == "0":
        up[W - 1] += 1
    else:
        left[W - 1] += 1

    # 真ん中
    for i in range(1, W - 1):
        if bridge[i - 1] == "0" and bridge[i] == "1":
            right[i] += 1
        elif bridge[i - 1] == "1" and bridge[i] == "0":
            left[i] += 1
        else:
            up[i] += 1

up = [0] + up + [0]
right = [0] + right + [0]
left = [0] + left + [0]

dp = [0] * (W + 2)
dp[K] = 1
for _ in range(H):
    newDP = [0] * (W + 2)
    for i in range(1, W + 1):
        newDP[i] += dp[i - 1] * right[i - 1]
        newDP[i] += dp[i] * up[i]
        newDP[i] += dp[i + 1] * left[i + 1]
        newDP[i] %= mod
    dp = newDP

ans = dp[1]
print(ans)


w = [1, 2]
for i in range(6):
    w.append(w[-2] + w[-1])
H, W, K = map(int,input().split())
mod = 10 ** 9 + 7
dp = [[0 for i in range(W)] for j in range(H+1)]
dp[0][0] = 1
for i in range(H):
    for j in range(W):
        if j >= 1:
            k = 1
            if j - 2 >= 0:
                k *= w[j - 2]
            if W - j - 2 >= 0:
                k *= w[W - j - 2]
            dp[i+1][j-1] += k * dp[i][j]
            dp[i+1][j-1] %= mod
        k = 1
        if j - 1 >= 0:
            k *= w[j - 1]
        if  W - j - 2 >= 0:
            k *= w[W - j - 2]
        dp[i+1][j] += k * dp[i][j]
        dp[i+1][j] %= mod
        if j <= W - 2:
            k = 1
            if j - 1 >= 0:
                k *= w[j - 1]
            if W - j - 3 >= 0:
                k *= w[W - j - 3]
            dp[i+1][j+1] += k * dp[i][j]
            dp[i+1][j+1] %= mod

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

h,w,k=map(int,input().split())
dp=[[0 for _ in range(w)]for _ in range(h+1)]
dp[0][0]=1
mod=10**9+7
for i in range(h):
    for bit in range(2**(w-1)):
        bit=bin(bit)[2:].zfill(w-1)
        f=0
        for j in range(w-2):
            if bit[j]=='1' and bit[j+1]=='1':
                f=1
                break
        if f:
            continue
        for j in range(w):
            if j==0:
                dp[i+1][j]+=dp[i][j+1] if bit[0]=='1' else dp[i][j]
            elif j==w-1:
                dp[i+1][j]+=dp[i][j-1] if bit[-1]=='1' else dp[i][j]
            else:
                dp[i+1][j]+=dp[i][j]*(bit[j-1]=='0' and bit[j]=='0')
                dp[i+1][j]+=dp[i][j-1]*(bit[j-1]=='1')
                dp[i+1][j]+=dp[i][j+1]*(bit[j]=='1')
            dp[i+1][j]%=mod
print(dp[-1][k-1])

# Python3 (3.4.3)
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------


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

mod = 10**9+7

# 左(あるいは右)にn本の縦棒があり、真横と繋がっている時の場合の数
j = [0,1,1,2,3,5,8,13];
# 左(あるいは右)にn本の縦棒があり、真横と繋がっていない時の場合の数
m = [1,1,2,3,5,8,13,21];
 
# dp[h][w] : h行目を終えた時点でwにいる場合の数
dp = [[0 for _ in range(W)] for _ in range(H+1)]
dp[0][0] = 1
 
for h in range(H+1):
    for w in range(W):
        # 右に移動
        if w != 0:
            dp[h][w] += dp[h-1][w-1] * j[w] * m[W-1-w]
        # 左に移動
        if w != W-1:
            dp[h][w] += dp[h-1][w+1] * m[w] * j[W-1-w]
        # 真下に移動
        dp[h][w] += dp[h-1][w] * m[w] * m[W-1-w]
        
        dp[h][w] %= mod;

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

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

# 連続するn区間に橋をかける方法は何通りあるか
# kakekata[b][i] : bが0の時はi区間目に橋をかけない方法 bが1の時はi区間目に橋をかける方法 が何通りあるか
kakekata = [[0] * 10] + [[0] * 10]
kakekata[0][0] = 1
for i in range(8):
    kakekata[0][i + 1] = kakekata[0][i] + kakekata[1][i]
    kakekata[1][i + 1] = kakekata[0][i]


MOD = 10 ** 9 + 7
class modint:
    def __init__(self, x):
        self.x = x.x if isinstance(x, modint) else x % MOD
    def __str__(self): return str(self.x)
    __repr__ = __str__
    def __int__(self): return self.x
    __index__ = __int__
    def __add__(self, other): return modint(self.x + modint(other).x)
    def __sub__(self, other): return modint(self.x - modint(other).x)
    def __mul__(self, other): return modint(self.x * modint(other).x)
    def __pow__(self, other): return modint(pow(self.x, modint(other).x, MOD))
    def __floordiv__(self, other): return modint(self.x * pow(modint(other).x, MOD - 2, MOD))
    def __eq__(self, other): return self.x == modint(other).x
    def __ne__(self, other): return self.x != modint(other).x
    def __inv__(self): return pow(self.x, MOD - 2, MOD)


dp = [[modint(0)] * (W + 2) for h in range(H + 1)]
dp[0][1] += 1
for h in range(H):
    for w in range(1, W + 1):
        # 左に何区間あるか 右に何区間あるか
        l, r = w - 1, W - w

        # そのまま渡す
        dp[h + 1][w] += dp[h][w] * kakekata[0][l] * kakekata[0][r]
        # 右に渡す
        dp[h + 1][w + 1] += dp[h][w] * kakekata[0][l] * kakekata[1][r]
        # 左に渡す
        dp[h + 1][w - 1] += dp[h][w] * kakekata[1][l] * kakekata[0][r]

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


h,w,K=list(map(int,input().split()))
def two(x):
	return "0"*(w-1-len(bin(x)[2:]))+bin(x)[2:]
dp=[[0]*w for _ in range(h+1)]
dp[0][0]=1
mod=10**9+7
for i in range(h):
	for j in range(2**(w-1)):
		r=two(j)
		f=1
		for k in range(w-2):
			if r[k]==r[k+1]=="1":
				f=0
				break
		if f:
			for k in range(w):
				if k+1<w:
					if r[k]=="1":
						dp[i+1][k+1]+=dp[i][k]
						dp[i+1][k+1]%=mod
						continue
				if k>0:
					if r[k-1]=="1":
						dp[i+1][k-1]+=dp[i][k]
						dp[i+1][k-1]%=mod
						continue
				dp[i+1][k]+=dp[i][k]
				dp[i+1][k]%=mod
print((dp[h][K-1]))



#実はDPと割り切るとわかりやすい
mod=10**9+7
h,w,K=map(int,input().split())
dp=[[0]*w for j in range(h+1)]
dp[0][0]=1
for i in range(1,h+1):
    for k in range(2**(w-1)):
        for l in range(w-2):
            if ((k>>l)&1) and ((k>>(l+1))&1):
                break
        else:
            for l in range(w):
                if l==0:
                    if ((k>>l)&1):
                        dp[i][l+1]+=dp[i-1][l]
                    else:
                        dp[i][l]+=dp[i-1][l]
                elif l==w-1:
                    if ((k>>(l-1))&1):
                        dp[i][l-1]+=dp[i-1][l]
                    else:
                        dp[i][l]+=dp[i-1][l]
                else:
                    if ((k>>l)&1) or ((k>>(l-1))&1):
                        if ((k>>l)&1):
                            dp[i][l+1]+=dp[i-1][l]
                        else:
                            dp[i][l-1]+=dp[i-1][l]
                    else:
                        dp[i][l]+=dp[i-1][l]
            #dp[i][l]%=mod
print(dp[h][K-1]%mod)

import sys
readline = sys.stdin.readline

# 0-indexedで考える
# 縦棒はW本、横棒を置ける場所は一行あたりW - 1箇所となる
# ・iとi + 1の間に横棒を引いた場合の数
# ・iから移動せずにそのままになる場合の数
# をそれぞれ求める

# LINE[i] = iとi + 1の間に横棒を引いた場合の数。
# POINT[i] = iから横棒が出ていない場合の数
# それぞれDPで求める

H,W,K = list(map(int,readline().split()))
DIV = 1000000007

# dp[i][j] = 間隔iまで処理したときに、j番目の間隔に棒がある(0,1)場合の数
LINE = [-1] * (W - 1)
for i in range(W - 1):
  # iとi + 1の間に棒がある場合
  dp = [[0] * 2 for j in range(W - 1)]
  if i == 0:
    dp[0][0] = 0
    dp[0][1] = 1
  else:
    dp[0][0] = 1
    dp[0][1] = 1
  for j in range(1, W - 1):
    if j == i:
      dp[j][0] = 0
      dp[j][1] = dp[j - 1][0]
    else:
      dp[j][0] += dp[j - 1][0] + dp[j - 1][1]
      dp[j][1] += dp[j - 1][0]
  LINE[i] = dp[-1][0] + dp[-1][1]
  LINE[i] %= DIV

POINT = [-1] * W
# 点iからまっすぐ下がる場合の数
# iから右に棒を引く/引かない場合の数を数える
for i in range(W):
  # i - 1にもiにも棒がない場合
  dp = [[0] * 2 for j in range(W)]
  if i - 1 == 0 or i == 0:
    dp[0][0] = 1
    dp[0][1] = 0
  else:
    dp[0][0] = 1
    dp[0][1] = 1
  for j in range(1, W):
    if j == i - 1 or j == i:
      dp[j][1] = 0
      dp[j][0] += dp[j - 1][0] + dp[j - 1][1]
    else:
      dp[j][0] += dp[j - 1][0] + dp[j - 1][1]
      if j == W - 1:
        dp[j][1] = 0
      else:
        dp[j][1] += dp[j - 1][0]
  POINT[i] = dp[-1][0] + dp[-1][1]
  POINT[i] %= DIV
  
# ここからDP
# dp[i][j] = あみだのi段目でjにいる場合の数

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

for i in range(1, len(dp)):
  for j in range(W):
    # jを出発点にして遷移する
    if j - 1 >= 0:
      dp[i][j] += dp[i - 1][j - 1] * LINE[j - 1]
    dp[i][j] += dp[i - 1][j] * POINT[j]
    if j + 1 < W:
      dp[i][j] += dp[i - 1][j + 1] * LINE[j]
      
    dp[i][j] %= DIV
    
print((dp[H][K - 1]))


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

# H = 1, 縦棒W本のあみだくじの数　→フィボナッチ数列
h1amida = [1, 1, 2] + [None] * 6
for i in range(3, 9):
    h1amida[i] = h1amida[i - 2] + h1amida[i - 1]

# dp[h][k] = 縦棒の長さh+1、縦棒の本数W、ゴールの棒kとなるあみだの数
# dp[0][*]とdp[*][0]はダミー
dp = [[0 for _ in range(W + 1)] for _ in range(H + 1)]

for k in range(1, W + 1):
    if k == 1:
        dp[1][k] = h1amida[W - 1]
    elif k == 2:
        dp[1][k] = h1amida[W - 2]
    else:
        dp[1][k] = 0

for h in range(2, H + 1):
    for k in range(1, W + 1):
        if k > 1:
            dp[h][k] += (dp[h - 1][k - 1] * h1amida[k - 2] % p) * h1amida[W - k] % p
        dp[h][k] += (dp[h - 1][k] * h1amida[k - 1] % p) * h1amida[W - k] % p
        if k < W:
            dp[h][k] += (dp[h - 1][k + 1] * h1amida[k - 1] % p) * h1amida[W - k - 1] % p
        dp[h][k] %= p

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


def isok(n):
    for i in range(w-2):
        if n >> i & 1 and n >> (i+1) & 1:
            return False
    return True
mod = 10**9+7
h,w,k = map(int,input().split())
h += 1
if w == 1:
    print(1)
    return
if w == 2:
    print(2**(h-2))
    return
dp = [[0]*(w+1) for _ in range(h+1)]
dp[1][1] = 1
amida = [0]*(w)
noamida = [0]*(w+1)
for i in range(2**(w-1)):
    if isok(i):
        for j in range(w-1):
            amida[j+1] += i >> j & 1
        for j in range(w-2):
            if i >> j & 1 == 0 and i >> (j+1) & 1 == 0:
                noamida[j+2] += 1
        if i >> 0 & 1 == 0:
                noamida[1] += 1
        if i >> (w-2) & 1 == 0:
                noamida[w] += 1
for i in range(1,h):
    dp[i+1][1] = (dp[i][2]*amida[1]+dp[i][1]*noamida[1]) % mod
    dp[i+1][w] = (dp[i][w-1]*amida[w-1]+dp[i][w]*noamida[w]) % mod
    for j in range(2,w):
        dp[i+1][j] = (dp[i][j-1]*amida[j-1]+dp[i][j+1]*amida[j]+dp[i][j]*noamida[j]) % mod
print(dp[h][k])

from functools import lru_cache

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

if W == 1:
    print(1)
    return

@lru_cache(maxsize=None)
def fib(width):
    if width < -1:
        return 0
    if width == -1:
        return 1
    return (fib(width - 1) + fib(width - 2)) % MOD

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

for _ in range(H):
    newDp = [0] * W

    newDp[0] = (dp[0] * fib(W - 2) + dp[1] * fib(W - 3)) % MOD
    newDp[W - 1] = (dp[W - 1] * fib(W - 2) + dp[W - 2] * fib(W - 3)) % MOD

    for w in range(1, W - 1):
        left = dp[w - 1] * max(1, fib(w - 2)) * max(1, fib(W - 1 - w - 1))
        right = dp[w + 1] * max(1, fib(w - 1)) * max(1, fib(W - 1 - w - 2))
        mid = dp[w] * max(1, fib(w - 1)) * max(1, fib(W - 1 - w - 1))
        newDp[w] = (left + mid + right) % MOD
    dp = newDp

print(dp[K])

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

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)

# |-| | | | |
# のように一番左の一本が決まったとき、残りの
#     | | | |
# には、線を引く場所が3つある
# 線を引く場所がN個あるときの線の引き方の組み合わせは
# A[1] = 2, A[2] = 3, A[N] = A[N - 2] + A[N - 1]
# のほぼフィボナッチ数列
# 2,3,5,8,13...
# これをあらかじめ最大数ぶん求めておく
# 横棒W本に対して、W - 1個の間隔があり、そのうち端の2か所が埋まった状態が最大なのでW - 3
# これを求める

import sys
readline = sys.stdin.readline

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

P = [0] * max(W - 2 + 1,3)
P[1],P[2] = 2,3
for i in range(3, len(P)):
  P[i] = P[i - 1] + P[i - 2]
  
# [0, 2, 3, 5, 8, 13, 21, 34, ...]

# 通らない線は上記で算出できるので、通る線を考える
# 上からi段目まで終えた時点で、縦棒jにいるときの場合の数でDPする

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

dp[0][0] = 1 # 上から0段目を終えた時点(まだ何もしていない)ときに0にいるので1通り

def calc(L,R): # LとRの間に線を引いた場合の、残りの線の引き方
  res = 1
  if 1 < L:
    # | | |-| Lが2のときはじめてスペースが1 (L - 1)できる
    res *= P[L - 1]
    res %= DIV
  if (W - 1) - (R + 1) >= 1:
    # |-| | | R + 2 = W - 1のときはじめてスペースが1(W - R)できる
    res *= P[(W - 1) - (R + 1)]
    res %= DIV
  return res
  
# 右に移動する、左に移動する、何もしない、の3通りでDP
for i in range(H):
  for j in range(W):
    # 右に移動する
    if j + 1 < W:
      dp[i + 1][j + 1] += dp[i][j] * calc(j, j + 1)
      dp[i + 1][j + 1] %= DIV
    # 左に移動する
    if j - 1 >= 0:
      dp[i + 1][j - 1] += dp[i][j] * calc(j - 1,j)
      dp[i + 1][j - 1] %= DIV
    # 何もしない
    dp[i + 1][j] += dp[i][j] * calc(j,j) # 左端も右端も同じ
    dp[i + 1][j] % DIV
    
# i = H段目まで終えた時点で、j = K - 1にいる場合の数
print(dp[H][K - 1] % DIV)

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

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

MOD = 10 ** 9 + 7

states = [0]
for state in range(1, 1 << (W - 1)):
    flag = True
    for j in range(1, W - 1):
        if ((state >> j - 1) & 1) and ((state >> j) & 1):
            flag = False
    if flag: states.append(state)

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

dp[0][0] = 1

# 貰うDP
for i in range(H):
    for state in states:
        for j in range(W - 1):
            if (state >> j) & 1:
                dp[i + 1][j] = (dp[i + 1][j] + dp[i][j + 1]) % MOD
                dp[i + 1][j + 1] = (dp[i + 1][j + 1] + dp[i][j]) % MOD
            else:
                if j == 0:
                    dp[i + 1][j] = (dp[i + 1][j] + dp[i][j]) % MOD
                elif not ((state >> j - 1) & 1):
                    dp[i + 1][j] = (dp[i + 1][j] + dp[i][j]) % MOD
                if j == W - 2:
                    dp[i + 1][j + 1] = (dp[i + 1][j + 1] + dp[i][j + 1]) % MOD

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

import itertools


def amida_patterns(w):
    # (0, 1, 2, ... , w - 1) -> ?
    ret = list()
    for bars in itertools.product([0, 1], repeat=w-1):
        if sum([b * bb for b, bb in zip(bars[1:], bars[:-1])]) > 0:
            continue
        location = list(range(w))
        for i in range(w):
            if i > 0 and bars[i - 1] == 1:
                location[i] = i - 1
            elif i < w - 1 and bars[i] == 1:
                location[i] = i + 1
        ret.append(location)
    return ret


def main():
    MOD = 10**9 + 7
    H, W, K = list(map(int, input().split(' ')))
    ap_list = amida_patterns(W)
    dp = [[0 for _ in range(W)] for _ in range(H + 1)]
    dp[0][0] = 1
    for h in range(1, H + 1):
        for a in ap_list:
            for w in range(W):
                dp[h][a[w]] += dp[h - 1][w]
                dp[h][a[w]] %= MOD
    print(dp[H][K - 1])


def __starting_point():
    main()
__starting_point()

import sys

def comb(n, r, mod=None):
    if r == 0 or r == n:
        return 1
    r = min([r, n-r])
    x, y = 1, 1
    ans = 1
    for i in range(1, r+1):
        if mod:
            x *= n+1-i
            y *= i
            x %= mod
            y %= mod
        else:
            ans *= n+1-i
            ans //= i
    ans = x*pow(y, mod-2, mod)%mod if mod else ans
    return ans


def main():
    h, w, k = map(int, input().split())
    mod = pow(10,9)+7
    
    if w == 1:
        print(1)
        return
    
    comb_list = [[0]*11 for _ in range(11)]
    for i in range(11):
        for j in range(11):
            if i >= j:
                comb_list[i][j] = comb(i, j)
    
    key_list = [1]*10
    for i in range(1, 10):
        key = 0
        for j in range(1, 10):
            if i < j*2-1:
                break
            key += comb_list[i-j+1][j]
        key_list[i] += key
    
    
    dp = [[0]*w for _ in range(h)]
    for i in range(h):
        if i == 0:
            dp[0][0] = key_list[w-2]
            dp[0][1] = key_list[w-3] if w != 2 else 1
            continue
        if w == 2:
            dp[i][0] = (dp[i-1][0]+dp[i-1][1])%mod
            dp[i][1] = (dp[i-1][0]+dp[i-1][1])%mod
            continue
            
        for j in range(w):
            if j == 0:
                dp[i][j] = (dp[i-1][j]*key_list[w-2]+dp[i-1][j+1]*key_list[w-3])%mod
            elif j == w-1:
                dp[i][j] = (dp[i-1][j]*key_list[w-2]+dp[i-1][j-1]*key_list[w-3])%mod
            else:
                dp[i][j] = 0
                dp[i][j] += (dp[i-1][j-1]*key_list[max([0, j-2])]*key_list[max([0, w-2-j])])%mod
                dp[i][j] += (dp[i-1][j]*key_list[max([0, j-1])]*key_list[max([0, w-2-j])])%mod
                dp[i][j] += (dp[i-1][j+1]*key_list[max([0, j-1])]*key_list[max([0, w-3-j])])%mod
                dp[i][j] %= mod
    print(dp[h-1][k-1])
                                                                           

def __starting_point():
    main()
__starting_point()

"""
    dp[h][w]: h番目のrow(h: 0~H(終着))で棒w(w: 0~W-1)にいる状態になるための横線(0~h)の組合せ数
    dp[h][w] = A*dp[h-1][w-1] + B*dp[h-1][w] + C*dp[h-1][w+1] o(1000)
    A, B, Cはなんかうまいこと決めれそう。(全探索でもmax7*7*3通り)o(1000) 
    どうやってもO(10**6)には入りそう
    """
def main():
    import sys
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    dp = [[0]*W for _ in range(H+1)]
    dp[0][0] = 1
    for h in range(1, H+1):
        for w in range(W):
            A, B, C = 0, 0, 0
            for i in range(2 ** (W-1)):
                lines = []
                for j in range(W-1):
                    if ((i >> j) & 1):
                        if lines and lines[-1]:
                            break
                        lines.append(True)
                    else:
                        lines.append(False)
                else:
                    if w-1 >= 0 and lines[w-1]:
                        A += 1
                    elif w <= W-2 and lines[w]:
                        C += 1
                    else:
                        B += 1
            if w-1 >= 0:
                dp[h][w] += dp[h-1][w-1] * A
            dp[h][w] += dp[h-1][w] * B
            if w+1 <= W-1:
                dp[h][w] += dp[h-1][w+1] * C
    print(dp[H][K-1] % (10**9+7))
    

def __starting_point():
    main()
__starting_point()

h,w,k=map(int,input().split())
mod=10**9+7
R=[[],[1],[1,1],[2,1,2],[3,2,2,3],[5,3,4,3,5],[8,5,6,6,5,8],[13,8,10,9,10,8,13]]
T=[1,2,3,5,8,13,21,34]
r=R[w-1]
t=T[w-1]
A=[0]*w
A[0]=1
if w==1:
    print(1)
else:
    for i in range(h):
        C=[0]*w
        for i in range(w):
            if i==0:
                C[0]+=(t-r[0])*A[0]
                C[1]+=r[0]*A[0]
            elif i==w-1:
                C[w-1]+=(t-r[w-2])*A[w-1]
                C[w-2]+=r[w-2]*A[w-1]
            else:
                C[i-1]+=r[i-1]*A[i]
                C[i]+=(t-r[i-1]-r[i])*A[i]
                C[i+1]+=r[i]*A[i]
        for i in range(w):
            C[i]%=mod
        A=C
    print(A[k-1])

import sys

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

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

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

if w == 1:
    print(1)
    return

for i in range(1, h + 1):
    for j in range(w):
        dp[i][j] = dp[i - 1][j] * fn[j] * fn[w - j - 1]
        if j < w - 1:
            dp[i][j] += dp[i - 1][j + 1] * fn[j] * fn[w - j - 2]
        if 0 < j:
            dp[i][j] += dp[i - 1][j - 1] * fn[j - 1] * fn[w - j - 1]
        dp[i][j] %= MOD

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

#!/usr/bin/env python
# -*- coding: utf-8 -*-

#number of amidakuji

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

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

#dp[i][j]=i段目まででjというところにいくために必要な方法の総和
#求めるのはdp[h][k]である
dp[0][1] = 1
mod=10**9+7
if w>1:
    for i in range(1,h+1):
        for j in range(2**(w-1)):
            st=format(j,"0%ib"%(w-1))
            flag=True
            for _ in range(w-2):
                if st[_]=="1" and st[_+1]=="1":
                    flag=False
            connect=[False for kyopuro in range(w+1)]
            if flag:
                li=[]
                for ss in range(w-1):
                    if st[ss]=="1":
                        li.append(ss+1)
                        connect[ss+1]=True
                        connect[ss+2]=True

                for some in li:
                    dp[i][some+1]+=dp[i-1][some]
                    dp[i][some+1]%=mod
                    dp[i][some]+=dp[i-1][some+1]
                    dp[i][some]%=mod
                for number in range(1,w+1):
                    if connect[number]==False:
                        dp[i][number]+=dp[i-1][number]
                        dp[i][number]%=mod
    print((dp[h][k]%mod))
                
        
else:
    print((1))




'''Yoshichiの日記
あみだくじ。
0本目からスタートし、W本の長さH + 1までにを任意の線を引いた時
K本目にたどり着くパターンは何パターンあるか答えよ。
現在の位置状態での線の引き方を全列挙し、DP(メモ化再帰)を用いて答える。
x → 現在の位置
y → 現在の進み具合
for分のi → 現在の位置にいる時の線の配置状態(1が隣接へつながっているとき)
for分のj → NGパターンの列挙(隣へ繋がっているかつ、
                   次の隣へも線が引かれている状態)
'''
from collections import defaultdict
h, w, k = map(int, input().split())
memo = defaultdict(lambda:defaultdict(int))
def dfs(x, y):
    if y == h:
        if x == k - 1:
            return 1
        else:
            return 0
    if y in memo[x]:
        return memo[x][y]
    ans = 0
    for i in range(1 << w - 1):
        flg = True
        for j in range(w - 2):
            if i & (1 << j) and i & (1 << j + 1):
                flg = False
                break
        if flg:
            nx = x
            if x > 0 and i & (1 << x - 1):
                nx = x - 1
            elif i & (1 << x):
                nx = x + 1
            ans += dfs(nx, y + 1)
            ans %= 1000000000 + 7
    memo[x][y] = ans
    return ans
print(dfs(0, 0))

#実はDPと割り切るとわかりやすい
mod=10**9+7
h,w,K=map(int,input().split())
dp=[[0]*w for j in range(h+1)]
dp[0][0]=1
for i in range(1,h+1):
    for k in range(2**(w-1)):
        for l in range(w-2):
            if ((k>>l)&1) and ((k>>(l+1))&1):
                break
        else:
            for l in range(w):
                if l==0:
                    if ((k>>l)&1):
                        dp[i][l+1]+=dp[i-1][l]
                    else:
                        dp[i][l]+=dp[i-1][l]
                elif l==w-1:
                    if ((k>>(l-1))&1):
                        dp[i][l-1]+=dp[i-1][l]
                    else:
                        dp[i][l]+=dp[i-1][l]
                else:
                    if ((k>>l)&1) or ((k>>(l-1))&1):
                        if ((k>>l)&1):
                            dp[i][l+1]+=dp[i-1][l]
                        else:
                            dp[i][l-1]+=dp[i-1][l]
                    else:
                        dp[i][l]+=dp[i-1][l]
            dp[i][l]%=mod
print(dp[h][K-1]%mod)

H, W, K = list(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, WW)
print((DP[-1][K-1]))


import sys
from itertools import product

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

    A = product((0, 1), repeat=W - 1)
    B = []
    for bars in A:
        ok = True
        for i in range(W - 2):
            if bars[i] and bars[i + 1]:
                ok = False
                break
        if ok:
            B.append(bars)

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

    for _ in range(H):
        dp, dp_prev = [0] * W, dp
        for bars in B:
            for i in range(W):
                if i > 0 and bars[i - 1]:
                    dp[i - 1] = (dp[i - 1] + dp_prev[i]) % MOD
                elif i < W - 1 and bars[i]:
                    dp[i + 1] = (dp[i + 1] + dp_prev[i]) % MOD
                else:
                    dp[i] = (dp[i] + dp_prev[i]) % MOD

    print((dp[K - 1]))

    return


def __starting_point():
    main()

__starting_point()

h,w,K=map(int,input().split())
mod=10**9+7
dp=[[0 for i in range(w)] for j in range(h+1)]
for i in range(2**(w-1)):dp[0][0]=1
for i in range(1,h+1):
    for j in range(2**(w-1)):
        s=format(j,"b").zfill(w-1)
        if "11" in s:continue
        exchanged=[False]*w
        for k in range(w-1):
            if s[k]=="1":
                dp[i][k]+=dp[i-1][k+1]
                dp[i][k+1]+=dp[i-1][k]
                dp[i][k]%=mod
                dp[i][k+1]%=mod
                exchanged[k]=True
                exchanged[k+1]=True
        for k in range(w):
            if exchanged[k]:continue
            dp[i][k]+=dp[i-1][k]
            dp[i][k]%=mod

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

# |-| | | | |
# のように一番左の一本が決まったとき、残りの
#     | | | |
# には、線を引く場所が3つある
# 線を引く場所がN個あるときの線の引き方の組み合わせは
# A[1] = 2, A[2] = 3, A[N] = A[N - 2] + A[N - 1]
# のほぼフィボナッチ数列
# 2,3,5,8,13...
# これをあらかじめ最大数ぶん求めておく
# 横棒W本に対して、W - 1個の間隔があり、そのうち端の2か所が埋まった状態が最大なのでW - 3
# これを求める

import sys
readline = sys.stdin.readline

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

P = [0] * max(W - 2 + 1,3)
P[1],P[2] = 2,3
for i in range(3, len(P)):
  P[i] = P[i - 1] + P[i - 2]
  
# [0, 2, 3, 5, 8, 13, 21, 34, ...]

# 通らない線は上記で算出できるので、通る線を考える
# 上からi段目まで終えた時点で、縦棒jにいるときの場合の数でDPする

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

dp[0][0] = 1 # 上から0段目を終えた時点(まだ何もしていない)ときに0にいるので1通り

def calc(L,R): # LとRの間に線を引いた場合の、残りの線の引き方
#  print("calc L",L,"R",R)
  res = 1
  if 1 < L:
    # | | |-| Lが2のときはじめてスペースが1 (L - 1)できる
    res *= P[L - 1]
#    print("P[L - 2]",P[L - 2],"res",res)
    res %= DIV
  if (W - 1) - (R + 1) >= 1:
    # |-| | | R + 2 = W - 1のときはじめてスペースが1(W - R)できる
#    print(min((W - 1) - (R + 1),len(P)))
    res *= P[(W - 1) - (R + 1)]
#    print("P[(W - 1) - (R + 1)]",min((W - 1) - (R + 1),len(P)),"res",res)
    res %= DIV
#  print(res,"通り")
  return res
  
# 右に移動する、左に移動する、何もしない、の3通りでDP
for i in range(H):
  for j in range(W):
    # 右に移動する
    if j + 1 < W:
#      print("i",i,"j",j,"からi + 1",i + 1,"j + 1",j + 1,"に移動する dp[i][j]",dp[i][j],"dp[i + 1][j + 1]",dp[i + 1][j + 1])
      dp[i + 1][j + 1] += dp[i][j] * calc(j, j + 1)
      dp[i + 1][j + 1] %= DIV
#      print("i",i,"j",j,"からi + 1",i + 1,"j + 1",j + 1,"に移動した dp[i][j]",dp[i][j],"dp[i + 1][j + 1]",dp[i + 1][j + 1])
    # 左に移動する
    if j - 1 >= 0:
#      print("i",i,"j",j,"からi + 1",i + 1,"j - 1",j - 1,"に移動する dp[i][j]",dp[i][j],"dp[i + 1][j - 1]",dp[i + 1][j - 1])
      dp[i + 1][j - 1] += dp[i][j] * calc(j - 1,j)
      dp[i + 1][j - 1] %= DIV
#      print("i",i,"j",j,"からi + 1",i + 1,"j - 1",j - 1,"に移動した dp[i][j]",dp[i][j],"dp[i + 1][j - 1]",dp[i + 1][j - 1])
    # 何もしない
#    print("i",i,"j",j,"からi",i,"j",j,"に移動する dp[i][j]",dp[i][j],"dp[i + 1][j]",dp[i + 1][j])
    dp[i + 1][j] += dp[i][j] * calc(j,j) # 左端も右端も同じ
    dp[i + 1][j] % DIV
#    print("i",i,"j",j,"からi",i,"j",j,"に移動した dp[i][j]",dp[i][j],"dp[i + 1][j]",dp[i + 1][j])
#  for d in dp:
#    print(dp)

    
# i = H段目まで終えた時点で、j = K - 1にいる場合の数
print(dp[H][K - 1] % DIV)

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

    if w == 1:
        print(1)
        return
    if w == 2:
        print(pow(2, h-1, mod))
        return

    k -= 1

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

    dp = [0] * w
    dp[0] = 1
    for _ in range(h):
        new_dp = [0] * w
        new_dp[0] = (dp[0] * fibo[w-2] + dp[1] * fibo[w-3]) % mod
        new_dp[1] = (dp[0] * fibo[w-3]) % mod
        new_dp[w-1] = (dp[w-1] * fibo[w-2] + dp[w-2] * fibo[w-3]) % mod
        new_dp[w-2] += (dp[w-1] * fibo[w-3]) % mod
        for i in range(1, w-1):
            new_dp[i] += ((fibo[i-1] * fibo[w-i-2]) * dp[i]) % mod
        for i in range(1, w-2):
            new_dp[i] += (fibo[i-1] * fibo[w-i-3]) * dp[i+1]
            new_dp[i] %= mod
            new_dp[i+1] += (fibo[i-1] * fibo[w-i-3]) * dp[i]
            new_dp[i+1] %= mod
        dp = new_dp

    print(dp[k] % mod)

main()

#!/usr/bin/env python3
from itertools import product
import sys

try:
    from typing import List, Tuple
except ImportError:
    pass


MOD = 1000000007  # type: int


def isvalid(ptn: "Tuple[bool]"):
    return not any(h1 and h2 for h1, h2 in zip(ptn, ptn[1:]))


def solve(H: int, W: int, K: int):
    validptns = [
        ptn
        for ptn in product((False, True), repeat=W - 1)
        if isvalid(ptn)
    ]  # type: List[Tuple[bool]]
    dp = [1 if i == K - 1 else 0 for i in range(W)]  # type: List[int]
    for _ in range(H):
        newdp = [0] * W  # type: List[int]
        for ptn in validptns:
            for s in range(W):
                t = s
                if s < W - 1 and ptn[s]:
                    t = s + 1
                elif s > 0 and ptn[s - 1]:
                    t = s - 1
                newdp[t] += dp[s]
                newdp[t] %= MOD
        dp = newdp

    print((dp[0]))


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


def __starting_point():
    main()

__starting_point()

h, w, k = list(map(int, input().split()))
p = 10**9+7
# DP[i][j]=i段目まで見て0からjに着くパターン数
DP = [[0 for j in range(w+1)] for i in range(h+1)]
DP[0][0] = 1
# F[k]=k個の枠に隣り合わないように線を引くパターンの数
F = [1, 1, 2, 3, 5, 8, 13, 21]
for i in range(h):
    for j in range(w):
        a = DP[i][j-1]*F[j-1]*F[w-1-j]
        b = DP[i][j]*F[j]*F[w-1-j]
        c = DP[i][j+1]*F[j]*F[w-2-j]
        DP[i+1][j] = (a+b+c) % p
print((DP[h][k-1]))


def f(i):
  if i == W-1:
    for j in range(W-2):
      if s[j] == s[j+1] == 1:
        return
    nonlocal 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)
  return
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])

import sys
input=sys.stdin.readline
INF = 10**9
MOD = 10**9 + 7

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

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

    for i in range(h):
        for bit in range(1<<(w-1)):
            flag = False
            before = -2
            line = [0] * (w-1)
            for j in range(w-1):
                if (bit>>j)&1:
                    if  before + 1 == j:
                        flag = True
                        break
                    
                    else:
                        before = j
                        line[j] = 1
  

            if flag:
                continue

            j = 0
            while j < w:
                if j == w-1:
                    dp[i+1][j] += dp[i][j]
                    dp[i+1][j] %= MOD
                    break
                if line[j]:
                    dp[i+1][j] += dp[i][j+1]
                    dp[i+1][j] %= MOD
                    dp[i+1][j+1] += dp[i][j]
                    dp[i+1][j+1] %= MOD
                    j += 2
                else:
                    dp[i+1][j] += dp[i][j]
                    dp[i+1][j] %= MOD
                    j += 1

    print((dp[-1][k-1]%MOD))
def __starting_point():
    main()

__starting_point()

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

dp = [[0]*W for _ in range(H+1)]
dp[0][0] = 1
for i in range(H):
    for b in range(1<<(W-1)):
        if '11' in bin(b): continue
        for k in range(W):
            if k and b&(1<<(k-1)):
                dp[i+1][k-1] += dp[i][k]
            elif b&(1<<k):
                dp[i+1][k+1] += dp[i][k]
            else:
                dp[i+1][k] += dp[i][k]

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


#!/usr/bin/env python3

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
        # print(bridges)
        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)

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


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

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

mod = 10**9 + 7
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)):
            ok = True
            for k in range(W-2):
                if bit & (1 << k) and bit & (1 << (k+1)):
                    ok = False
            if not ok:
                continue

            jj = j
            if j > 0 and bit & (1 << (j-1)):
                jj -= 1
            elif j < W - 1 and bit & (1 << j):
                jj += 1
            dp[i+1][jj] += dp[i][j]
            dp[i+1][jj] %= mod


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


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

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

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

    for i in range(1, h + 1):
        for j in range(1, w + 1):
            dp[i][j] = c[j - 1] * c[w - j] * dp[i - 1][j] + c[j - 1] * c[w - j - 1] * dp[i - 1][j + 1] + c[j - 2] * c[w - j] * dp[i - 1][j - 1]

    print((dp[h][k] % (10 ** 9 + 7)))


def __starting_point():
    main()

__starting_point()

def f(i):
    if i == w - 1:
        for j in range(w - 2):
            if s[j] == s[j + 1] == 1:
                return
        nonlocal 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)
    return
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])