Problem:
 Score: 400 points    Problem Statement 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 1 3 2      Sample Output 1 1  Only the following one amidakuji satisfies the condition:        Sample Input 2 1 3 1      Sample Output 2 2  Only the following two amidakuji satisfy the condition:        Sample Input 3 2 3 3      Sample Output 3 1  Only the following one amidakuji satisfies the condition:        Sample Input 4 2 3 1      Sample Output 4 5  Only the following five amidakuji satisfy the condition:        Sample Input 5 7 1 1      Sample Output 5 1  As there is only one vertical line, we cannot draw any horizontal lines. Thus, there is only one amidakuji that satisfies the condition: the amidakuji with no horizontal lines.       Sample Input 6 15 8 5      Sample Output 6 437760187  Be sure to print the answer modulo 1\ 000\ 000\ 007 .

Solution (Python):
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict, Counter
from bisect import bisect
import functools

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

H, W, K = reads()
P = 10**9 + 7

M = W + 100
fib = [0] * M
fib[0] = fib[1] = 1
for i in range(M-2):
  fib[i+2] = (fib[i] + fib[i+1]) % P

@functools.lru_cache(100000)
def solve(h, k):
  if h == 0:
    return 1 if k == 1 else 0
  if k == 1:
    return (solve(h-1, 1) * fib[W-1] + solve(h-1, 2) * fib[W-2]) % P
  elif k == W:
    return (solve(h-1, W) * fib[W-1] + solve(h-1, W-1) * fib[W-2]) % P
  else:
    return (solve(h-1, k) * fib[k-1] * fib[W-k]
      + solve(h-1, k-1) * fib[k-2] * fib[W-k]
      + solve(h-1, k+1) * fib[k-1] * fib[W-k-1]) % P

if W == 1:
  print(1); exit()
print(solve(H, K))

Solution (Python):
H,W,K = map(int, raw_input().split())
K -= 1

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

mod = 1000000007

T = [0]*W
T[0] = 1
for i in range(H):
  P = T
  T = [0]*W
  for b in range(1<<(W-1)):
    ok = True
    for j in range(W-2):
      if b>>j&1 and b>>(j+1)&1:
        ok = False
    if ok:
      for j in range(W):
        if j>0 and b>>(j-1)&1:
          T[j-1] += P[j]
          T[j-1] %= mod
        elif j<W-1 and b>>j&1:
          T[j+1] += P[j]
          T[j+1] %= mod
        else:
          T[j] += P[j]
          T[j] %= mod
print T[K]

Solution (Python):
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  

mod = 1000000007

h, w, kk = na()
kk -= 1

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

vs = []
for j in range(1 << w - 1):
    ok = True
    for k in range(w):
        if (j & 3 << k) == 3 << k:
            ok = False
            break
    if ok:
        vs.append(j)

for i in range(h):
    ndp = [0] * w
    for j in range(w):
        for l in vs:
            if l>>j&1:
                ndp[j+1] += dp[j]
            elif j >= 1 and (l>>j-1&1) > 0:
                ndp[j-1] += dp[j]
            else:
                ndp[j] += dp[j]

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

print(dp[kk])