CodeEff/ECCO huggingface dataset:
# Original solution
# ABC 113 D
MOD = 7 + 10**9 
H, W, K = list(map(int,input().split()))
dp = [[0 for k in range(W)] for l 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)):
            f = 1
            for l in range(W-2):
                if (k>>l)&1 and (k>>(l+1))&1:
                    f = 0
            if f:
                if 0<j and (k>>(j-1))&1:
                    dp[i+1][j-1] += dp[i][j]
                    dp[i+1][j-1] %= MOD
                elif j <= W-2 and (k>>j)&1:
                    dp[i+1][j+1] += dp[i][j]
                    dp[i+1][j+1] %= MOD
                else:
                    dp[i+1][j] += dp[i][j]
                    dp[i+1][j] %= MOD

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


# Optimized solution
MOD = 10**9 + 7
H, W, K = list(map(int,input().split()))
dp = [[0 for k in range(W)] for l in range(H+1)]
dp[0][0] = 1
A = []  # ありうる横棒のリスト
for b in range(2**(W-1)):
    if "11" not in bin(b):
        A.append(bin(b)[2:].zfill(W-1))

for k in range(H):
    for e in A:
        for i in range(W):
            if i < W-1 and e[i] == "1": # 右に行くパターン
                dp[k+1][i+1] += dp[k][i]
                dp[k+1][i+1] %= MOD
            elif i >= 1 and e[i-1] == "1": # 左に行くパターン
                dp[k+1][i-1] += dp[k][i]
                dp[k+1][i-1] %= MOD
            else:
                dp[k+1][i] += dp[k][i]
                dp[k+1][i] %= MOD

print((dp[H][K-1]))
# Original solution
from collections import defaultdict
A = [1, 2, 3, 5, 8, 13, 21, 34]
MOD = 10**9 + 7
H, W, K = list(map(int, input().split()))
K -= 1
if W == 0:
    print((1))
    exit()
dp = [[0] * W for _ in range(H + 1)]
dp[0][0] = 1
for i in range(1, H + 1):
    for j in range(i + 1):
        for k in [-1, 0, 1]:
            if not 0 <= j + k < W: continue
            if not 0 <= j < W: continue
            if k == -1:
                left = max(0, j - 1 - 1)
                right = max(0, W - j - 2)
            elif k == 0:
                left = max(0, j - 1)
                right = max(0, W - j - 2)
            elif k == 1:
                left = max(0, j - 1)
                right = max(0, W - j - 2 - 1)
            dp[i][j] += dp[i - 1][j + k] * A[left] * A[right]
print((dp[H][K] % MOD))

# Optimized solution
A = [1, 2, 3, 5, 8, 13, 21]
MOD = 10**9 + 7
H, W, K = list(map(int, input().split()))
if W == 0:
    print((1))
    exit()
dp = [[0] * W for _ in range(H + 1)]
dp[0][0] = 1
for i in range(1, H + 1):
    for j in range(i + 1):
        for k in [-1, 0, 1]:
            if not 0 <= j + k < W: continue
            if not 0 <= j < W: continue
            if k == -1:
                left = max(0, j - 1 - 1)
                right = max(0, W - j - 2)
            elif k == 0:
                left = max(0, j - 1)
                right = max(0, W - j - 2)
            elif k == 1:
                left = max(0, j - 1)
                right = max(0, W - j - 2 - 1)
            dp[i][j] += dp[i - 1][j + k] * A[left] * A[right]
            dp[i][j] %= MOD
print((dp[H][K - 1]))
# Original solution
import sys
stdin = sys.stdin

sys.setrecursionlimit(10**5)

def li(): return list(map(int, stdin.readline().split()))
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return list(map(float, stdin.readline().split()))
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

h,w,k = li()
MOD = 10**9+7

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

nex_list = []
for i in range(1<<(w-1)):
    if not "11" in bin(i)[2:]:
        nex_list.append(i)
        
for hi in range(1,h+1):
    for bit in nex_list:
        changed = [0]*w

        for i, b in enumerate(bin(bit)[2:].zfill(w-1)):
            
            if b == "1":
                cnt[hi][i] += cnt[hi-1][i+1]
                cnt[hi][i+1] += cnt[hi-1][i]
                changed[i] = 1
                changed[i+1] = 1
        for j,c in enumerate(changed):
            if c == 0:
                cnt[hi][j] += cnt[hi-1][j]
                
    for wj in range(w):
        cnt[hi][wj] %= MOD
        
print((cnt[h][k-1]))
        

# Optimized solution
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return list(map(int, stdin.readline().split()))
def li_(): return [int(x) - 1 for x in stdin.readline().split()]
def lf(): return list(map(float, stdin.readline().split()))
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

h,w,k = li()
k -= 1
MOD = 10**9 + 7

# 遷移行列
if w > 1:
    matrix = [[0]*w for _ in range(w)]
    for num in range(1 << (w-1)):
        if "11" in bin(num):
            continue

        ex = False
        for i, bit in enumerate(bin(num)[2:].zfill(w-1)):
            if bit == "1":
                ex = True
                matrix[i][i+1] += 1
                matrix[i+1][i] += 1

            elif ex:
                ex = False

            else:
                matrix[i][i] += 1

        if not ex:
            matrix[w-1][w-1] += 1

    # 適用
    dp = [1] + [0]*(w-1)
    for hi in range(h):
        nex = [0]*w
        for wj in range(w):
            for wk in range(w):
                nex[wj] += matrix[wj][wk] * dp[wk]
                nex[wj] %= MOD

        dp = nex

    print((dp[k]))

else:
    print((1))
# Original solution
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(1, h+1):
    for j in range(w):
        left, center, right = 0, 0, 0

        for k in range(2**(w-1)):
            invalid = False
            for l in range(1, w-1):
                if k >> l & 1 and k >> (l-1) & 1:
                    invalid = True

            if invalid:
                continue

            no_line = True

            if j > 0:
                if k >> (j-1) & 1:
                    left += 1
                    no_line = False

            if j < w-1:
                if k >> j & 1:
                    right += 1
                    no_line = False

            if no_line:
                center += 1

        if j > 0:
            dp[i][j] += dp[i-1][j-1] * left

        if j < w-1:
            dp[i][j] += dp[i-1][j+1] * right

        dp[i][j] += dp[i-1][j] * center
        dp[i][j] %= mod

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


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

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


def fib(n):
    if n <= 1:
        return 1
    return fib(n-1) + fib(n-2)


for i in range(1, H+1):
    for j in range(W):
        left = j
        right = W - j - 1

        dp[i][j] = dp[i-1][j] * fib(left) * fib(right)

        if j > 0:
            dp[i][j] += dp[i-1][j-1] * fib(left-1) * fib(right)

        if j < W-1:
            dp[i][j] += dp[i-1][j+1] * fib(left) * fib(right - 1)

        dp[i][j] %= mod

print((dp[-1][K-1]))
# Original solution
h,w,k=list(map(int,input().split()));p=[sum(('11'in str(bin(j)))^1for j in range(1<<i))for i in range(8)];d=[w*[0]for _ in[0]*-~h];d[0][0]=1
for i in range(h):
 b=d[i]
 for j in range(w):
  t=u=D=0
  if j:t=p[max(0,j-2)]*p[max(0,w-j-2)];D=b[j-1]*t
  if j<w-1:u=p[max(0,j-1)]*p[max(0,w-j-3)];D+=b[j+1]*u
  d[i+1][j]=(b[j]*(p[w-1]-t-u)+D)%(10**9+7)
print((d[-1][k-1]))

# Optimized solution
h,w,k=list(map(int,input().split()))
p=[sum(('11'in str(bin(j)))^1for j in range(1<<i))for i in range(8)]
dp=[w*[0]for _ in[0]*-~h]
dp[0][0]=1
for i in range(1,h+1):
    for j in range(w):
        t=u=0
        if j:
            t=p[max(0,j-2)]*p[max(0,w-j-2)]
            dp[i][j]+=dp[i-1][j-1]*t
        if j<w-1:
            u=p[max(0,j-1)]*p[max(0,w-j-3)]
            dp[i][j]+=dp[i-1][j+1]*u
        dp[i][j]=(dp[i][j]+dp[i-1][j]*(p[w-1]-t-u))%(10**9+7)
print((dp[-1][k-1]))
# Original solution
H,W,K = list(map(int,input().split()))
K -= 1
MOD = 10**9+7

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

for i in range(H):
    for b in range(2**(W-1)):
        if '11' in bin(b): continue
        b *= 2
        for j in range(W):
            if b&(1<<j):
                dp[i+1][j-1] += dp[i][j]
                dp[i+1][j-1] %= MOD
            elif b&(1<<(j+1)):
                dp[i+1][j+1] += dp[i][j]
                dp[i+1][j+1] %= MOD
            else:
                dp[i+1][j] += dp[i][j]
                dp[i+1][j] %= MOD
print((dp[-1][K]))


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

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

dp = [[0]*W for i in range(H+1)]
dp[0][0] = 1
for i in range(H):
    for b in range(2**(W-1)):
        if '11' in bin(b): continue
        b *= 2
        for j in range(W):
            if b&(1<<j):
                dp[i+1][j-1] += dp[i][j]
            elif b&(1<<(j+1)):
                dp[i+1][j+1] += dp[i][j]
            else:
                dp[i+1][j] += dp[i][j]
print((dp[-1][K-1] % MOD))
# Original solution
H,W,K = list(map(int,input().split()))
 
 
amida = [0 for i in range(8)]
amida[0]=1
amida[1]=2
amida[2]=3
amida[3]=5
amida[4]=8
amida[5]=13
amida[6]=21
amida[7]=34
 
def amida_num(k,l):
    return amida[max(k,0)]*amida[max(l,0)]
 
 
dp=[[0 for i in range(W)] for j in range(H+1)]
 
dp[0][0] = 1
 
if W!=1:
    for i in range(1,H+1):
        for j in range(W):
            if j==0:
                dp[i][j]=dp[i-1][j+1]*amida_num(0,W-3) + dp[i-1][j]* amida_num(0,W-2)
            elif j==W-1:
                dp[i][j]=dp[i-1][j-1]*amida_num(0,W-3) + dp[i-1][j]* amida_num(0,W-2)
            else:
                dp[i][j]=dp[i-1][j-1]*amida_num(j-2,W-j-2) + dp[i-1][j]*amida_num(j-1,W-j-2) + dp[i-1][j+1]*amida_num(j-1,W-j-3)
    print((dp[H][K-1]%(10**9+7)))
else:
    print((1))

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

r = 10**9 + 7

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

dp[0][0]=1

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

if W!=1:
    for i in range(H):
        for j in range(W):
            if j==0:
                dp[i+1][j]=(num[W-1]*dp[i][j]+num[W-2]*dp[i][j+1])%r
            elif j==W-1:
                dp[i+1][j]=(num[W-1]*dp[i][j]+num[W-2]*dp[i][j-1])%r
            else:
                dp[i+1][j]=(num[j]*num[W-j-1]*dp[i][j]+num[j-1]*num[W-j-1]*dp[i][j-1]+num[j]*num[W-j-2]*dp[i][j+1])%r
    print((dp[H][K-1]))
else:
    print((1))
# Original solution
h,w,k = list(map(int,input().split()))

honsu=w


a = 0
def amida(h,w):
  global a
  if h == 0 and w == k:
    return 1
  if h ==0:
    return 0
  if not(1<=w<=honsu):
    return 0
  com1 = fib(honsu-w+1)*fib(w-1)*amida(h-1,w-1)
  com2 = fib(honsu-w+1)*fib(w)*amida(h-1,w) 
  com3 = fib(honsu-w)*fib(w)*amida(h-1,w+1)   
  
  return com1+com2+com3
  
fib_memo = {}
def fib(n):
    if n < 3: return 1
    if n not in fib_memo:
        fib_memo[n] = fib(n-1) + fib(n-2)
    return fib_memo[n]

print((amida(h,1)%1000000007))

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

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

fib_memo = {}
def fib(n):
    if n < 3: return 1
    if n not in fib_memo:
        fib_memo[n] = fib(n-1) + fib(n-2)
    return fib_memo[n]
  

for j in range(w):
  a[0][j]=0
a[0][0]=1

for i in range(1,h+1):
  for j in range(w):
    if w==1:
      a[i][j]=a[i-1][j]
    elif j==0:
      a[i][j]=a[i-1][j]*fib(w)+a[i-1][j+1]*fib(w-1)
    elif 1<=j<w-1:
      a[i][j]=a[i-1][j-1]*fib(w-j)*fib(j)+a[i-1][j]*fib(w-j)*fib(j+1)+a[i-1][j+1]*fib(w-j-1)*fib(j+1)
    elif j==w-1:
      a[i][j]=a[i-1][j]*fib(w)+a[i-1][j-1]*fib(w-1)
print((a[h][k-1]%1000000007))
# Original solution
H, W, K = [int(_) for _ in input().split()]

MOD = 1000000007

P = [""]
for i in range(W - 1):
    Q = []
    for p in P:
        Q.append(p + "0")
        if len(p) == 0 or p[-1] == "0":
            Q.append(p + "1")
    P = Q

rs = [1] + [0] * (W - 1)

for j in range(H):
    nrs = [0] * W
    for p in P:
        drs = rs[:]
        for i, c in enumerate(p):
            if c == "1":
                drs[i], drs[i + 1] = drs[i + 1], drs[i]
        for i in range(W):
            nrs[i] = (nrs[i] + drs[i]) % MOD
    rs = nrs

print((rs[K - 1]))


# Optimized solution
H, W, K = [int(_) for _ in input().split()]

MOD = 1000000007

pats = [[0]]

for i in range(1, W):
    pats = [p + [i] for p in pats] + [p[:-1] + [i, i - 1] for p in pats if p[-1] == i - 1]

rs = [1] + [0] * (W - 1)

for j in range(H):
    rs = [sum(rs[p[i]] for p in pats) % MOD for i in range(W)]

print((rs[K - 1]))
# Original solution
h, w, k = list(map(int, input().split()))
dp = [1] + [0] * (w - 1)
mod = 1000000007
for _ in range(h):
    newdp = [0] * w
    for b in range(1 << (w - 1)):
        valid = True
        for i in range(w - 1):
            if (b >> i) & 3 == 3:
                valid = False
        if valid:
            for i in range(w):
                if (b >> i) & 1 != 0:
                    newdp[i + 1] = (newdp[i + 1] + dp[i]) % mod
                elif i > 0 and (b >> (i - 1)) & 1 != 0:
                    newdp[i - 1] = (newdp[i - 1] + dp[i]) % mod
                else:
                    newdp[i    ] = (newdp[i    ] + dp[i]) % mod
    dp = newdp
print((dp[k - 1]))


# Optimized solution
h, w, k = list(map(int, input().split()))
dp = [1] + [0] * (w - 1)
mod = 1000000007

def mul(a, b):
    newmatrix = [[0] * w for _ in range(w)]
    for i in range(w):
        for j in range(w):
            newmatrix[i][j] = sum(a[i][k] * b[k][j] for k in range(w)) % mod
    return newmatrix

matrix = [[0] * w for _ in range(w)]
for b in range(1 << (w - 1)):
    valid = True
    for i in range(w - 1):
        if (b >> i) & 3 == 3:
            valid = False
    if valid:
        for i in range(w):
            if (b >> i) & 1 != 0:
                matrix[i][i + 1] += 1
            elif i > 0 and (b >> (i - 1)) & 1 != 0:
                matrix[i][i - 1] += 1
            else:
                matrix[i][i] += 1

ret = [[1 if i == j else 0 for i in range(w)] for j in range(w)]
while h > 0:
    if h & 1 == 1:
        ret = mul(ret, matrix)
    matrix = mul(matrix, matrix)
    h //= 2

print((ret[0][k - 1]))
# Original solution
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))


# Optimized solution
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))
# Original solution
h,w,k = list(map(int, input().split()))
# (上から, 左右から)の通り数
memo = [[0]*w for i in range(h+1)]
for i in range(0, w):
    memo[0][i] = 0
memo[0][0] = 1

# print(memo)

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

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


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

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

print((memo[h][k-1]))
# Original solution
MOD=10**9+7
H,W,K=list(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]))

# Optimized solution
MOD=10**9+7

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

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

for i in range(1,H+1):
    for k in range(W):
        l,c,r=0,0,0
        for bit in range(2**(W-1)):
            if not isvalid(bit):
                continue
            if ((k>0 and not(bit>>(k-1)&1)) or k==0) and ((k<W-1 and not(bit>>k&1))or k==W-1):
                c+=1
            if (k>0) and (bit>>(k-1)&1):
                l+=1
            if (k<W-1) and (bit>>k&1):
                r+=1
        dp[i][k]=(dp[i][k]+dp[i-1][k]*c)%MOD
        if k>0:
            dp[i][k]=(dp[i][k]+dp[i-1][k-1]*l)%MOD
        if k<W-1:
            dp[i][k]=(dp[i][k]+dp[i-1][k+1]*r)%MOD
print((dp[H][K-1]))
# Original solution
import sys
mod = pow(10, 9) + 7
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

NNN = (10**5) * 2
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

for i in range( 2, NNN + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )


def erabu(aW):
    r = 0
    for i in range(aW // 2 + 1 + 1):
        sp = aW - (2*i -1)
        r += cmb(sp+i+1-1, sp, mod)
    return r

N, W, K = [int(x) for x in input().strip().split(" ")]
hasi = 0
cc = []
if W == 1:
    if K == 1:
        print((1))
    else:
        print((0))
    sys.exit()
elif W == 2:
    cccl = [1, 1]
    cc = [1, 1]
elif W == 3:
    cccl = [1, 1, 1]
    cc = [2, 1, 2]
elif W >= 4:
    aW = W - 1
    hW = aW - 2
    nhW = aW - 3
    cc = []
    cccl = []
    for w in range(W):
        nn = max(W - 1 - w - 1, 0)
        nnn = max((W - 1) - nn - 2, 0)
        if w == W -1:
            nnn += 1
        cc.append(erabu(nn) * erabu(nnn))
        cccl.append(erabu(nn) * erabu(nnn-1))

cccl[0] = 0
cccr = cccl[::-1]
d = [1] + [0 for x in range(W-1)]
for i in range(N):
    newd = []
    for j in range(W):
        newd.append(0)
        if j != 0:
            newd[j] = (newd[j] + (d[j-1] * cccl[j]) )% mod
        if j != W-1:
            newd[j] = (newd[j] + (d[j+1] * cccr[j])) % mod
        newd[j] = (newd[j] + (d[j] * cc[j])) % mod
    d = newd[:]

print((d[K-1]))


# Optimized solution
import sys
mod = pow(10, 9) + 7
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

NNN = (10**2)
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

for i in range( 2, NNN + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )


def erabu(aW):
    r = 0
    for i in range(aW // 2 + 1 + 1):
        sp = aW - (2*i -1)
        r += cmb(sp+i+1-1, sp, mod)
    return r

N, W, K = [int(x) for x in input().strip().split(" ")]
hasi = 0
cc = []
if W == 1:
    if K == 1:
        print((1))
    else:
        print((0))
    sys.exit()
elif W == 2:
    cccl = [1, 1]
    cc = [1, 1]
elif W == 3:
    cccl = [1, 1, 1]
    cc = [2, 1, 2]
elif W >= 4:
    aW = W - 1
    hW = aW - 2
    nhW = aW - 3
    cc = []
    cccl = []
    for w in range(W):
        nn = max(W - 1 - w - 1, 0)
        nnn = max((W - 1) - nn - 2, 0)
        if w == W -1:
            nnn += 1
        cc.append(erabu(nn) * erabu(nnn))
        cccl.append(erabu(nn) * erabu(nnn-1))

cccl[0] = 0
cccr = cccl[::-1]
d = [1] + [0 for x in range(W-1)]
for i in range(N):
    newd = []
    for j in range(W):
        newd.append(0)
        if j != 0:
            newd[j] = (newd[j] + (d[j-1] * cccl[j]) )% mod
        if j != W-1:
            newd[j] = (newd[j] + (d[j+1] * cccr[j])) % mod
        newd[j] = (newd[j] + (d[j] * cc[j])) % mod
    d = newd[:]

print((d[K-1]))