CodeEff/ECCO huggingface dataset:
# Original solution
#!/usr/bin/env python3
import collections

H, W, M = list(map(int, input().split()))
tate = []
yoko = []
S = []

for i in range(M):
    h, w = list(map(int, input().split()))
    tate.append(h-1)
    yoko.append(w-1)
    S.append([h-1, w-1])

tate = collections.Counter(tate)
yoko = collections.Counter(yoko)
yoko_max = yoko.most_common()[0][1]
yoko_index = []
tate_max = tate.most_common()[0][1]
tate_index = []

for k, v in yoko.most_common():
    if v == yoko_max: yoko_index.append(k)
    else: break

for k, v in tate.most_common():
    if v == tate_max: tate_index.append(k)
    else: break

for i in range(len(yoko_index)):
    for j in range(len(tate_index)):
        if [tate_index[j], yoko_index[i]] in S:
            continue
        else:
            print((tate_max + yoko_max))
            exit()


print((tate_max + yoko_max - 1))


# Optimized solution
#!/usr/bin/env python3
import collections

H, W, M = list(map(int, input().split()))
tate = []
yoko = []
S = set()

for i in range(M):
    h, w = list(map(int, input().split()))
    tate.append(h-1)
    yoko.append(w-1)
    S.add((h-1, w-1))

tate = collections.Counter(tate)
yoko = collections.Counter(yoko)
yoko_max = yoko.most_common()[0][1]
yoko_index = []
tate_max = tate.most_common()[0][1]
tate_index = []

for k, v in yoko.most_common():
    if v == yoko_max: yoko_index.append(k)
    else: break

for k, v in tate.most_common():
    if v == tate_max: tate_index.append(k)
    else: break

for i in yoko_index:
    for j in tate_index:
        if (j, i) in S:
            continue
        else:
            print((tate_max + yoko_max))
            exit()


print((tate_max + yoko_max - 1))
# Original solution
import math
while 1:
    n = int(input())
    if not n:
        break
    ans = 0
    for p in range(1, int(math.sqrt(2*n))+1):
        if 2*n % p ==0:
            q = 2*n / p
            if p>1 and (p+q)%2:
                ans += 1
    print(ans)

# Optimized solution
while 1:
    n = int(input())
    if not n:
        break
    ans = 0
    p = 2
    while p**2 <= 2*n:
        if not 2*n % p:
            if (p + 2*n/p) % 2:
                ans += 1
        p += 1
    print(ans)
# Original solution
if __name__ == "__main__":
    while True:
        n = int(eval(input()))
        if n ==0:break
        nline = [i for i in range(1,n+1)]
        count = 0
        for i in range(n):
            for j in  range(i+1,n):
                if sum(nline[i:j]) > n:break
                if sum(nline[i:j]) == n:count +=1

        print(count)

# Optimized solution
if __name__ == "__main__":
    while True:
        n = int(eval(input()))
        if n ==0:break
        count = 0
        for i in range(1,n):
            for j in range(i+1,n):
                sum = (i+j)*(j-i+1)/2
                if sum> n:break
                if sum == n:count +=1

        print(count)
# Original solution
import sys
from io import StringIO
import unittest
import math

def resolve():
    x = int(input())

    a = math.floor(x ** 0.2)

    b5 = a ** 5 - x # マイナスになる

    b = 0

    right = 0
    left = b5 - 10
    if x == 1:
        a = 0
        b = -1
    else:
        while 1:
            mid = (right + left) // 2

            if mid ** 5 > b5:
                right = mid - 1
            elif mid ** 5 < b5:
                left = mid + 1
            else:
                b = mid
                break

    print(a, b, sep=' ')


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """33"""
        output = """2 -1"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """1"""
        output = """0 -1"""
        self.assertIO(input, output)

if __name__ == "__main__":
    # unittest.main()
    resolve()


# Optimized solution
import sys
from io import StringIO
import unittest
import math

def resolve():
    x = int(input())

    a = math.floor(x ** 0.2) + 1

    b5 = a ** 5 - x

    if x == 1:
        a = 0
        b = -1
    elif b5 == 0:
        b = 0
    else:
        right = (10 ** 9)
        left = -1 * (10 ** 9)
        pre_right = (10 ** 9)
        pre_left = -1 * (10 ** 9)

        b = 0
        pre_mid = 10 ** 9
        while 1:
            mid = (right + left) // 2
            ans = mid ** 5
            # print(left, right)

            if ans > b5:
                right = mid - 1
            elif ans < b5:
                left = mid + 1
            else:
                b = mid
                break

            if [pre_right, pre_left] == [right, left]:
                a -= 1
                b5 = a ** 5 - x
                right = (10 ** 9)
                left = -1 * (10 ** 9)

            pre_right = right
            pre_left = left

    print(a, b, sep=' ')


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """33"""
        output = """2 -1"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """1"""
        output = """0 -1"""
        self.assertIO(input, output)

if __name__ == "__main__":
    # unittest.main()
    resolve()
# Original solution
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys


def fib_bad(n):
    if not n or n == 1:
        return 1
    return fib_bad(n - 2) + fib_bad(n - 1)


def fib_dp(n):
    fib_list[:1] = [1, 1]
    for i in range(2, n + 1):
        fib_list[i] = fib_list[i - 2] + fib_list[i - 1]
    return fib_list.pop()


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    index = int(_input[0])
    fib_list = [None] * index
    # print(fib_bad(index))
    print((fib_dp(index)))

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

import sys


# def fib_bad(n):
#     if not n or n == 1:
#         return 1
#     return fib_bad(n - 2) + fib_bad(n - 1)


def fib_dp(n):
    fib_list[:1] = [1, 1]
    for i in range(2, n + 1):
        fib_list[i] = fib_list[i - 2] + fib_list[i - 1]
    return fib_list.pop()


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    index = int(_input[0])
    fib_list = [None] * index
    print((fib_dp(index)))
# Original solution
def fibonacci(n):
    if n == 0 or n == 1:
        return 1
    return fibonacci(n - 2) + fibonacci(n - 1)

print((fibonacci(int(eval(input())))))

# Optimized solution
def fibonacci(f, n):
    if n == 0 or n == 1:
        f[n] = 1
        return f[n]
    if f[n]:
        return f[n]
    f[n] = fibonacci(f, n - 2) + fibonacci(f, n - 1)
    return f[n]

n = int(eval(input()))
f = [None for i in range(n + 1)]
print((fibonacci(f, n)))
# Original solution
f=lambda n:f(n-1)+f(n-2)if n>1 else 1
print((f(int(eval(input())))))


# Optimized solution
f=[1,1]
for _ in range(2,45):f+=[sum(f[-2:])]
print((f[int(eval(input()))]))
# Original solution
#coding:UTF-8
def FN(n):
    if n==0 or n==1:
        return 1
    else:
        ans=FN(n-1)+FN(n-2)
        return ans
if __name__=="__main__":
    n=int(eval(input()))
    ans=FN(n)
    print(ans)

# Optimized solution
#coding:UTF-8
def FN(n):
    if n==0 or n==1:
        F[n]=1
        return F[n]
    if F[n]!=None:
        return F[n]
    F[n]=FN(n-1)+FN(n-2)
    return F[n]

if __name__=="__main__":
    n=int(eval(input()))
    F=[None]*(n+1)
    ans=FN(n)
    print(ans)
# Original solution
n = int(input())

def fib(N):
    if N in [0, 1]:
        return 1
    else:
        return fib(N-1) + fib(N-2)

print(fib(n))

# Optimized solution
n = int(input())
a = 1
b = 1
for i in range(n-1):
    tmp = a
    a = b
    b += tmp
print(b)
# Original solution
def fib(n):
	if n == 0:
		return 1
	elif n == 1:
		return 1
	else:
		return fib(n - 1) + fib(n - 2)

n = eval(input())
print(fib(n))

# Optimized solution
cache = {}
def fib(x):
	if x in cache:
		return cache[x]
	elif x == 0 or x == 1:
		return 1
	else:
		v = fib(x - 1) + fib(x - 2)
		cache[x] = v
		return v

x = eval(input())
print(fib(x))
# Original solution
def fib(n):
    if n==0 or n==1:
        return 1
    else:
        return fib(n-1) + fib(n-2)
print((fib(int(eval(input())))))



# Optimized solution
def fib(n):
    if n ==0 or n == 1:
        return 1
    l = [0] * (n+1)
    l[0] = 1
    l[1] = 1

    for i in range(2,n+1):
        l[i] = l[i-2] + l[i-1]
    return l[i]

print((fib(int(eval(input())))))
# Original solution
def fib(n):
    return 1 if n == 0 or n == 1 else fib(n - 1) + fib(n - 2)

print((fib(int(eval(input())))))

# Optimized solution
def fib(n):
    n1 = n2 = tmp = 1
    for _ in range(n - 1):
        tmp = n1 + n2
        n1, n2 = n2, tmp
    return tmp

print((fib(int(eval(input())))))
# Original solution
def fib(n):
    if n == 0 or n == 1:
        return 1
    return fib(n-1) + fib(n-2)

n = int(eval(input()))
print((fib(n)))

# Optimized solution
def fib(n, fib_table):
    if n == 0 or n == 1:
        return 1
    if fib_table[n] != None:
        return fib_table[n]
    fib_table[n] = fib(n-1, fib_table) + fib(n-2, fib_table)
    return fib_table[n]

n = int(eval(input()))
fib_table = [None]*(n+1)
fib_table[0] = 1
fib_table[1] = 1

print((fib(n, fib_table)))
# Original solution
def fibonacci(n):
    if n == 0 or n == 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

if __name__ == '__main__':
    n = int(eval(input()))
    print((fibonacci(n)))

# Optimized solution
def fibonacci(n):
    a, b = 1, 1
    for i in range(n-1):
        a, b = b, a+b

    return b

if __name__ == '__main__':
    n = int(eval(input()))
    print((fibonacci(n)))
# Original solution
F_list = [1,1] + [None]*43

def fibo(n):
  F=F_list[n]
  if n==0 or n==1: return F
  F = fibo(n-1)+fibo(n-2)
  F_list[n]=F
  return F


n = int(eval(input()))

print((fibo(n)))

# Optimized solution
F =[1,1] + [0 for i in range(44)]

n = int(eval(input()))

for i in range(2,n+1):
  F[i]=F[i-1]+F[i-2]

print((F[n]))
# Original solution
def check(pattern):
    for i in range(W - 2):
        mask = 0b11 << i
        if pattern & mask == mask:
            return False
    return True


def simulate(a1, pattern):
    pat = [pattern & (1 << w) != 0 for w in range(W - 1)]
    if a1 != W - 1 and pat[a1]:
        return a1 + 1
    elif a1 != 0 and pat[a1 - 1]:
        return a1 - 1
    else:
        return a1


H, W, K = list(map(int, input().split()))
dp = [[0] * W for h in range(H + 1)]
dp[0][0] = 1
for h in range(1, H + 1):
    for pattern in range(2 ** (W - 1)):
        for w in range(W):
            if check(pattern):
                dp[h][simulate(w, pattern)] += dp[h - 1][w]
                dp[h][simulate(w, pattern)] %= 1000000007
print((dp[H][K - 1]))


# Optimized solution
def check(pat):
    for i in range(W - 2):
        mask = 0b11 << i
        if pat & mask == mask:
            return False
    return True


def simulate(a1, pat):
    if a1 != W - 1 and pat & 1 << a1 != 0:
        return a1 + 1
    elif a1 != 0 and pat & 1 << a1 - 1 != 0:
        return a1 - 1
    else:
        return a1


H, W, K = list(map(int, input().split()))
dp = [[0] * W for h in range(H + 1)]
dp[0][0] = 1
for h in range(1, H + 1):
    for pat in range(2 ** (W - 1)):
        for w in range(W):
            if check(pat):
                dp[h][simulate(w, pat)] += dp[h - 1][w]
                dp[h][simulate(w, pat)] %= 1000000007
print((dp[H][K - 1]))
# Original solution

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


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

ws = set()
for bit in range(1 << (W-1)):
    if "11" in bin(bit):
        continue
    ws.add(bit)


for i in range(H):
    for bit in ws:
        # 高さi、左からj本目の縦棒にいるとき、どう移動するか。
        for j in range(W):
          

            # 右に移る棒がある時に、右に行ってから下へ移動する場合
            if j != W-1 and bit & (1 << (W-2-j)): # j=0 の時に左端に1が立っているか確認したい、
                    dp[i+1][j+1] += dp[i][j]
                    dp[i+1][j+1] %= MOD

            # 左に移る棒があるときに、左に行ってから下へ移動する場合
            elif j != 0 and bit & (1 << (W-1-j)): # j=W-1 のときに、右端に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(i,bin(bit),j,dp)



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

# Optimized solution


"""
AtCoder Beginner Contest 113  D - Number of Amidakuji

愚直に考えると、
・それぞれの縦棒の間に、横棒があるかないかの2通り。これがある高さhだけで、2^(W-1)通りある（横棒が２連続で続かないので、厳密には違うが）。
・これが高さH（最大100個分）あるので、(2^7)^100 とか？とにかく全探索は間に合わない。

メタ視点だが、W<=8なので、bitDPとかやれそう。
愚直解の何がよくないかというと、たとえば H = 6,W = 4 みたいなあみだくじについて考えるとして、
・この中で上から3段目までが同じでそれより下が異なるあみだくじというのがあるが、同じ部分も毎回シミュレートしてしまうのが重複計算になって無駄。

なので、高さごとに取りうる横棒のパターンを確認して、それらについて移動先の場合の数を求めていけばいいか。

各高さについて毎回横棒のパターンをbitで探索するが何故か思いつかなかった。
"""

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


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

ws = set()
for bit in range(1 << (W-1)):
    if "11" in bin(bit):
        continue
    ws.add(bit)


for i in range(H):
    for bit in ws:
        # 高さi、左からj本目の縦棒にいるとき、どう移動するか。
        for j in range(W):
          

            # 右に移る棒がある時に、右に行ってから下へ移動する場合
            if j != W-1 and bit & (1 << (W-2-j)): # j=0 の時に左端に1が立っているか確認したい、
                    dp[i+1][j+1] += dp[i][j]
                    dp[i+1][j+1] %= MOD

            # 左に移る棒があるときに、左に行ってから下へ移動する場合
            elif j != 0 and bit & (1 << (W-1-j)): # j=W-1 のときに、右端に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(i,bin(bit),j,dp)



print((dp[-1][K-1]))
#print(dp)
#print(ws)
# Original solution
H, W, K = list(map(int, input().split()))
mod = 10 ** 9 + 7
F = [1, 1, 2, 3, 5, 8, 13, 21, 34]
inv_F = pow(F[W], mod - 2, mod)
P = [[0 for w in range(W + 2)] for h in range(H + 1)]
P[0][1] = 1

if W > 1:
    for h in range(1, H + 1):
        for w in range(1, W + 1):
            P[h][w] = (P[h - 1][w - 1] * F[w - 2] * F[W - w] % mod
                       + P[h - 1][w] * F[w - 1] * F[W - w] % mod
                       + P[h - 1][w + 1] * F[w - 1] * F[W - w - 1] % mod) * inv_F % mod

    print((P[H][K] * pow(F[W], H, mod) % mod))
else:
    print((1))

# Optimized solution
H, W, K = list(map(int, input().split()))
mod = 10 ** 9 + 7
F = [1, 1, 2, 3, 5, 8, 13, 21, 34]
inv_F = pow(F[W], mod - 2, mod)
P = [[0 for w in range(W + 2)] for h in range(H + 1)]
P[0][1] = 1

for h in range(1, H + 1):
    for w in range(1, W + 1):
        P[h][w] = (P[h - 1][w - 1] * F[w - 2] * F[W - w] % mod
                   + P[h - 1][w] * F[w - 1] * F[W - w] % mod
                   + P[h - 1][w + 1] * F[w - 1] * F[W - w - 1] % mod) * inv_F % mod

print((P[H][K] * pow(F[W], H, mod) % mod))
# Original solution
H, W, K = list(map(int, input().split()))
mod = 10 ** 9 + 7

# 高さiにおいて左からj番目の棒にいる通り数
dp = [[0] * W for i in range(H + 1)]
dp[0][0] = 1


def pattern(w):
    """ 幅wのあみだにおいて、validなものの通り数を返す """
    # 例外処理
    if w < 0:
        return 1

    cnt = 0
    for i in range(2 ** w):
        b = bin(2 ** w + i)[3:]
        if '11' not in b:
            cnt += 1
    return cnt


for i in range(1, H + 1):
    for j in range(W):
        tmp = 0
        # 上からおりてくる
        tmp += dp[i - 1][j] * pattern(j - 1) * pattern(W - j - 2) % mod

        # 左からおりてくる
        if j > 0:
            tmp += dp[i - 1][j - 1] * pattern(j - 2) * pattern(W - j - 2) % mod

        # 右からおりてくる
        if j < W - 1:
            tmp += dp[i - 1][j + 1] * pattern(j - 1) * pattern(W - j - 3) % mod

        dp[i][j] += tmp

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


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

# dp[i][j]:= 上からi番目, 左からj番目にいる通り数
dp = [[0] * W for i in range(H + 1)]
dp[0][0] = 1


def calc(x):
    if x < 0:
        return 1
    ret = 0
    for p in product(['0', '1'], repeat=x):
        p = ''.join(p)
        if '11' not in p:
            ret += 1
    return ret


for i in range(1, H + 1):
    for j in range(W):
        tmp = 0
        if j > 0:  # 左から
            tmp += dp[i - 1][j - 1] * calc(j - 2) * calc(W - j - 2) % mod

        # 上から
        tmp += dp[i - 1][j] * calc(j - 1) * calc(W - j - 2) % mod

        if j + 1 < W:  # 右から
            tmp += dp[i - 1][j + 1] * calc(j - 1) * calc(W - j - 3) % mod

        dp[i][j] = tmp

print((dp[H][K - 1] % mod))
# Original solution
from itertools import product
H, W, K = list(map(int, input().split()))
mod = 10 ** 9 + 7

# dp[i][j]:= 上からi番目, 左からj番目にいる通り数
dp = [[0] * W for i in range(H + 1)]
dp[0][0] = 1


def calc(x):
    if x < 0:
        return 1
    ret = 0
    for p in product(['0', '1'], repeat=x):
        p = ''.join(p)
        if '11' not in p:
            ret += 1
    return ret


for i in range(1, H + 1):
    for j in range(W):
        tmp = 0
        if j > 0:  # 左から
            tmp += dp[i - 1][j - 1] * calc(j - 2) * calc(W - j - 2) % mod

        # 上から
        tmp += dp[i - 1][j] * calc(j - 1) * calc(W - j - 2) % mod

        if j + 1 < W:  # 右から
            tmp += dp[i - 1][j + 1] * calc(j - 1) * calc(W - j - 3) % mod

        dp[i][j] = tmp

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


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


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


# h行w列に到達する方法
dp = [[0] * W for h in range(H + 1)]
dp[0][0] = 1

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

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

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

print((dp[H][K - 1]))
# Original solution
from itertools import product
H, W, K = list(map(int, input().split()))
MOD = 10 ** 9 + 7

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


def calc(w):
    if w <= 0:
        return 1
    ret = 0
    for pattern in product([0, 1], repeat=w):
        pattern = ''.join(list(map(str, pattern)))
        if '11' not in pattern:
            ret += 1
    return ret


for h in range(H):
    for w in range(W):
        dp[h + 1][w] = (dp[h + 1][w] + dp[h][w] * calc(w - 1) * calc(W - w - 2)) % MOD
        if w + 1 < W:
            dp[h + 1][w + 1] = (dp[h + 1][w + 1] + dp[h][w] * calc(w - 1) * calc(W - w - 3) % MOD)
        if w - 1 >= 0:
            dp[h + 1][w - 1] = (dp[h + 1][w - 1] + dp[h][w] * calc(w - 2) * calc(W - w - 2) % MOD)

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


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

dp = [[0] * W for i in range(H + 1)]
dp[0][0] = 1
fib = [1, 2, 3, 5, 8, 13, 21, 34]


def calc(w):
    if w < 0:
        return 1
    return fib[w]


for h in range(H):
    for w in range(W):
        dp[h + 1][w] = (dp[h + 1][w] + dp[h][w] * calc(w - 1) * calc(W - w - 2)) % MOD
        if w + 1 < W:
            dp[h + 1][w + 1] = (dp[h + 1][w + 1] + dp[h][w] * calc(w - 1) * calc(W - w - 3) % MOD)
        if w - 1 >= 0:
            dp[h + 1][w - 1] = (dp[h + 1][w - 1] + dp[h][w] * calc(w - 2) * calc(W - w - 2) % MOD)

print((dp[H][K - 1] % MOD))
# Original solution
import sys

def S(): return sys.stdin.readline().rstrip()

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

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

fib = [1,1,2,3,5,8,13,21]  # fib[i] = i本の縦線に横線を引く方法の数(同じ高さ)

dp = [[0]*(W+1) for _ in range(H+1)]  # dp[i][j] = i行目にjに達する横線の引き方

for i in range(H+1):
    for j in range(W+1):
        if i == 0:
            if j == 1:
                dp[i][j] = 1
        else:
            if j == 1:
                dp[i][j] = dp[i-1][j]*fib[W-1] + dp[i-1][j+1]*fib[W-2]
                dp[i][j] %= mod
            elif j == W:
                dp[i][j] = dp[i-1][j-1]*fib[W-2] + dp[i-1][j]*fib[W-1]
                dp[i][j] %= mod
            elif 2 <= j <= W-1:
                dp[i][j] = dp[i-1][j-1]*(fib[j-2]*fib[W-j]) + dp[i-1][j]*(fib[j-1]*fib[W-j]) + dp[i-1][j+1]*(fib[j-1]*fib[W-j-1])
                dp[i][j] %= mod

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

# Optimized solution
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

H,W,K = MI()
mod = 10**9+7

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

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

dp = [[0]*(W+1) for _ in range(H+1)]
dp[0][1] = 1
for i in range(1,H+1):
    for j in range(1,W+1):
        if W == 2:
            if j == 1:
                dp[i][j] = dp[i-1][j] + dp[i-1][j+1]
                dp[i][j] %= mod
            else:
                dp[i][j] = dp[i-1][j] + dp[i-1][j-1]
                dp[i][j] %= mod
        else:
            if j == 1:
                dp[i][j] = dp[i-1][j+1]*fib[W-2] + dp[i-1][j]*fib[W-j]
                dp[i][j] %= mod
            elif j == W:
                dp[i][j] = dp[i-1][j-1]*fib[W-2] + dp[i-1][j]*fib[j-1]
                dp[i][j] %= mod
            else:
                dp[i][j] = dp[i-1][j-1]*fib[j-2]*fib[W-j] + dp[i-1][j+1]*fib[j-1]*fib[W-j-1] + dp[i-1][j]*(fib[W-j]*fib[j-1])
                dp[i][j] %= mod

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

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

H,W,K = MI()
mod = 10**9+7

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

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

dp = [[0]*(W+1) for _ in range(H+1)]
dp[0][1] = 1
for i in range(1,H+1):
    for j in range(1,W+1):
        if W == 2:
            if j == 1:
                dp[i][j] = dp[i-1][j] + dp[i-1][j+1]
                dp[i][j] %= mod
            else:
                dp[i][j] = dp[i-1][j] + dp[i-1][j-1]
                dp[i][j] %= mod
        else:
            if j == 1:
                dp[i][j] = dp[i-1][j+1]*fib[W-2] + dp[i-1][j]*fib[W-j]
                dp[i][j] %= mod
            elif j == W:
                dp[i][j] = dp[i-1][j-1]*fib[W-2] + dp[i-1][j]*fib[j-1]
                dp[i][j] %= mod
            else:
                dp[i][j] = dp[i-1][j-1]*fib[j-2]*fib[W-j] + dp[i-1][j+1]*fib[j-1]*fib[W-j-1] + dp[i-1][j]*(fib[W-j]*fib[j-1])
                dp[i][j] %= mod

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


# Optimized solution
import sys
def MI(): return list(map(int,sys.stdin.readline().rstrip().split()))

H,W,K = MI()
mod = 10**9+7

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

fib = [1,1,2,3,5,8,13,21]  # fib[i] = i本のあみだくじの、ある列に横線を引く方法の数

dp = [[0]*(W+1) for _ in range(H+1)]  # dp[i][j] = i段横線を引いたときに1からKに至るような横線の引き方
dp[0][1] = 1
for i in range(1,H+1):
    for j in range(1,W+1):
        if j == 1:
            dp[i][j] = dp[i-1][j+1]*fib[W-j-1] + dp[i-1][j]*fib[W-j]
            dp[i][j] %= mod
        elif j == W:
            dp[i][j] = dp[i-1][j-1]*fib[j-2] + dp[i-1][j]*fib[j-1]
            dp[i][j] %= mod
        else:
            dp[i][j] = dp[i-1][j-1]*fib[j-2]*fib[W-j] + dp[i-1][j+1]*fib[j-1]*fib[W-j-1] + dp[i-1][j]*fib[W-j]*fib[j-1]
            dp[i][j] %= mod

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