AtCoder Beginner Contest 113 - Number of Amidakuji

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: MEDIUM

Starter code:

Solutions:
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()))
dp = [[0] * (h + 2) for _ in range(w + 2)]
comb = [1] * (w + 5)
comb[2] = 2
for i in range(3, w + 1):
	for j in range(1, i):
		comb[i] += comb[i - j - 1]
dp[1][0] = 1
mod = 10 ** 9 + 7
for hh in range(1, h + 1):
	for ww in range(1, w + 1):
		dp[ww][hh] += comb[ww - 1] * comb[w - ww] * dp[ww][hh - 1]
		dp[ww][hh] += comb[ww - 2] * comb[w - ww] * dp[ww - 1][hh - 1]
		dp[ww][hh] += comb[ww - 1] * comb[w - ww - 1] * dp[ww + 1][hh - 1]
		dp[ww][hh] %= mod
print(dp[k][h])


(H, W, K) = map(int, input().split())
MOD = 10 ** 9 + 7
dp = [[0 for _ in range(W)] for _ in range(H + 1)]
dp[0][0] = 1
fib = [1] * (W + 2)
for i in range(2, W + 2):
	fib[i] = fib[i - 1] + fib[i - 2]

def pat(w):
	if w < 1:
		return 1
	else:
		return fib[w + 1]
for i in range(H):
	for j in range(W):
		dp[i + 1][j] = (dp[i + 1][j] + dp[i][j] * pat(j - 1) * pat(W - j - 2)) % MOD
		if j > 0:
			dp[i + 1][j - 1] = (dp[i + 1][j - 1] + dp[i][j] * pat(j - 2) * pat(W - j - 2)) % MOD
		if j <= W - 2:
			dp[i + 1][j + 1] = (dp[i + 1][j + 1] + dp[i][j] * pat(j - 1) * pat(W - j - 3)) % MOD
print(dp[H][K - 1] % MOD)


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

def multiple(N):
	temp = [1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
	return temp[N + 1]
for i in range(1, H + 1):
	for j in range(1, W + 2):
		if j < 1 or j > W:
			A[i][j] = 0
		else:
			A[i][j] = (A[i - 1][j - 1] * (multiple(j - 2) * multiple(W - j)) + A[i - 1][j] * (multiple(j - 1) * multiple(W - j)) + A[i - 1][j + 1] * (multiple(j - 1) * multiple(W - j - 1))) % mod
print(A[H][K])


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


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


(h, w, k) = map(int, input().split())
a = [0] * (w - 1) + [0, 1]
for i in range(w - 1):
	a[i] = a[i - 1] + a[i - 2]
dp = [0] * (w + 1)
tmp = [0] * (w + 1)
dp[0] = 1
for _ in range(1, h + 1):
	for i in range(w):
		tmp[i] = (dp[i] * a[i - 1] * a[w - i - 2] + dp[i + 1] * a[i - 1] * a[w - i - 3] + dp[i - 1] * a[i - 2] * a[w - i - 2]) % (10 ** 9 + 7)
	(dp, tmp) = (tmp, dp)
print(dp[k - 1])


from itertools import product
(h, w, k) = 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)


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]
				elif 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]
print(dp[h][K - 1] % mod)


import sys
(H, W, K) = map(int, input().split())
if W == 1:
	print(1)
	sys.exit()
L = [1, 1, 2, 3, 5, 8, 13, 21, 34]
mod = 10 ** 9 + 7
dp = [[0] * W for i in range(H + 1)]
dp[0][0] = 1
for i in range(H):
	for j in range(W):
		if j == 0:
			dp[i + 1][j] += dp[i][j] * L[W - 1]
			dp[i + 1][j] += dp[i][j + 1] * L[W - 2]
			dp[i + 1][j] %= mod
		elif j == W - 1:
			dp[i + 1][j] += dp[i][j] * L[W - 1]
			dp[i + 1][j] += dp[i][j - 1] * L[W - 2]
			dp[i + 1][j] %= mod
		else:
			dp[i + 1][j] += dp[i][j - 1] * L[j - 1] * L[W - j - 1]
			dp[i + 1][j] += dp[i][j] * L[j] * L[W - j - 1]
			dp[i + 1][j] += dp[i][j + 1] * L[j] * L[W - j - 2]
			dp[i + 1][j] %= mod
print(dp[H][K - 1])


(h, w, k) = map(int, input().split())
mod = 10 ** 9 + 7
am = [1, 1, 2, 3, 5, 8, 13, 21]
DP = [[0 for i in range(w + 1)] for j in range(h + 1)]
DP[0][1] = 1
for i in range(1, h + 1):
	for j in range(1, w + 1):
		DP[i][j] = DP[i - 1][j] * am[j - 1] * am[w - j] % mod
		if j > 1:
			DP[i][j] += DP[i - 1][j - 1] * am[j - 2] * am[w - j] % mod
		if j < w:
			DP[i][j] += DP[i - 1][j + 1] * am[j - 1] * am[w - j - 1] % mod
print(DP[h][k] % mod)


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


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


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


mod = 10 ** 9 + 7
(H, W, K) = map(int, input().split())
K -= 1
dp = [0] * W
dp[0] = 1
ndp = [0] * W
for r in range(H):
	for i in range(1 << W - 1):
		if '11' in bin(i):
			continue
		perm = [i for i in range(W)]
		for j in range(W - 1):
			if i >> j & 1:
				(perm[j], perm[j + 1]) = (perm[j + 1], perm[j])
		for j in range(W):
			next_line = perm[j]
			ndp[next_line] += dp[j]
			ndp[next_line] %= mod
	dp = ndp.copy()
	ndp = [0] * W
print(dp[K])


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


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


mod = 10 ** 9 + 7
(H, W, K) = map(int, input().split())
if W == 1:
	print(1)
	exit()
dp = [[0] * W for _ in range(H + 1)]
dp[0][K - 1] = 1
factor = [0] * (W - 1)
for i in range(W - 1):
	for j in range(1 << i):
		for k in range(i - 1):
			if j >> k & j >> k + 1:
				break
		else:
			factor[i] += 1
for i in range(1, H + 1):
	for j in range(W):
		for k in [-1, 0, 1]:
			if 0 <= j + k < W:
				left = max(min(j, j + k) - 1, 0)
				right = max(W - max(j, j + k) - 2, 0)
				dp[i][j] += dp[i - 1][j + k] * factor[left] * factor[right]
		dp[i][j] %= mod
print(dp[H][0])


def check(pat):
	for i in range(W - 2):
		mask = 3 << 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) = 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])


def bin_cho(n):
	if n == 1:
		return 2
	elif n <= 0:
		return 1
	else:
		return bin_cho(n - 2) + bin_cho(n - 1)
(h, w, k) = map(int, input().split())
l = [[0] * w for _ in range(h + 1)]
l[0][0] = 1
for j in range(1, h + 1):
	for i in range(w):
		l[j][i] += l[j - 1][i] * bin_cho(w - i - 2) * bin_cho(i - 1)
		if i - 1 >= 0:
			l[j][i] += l[j - 1][i - 1] * bin_cho(w - i - 2) * bin_cho(i - 2)
		if i + 1 <= w - 1:
			l[j][i] += l[j - 1][i + 1] * bin_cho(w - i - 3) * bin_cho(i - 1)
		l[j][i] %= 10 ** 9 + 7
print(l[h][k - 1])


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
	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()
__starting_point()


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)
__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):
			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) = 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 = 0 if w == 1 else 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])


import copy

def f(n):
	if n == 0:
		return 1
	elif n == 1:
		return 2
	else:
		return f(n - 1) + f(n - 2)
p = 10 ** 9 + 7
(H, W, K) = map(int, input().split())
if W == 1:
	ans = 1
else:
	d = {}
	for i in range(8):
		d[i] = f(i)
	d[-1] = d[-2] = d[-3] = 1
	b = [0 for i in range(W + 2)]
	a = [0 for i in range(W + 2)]
	b[1] = d[W - 2]
	b[2] = d[W - 3]
	for i in range(H - 1):
		for k in range(1, W + 1):
			a[k] = b[k - 1] * d[k - 3] * d[W - k - 1]
			a[k] += b[k] * d[k - 2] * d[W - k - 1]
			a[k] += b[k + 1] * d[k - 2] * d[W - k - 2]
			a[k] %= p
		b = copy.copy(a)
	ans = b[K]
print(ans)


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


mod = 10 ** 9 + 7
(H, W, K) = map(int, input().split())
a = [0] * 20
a[0] = 1
a[1] = 1
for i in range(10):
	a[i + 2] = a[i + 1] + a[i]
dp = [[0] * (W + 1) for _ in range(H + 1)]
dp[0][0] = 1
for h in range(H):
	for k in range(W):
		dp[h + 1][k] += a[k] * a[W - k - 1] * dp[h][k]
		dp[h + 1][k] += a[k - 1] * a[W - k - 1] * dp[h][k - 1]
		dp[h + 1][k] += a[k] * a[W - k - 2] * dp[h][k + 1]
		dp[h + 1][k] %= mod
print(dp[H][K - 1])


(H, W, K) = map(int, input().split())
mod = 10 ** 9 + 7
dp = [[0 for _ in range(W + 2)] for _ in range(H + 2)]
dp[0][1] = 1
fib = [0] * (W + 1)
fib[1] = 1
for i in range(2, W + 1):
	fib[i] = fib[i - 1] + fib[i - 2]
for i in range(1, H + 1):
	for j in range(1, W + 1):
		dp[i][j] = (dp[i - 1][j - 1] * fib[j - 1] * fib[W - j + 1] + dp[i - 1][j] * fib[j] * fib[W - j + 1] + dp[i - 1][j + 1] * fib[j] * fib[W - j]) % mod
print(dp[H][K])


from collections import defaultdict
(H, W, K) = map(int, input().split())
dp1 = [[0] * 2 for _ in range(W)]
dp1[0][0] = 1
for i in range(W - 1):
	dp1[i + 1][0] = dp1[i][0] + dp1[i][1]
	dp1[i + 1][1] = dp1[i][0]
d = defaultdict(int)
d[-1] = 1
for i in range(W):
	d[i] = dp1[i][0] + dp1[i][1]
dp2 = [[0] * W for _ in range(H + 1)]
dp2[0][0] = 1
MOD = 10 ** 9 + 7
for i in range(H):
	for j in range(W):
		for k in range(max(0, j - 1), min(W - 1, j + 1) + 1):
			l = min(j, k) - 1
			r = W - 2 - max(j, k)
			dp2[i + 1][k] += dp2[i][j] * d[l] * d[r]
			dp2[i + 1][k] %= MOD
print(dp2[H][K - 1])


(h, w, K) = map(int, input().split())
mod = 10 ** 9 + 7
dp = [[0] * (w + 1) 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)):
			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 - 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])


(h, w, k) = 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])


import sys
import math
import collections
import bisect
import copy
sys.setrecursionlimit(10 ** 7)
INF = 10 ** 16
MOD = 10 ** 9 + 7
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()])

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:
				dp[y][x] += dp[y - 1][x] * fibo[max(0, w - 1 - 1)]
				if w > 1:
					dp[y][x] += dp[y - 1][x + 1] * fibo[max(0, w - 1 - 2)]
			elif x == w - 1:
				dp[y][x] += dp[y - 1][x] * fibo[max(0, w - 1 - 1)]
				if w > 1:
					dp[y][x] += dp[y - 1][x - 1] * fibo[max(0, w - 1 - 2)]
			else:
				dp[y][x] += dp[y - 1][x] * fibo[x - 1] * fibo[max(0, w - 1 - x - 1)]
				dp[y][x] += dp[y - 1][x - 1] * fibo[max(0, x - 1 - 1)] * fibo[max(0, w - 1 - x - 1)]
				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
(H, W, K) = map(int, input().split())
if W == 1:
	print(1)
	sys.exit()
elif W == 2:
	print(2 ** (H - 1))
	sys.exit()
dic = [1, 2, 3, 5, 8, 13, 21, 34, 55, 1]
a = [[0] * W for i in range(H + 1)]
a[0][0] = 1
for i in range(1, H + 1):
	a[i][0] = a[i - 1][0] * dic[W - 2] + a[i - 1][1] * dic[W - 3]
	for j in range(1, W - 1):
		a[i][j] = a[i - 1][j - 1] * dic[j - 2] * dic[W - j - 2] + a[i - 1][j] * dic[j - 1] * dic[W - j - 2] + a[i - 1][j + 1] * dic[j - 1] * dic[W - j - 3]
	a[i][W - 1] = a[i - 1][W - 1] * dic[W - 2] + a[i - 1][W - 2] * dic[W - 3]
print(a[H][K - 1] % 1000000007)


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

def dfs(i, T, flag):
	if i >= W - 1:
		for (j, t) in enumerate(T):
			F[j][t] += 1
		return None
	dfs(i + 1, T[:], False)
	if not flag:
		(T[i], T[i + 1]) = (T[i + 1], T[i])
		dfs(i + 1, T[:], True)
dfs(0, [i for i in range(W)], False)
A = [[0] * W for i in range(H + 1)]
A[0][0] = 1
for h in range(H):
	for w in range(W):
		for w2 in range(W):
			A[h + 1][w2] += A[h][w] * F[w][w2]
			A[h + 1][w2] %= p
print(A[H][K - 1])


from functools import lru_cache

def solve(string):
	(h, w, k) = map(int, string.split())
	c = [1, 1]
	for _ in range(1, 7):
		(i, j) = c[-2:]
		c.append(i + j)

	@lru_cache(h * w)
	def rec(pos, depth):
		if depth == h:
			return 1 if pos == 1 else 0
		ans = rec(pos, depth + 1) * c[pos - 1] * c[w - pos]
		if pos < w:
			ans += rec(pos + 1, depth + 1) * c[pos - 1] * c[w - pos - 1]
		if pos > 1:
			ans += rec(pos - 1, depth + 1) * c[pos - 2] * c[w - pos]
		return ans
	return str(rec(k, 0) % (10 ** 9 + 7))
print(solve(input()))


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


(H, W, K) = map(int, input().split())
A = [[0] * W for i in range(H + 1)]
A[0][0] = 1
MOD = 10 ** 9 + 7
for i in range(H):
	for j in range(W):
		for k in range(1 << W - 1):
			for l in range(W - 1):
				if k >> l & 1 and k >> l + 1 & 1:
					break
			else:
				if j > 0 and k >> j - 1 & 1:
					A[i + 1][j - 1] += A[i][j]
					A[i + 1][j - 1] %= MOD
				elif j < W - 1 and k >> j & 1:
					A[i + 1][j + 1] += A[i][j]
					A[i + 1][j + 1] %= MOD
				else:
					A[i + 1][j] += A[i][j]
					A[i + 1][j] %= MOD
print(A[H][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()


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


(h, w, k) = list(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, 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])


def amida(arr, rest):
	num = 0
	if rest < 1:
		return 1
	num += amida(arr, rest - 2)
	arr[-rest - 1] += num
	num += amida(arr, rest - 1)
	return num
(H, W, K) = list(map(int, input().split()))
arr = [0 for i in range(W + 2)]
arr[1] = 1
line = [0 for i in range(W + 1)]
sum_ = amida(line, W - 1)
for i in range(H):
	tmp = arr[:]
	for j in range(1, W + 1):
		arr[j] = (tmp[j] * (sum_ - line[j] - line[j - 1]) + tmp[j + 1] * line[j] + tmp[j - 1] * line[j - 1]) % (10 ** 9 + 7)
print(arr[K])


mod = 10 ** 9 + 7
A = [1, 1, 2, 3, 5, 8, 13, 21, 34]
(H, W, K) = map(int, input().split())
dp = [[0] * W for i in range(H + 1)]
dp[0][0] = 1
for h in range(1, H + 1):
	for i in range(W):
		dp[h][i] = dp[h - 1][i] * A[i] * A[W - i - 1]
		if i > 0:
			dp[h][i] += dp[h - 1][i - 1] * A[i - 1] * A[W - i - 1]
		if i < W - 1:
			dp[h][i] += dp[h - 1][i + 1] * A[i] * A[W - i - 2]
		dp[h][i] = dp[h][i] % mod
print(dp[H][K - 1])


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

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


MOD = 10 ** 9 + 7
(H, W, K) = 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):
			ok = True
			for k in range(W - 2):
				if bit & 1 << k and bit & 1 << k + 1:
					ok = False
			if not ok:
				continue
			nj = j
			if bit & 1 << j:
				nj = j + 1
			elif j > 0 and bit & 1 << j - 1:
				nj = j - 1
			dp[i + 1][nj] += dp[i][j]
			dp[i + 1][nj] %= MOD
print(dp[H][K] % MOD)


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


import sys, collections as cl
Max = sys.maxsize

def l():
	return list(map(int, input().split()))

def m():
	return map(int, input().split())

def s(x):
	a = []
	aa = x[i]
	su = 1
	for i in range(len(x) - 1):
		if aa == x[i + 1]:
			a.append([aa, su])
			aa = x[i + 1]
			su = 1
		else:
			su += 1
	a.append([aa, su])
	return a
(h, w, k) = m()
a = [1, 1]
for i in range(98):
	a.append(a[-1] + a[-2])
l = [[0 for i in range(w + 2)] for j in range(h + 1)]
l[0][1] = 1
for i in range(h):
	for j in range(w):
		l[i + 1][j + 1] = (l[i][j] * (a[max(0, j - 1)] * a[w - 1 - j]) + l[i][j + 1] * (a[j] * a[w - 1 - j]) + l[i][j + 2] * (a[j] * a[max(0, w - 2 - j)])) % (10 ** 9 + 7)
print(l[h][k])


mod = 10 ** 9 + 7
fib = [1, 1, 2, 3, 5, 8, 13, 21, 34]
(H, W, K) = map(int, input().split())
dp = [0] * W
dp[0] = 1
for _ in range(H):
	T = [0] * W
	for i in range(W):
		if 0 < i:
			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])


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


(h, w, k) = map(int, input().split())
dp = [[0] * w for _ in range(h + 1)]
dp[0][0] = 1
fb = (1, 1, 2, 3, 5, 8, 13, 21)
for y in range(1, h + 1):
	for x in range(w):
		if x - 1 >= 0:
			dp[y][x] += dp[y - 1][x - 1] * fb[x - 1] * fb[w - x - 1]
		if x + 1 <= w - 1:
			dp[y][x] += dp[y - 1][x + 1] * fb[x] * fb[w - x - 2]
		dp[y][x] += dp[y - 1][x] * fb[x] * fb[w - x - 1]
		dp[y][x] %= 1000000007
print(dp[h][k - 1])


(H, W, K) = map(int, input().split())
mod = 10 ** 9 + 7
a = [1, 1, 2, 3, 5, 8, 13, 21]
T = [[-1 for i in range(9)] for i in range(H + 1)]

def n(h, k):
	if T[h][k] != -1:
		return T[h][k]
	res = 0
	if h == 1:
		if k == 1 or k == 2:
			T[h][k] = a[W - k]
			return a[W - k]
		else:
			T[h][k] = 0
			return 0
	res += n(h - 1, k) * (a[k - 1] * a[W - k])
	if k != 1:
		res += n(h - 1, k - 1) * (a[k - 1 - 1] * a[W - k])
	if k != W:
		res += n(h - 1, k + 1) * (a[k - 1] * a[W - k - 1])
	T[h][k] = res
	return res % mod
ans = n(H, K)
print(ans)


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


(h, w, k) = map(int, input().split())
mod = 10 ** 9 + 7
g = [[0] * 3 for _ in range(w)]
for bit in range(1 << w - 1):
	f = 0
	for i in range(w - 2):
		if bit & 3 << i == 3 << i:
			f = 1
			break
	if f:
		continue
	neu = [1] * w
	for i in range(w - 1):
		if bit & 1 << i:
			g[i][2] += 1
			g[i + 1][0] += 1
			neu[i] = 0
			neu[i + 1] = 0
		g[i][1] += neu[i]
	g[-1][1] += neu[-1]
g = [[0] * 3] + g + [[0] * 3]
ol = [0] * (w + 2)
ol[k] = 1
for _ in range(h):
	new = [0] * (w + 2)
	for i in range(1, w + 1):
		new[i] = (ol[i - 1] * g[i - 1][2] + ol[i] * g[i][1] + ol[i + 1] * g[i + 1][0]) % mod
	ol = new
print(ol[1])


(H, W, K) = [int(i) for i in input().split()]
Fn = [1, 1, 2, 3, 5, 8, 13, 21, 0]
ans = []
ans0 = [0 for i in range(W + 2)]
ans0[1] = 1
ans.append(ans0)
for i in range(1, H + 1):
	ansi = [0 for i in range(W + 2)]
	for j in range(1, W + 1):
		ansi[j - 1] += ans[i - 1][j] * Fn[j - 2] * Fn[W - j]
		ansi[j] += ans[i - 1][j] * Fn[j - 1] * Fn[W - j]
		ansi[j + 1] += ans[i - 1][j] * Fn[j - 1] * Fn[W - j - 1]
	for j in range(W + 2):
		ansi[j] %= 1000000007
	ans.append(ansi)
print(ans[H][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)


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


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


MOD = int(1000000000.0 + 7)
(sizeI, sizeJ, targetJ) = map(int, input().split())
validRows = [row for row in range(1 << sizeJ - 1) if '11' not in bin(row)]
dp = [[0 for _ in range(sizeJ)] for _ in range(sizeI + 1)]
dp[0][0] = 1
for i in range(1, sizeI + 1):
	for j in range(sizeJ):
		for prevRow in validRows:
			if j - 1 >= 0 and prevRow >> j - 1 & 1:
				dp[i][j] += dp[i - 1][j - 1]
			elif prevRow >> j & 1:
				dp[i][j] += dp[i - 1][j + 1]
			else:
				dp[i][j] += dp[i - 1][j]
			dp[i][j] %= MOD
print(dp[sizeI][targetJ - 1])


import sys
from collections import defaultdict
input = sys.stdin.readline
(H, W, K) = list(map(int, input().split()))
mod = 1000000007
c = defaultdict(lambda : 1)
c.update({0: 1, 1: 2, 2: 3, 3: 5, 4: 8, 5: 13, 6: 21})
dp = [{0: 0, 1: 1, 2: 0, 3: 0, 4: 0, 5: 0, 6: 0, 7: 0, 8: 0, 9: 0}]
for i in range(1, H + 2):
	dp_i = {0: 0, W + 1: 0}
	for j in range(1, W + 1):
		dp_i[j] = dp[i - 1][j - 1] * c[j - 3] * c[W - j - 1] % mod + dp[i - 1][j] * c[j - 2] * c[W - j - 1] % mod + dp[i - 1][j + 1] * c[j - 2] * c[W - j - 2] % mod
	dp.append(dp_i)
print(dp[H][K] % mod)


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)
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())
p = [sum((('11' in str(bin(j))) ^ 1 for 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])


MOD = 10 ** 9 + 7
(h, w, k) = 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())
n = w - 1
dp = [[0] * w for _ in range(h + 1)]
dp[0][0] = 1

def judge(edge):
	for i in range(1, n):
		if edge[i] and edge[i - 1]:
			return False
	return True
for i in range(1, h + 1):
	for j in range(w):
		for k in range(2 ** n):
			edge = [1 & k >> l for l in range(n)]
			if not judge(edge):
				continue
			if j < w - 1 and edge[j]:
				dp[i][j] += dp[i - 1][j + 1]
			if j > 0 and edge[j - 1]:
				dp[i][j] += dp[i - 1][j - 1]
			edge.append(0)
			if not edge[j] and (not edge[j - 1]):
				dp[i][j] += dp[i - 1][j]
			dp[i][j] %= MOD
print(dp[h][K - 1])


(h, w, K) = 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])


import itertools

def amida_patterns(w):
	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()


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


(H, W, K) = map(int, input().split())
C = [1, 1, 2, 3, 5, 8, 13, 21]
Q = 10 ** 9 + 7
dp = [[1] + [0] * (W - 1) for _ in range(H + 1)]
if W == 1:
	H = 0
for i in range(1, H + 1):
	for j in range(W):
		if j == 0:
			dp[i][0] = (dp[i - 1][0] * C[W - 1] + dp[i - 1][1] * C[W - 2]) % Q
		elif j == W - 1:
			dp[i][W - 1] = (dp[i - 1][W - 1] * C[W - 1] + dp[i - 1][W - 2] * C[W - 2]) % Q
		else:
			dp[i][j] = (dp[i - 1][j] * C[j] * C[W - j - 1] + dp[i - 1][j - 1] * C[j - 1] * C[W - j - 1] + dp[i - 1][j + 1] * C[j] * C[W - j - 2]) % Q
print(dp[H][K - 1])


def memorize(func):
	memo = {}

	def wrapper(*args):
		if args not in memo:
			memo[args] = func(*args)
		return memo[args]
	return wrapper

@memorize
def amida(W):
	if W < 2:
		return 1
	else:
		return amida(W - 1) + amida(W - 2)

@memorize
def amida2(H, W, x):
	if H == 0:
		return 1 if x == 1 else 0
	a = 0 if x == 1 else amida(x - 2) * amida(W - x) * amida2(H - 1, W, x - 1)
	b = amida(x - 1) * amida(W - x) * amida2(H - 1, W, x)
	c = 0 if x == W else amida(x - 1) * amida(W - x - 1) * amida2(H - 1, W, x + 1)
	return (a + b + c) % 1000000007
print(amida2(*map(int, input().split())))


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


(H, W, K) = map(int, input().split())
mod = 10 ** 9 + 7
dp = [[0] * W for _ in range(H + 1)]
dp[0][0] = 1
L = [1, 2, 3, 5, 8, 13, 21]
for i in range(H):
	for j in range(W):
		if j > 0:
			dp[i + 1][j] += dp[i][j - 1] * L[max(0, j - 2)] * L[max(0, W - 2 - j)]
		if j < W - 1:
			dp[i + 1][j] += dp[i][j + 1] * L[max(0, j - 1)] * L[max(0, W - 3 - j)]
		dp[i + 1][j] += dp[i][j] * L[max(0, j - 1)] * L[max(0, W - 2 - j)]
		dp[i + 1][j] %= mod
print(dp[H][K - 1])


(h, w, k) = 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])


(h, w, k) = map(int, input().split())
mod = 10 ** 9 + 7
dp = [0] * (w + 2)
dp[1] = 1
ref = [1, 2, 3, 5, 8, 13, 21]
pat = lambda l, r: ref[max(l, 0)] * ref[max(r, 0)]
for i in range(h):
	_dp = [0] * (w + 2)
	for j in range(1, w + 1):
		_dp[j] = dp[j - 1] * pat(j - 3, w - j - 1) + dp[j] * pat(j - 2, w - j - 1) + dp[j + 1] * pat(j - 2, w - j - 2)
		_dp[j] %= mod
	dp = _dp
print(dp[k])


def main():
	[H, W, K] = list(map(int, input().split()))
	if W == 1:
		print(1)
		return
	dp = []
	for h in range(H + 1):
		dp.append([0] * (W + 1))
	ft = [1, 1, 2, 3, 5, 8, 13, 21, 34]
	d = 10 ** 9 + 7
	dp[0][1] = 1
	for h in range(1, H + 1):
		for w in range(1, W + 1):
			v = dp[h - 1][w] * ft[w - 1] * ft[W - w]
			if 2 <= w:
				v += dp[h - 1][w - 1] * ft[w - 2] * ft[W - w]
			if w <= W - 1:
				v += dp[h - 1][w + 1] * ft[w - 1] * ft[W - w - 1]
			dp[h][w] = v % d
	print(dp[H][K])
main()


(H, W, K) = map(int, input().split())
hp = {-2: 1, -1: 1, 0: 1, 1: 2, 2: 3, 3: 5, 4: 8, 5: 13, 6: 21, 7: 34}
d = {}
for s in range(1, W + 1):
	for g in range(1, W + 1):
		if s == g:
			d[0, s, g] = 1
		else:
			d[0, s, g] = 0
for h in range(1, H + 1):
	for s in range(1, W + 1):
		for g in range(1, W + 1):
			p = d[h - 1, s, g] * hp[s - 2] * hp[W - s - 1]
			if s > 1:
				p = p + d[h - 1, s - 1, g] * hp[s - 3] * hp[W - s - 1]
			if s < W:
				p = p + d[h - 1, s + 1, g] * hp[s - 2] * hp[W - s - 2]
			p = p % 1000000007
			d[h, s, g] = p
print(d[H, 1, 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])


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
		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
				elif 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()


(H, W, K) = map(int, input().split())
f = [1, 1]
while len(f) <= W:
	f.append(f[-2] + f[-1])
A = {(0, k): 1 if k == 1 else 0 for k in range(1, W + 1)}
for h in range(1, H + 1):
	for x in range(1, W + 1):
		pat = f[x - 1] * f[W - x] * A[h - 1, x]
		if x > 1:
			pat += f[x - 2] * f[W - x] * A[h - 1, x - 1]
		if x < W:
			pat += f[x - 1] * f[W - x - 1] * A[h - 1, x + 1]
		A[h, x] = pat
print(A[H, K] % 1000000007)


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


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


(H, W, K) = map(int, input().split())
a = [0]
b = [1]
c = [1]
P = 10 ** 9 + 7
X = [0 for i in range(W)]
X[0] = 1
for i in range(W):
	a.append(b[i])
	b.append(a[i] + b[i])
	c.append(a[-1] + b[-1])
for h in range(H):
	Y = [0 for i in range(W)]
	for w in range(W):
		t = X[w] * b[w] * b[W - w - 1]
		if w > 0:
			t += X[w - 1] * b[w - 1] * b[W - w - 1]
		if w < W - 1:
			t += X[w + 1] * b[w] * b[W - w - 2]
		t %= P
		Y[w] = t
	X = Y
print(X[K - 1])


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


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


(h, w, k) = list(map(int, input().split()))
n = [0, 1] + [0 for _ in range(w - 1)]
c = {0: 1, 1: 1, 2: 2, 3: 3, 4: 5, 5: 8, 6: 13, 7: 21}
for i in range(h):
	nn = [0 for _ in range(w + 1)]
	for j in range(1, w + 1):
		nn[j] += c[max(0, j - 1)] * n[j] * c[max(0, w - j)]
	for j in range(2, w + 1):
		nn[j] += c[max(0, j - 2)] * n[j - 1] * c[max(0, w - j)]
	for j in range(1, w):
		nn[j] += c[max(0, j - 1)] * n[j + 1] * c[max(0, w - j - 1)]
	n = nn
print(n[k] % 1000000007)


(H, W, k) = map(int, input().split())
MOD = 10 ** 9 + 7
if W == 1:
	print(1)
else:
	l = [1, 2, 3, 5, 8, 13, 21, 34, 1, 1, 1]
	dp = [[0 for _ in range(W)] for _ in range(H + 1)]
	dp[0][0] = 1
	for h in range(0, H):
		for w in range(W):
			if w != 0 and w != W - 1:
				dp[h + 1][w] = l[w - 1] * l[W - 2 - w] * dp[h][w] + l[w - 2] * l[W - 2 - w] * dp[h][w - 1] + l[w - 1] * l[W - 3 - w] * dp[h][w + 1]
			elif w == 0:
				dp[h + 1][w] = l[w - 1] * l[W - 2 - w] * dp[h][w] + l[w - 1] * l[W - 3 - w] * dp[h][w + 1]
			else:
				dp[h + 1][w] = l[w - 1] * l[W - 2 - w] * dp[h][w] + l[w - 2] * l[W - 2 - w] * dp[h][w - 1]
			dp[h + 1][w] %= MOD
	print(dp[H][k - 1])


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


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


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


from itertools import product
(H, W, K) = map(int, input().split())
pr = 10 ** 9 + 7
b = [0] * W
b[0] = 1
z = [0] * W
rl = tuple(product([0, 1], repeat=W - 1))
l = []
for i in rl:
	for j in range(W - 2):
		if i[j] and i[j + 1]:
			break
	else:
		l.append([0] + list(i) + [0])
for i in range(H):
	a = z.copy()
	for j in l:
		for k in range(W):
			if j[k]:
				a[k] = (b[k - 1] + a[k]) % pr
			elif j[k + 1]:
				a[k] = (b[k + 1] + a[k]) % pr
			else:
				a[k] = (b[k] + a[k]) % pr
	b = a
print(b[K - 1])


from collections import defaultdict
MOD = 10 ** 9 + 7
(H, W, K) = map(int, input().split())
fib = {-2: 0, -1: 1, 0: 1}
for i in range(1, W):
	fib[i] = fib[i - 1] + fib[i - 2]
dp = defaultdict(int)
dp[0, 1] = 1
for i in range(1, H + 1):
	for j in range(1, W + 1):
		dp[i, j] = fib[j - 3] * fib[W - j - 1] * dp[i - 1, j - 1] + fib[j - 2] * fib[W - j - 1] * dp[i - 1, j] + fib[j - 2] * fib[W - j - 2] * dp[i - 1, j + 1]
		dp[i, j] %= MOD
print(dp[H, K])


(h, w, k) = map(int, input().split())
mo = 10 ** 9 + 7
p = [-1] * (w + 1)
p[0] = 1
p[1] = 2

def pat(x):
	if x < 0 or x >= w:
		return 1
	elif p[x] != -1:
		return p[x]
	else:
		return pat(x - 2) + pat(x - 1)
a = [[0 for i in range(w)] for i in range(h + 1)]
a[0] = [1] + [0] * (w - 1)
for i in range(1, h + 1):
	for j in range(0, w):
		if j > 0:
			a[i][j] += a[i - 1][j - 1] * pat(j - 2) * pat(w - j - 2)
		a[i][j] += a[i - 1][j] * pat(j - 1) * pat(w - 1 - j - 1)
		if j < w - 1:
			a[i][j] += a[i - 1][j + 1] * pat(j - 1) * pat(w - j - 3)
print(a[h][k - 1] % mo)


(H, W, K) = map(int, input().split())
dpW = [[1, 0] for i in range(9)]
for i in range(1, 9):
	dpW[i][0] = dpW[i - 1][0] + dpW[i - 1][1]
	dpW[i][1] = dpW[i - 1][0]
dpH = [[0 for i in range(W + 2)] for j in range(H + 1)]
dpH[0][1] = 1
for i in range(1, H + 1):
	for j in range(1, W + 1):
		dpH[i][j] += dpH[i - 1][j] * dpW[W - j][0] * dpW[j - 1][0]
		if W - j - 1 >= 0:
			dpH[i][j] += dpH[i - 1][j + 1] * dpW[W - j - 1][0] * dpW[j - 1][0]
		if j - 2 >= 0:
			dpH[i][j] += dpH[i - 1][j - 1] * dpW[W - j][0] * dpW[j - 2][0]
		dpH[i][j] %= 10 ** 9 + 7
print(dpH[H][K])


def main():
	(h, w, k) = 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))
main()


def main():
	import sys
	input = sys.stdin.readline
	sys.setrecursionlimit(10 ** 7)
	from collections import Counter, deque
	from itertools import combinations, permutations, accumulate, groupby
	from bisect import bisect_left, bisect_right
	from heapq import heapify, heappop, heappush
	from math import floor, ceil
	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
				elif 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()


(h, w, k) = map(int, input().split())
fib = [0, 1, 1, 2, 3, 5, 8, 13, 21]
dp = [[0] * (w + 2) for i in range(h + 1)]
dp[0][1] = 1
for j in range(h):
	for l in range(1, w + 1):
		dp[j + 1][l] = fib[l] * fib[w - l + 1] * dp[j][l] + fib[l - 1] * fib[w - l + 1] * dp[j][l - 1] + fib[l] * fib[w - l] * dp[j][l + 1]
print(dp[h][k] % 1000000007)


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


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
			elif 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) = map(int, input().split())
MOD = 10 ** 9 + 7
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):
			ok = True
			for _ in range(w - 2):
				if not bit + (bit << 1) == bit ^ bit << 1:
					ok = False
			if not ok:
				continue
			ni = i + 1
			nj = j
			if bit >> j & 1:
				nj = j + 1
			elif j > 0 and bit >> j - 1 & 1:
				nj = j - 1
			dp[ni][nj] += dp[i][j]
			dp[ni][nj] %= MOD
ans = dp[h][k]
ans %= MOD
print(ans)


import sys
readline = sys.stdin.readline
(H, W, K) = list(map(int, readline().split()))
DIV = 1000000007
LINE = [-1] * (W - 1)
for i in range(W - 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
for i in range(W):
	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 = [[0] * W for i in range(H + 1)]
dp[0][0] = 1
for i in range(1, len(dp)):
	for j in range(W):
		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])


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


(h, w, k) = map(int, input().split())
mod = 10 ** 9 + 7
fib = [1, 1]
for i in range(6):
	fib.append(fib[-2] + fib[-1])
dp = [[0] * w for i in range(h + 1)]
dp[0][0] = 1
for i in range(h):
	for j in range(w):
		if w == 1:
			dp[i + 1][j] = dp[i][j]
		elif j == 0:
			dp[i + 1][j] = (dp[i][j] * fib[j] * fib[w - j - 1] + dp[i][j + 1] * fib[j] * fib[w - j - 2]) % mod
		elif j == w - 1:
			dp[i + 1][j] = (dp[i][j - 1] * fib[j - 1] * fib[w - j - 1] + dp[i][j] * fib[j] * fib[w - j - 1]) % mod
		else:
			dp[i + 1][j] = (dp[i][j - 1] * fib[j - 1] * fib[w - j - 1] + dp[i][j] * fib[j] * fib[w - j - 1] + dp[i][j + 1] * fib[j] * fib[w - j - 2]) % mod
print(dp[h][k - 1])


(h, w, k) = map(int, input().split())
dp = [0] * w
l = [1, 1, 2, 3, 5, 8, 13, 21, 34]
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])


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]
dp = [[0 for j in range(W)] for i in range(H + 1)]
dp[0][0] = 1

def calc(L, R):
	res = 1
	if 1 < L:
		res *= P[L - 1]
		res %= DIV
	if W - 1 - (R + 1) >= 1:
		res *= P[W - 1 - (R + 1)]
		res %= DIV
	return res
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
print(dp[H][K - 1] % DIV)


(H, W, K) = map(int, input().split())
C = [1, 1, 2, 3, 5, 8, 13, 21]
Amida = [[0] * W for h in range(H + 1)]
for h in range(H + 1):
	if W == 1:
		break
	for w in range(W):
		if h == 0:
			if w == 0:
				Amida[h][w] = 1
			else:
				Amida[h][w] = 0
		elif w == 0:
			Amida[h][w] = C[W - 2] * Amida[h - 1][w + 1] + C[W - 1] * Amida[h - 1][w]
		elif w == W - 1:
			Amida[h][w] = C[W - 2] * Amida[h - 1][w - 1] + C[W - 1] * Amida[h - 1][w]
		else:
			Amida[h][w] += C[w - 1] * C[W - w - 1] * Amida[h - 1][w - 1]
			Amida[h][w] += C[w] * C[W - w - 1] * Amida[h - 1][w]
			Amida[h][w] += C[w] * C[W - w - 2] * Amida[h - 1][w + 1]
		Amida[h][w] = Amida[h][w] % 1000000007
if W == 1:
	if K == 1:
		print(1)
	else:
		print(0)
else:
	print(Amida[H][K - 1])


(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]
			elif 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[h][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)
	sys.exit()
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)


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


(H, W, K) = [int(str) for str in input().strip().split()]
MOD = 1000000007
dp = [[0] * W for _ in range(H + 1)]
dp[0][0] = 1
for h in range(H):
	for w in range(W):
		for bit in range(2 ** (W - 1)):
			if bit & bit << 1:
				continue
			if w > 0 and bit & 1 << w - 1:
				dp[h + 1][w - 1] += dp[h][w]
				dp[h + 1][w - 1] %= MOD
			elif w < W - 1 and bit & 1 << w:
				dp[h + 1][w + 1] += dp[h][w]
				dp[h + 1][w + 1] %= MOD
			else:
				dp[h + 1][w] += dp[h][w]
				dp[h + 1][w] %= MOD
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
		elif 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])


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


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


(H, W, K) = map(int, input().split())
mod = 1000000007
K -= 1
Hikikata = [1] * (W + 10)
Hikikata[0] = 1
Hikikata[1] = 2
for i in range(2, W + 1):
	Hikikata[i] = Hikikata[i - 1] + Hikikata[i - 2]
	Hikikata[i] %= mod
DP = [[0] * (W + 10) for _ in range(H + 1)]
DP[0][K] = 1
for i in range(1, H + 1):
	for j in range(W):
		DP[i][j] = DP[i - 1][j] * (Hikikata[j - 1] * Hikikata[W - j - 2]) % mod + DP[i - 1][j - 1] * (Hikikata[j - 2] * Hikikata[W - j - 2]) % mod + DP[i - 1][j + 1] * (Hikikata[j - 1] * Hikikata[W - j - 3]) % mod
		DP[i][j] %= mod
print(DP[H][0])


mod = 1000000007
(H, W, K) = map(int, input().split())
dp = [[0] * W for i in range(1 + H)]
dp[0][0] = 1
C = [0] * (W + 1)
C[0] = 1
c = [[0, 0] for i in range(1 + W)]
c[0][0] = 1
for i in range(1, 1 + W):
	c[i][0] = c[i - 1][0] + c[i - 1][1]
	c[i][1] = c[i - 1][0]
for w in range(1, 1 + W):
	C[w] = c[w][0]
for i in range(H):
	for k in range(W):
		for l in range(k - 1, k + 2):
			if l < 0 or l >= W:
				continue
			x = dp[i][k] * C[min(k, l)] * C[W - 1 - max(k, l)] % mod
			dp[i + 1][l] = (dp[i + 1][l] + x) % mod
print(dp[H][K - 1])


from functools import lru_cache
(H, W, K) = map(int, input().split())

def f(k):
	return 1 if k <= 0 else f(k - 1) + f(k - 2)

@lru_cache(maxsize=H * W)
def a(i, j):
	if j < 1 or j > W or (i == 0 and j != 1):
		return 0
	if i == 0 and j == 1:
		return 1
	return (f(j - 3) * f(W - j - 1) * a(i - 1, j - 1) + f(j - 2) * f(W - j - 1) * a(i - 1, j) + f(j - 2) * f(W - j - 2) * a(i - 1, j + 1)) % 1000000007
ans = a(H, K)
print(ans)


(H, W, K) = map(int, input().split())
MODN = int(1000000000.0 + 7)
A = [[0] * (W + 2) for i in range(H + 1)]
A[0][1] = 1

def multip(N):
	tempa = [1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
	return tempa[N + 1]
for i in range(1, H + 1):
	for j in range(1, W + 2):
		if j < 1 or j > W:
			A[i][j] = 0
		else:
			A[i][j] = (A[i - 1][j - 1] * (multip(j - 2) * multip(W - j)) + A[i - 1][j] * (multip(j - 1) * multip(W - j)) + A[i - 1][j + 1] * (multip(j - 1) * multip(W - j - 1))) % MODN
print(A[H][K])


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


mod = 10 ** 9 + 7
(H, W, K) = map(int, input().split())
D = [[0] * W for _ in range(W)]
for S in range(1 << W - 1):
	if S & S << 1 != 0:
		continue
	S <<= 1
	for i in range(W):
		if S >> i & 1:
			D[i][i - 1] += 1
		elif S >> i + 1 & 1:
			D[i][i + 1] += 1
		else:
			D[i][i] += 1
E = [[0] * W for _ in range(W)]
for i in range(W):
	E[i][i] = 1
for i in range(H):
	A = [[0] * W for _ in range(W)]
	for x in range(W):
		for y in range(W):
			A[x][y] = sum((E[x][z] * D[z][y] % mod for z in range(W))) % mod
	E = A
print(A[0][K - 1])


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)]
	dp[0][0] = 1
	for h in range(H):
		for bit in range(1 << W - 1):
			if '11' in bin(bit):
				continue
			for w in range(W):
				if w and bit & 1 << w - 1:
					dp[h + 1][w - 1] += dp[h][w] % MOD
				elif bit & 1 << w:
					dp[h + 1][w + 1] += dp[h][w] % MOD
				else:
					dp[h + 1][w] += dp[h][w] % MOD
	print(dp[H][K - 1] % MOD)

def __starting_point():
	main()
__starting_point()


(H, W, K) = [int(i) for i in input().split()]
DP = [[0 for i in range(W)] for j in range(2)]
t = [0 for i in range(W + 10)]
t[0] = 1
t[1] = 1
t[2] = 2
for i in range(2, W + 8):
	t[i + 1] = t[i] + t[i - 1]
n = 0
DP[0][0] = 1
for i in range(H):
	if W == 1:
		break
	DP[not n][0] = (DP[n][0] * t[W - 1] + DP[n][1] * t[W - 2]) % 1000000007
	for i in range(1, W - 1):
		DP[not n][i] = (DP[n][i - 1] * (t[W - i - 1] * t[i - 1]) + DP[n][i] * (t[i] * t[W - i - 1]) + DP[n][i + 1] * (t[W - i - 2] * t[i])) % 1000000007
	DP[not n][W - 1] = (DP[n][W - 2] * t[W - 2] + DP[n][W - 1] * t[W - 1]) % 1000000007
	n = not n
print(DP[n][K - 1])


(H, W, K) = map(int, input().split())
mod = 10 ** 9 + 7
dp = [['0'] * (W + 2) for _ in range(H + 1)]
for h in range(H + 1):
	dp[h][0] = 0
	dp[h][W + 1] = 0
for w in range(W + 2):
	dp[0][w] = 0
dp[0][1] = 1
cmb = [1, 2, 3, 5, 8, 13, 21, 34]

def f(h, w):
	if dp[h][w] != '0':
		return dp[h][w]
	dp[h][w] = 0
	dp[h][w] += f(h - 1, w - 1) * cmb[max(0, w - 3)] * cmb[max(0, W - w - 1)]
	dp[h][w] += f(h - 1, w) * cmb[max(0, w - 2)] * cmb[max(0, W - w - 1)]
	dp[h][w] += f(h - 1, w + 1) * cmb[max(0, w - 2)] * cmb[max(0, W - w - 2)]
	dp[h][w] %= mod
	return dp[h][w]
print(f(H, K))


mod = 10 ** 9 + 7
(h, w, k) = map(int, input().split())
k -= 1
dp = [0] * w
dp[0] = 1
ndp = [0] * w
for _ in range(h):
	for bits in range(1 << w - 1):
		if '11' in bin(bits):
			continue
		to = list(range(w))
		for i in range(w - 1):
			if bits >> i & 1:
				(to[i], to[i + 1]) = (to[i + 1], to[i])
		for i in range(w):
			ndp[to[i]] += dp[i]
			ndp[to[i]] %= mod
	dp = ndp
	ndp = [0] * w
print(dp[k])


import sys

def num(x):
	return [0, 1, 1, 2, 3, 5, 8, 13, 21][x + 2]
(H, W, K) = map(int, input().split())
if W == 1:
	print(1)
	sys.exit()
f = [[0 for _ in range(W + 2)] for _ in range(H + 1)]
f[0][1] = 1
for h in range(1, H + 1):
	for k in range(1, W + 1):
		f[h][k] = num(k - 2) * num(W - k - 1) * f[h - 1][k] + num(k - 3) * num(W - k - 1) * f[h - 1][k - 1] + num(k - 2) * num(W - k - 2) * f[h - 1][k + 1]
print(f[H][K] % 1000000007)


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)


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


from itertools import product
(H, W, K) = map(int, input().split())
MOD = 10 ** 9 + 7
S = [0] * W
S[0] = 1
if W > 1:
	for i in range(H):
		T = [0] * W
		for P in product((0, 1), repeat=W - 1):
			if any((P[i] == 1 == P[i + 1] for i in range(W - 2))):
				continue
			for i in range(W):
				if i < W - 1 and P[i]:
					T[i + 1] += S[i]
					T[i] += S[i + 1]
				elif i == 0 or not P[i - 1]:
					T[i] += S[i]
		S = T
		for i in range(W):
			S[i] %= MOD
print(S[K - 1])


(H, W, K) = list(map(int, input().split()))
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])


mod = 1000000007
(H, W, K) = map(int, input().split())
fib = [1, 1, 2, 3, 5, 8, 13, 21, 34]
dp = [[0] * (W + 1) for j in range(H + 1)]
dp[0][0] = 1
dp[0][1] = 1
for h in range(1, H + 1):
	for w in range(1, W + 1):
		dp[h][w] = dp[h - 1][w] * fib[w - 1] * fib[W - w]
		if w > 1:
			dp[h][w] += dp[h - 1][w - 1] * fib[w - 2] * fib[W - w]
		if w < W:
			dp[h][w] += dp[h - 1][w + 1] * fib[w - 1] * fib[W - w - 1]
		dp[h][w] %= mod
print(dp[H][K])


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


S = list(map(int, input().split()))
H = S[0]
W = S[1]
K = S[2]
fib = [1, 2, 3, 5, 8, 13, 21, 0, 1]
List = [1]
for x in range(0, W):
	List.append(0)
for x in range(0, H):
	X = tuple(List)
	for y in range(0, W):
		List[y] = fib[y - 2] * fib[W - y - 2] * X[y - 1] + fib[y - 1] * fib[W - y - 2] * X[y] + fib[y - 1] * fib[W - y - 3] * X[y + 1]
ans = List[K - 1] % 1000000007
print(ans)


def main():
	(h, w, k) = map(int, input().split())
	mod = 10 ** 9 + 7
	b = [1, 1, 2, 3, 5, 8, 13, 21, 34]
	dp = [[0 for _ in range(w)] for j in range(h + 1)]
	dp[0][0] = 1
	if w == 1:
		return 1
	for i in range(h):
		for j in range(w):
			if j == 0:
				dp[i + 1][j] = (dp[i][j] * b[w - 1] + dp[i][j + 1] * b[w - 2]) % mod
			elif j == w - 1:
				dp[i + 1][j] = (dp[i][j] * b[w - 1] + dp[i][j - 1] * b[w - 2]) % mod
			else:
				dp[i + 1][j] = (dp[i][j] * b[j] * b[w - 1 - j] + dp[i][j - 1] * b[j - 1] * b[w - 1 - j] + dp[i][j + 1] * b[j] * b[w - 2 - j]) % mod
	return dp[h][k - 1]
print(main())


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


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


(h, w, k) = map(int, input().split())
dp = [1] + [0] * (w - 1)
facts = [1, 1, 2, 3, 5, 8, 13, 21, 34]
for _ in range(h):
	ndp = [0] * w
	for b in range(w):
		if b > 0:
			ndp[b] += dp[b - 1] * facts[b - 1] * facts[w - b - 1]
		ndp[b] += dp[b] * facts[b] * facts[w - b - 1]
		if b < w - 1:
			ndp[b] += dp[b + 1] * facts[b] * facts[w - b - 2]
		ndp[b] %= 1000000007
	dp = ndp
print(dp[k - 1])


(H, W, K) = map(int, input().split())
amari = [1, 1, 2, 3, 5, 8, 13, 21]
lis = [0] * W
lis[0] += 1
for j in range(H):
	nlis = [0] * W
	for i in range(W):
		if i > 0:
			if i == 1:
				nlis[i - 1] += lis[i] * amari[W - 2]
			else:
				nlis[i - 1] += lis[i] * amari[i - 1] * amari[W - 1 - i]
		nlis[i] += lis[i] * amari[i] * amari[W - 1 - i]
		if i < W - 1:
			if i == W - 2:
				nlis[i + 1] += lis[i] * amari[W - 2]
			else:
				nlis[i + 1] += lis[i] * amari[i] * amari[W - i - 2]
	for i in range(W):
		lis[i] = nlis[i] % (10 ** 9 + 7)
print(lis[K - 1] % (10 ** 9 + 7))


import math
(h, w, k) = map(int, input().split())
l = [0] * 9
for i in range(9):
	a = 0
	b = i
	while b >= a:
		l[i] += int(math.factorial(b) / math.factorial(a) / math.factorial(b - a))
		b -= 1
		a += 1
dp = [[0] * (w + 2) for i in range(h + 1)]
dp[0][1] = 1
for i in range(1, h + 1):
	for j in range(1, w + 1):
		dp[i][j] = int(dp[i - 1][j - 1] * l[j - 2] * l[w - j] + dp[i - 1][j] * l[j - 1] * l[w - j] + dp[i - 1][j + 1] * l[j - 1] * l[w - j - 1])
		dp[i][j] %= 10 ** 9 + 7
print(int(dp[-1][k]))


import collections
cd = collections.defaultdict
dp = cd(lambda : cd(int))
dp[0][1] = 1
(H, W, K) = [int(_) for _ in input().split()]
mod = 10 ** 9 + 7
fib = [1, 1, 2, 3, 5, 8, 13, 21] + [1] * 8
for h in range(1, H + 1):
	for w in range(1, W + 1):
		dp[h][w] = dp[h - 1][w] * fib[w - 1] * fib[W - w]
		dp[h][w] += dp[h - 1][w - 1] * fib[w - 2] * fib[W - w]
		dp[h][w] += dp[h - 1][w + 1] * fib[w - 1] * fib[W - w - 1]
		dp[h][w] %= mod
print(dp[H][K])


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


(H, W, K) = list(map(int, input().split()))
S = [1, 1]
for i in range(W - 1):
	S.append(S[-1] + S[-2])
dp = [0] * W
dp[0] = 1
for h in range(H):
	dp_new = [0] * W
	for w in range(W):
		dp_new[w] = S[w] * S[W - 1 - w] * dp[w]
	for w in range(W - 1):
		dp_new[w] += S[w] * S[W - 2 - w] * dp[w + 1]
		dp_new[w + 1] += S[w] * S[W - 2 - w] * dp[w]
	dp = [d % 1000000007 for d in dp_new]
print(dp[K - 1])


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)
	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]
	return dp[-1][K - 1] % (10 ** 9 + 7)
print(main())


from itertools import product
(H, W, K) = map(int, input().split())
MOD = 10 ** 9 + 7
dp = [[0] * W for _ in range(H + 1)]
dp[0][0] = 1
for h in range(H):
	for bit in range(1 << W - 1):
		if '11' in bin(bit):
			continue
		for w in range(W):
			if w > 0 and bit >> w - 1 & 1:
				dp[h + 1][w - 1] += dp[h][w]
				dp[h + 1][w - 1] %= MOD
			elif bit >> w & 1:
				dp[h + 1][w + 1] += dp[h][w]
				dp[h + 1][w + 1] %= MOD
			else:
				dp[h + 1][w] += dp[h][w]
				dp[h + 1][w] %= MOD
print(dp[-1][K - 1] % MOD)


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


(H, W, K) = map(int, input().split())
ans = [0] * W
buf = [0] * W
fibonacci = [1] * (W + 1)
for i in range(2, W + 1):
	fibonacci[i] = fibonacci[i - 1] + fibonacci[i - 2]
ans[0] = 1
if W == 1:
	print(1)
else:
	for i in range(H):
		buf[0] = ans[0] * fibonacci[W - 1] + ans[1] * fibonacci[W - 2]
		buf[W - 1] = ans[W - 1] * fibonacci[W - 1] + ans[W - 2] * fibonacci[W - 2]
		for j in range(1, W - 1):
			buf[j] = ans[j - 1] * fibonacci[j - 1] * fibonacci[W - j - 1] + ans[j] * fibonacci[j] * fibonacci[W - j - 1] + ans[j + 1] * fibonacci[j] * fibonacci[W - j - 2]
		for j in range(W):
			ans[j] = buf[j] % 1000000007
	print(ans[K - 1])


base = 10 ** 9 + 7
(h, w, k) = map(int, input().split())
wc = [1] * 9
for i in range(2, 9):
	wc[i] = wc[i - 1] + wc[i - 2]
dp = [0] * (w + 2)
dp[1] = 1
for i in range(h):
	tmp = [0] * (w + 2)
	for j in range(1, w + 1):
		tmp[j] = dp[j] * wc[j - 1] * wc[w - j]
		if j > 1:
			tmp[j] += dp[j - 1] * wc[j - 2] * wc[w - j]
		if j < w:
			tmp[j] += dp[j + 1] * wc[j - 1] * wc[w - j - 1]
		tmp[j] = tmp[j] % base
	dp = tmp
print(dp[k])


def fib(W):
	(a, b) = (1, 1)
	n = [a, b]
	while W > len(n):
		(a, b) = (b, b + a)
		n.append(b)
	return n
(H, W, K) = map(int, input().split())
f = fib(W)
r = [1] + [0] * (W - 1)
for i in range(H):
	tmp = [0] * W
	for j in range(W):
		if j == 0:
			tmp[j] = r[j] * f[W - j - 1] + r[j + 1] * f[W - j - 2] if W != 1 else 1
		elif j == W - 1:
			tmp[j] = r[j] * f[j] + r[j - 1] * f[j - 1]
		else:
			tmp[j] = r[j] * f[j] * f[W - j - 1] + r[j + 1] * f[W - j - 2] * f[j] + r[j - 1] * f[W - j - 1] * f[j - 1]
	r = tmp
print(r[K - 1] % 1000000007)


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


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


(H, W, K) = map(int, input().split())
MOD = 10 ** 9 + 7
if W == 1:
	print(1)
	exit()
possible = []
for i in range(1 << W - 1):
	b = bin(i)[2:]
	flag = 1
	for j in range(len(b) - 1):
		if b[j] == b[j + 1] == '1':
			flag = 0
	if flag:
		possible.append(int(b, 2))

def amida(b):
	ret = [i for i in range(W)]
	for i in range(W - 1):
		if b >> i & 1:
			(ret[i], ret[i + 1]) = (ret[i + 1], ret[i])
	return ret
ans = [0 for i in range(W)]
ans[0] = 1
for _ in range(H):
	new_ans = [0 for i in range(W)]
	for b in possible:
		for i in range(W):
			new_ans[i] = (new_ans[i] + ans[amida(b)[i]]) % MOD
	ans = new_ans
print(ans[K - 1])


from itertools import product
(h, w, k) = list(map(int, input().split()))
seqs = [s for s in product([0, 1], repeat=w - 1) if not any((x & y for (x, y) in zip(s, s[1:])))]
cache = {}

def f(x, y):
	if y > h:
		return int(x == k)
	if (x, y) in cache:
		return cache[x, y]
	r = 0
	for s in seqs:
		nx = x
		if x < w and s[x - 1]:
			nx += 1
		elif x > 1 and s[x - 2]:
			nx -= 1
		r = (r + f(nx, y + 1)) % (10 ** 9 + 7)
	cache[x, y] = r
	return r
print(f(1, 1))


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


(h, w, k) = map(int, input().split())
dp = [[0] * w for i in range(h + 1)]
mod = 1000000007
dp[0][k - 1] = 1
a = [1, 1, 2, 3, 5, 8, 13, 21]
for i in range(h):
	for j in range(w):
		if j != 0:
			if j == w - 1 or j == 1:
				dp[i + 1][j] += dp[i][j - 1] * a[w - 2] % mod
			else:
				dp[i + 1][j] += dp[i][j - 1] * (a[j - 1] * a[w - 1 - j]) % mod
		if j != w - 1:
			if j == 0 or j == w - 2:
				dp[i + 1][j] += dp[i][j + 1] * a[w - 2] % mod
			else:
				dp[i + 1][j] += dp[i][j + 1] * (a[j] * a[w - 2 - j]) % mod
		if j == 0 or j == w - 1:
			dp[i + 1][j] += dp[i][j] * a[w - 1] % mod
		else:
			dp[i + 1][j] += dp[i][j] * (a[j] * a[w - 1 - j]) % mod
print(dp[h][0] % mod)


(h, w, k) = 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())
if w == 1:
	print(1)
	exit()
a = [0] * (w + 2)
a[1] = 1
f = [0] * (w - 1)
p = 0
q = 1
for i in range(w - 1):
	f[i] = p + q
	q = p + q
	p = q - p
f.append(1)
b = []
mod = 10 ** 9 + 7
for i in range(w):
	if i == 0:
		b.append([0, f[w - 2], f[w - 3]])
	elif i == w - 1:
		b.append([f[w - 3], f[w - 2], 0])
	else:
		b.append([f[i - 2] * f[w - i - 2], f[i - 1] * f[w - i - 2], f[i - 1] * f[w - i - 3]])
for _ in range(h):
	newa = [0] * (w + 2)
	for i in range(1, w + 1):
		newa[i] = (a[i - 1] * b[i - 1][0] + a[i] * b[i - 1][1] + a[i + 1] * b[i - 1][2]) % mod
	a = newa
print(a[k])


(H, W, K) = map(int, input().split())
mod = int(1000000000.0 + 7)
if W == 1:
	print(1)
else:
	dp = [[0 for _ in range(W)] for _ in range(H + 1)]
	P = [1, 1, 2, 3, 5, 8, 13, 21]
	dp[0][0] = 1
	for h in range(1, H + 1):
		for k in range(W):
			if k == 0:
				dp[h][k] = (P[k] * P[W - k - 1] * dp[h - 1][k] + P[k] * P[W - k - 2] * dp[h - 1][k + 1]) % mod
			elif k == W - 1:
				dp[h][k] = (P[k - 1] * P[W - k - 1] * dp[h - 1][k - 1] + P[k] * P[W - k - 1] * dp[h - 1][k]) % mod
			else:
				dp[h][k] = (P[k - 1] * P[W - k - 1] * dp[h - 1][k - 1] + P[k] * P[W - k - 1] * dp[h - 1][k] + P[k] * P[W - k - 2] * dp[h - 1][k + 1]) % mod
	print(dp[H][K - 1])


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


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


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


md = 1000000000 + 7

def fi(n):
	if n < 0:
		return 0
	elif n <= 1:
		return 1
	elif n == 2:
		return 2
	else:
		return (fi(n - 1) + fi(n - 2)) % md
(h, w, k) = map(int, input().split())
li = [0 for i in range(w)]
li[0] = 1
li_prev = []
li_next = []
li_prev[:] = li[:]
li_next[:] = li[:]
for j in range(h):
	for i in range(w):
		li_next[i] = (li_prev[max(0, i - 1)] * fi(i - 1) * fi(w - i - 1) + li_prev[i] * fi(i) * fi(w - i - 1) + li_prev[min(w - 1, i + 1)] * fi(i) * fi(w - i - 2)) % md
	li_prev[:] = li_next[:]
print(li_prev[k - 1])


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


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


MOD = 10 ** 9 + 7
(H, W, K) = map(int, input().split())
F = [1, 1, 2, 3, 5, 8, 13, 21, 34]
dp = [[0 for j in range(W)] for i in range(H + 1)]
dp[0][0] = 1
for i in range(1, H + 1):
	for j in range(W):
		dp[i][j] += dp[i - 1][j] * F[j] * F[W - j - 1]
		if j != W - 1:
			dp[i][j] += dp[i - 1][j + 1] * F[j] * F[W - j - 2]
		if j != 0:
			dp[i][j] += dp[i - 1][j - 1] * F[j - 1] * F[W - j - 1]
		dp[i][j] %= MOD
print(dp[H][K - 1])


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

def getFib(i):
	return fibs[i + 2]
(numLs, numCs, numRs) = ([0] * W, [0] * W, [0] * W)
for j in range(W):
	numCs[j] = getFib(j - 1) * getFib(W - 1 - j - 1)
	numLs[j] = getFib(j - 2) * getFib(W - 1 - j - 1)
	numRs[j] = getFib(j - 1) * getFib(W - 1 - j - 2)
dp = [[0] * W for _ in range(H + 1)]
dp[0][0] = 1
for i in range(H):
	for j in range(W):
		dp[i + 1][j] += dp[i][j] * numCs[j]
		if j > 0:
			dp[i + 1][j - 1] += dp[i][j] * numLs[j]
		if j < W - 1:
			dp[i + 1][j + 1] += dp[i][j] * numRs[j]
	for j in range(W):
		dp[i + 1][j] %= MOD
print(dp[H][K - 1])


(h, w, k) = list(map(int, input().split()))
dp = [[0 for i in range(w + 1)] for i in range(h + 1)]
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)


(H, W, K) = tuple((int(i) for i in input().split()))
row = [0, 1]
row_b = [0, 0]
for _ in range(W - 1):
	temp = [i + j for (i, j) in zip(row, row_b)]
	row_b = row
	row = temp
	row.append(row[1])
	row_b.append(0)
row.append(0)
row_b.append(0)
a = {(0, i): 0 for i in range(W + 2)}
a[0, 1] = 1
for h in range(1, H + 1):
	for w in range(0, W + 2):
		if w == 0 or w == W + 1:
			a[h, w] = 0
		else:
			a[h, w] = row_b[w - 1] * a[h - 1, w - 1] + row[w] * a[h - 1, w] + row_b[w] * a[h - 1, w + 1]
print(a[H, K] % 1000000007)


MOD = 1000000000 + 7

def run():
	(H, W, K) = map(int, input().split())
	K = K - 1
	dp = [0] * 1000
	dp[0] = 1
	dp[1] = 1
	dp[2] = 2
	for i in range(3, 1000):
		dp[i] = (dp[i - 1] + dp[i - 2]) % MOD
	dp2 = [[0 for j in range(W)] for i in range(H + 1)]
	dp2[0][0] = 1
	for i in range(H):
		for j in range(W):
			dp2[i + 1][j] = (dp2[i + 1][j] + dp2[i][j] * dp[j] % MOD * dp[W - j - 1] % MOD) % MOD
			if j - 1 >= 0:
				dp2[i + 1][j - 1] = (dp2[i + 1][j - 1] + dp2[i][j] * dp[j - 1] % MOD * dp[W - j - 1] % MOD) % MOD
			if j + 1 < W:
				dp2[i + 1][j + 1] = (dp2[i + 1][j + 1] + dp2[i][j] * dp[j] % MOD * dp[W - j - 2] % MOD) % MOD
	print(dp2[H][K])
run()


def main():
	(h, w, k) = map(int, input().split())
	MOD = 10 ** 9 + 7
	patterns = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
	x = [0] * (w - 1)
	for i in range(w - 1):
		x[i] = patterns[i] * patterns[max(0, w - i - 2)]
	y = [0] * w
	for i in range(w):
		y[i] = patterns[i] * patterns[max(0, w - i - 1)]
	dp = [[0] * w for _ in range(h + 1)]
	dp[0][0] = 1
	for j in range(h):
		for i in range(w):
			d = dp[j][i] * y[i]
			if i - 1 >= 0:
				d += dp[j][i - 1] * x[i - 1]
			if i + 1 < w:
				d += dp[j][i + 1] * x[i]
			dp[j + 1][i] = d % MOD
	print(dp[h][k - 1])
main()


(H, W, K) = [int(x) for x in input().split()]
p = 10 ** 9 + 7
h1amida = [1, 1, 2] + [None] * 6
for i in range(3, 9):
	h1amida[i] = h1amida[i - 2] + h1amida[i - 1]
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])


(H, W, K) = map(int, input().split())
bit = []
for i in range(1 << W - 1):
	flag = True
	for j in range(W - 1):
		if i & 1 << j and i & 1 << j + 1:
			flag = False
			break
	if flag:
		bit.append(i)
MOD = 10 ** 9 + 7
dp = [[0] * W for i in range(H + 1)]
dp[0][0] = 1
for i in range(H):
	for j in range(W):
		for k in bit:
			ne = j
			if k & 1 << j:
				ne = j + 1
			elif j - 1 >= 0 and k & 1 << j - 1:
				ne = j - 1
			dp[i + 1][ne] += dp[i][j]
			dp[i + 1][ne] %= MOD
print(dp[H][K - 1])


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


import copy
import sys
(H, W, K) = list(map(int, input().split()))
if W == 1:
	print(1)
	sys.exit()
D = [0 for i in range(W)]
T = copy.deepcopy(D)
D[0] = 1
F = [1, 1, 2, 3, 5, 8, 13, 21]
for i in range(H):
	T[0] = D[1] * F[W - 2] + D[0] * F[W - 1]
	T[W - 1] = D[W - 2] * F[W - 2] + D[W - 1] * F[W - 1]
	for j in range(1, W - 1):
		T[j] = D[j - 1] * F[j - 1] * F[W - j - 1] + D[j + 1] * F[j] * F[W - j - 2] + D[j] * F[j] * F[W - j - 1]
	D = copy.deepcopy(T)
print(D[K - 1] % 1000000007)


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


(h, w, k) = map(int, input().split())
mod = 10 ** 9 + 7
dp = [[0] * w for _ in range(h)]
D = [[0] * w for _ in range(w)]
for i in range(2 ** (w - 1)):
	s = '0' + bin(i)[2:].rjust(w - 1, '0') + '0'
	if '11' in s:
		continue
	for i in range(w - 1):
		if s[i + 1] == '1':
			D[i][i + 1] += 1
			D[i + 1][i] += 1
	for i in range(w):
		if s[i:i + 2] == '00':
			D[i][i] += 1
dp[0] = D[0]
for i in range(1, h):
	for j in range(1, w):
		dp[i][j] += dp[i - 1][j - 1] * D[j - 1][j]
	for j in range(w - 1):
		dp[i][j] += dp[i - 1][j + 1] * D[j + 1][j]
	for j in range(w):
		dp[i][j] += dp[i - 1][j] * D[j][j]
		dp[i][j] %= mod
print(dp[-1][k - 1])


(H, W, K) = map(int, input().split())
mod = 10 ** 9 + 7
fib = [1, 1, 2, 3, 5, 8, 13, 21]
from functools import lru_cache

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


(H, W, K) = map(int, input().split())
mod = 10 ** 9 + 7
from collections import defaultdict
NOW = defaultdict(int)
VAR = dict()
VAR[-2] = 1
VAR[-1] = 1
VAR[0] = 1
VAR[1] = 1
VAR[2] = 2
for i in range(3, W + 1):
	VAR[i] = VAR[i - 1] + VAR[i - 2]
NOW[1] = 1
for i in range(H):
	NEXT = defaultdict(int)
	for j in NOW:
		if j <= 0 or j > W:
			continue
		x = NOW[j]
		NEXT[j - 1] = (NEXT[j - 1] + x * VAR[j - 2] * VAR[W - j]) % mod
		NEXT[j] = (NEXT[j] + x * VAR[j - 1] * VAR[W - j]) % mod
		NEXT[j + 1] = (NEXT[j + 1] + x * VAR[j - 1] * VAR[W - j - 1]) % mod
	NOW = NEXT
print(NOW[K] % mod)


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


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


(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[-1][K - 1])


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


(H, W, K) = map(int, input().split())
dp = [[0] * W for _ in range(H + 1)]
dp[0][0] = 1
B = [format(i, 'b').zfill(W - 1) for i in range(2 ** (W - 1)) if '11' not in format(i, 'b')]
for h in range(H):
	for w in range(W):
		for b in B:
			if w > 0 and b[w - 1] == '1':
				dp[h + 1][w - 1] += dp[h][w]
			elif w < W - 1 and b[w] == '1':
				dp[h + 1][w + 1] += dp[h][w]
			else:
				dp[h + 1][w] += dp[h][w]
print(dp[H][K - 1] % (10 ** 9 + 7))


(H, W, K) = map(int, input().split())
mod = 1000000007
draw_line = [0 for _ in range(W)]
draw_line[0] = 1
if W > 1:
	draw_line[1] = 1
for i in range(2, W):
	draw_line[i] = draw_line[i - 1] + draw_line[i - 2]
dp = [[0 for _ in range(W)] for _ in range(H + 1)]
dp[0][0] = 1
for h in range(1, H + 1):
	for w in range(W):
		if w > 0:
			dp[h][w] += dp[h - 1][w - 1] * draw_line[w - 1] * draw_line[W - w - 1]
		dp[h][w] += dp[h - 1][w] * draw_line[w] * draw_line[W - w - 1]
		if w < W - 1:
			dp[h][w] += dp[h - 1][w + 1] * draw_line[w] * draw_line[W - w - 2]
print(dp[H][K - 1] % mod)


(H, W, K) = map(int, input().split())
K -= 1
P = 10 ** 9 + 7
dp = [[0 for j in range(W)] for i in range(H + 1)]
dp[0][0] = 1
F = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233]
for i in range(H):
	for j in range(W):
		dp[i + 1][j] += dp[i][j] * F[j] * F[W - j - 1]
		dp[i + 1][j] %= P
		if j != W - 1:
			dp[i + 1][j] += dp[i][j + 1] * F[j] * F[W - j - 2]
			dp[i + 1][j] %= P
		if j != 0:
			dp[i + 1][j] += dp[i][j - 1] * F[j - 1] * F[W - j - 1]
			dp[i + 1][j] %= P
print(dp[H][K])


from itertools import product
(H, W, K) = map(int, input().split())
mod = 10 ** 9 + 7
dp = [[0] * W for _ in range(H + 1)]
dp[0][0] = 1
for (i, j, k) in product(range(H), range(W), range(1 << W - 1)):
	ok = True
	for l in range(W - 2):
		if k >> l & 1 and k >> l + 1 & 1:
			ok = False
	if not ok:
		continue
	if j >= 1 and k >> j - 1 & 1:
		dp[i + 1][j - 1] += dp[i][j]
		dp[i + 1][j - 1] %= mod
	elif j <= W - 2 and k >> j & 1:
		dp[i + 1][j + 1] += dp[i][j]
		dp[i + 1][j + 1] %= mod
	else:
		dp[i + 1][j] += dp[i][j]
		dp[i + 1][j] %= mod
print(dp[H][K - 1])


import collections
cd = collections.defaultdict
memo = cd(lambda : cd(int))
memo[0][1] = 1
(H, W, K) = [int(_) for _ in input().split()]
mod = 10 ** 9 + 7
fib = [1, 1, 2, 3, 5, 8, 13, 21] + [1] * 8

def count(h, w):
	if memo[h][w]:
		return memo[h][w]
	elif h == 0 or w == 0 or w == W + 1:
		return 0
	else:
		ret = count(h - 1, w) * fib[w - 1] * fib[W - w]
		ret += count(h - 1, w - 1) * fib[w - 2] * fib[W - w]
		ret += count(h - 1, w + 1) * fib[w - 1] * fib[W - w - 1]
		ret %= mod
		memo[h][w] = ret
		return ret
print(count(H, K))


(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 = [[0] * (W + 2) for h in range(H + 1)]
dp[0][1] = 1
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
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])


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)


f = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
(h, w, k) = map(int, input().split())
a = [0] * (w + 2)
b = [0] * (w + 2)
a[1] = 1
for i in range(h):
	for j in range(1, w + 1):
		b[j] = (f[j - 1] * f[w - j + 1] * a[j - 1] + f[j] * f[w - j + 1] * a[j] + f[j] * f[w - j] * a[j + 1]) % 1000000007
	for j in range(1, w + 1):
		a[j] = b[j]
print(a[k])


F = [1, 1]
for i in range(7):
	F.append(F[i] + F[i + 1])
(h, w, k) = map(int, input().split())
mod = 10 ** 9 + 7
a = [[0 for i in range(w)] for i in range(h + 1)]
a[0][0] = 1
if w == 1:
	print(1)
else:
	for i in range(h):
		for j in range(w):
			if j == 0:
				a[i + 1][j] += F[w - 1] * a[i][j] % mod
				a[i + 1][j + 1] += F[w - 2] * a[i][j] % mod
			elif j == w - 1:
				a[i + 1][j] += F[w - 1] * a[i][j] % mod
				a[i + 1][j - 1] += F[w - 2] * a[i][j] % mod
			else:
				a[i + 1][j] += F[j] * F[w - j - 1] * a[i][j] % mod
				a[i + 1][j + 1] += F[j] * F[w - j - 2] * a[i][j] % mod
				a[i + 1][j - 1] += F[j - 1] * F[w - j - 1] * a[i][j] % mod
	print(a[-1][k - 1] % mod)


def main():
	(H, W, K) = list(map(int, input().split()))
	dp = [[0 for _ in range(W)] for _ in range(H + 1)]
	dp[0][0] = 1
	for i in range(H):
		for j in range(1 << W - 1):
			if '11' in bin(j):
				continue
			j <<= 1
			for w in range(W):
				if j & 1 << w:
					dp[i + 1][w] += dp[i][w - 1]
				elif j & 1 << w + 1:
					dp[i + 1][w] += dp[i][w + 1]
				else:
					dp[i + 1][w] += dp[i][w]
				dp[i + 1][w] %= 10 ** 9 + 7
	print(dp[H][K - 1])
main()


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)
(h, w, k) = map(int, readline().split())
dp = [[0] * w for _ 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 j in range(w):
			if j and b & 1 << j - 1:
				dp[i + 1][j - 1] += dp[i][j]
			elif b & 1 << j:
				dp[i + 1][j + 1] += dp[i][j]
			else:
				dp[i + 1][j] += dp[i][j]
print(dp[-1][k - 1] % mod)


ri = lambda : int(input())
rl = lambda : list(map(int, input().split()))
rr = lambda N: [ri() for _ in range(N)]
YN = lambda b: print('YES') if b else print('NO')
INF = 10 ** 18
(H, W, K) = rl()
DIV = 1000000007
rc = K - 1
dp = [[0 for _ in range(W)] for _ in range(H + 1)]
dp[0][0] = 1
bar = [1, 1 + 0, 1 + 1, 2 + 1, 3 + 2, 5 + 3, 8 + 5, 13 + 8, 21 + 13]
for h in range(1, H + 1):
	for w in range(W):
		if w != 0:
			dp[h][w] += dp[h - 1][w - 1] * bar[w - 1] * bar[W - w - 1]
		dp[h][w] += dp[h - 1][w] * bar[w] * bar[W - w - 1]
		if w != W - 1:
			dp[h][w] += dp[h - 1][w + 1] * bar[w] * bar[W - w - 2]
print(dp[H][K - 1] % DIV)


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


def main():
	(H, W, K) = map(int, input().split())
	u = [1] + [0] * (W - 1)
	mod = 10 ** 9 + 7

	def cw(n):
		if n == 0:
			return 0
		if n == 1:
			return 2
		return cw(n - 2) + cw(n - 1)
	CW = [1, 2, 3, 5, 8, 13, 21, 34, 55, 1, 1, 1]
	for _ in range(H):
		v = [0] * W
		for w in range(W):
			t = 0
			if w >= 1:
				t += u[w - 1] * CW[w - 2] * CW[W - w - 2]
			t += u[w] * CW[w - 1] * CW[W - w - 2]
			if w < W - 1:
				t += u[w + 1] * CW[w - 1] * CW[W - w - 3]
			v[w] = t % mod
		u = v
	print(u[K - 1])
main()


def way(h, w, k):
	if w == 1:
		return 1
	if [h, k] == [1, 1] or [h, k] == [1, 2]:
		return fibo[w - k]
	if h == 1:
		return 0
	if memo[h][k] != -1:
		return memo[h][k]
	re = way(h - 1, w, k) * fibo[k - 1] * fibo[w - k]
	if k != 1:
		re += way(h - 1, w, k - 1) * fibo[max(k - 2, 0)] * fibo[w - k]
	if k != w:
		re += way(h - 1, w, k + 1) * fibo[k - 1] * fibo[max(w - k - 1, 0)]
	memo[h][k] = re
	return re
(h, w, k) = map(int, input().split())
fibo = [1, 1]
for i in range(2, w):
	fibo += [fibo[i - 1] + fibo[i - 2]]
memo = [[-1] * (w + 1) for _ in range(h + 1)]
print(way(h, w, k) % 1000000007)


MOD = 1000000007
(H, W, K) = map(int, input().split())
cand = []
for bits in range(1 << W - 1):
	s = '{:b}'.format(bits)
	if s.count('11') > 0:
		continue
	while len(s) < W - 1:
		s = '0' + s
	cand.append(s)
dp = [0] * W
dp[0] = 1
for _ in range(H):
	ndp = [0] * W
	for c in cand:
		for i in range(W):
			if i + 1 < W and c[i] == '1':
				ndp[i + 1] += dp[i]
			elif i - 1 >= 0 and c[i - 1] == '1':
				ndp[i - 1] += dp[i]
			else:
				ndp[i] += dp[i]
	dp = ndp
	for i in range(W):
		dp[i] %= MOD
print(dp[K - 1])


(h, w, k) = map(int, input().split())
k -= 1
mod = 1000000007
if w == 1:
	print(1)
	exit()
dp = [[0 for _ in range(w)] for _ in range(h + 1)]
dp[0][0] = 1
for hi in range(1, h + 1):
	for b in range(2 ** (w - 1)):
		judge = False
		for i in range(w - 2):
			if b >> i & 3 == 3:
				judge = True
				break
		if judge:
			continue
		perm = [i for i in range(w)]
		for i in range(w - 1):
			if b >> i & 1 == 1:
				(perm[i], perm[i + 1]) = (perm[i + 1], perm[i])
		for i in range(w):
			dp[hi][perm[i]] = (dp[hi][perm[i]] + dp[hi - 1][i]) % mod
print(dp[h][k])


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
MOD = 10 ** 9 + 7
(H, W, K) = map(int, readline().split())
facts = [1, 1, 2, 3, 5, 8, 13, 21, 34]
dp = [0] * W
dp[0] = 1
for _ in range(H):
	ndp = [0] * W
	for w in range(W):
		ndp[w] += dp[w] * facts[w] * facts[W - w - 1]
		if w > 0:
			ndp[w] += dp[w - 1] * facts[w - 1] * facts[W - w - 1]
		if w < W - 1:
			ndp[w] += dp[w + 1] * facts[w] * facts[W - w - 2]
		ndp[w] %= MOD
	dp = ndp
print(dp[K - 1])


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


(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 j in range(W):
		for bit in range(1 << W - 1):
			flag = 1
			for k in range(W - 2):
				if bit & 1 << k and bit & 1 << k + 1:
					flag = 0
			if flag != 1:
				continue
			nj = j
			if bit & 1 << j:
				nj = 1 + j
			if j > 0 and bit & 1 << j - 1:
				nj = j - 1
			dp[i + 1][nj] += dp[i][j]
			dp[i + 1][nj] %= 10 ** 9 + 7
print(dp[H][K - 1])


import sys
input = sys.stdin.readline
(h, w, k) = map(int, input().split())
lis = [0] * (w - 1)
n = 0
for i in range(2 ** (w - 1)):
	tmp = bin(i)[2:].zfill(w - 1)
	if '11' in tmp:
		continue
	n += 1
	for j in range(w - 1):
		lis[j] += int(tmp[j])
res = [1] + [0] * (w - 1)
for i in range(h):
	res2 = res.copy()
	for j in range(w):
		if j == 0:
			a = 0
			x = 0
		else:
			a = lis[j - 1]
			x = res[j - 1]
		if j == w - 1:
			b = 0
			y = 0
		else:
			b = lis[j]
			y = res[j + 1]
		res2[j] = x * a + res[j] * (n - a - b) + y * b
	res = res2
print(res[k - 1] % (10 ** 9 + 7))


def f():
	import sys
	input = sys.stdin.buffer.readline
	sys.setrecursionlimit(10 ** 9)
	(h, w, k) = map(int, input().split())
	dp = [0] * w
	dp[k - 1] = 1
	ne = [0] * w
	mod = 10 ** 9 + 7
	table = [1, 1, 2, 3, 5, 8, 13, 21, 34]
	for c in range(h):
		for i in range(w):
			ne[i] = dp[i] * table[i] * table[w - i - 1]
			if i > 0:
				ne[i] += dp[i - 1] * table[i - 1] * table[w - i - 1]
			if i < w - 1:
				ne[i] += dp[i + 1] * table[i] * table[w - i - 2]
			ne[i] %= mod
		(dp, ne) = (ne, dp)
	print(dp[0])
f()


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


(h, w, k) = 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)


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


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


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


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


fib = [1, 1, 2, 3, 5, 8, 13, 21, 34]
mod = 1000000007
(H, W, K) = list(map(int, input().split()))
dp = [[0] * (W + 2) for i in range(H + 1)]
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] * fib[W - 1] + dp[i - 1][j + 1] * fib[W - 2]) % mod
		elif j == W + 1:
			dp[i][j - 1] = (dp[i - 1][j] * fib[j - 2] * fib[W - j] + dp[i - 1][j] * fib[j - 1] * fib[W - j]) % mod
		else:
			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]) % mod
print(dp[-1][K])


import sys
input = sys.stdin.readline
(H, W, K) = map(int, input().split())
mod = 10 ** 9 + 7
j = [0, 1, 1, 2, 3, 5, 8, 13]
m = [1, 1, 2, 3, 5, 8, 13, 21]
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])


MOD = 10 ** 9 + 7
(H, W, K) = 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])


(h, w, k) = map(int, input().split())
dp = [[0] * (w + 1) for i in range(h + 2)]
dp[1][1] = 1
p = 10 ** 9 + 7
line = [1] * 101
line[2] = 2
for i in range(3, 101):
	line[i] = line[i - 1] + line[i - 2]
for i in range(1, h + 1):
	for j in range(1, w + 1):
		dp[i + 1][j] += dp[i][j] * line[j - 1] * line[w - j]
		dp[i + 1][j] %= p
		if 2 <= j:
			dp[i + 1][j] += dp[i][j - 1] * line[j - 2] * line[w - j]
			dp[i + 1][j] %= p
		if j + 1 <= w:
			dp[i + 1][j] += dp[i][j + 1] * line[j - 1] * line[w - j - 1]
			dp[i + 1][j] %= p
print(dp[h + 1][k])


(H, W, K) = map(int, input().split())
L = [-1] * W

def line(n):
	if n < 2:
		return 1
	elif L[n] != -1:
		return L[n]
	else:
		a = 0
		for i in range(n - 1):
			a += line(n - i - 2)
		return a + 1
arr = [[-1 for i in range(H)] for j in range(W)]

def ans(h, k):
	if k < 1 or k > W:
		return 0
	elif h == 0:
		if k == 1:
			return 1
		else:
			return 0
	elif arr[k - 1][h - 1] != -1:
		return arr[k - 1][h - 1]
	else:
		arr[k - 1][h - 1] = ans(h - 1, k) * (line(k - 1) * line(W - k)) + ans(h - 1, k - 1) * line(k - 2) * line(W - k) + ans(h - 1, k + 1) * line(k - 1) * line(W - k - 1)
		arr[k - 1][h - 1] %= 1000000007
		return arr[k - 1][h - 1]
print(ans(H, K))


(H, W, K) = map(int, input().split())
l = [[0], [1]]
for i in range(2, W):
	for (n, j) in enumerate(l):
		if j[-1] < i - 1:
			l.append(j + [i])
m = [0] * (W + 1)
for i in l:
	for j in i:
		m[j] += 1
m[0] = 0
wa = len(l)
ans = [{i: 0 for i in range(W + 2)} for _ in range(H + 1)]
ans[0][1] = 1
for i in range(H):
	for j in range(1, W + 1):
		ans[i + 1][j] = (wa - m[j - 1] - m[j]) * ans[i][j] + m[j - 1] * ans[i][j - 1] + m[j] * ans[i][j + 1]
if W == 1:
	print(1)
else:
	print(ans[H][K] % (10 ** 9 + 7))


mod = 10 ** 9 + 7
a = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 1]
(H, W, K) = map(int, input().split())
dp = [[0] * W for i in range(H)]
if W == 1:
	print(1)
else:
	dp[0][0] = a[W - 1]
	dp[0][1] = a[W - 2]
	for i in range(H - 1):
		for j in range(W):
			dp[i + 1][j] = dp[i][j]
			dp[i + 1][j] *= a[j]
			dp[i + 1][j] *= a[W - j - 1]
			if j > 0:
				dp[i + 1][j] += dp[i][j - 1] * a[W - j - 1] * a[j - 1]
			if j < W - 1:
				dp[i + 1][j] += dp[i][j + 1] * a[W - j - 2] * a[j]
			dp[i + 1][j] %= mod
	print(dp[H - 1][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:
					dp[i][j - 1] += dp[i - 1][j]
					dp[i][j - 1] %= modp
				elif j < w - 1 and pt[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()


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
		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[-1][k - 1] % mod)


from itertools import product
import sys
try:
	from typing import List, Tuple
except ImportError:
	pass
MOD = 1000000007

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)]
	dp = [1 if i == K - 1 else 0 for i in range(W)]
	for _ in range(H):
		newdp = [0] * W
		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))
	W = int(next(tokens))
	K = int(next(tokens))
	solve(H, W, K)

def __starting_point():
	main()
__starting_point()


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


from collections import Counter
(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]
iws = [Counter(r) for r in zip(*pats)]
rs = [1] + [0] * (W - 1)
for j in range(H):
	rs = [sum((rs[i] * iw[i] for i in iw)) % MOD for iw in iws]
print(rs[K - 1])


(H, W, K) = map(int, input().split())
MOD = 10 ** 9 + 7
dp = [[0] * W for _ in range(H + 1)]
dp[0][K - 1] = 1
multi = [1, 2, 3, 5, 8, 13, 21]

def f(num, l, r):
	left = max(0, l)
	right = num - 1 - min(r, num - 1)
	return multi[left] * multi[right]
for h in range(1, H + 1):
	for w in range(W):
		dp[h][w] += dp[h - 1][w] * f(W, w - 1, w + 1)
		if w > 0:
			dp[h][w] += dp[h - 1][w - 1] * f(W, w - 2, w + 1)
		if w < W - 1:
			dp[h][w] += dp[h - 1][w + 1] * f(W, w - 1, w + 2)
		dp[h][w] %= MOD
print(dp[H][0])


(h, w, k) = 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(2 ** (w - 1)):
		tmp = format(j, 'b')
		if len(tmp) != w - 1:
			tmp = (w - 1 - len(tmp)) * '0' + tmp
		flag = True
		for l in range(1, w - 1):
			if tmp[l] == '1' and tmp[l - 1] == '1':
				flag = False
				break
		if flag == False:
			continue
		else:
			arr = [i for i in range(1, w + 1)]
			for m in range(w - 1):
				if tmp[m] == '1':
					(arr[m], arr[m + 1]) = (arr[m + 1], arr[m])
			for m in range(w):
				dp[i][m] += dp[i - 1][arr[m] - 1] % mod
print(dp[h][k - 1] % mod)


import sys
input = sys.stdin.readline
import copy
(h, w, k) = map(int, input().split())
ans = [0] + [1] + [0] * w
sequence_list = [1, 1, 2, 3, 5, 8, 13, 21, 34]
move_pattern = {}
for i in range(1, w + 1):
	move_pattern[str(i)] = sequence_list[w - i] * sequence_list[i - 1]
for i in range(1, w):
	move_pattern[i * 11 + 1] = sequence_list[i - 1] * sequence_list[w - i - 1]
move_pattern[1] = 0
move_pattern[w * 11 + 1] = 0
for _ in range(h):
	keep_ans = copy.deepcopy(ans)
	for i in range(1, w + 1):
		ans[i] = keep_ans[i - 1] * move_pattern[i * 11 - 10] + keep_ans[i] * move_pattern[str(i)] + keep_ans[i + 1] * move_pattern[i * 11 + 1]
print(ans[k] % 1000000007)


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

def fb(n):
	if n < 0:
		print('error')
		return -1
	if n == 0:
		return 1
	if n == 1:
		return 1
	if n in fb_dic:
		return fb_dic[n]
	ret = fb(n - 1) + fb(n - 2)
	fb_dic[n] = ret
	return ret
for y in range(1, h + 1):
	for x in range(w):
		if x - 1 >= 0:
			dp[y][x] += dp[y - 1][x - 1] * fb(x - 1) * fb(w - x - 1)
		if x + 1 <= w - 1:
			dp[y][x] += dp[y - 1][x + 1] * fb(x) * fb(w - x - 2)
		dp[y][x] += dp[y - 1][x] * fb(x) * fb(w - x - 1)
		dp[y][x] %= 1000000007
print(dp[h][k - 1])


import collections
(H, W, K) = map(int, input().split())
MOD = 10 ** 9 + 7
F = [1, 1, 2, 3, 5, 8, 13, 21, 34]
c1 = collections.Counter([1])
for i in range(H):
	tmp = collections.Counter()
	for c in c1:
		if c > 1:
			tmp[c - 1] += c1[c] * F[max([0, c - 2])] * F[W - c]
		tmp[c] += c1[c] * F[c - 1] * F[W - c]
		if c < W:
			tmp[c + 1] += c1[c] * F[c - 1] * F[W - c - 1]
	c1 = collections.Counter(tmp)
ans = c1[K]
print(ans % MOD)


(h, w, k) = map(int, input().split())
dp = [[0 for _ in range(w)] for _ in range(h + 1)]
perm = [1, 2, 3, 5, 8, 13, 21, 34]
law = 1000000007
for row in range(h + 1):
	for col in range(w):
		if row == 0:
			dp[row][col] = int(col == 0)
		else:
			if col > 0:
				dp[row][col] = (dp[row][col] + dp[row - 1][col - 1] * perm[max(0, col - 2)] * perm[max(0, w - col - 2)]) % law
			if col < w - 1:
				dp[row][col] = (dp[row][col] + dp[row - 1][col + 1] * perm[max(0, col - 1)] * perm[max(0, w - col - 3)]) % law
			dp[row][col] = (dp[row][col] + dp[row - 1][col] * perm[max(0, col - 1)] * perm[max(0, w - col - 2)]) % law
print(dp[h][k - 1])


import copy
(H, W, K) = map(int, input().split())
w_list = [None, 1]
for i in range(W - 1):
	w_list.append(0)
fibo = [1, 1, 2, 3, 5, 8, 13, 21]
if W >= 2:
	for step in range(1, H + 1):
		w_list_temp = copy.copy(w_list)
		w_list[1] = w_list_temp[1] * fibo[W - 1] + w_list_temp[2] * fibo[W - 2]
		w_list[W] = w_list_temp[W] * fibo[W - 1] + w_list_temp[W - 1] * fibo[W - 2]
		for Ind in range(2, W):
			w_list[Ind] = w_list_temp[Ind] * fibo[Ind - 1] * fibo[W - (Ind - 1) - 1] + w_list_temp[Ind - 1] * fibo[Ind - 2] * fibo[W - (Ind - 1) - 1] + w_list_temp[Ind + 1] * fibo[Ind - 1] * fibo[W - (Ind - 1) - 2]
print(w_list[K] % 1000000007)


(h, w, k) = map(int, input().split())
mod = 10 ** 9 + 7
t = [1, 1, 2, 3, 5, 8, 13, 21]
if w == 1:
	print(1)
	exit()
s = [1] + [0 for _ in range(w - 1)]
for i in range(h):
	ss = [None for _ in range(w)]
	ss[0] = (s[0] * t[w - 1] + s[1] * t[w - 2]) % mod
	ss[w - 1] = (s[w - 1] * t[w - 1] + s[w - 2] * t[w - 2]) % mod
	for j in range(1, w - 1):
		ss[j] = (s[j - 1] * t[j - 1] * t[w - j - 1] + s[j] * t[j] * t[w - j - 1] + s[j + 1] * t[w - j - 2] * t[j]) % mod
	s = ss
print(s[k - 1])


import math
import itertools
from collections import deque
from collections import Counter
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])


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


(H, W, K) = map(int, input().split())
mod = 1000000007
dp = [[0 for _ in range(W)] for _ in range(H + 1)]
dp[0][0] = 1
for h in range(H):
	cnt = 0
	while cnt < 1 << W - 1:
		if '11' not in format(cnt, 'b'):
			for w in range(W):
				if w > 0 and cnt >> w - 1 & 1:
					dp[h + 1][w - 1] += dp[h][w]
				elif w < W - 1 and cnt >> w & 1:
					dp[h + 1][w + 1] += dp[h][w]
				else:
					dp[h + 1][w] += dp[h][w]
		cnt += 1
print(dp[-1][K - 1] % mod)


MOD = 10 ** 9 + 7
(H, W, K) = map(int, input().split())
if W == 1:
	print(1)
	exit()
dp = [[0 for x in range(W)] for h in range(H + 1)]
dp[0][0] = 1
for h in range(H):
	(X, Y, Z) = (0, 0, 0)
	for i in range(2 ** (W - 1)):
		if bin(i).count('11') >= 1:
			continue
		perm = [k for k in range(W)]
		for j in range(W - 1):
			if i >> j & 1:
				(perm[j], perm[j + 1]) = (perm[j + 1], perm[j])
		for j in range(W):
			dp[h + 1][perm[j]] += dp[h][j]
			dp[h + 1][perm[j]] %= MOD
print(dp[H][K - 1])


(h, w, k) = (int(x) for x in input().split())
MOD = 1000000007
dp = [[0] * (w + 2) for _ in range(h + 2)]
fib = [0] * (w + 1)
fib[1] = 1
dp[0][1] = 1
for i in range(2, w + 1):
	fib[i] = fib[i - 1] + fib[i - 2]
for i in range(1, h + 1):
	for j in range(1, w + 1):
		dp[i][j] = (dp[i - 1][j - 1] * fib[j - 1] * fib[w - j + 1] + dp[i - 1][j] * fib[j] * fib[w - j + 1] + dp[i - 1][j + 1] * fib[j] * fib[w - j]) % MOD
print(dp[h][k])


import sys

def fib(n):
	if n == 0:
		return 1
	elif n == 1:
		return 1
	else:
		return fib(n - 1) + fib(n - 2)

def main():
	input = sys.stdin.readline
	(H, W, K) = map(int, input().split())
	DP = [[0 for _ in range(W)] for _ in range(H + 1)]
	DP[0][0] = 1
	for i in range(H):
		for j in range(W):
			if j - 1 >= 0:
				X = fib(j - 1) * fib(W - (j + 1))
				DP[i + 1][j - 1] += X * DP[i][j]
			if j + 1 <= W - 1:
				Z = fib(j) * fib(W - (j + 2))
				DP[i + 1][j + 1] += Z * DP[i][j]
			Y = fib(j) * fib(W - (j + 1))
			DP[i + 1][j] += Y * DP[i][j]
	print(DP[H][K - 1] % (10 ** 9 + 7))
main()