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):
h, w, k = map(int, input().split())
if w == 1:
    print(1)
    exit()
mod = 10 ** 9 + 7

def fibo(w):
    if w == 0:
        return 1
    if w == 1:
        return 1
    elif w == 2:
        return 2
    else:
        return fibo(w - 1) + fibo(w - 2)

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

Solution (Python):


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


if __name__ == '__main__':
    main()

Solution (Python):
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)

Solution (Python):



import array
from bisect import *
from collections import *
import fractions
import heapq 
from itertools import *
import math
import random
import re
import string
import sys

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

MOD = 1000000007

def solve(H, W, K):
    if W == 1:
        return 1

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

    for h in range(1, H+1):
        
        
        for i in range(1 << (W-1)):
            
            ok = True
            for j in range(1, W-1):
                if (i & (1 << j)) and (i & (1 << (j-1))):
                    ok = False
            if not ok:
                continue

            
            
            
            
            
            
            
            for j in range(W):
                
                if j != 0 and i & (1 << (j - 1)):
                    dp[h][j] += dp[h-1][j-1]
                    dp[h][j] %= MOD
                
                elif j != W-1 and i & (1 << j):
                    dp[h][j] += dp[h-1][j+1]
                    dp[h][j] %= MOD
                
                else:
                    dp[h][j] += dp[h-1][j]
                    dp[h][j] %= MOD

    return dp[H][K-1]

print(solve(H, W, K))

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

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

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

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

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


for i in range(H):
    for j in range(W):
        for k in range(1<<W-1):
            ok = 1
            for l in range(W-2):
                if ((k >> l)&1 == 1)and((k>>l+1)&1 == 1):
                    ok = 0

            if ok:
                
                if (j >= 1) and ((k>>j-1)&1 == 1):
                    dp[i+1][j-1] += dp[i][j]
                    dp[i+1][j-1] %= mod
                
                elif (j <= W-2) and ((k>>j)&1 == 1):
                    dp[i+1][j+1] += dp[i][j]
                    dp[i+1][j+1] %= mod
                
                else:
                    dp[i+1][j] += dp[i][j]
                    dp[i+1][j] %= mod

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

Solution (Python):
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))

Solution (Python):
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)

Solution (Python):
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])


if __name__ == '__main__':
    main()

Solution (Python):


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(H):
    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 + 1][perm[i]] += dp[h][i]
            dp[h + 1][perm[i]] %= MOD

print(dp[H][K])

Solution (Python):
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)

Solution (Python):
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))

Solution (Python):
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]

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

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

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


def num(n):
    ret = 0
    if n == 0:
        return 1
    for i in range(2**(n-1)):
        dig = format(i, 'b')
        if not '11' in dig:
            ret += 1

    return ret


if w == 1:
    print('1')
    exit()

for col in range(1, h+1):
    for row in range(w):
        if row == 0:
            mat[col][row] = mat[col-1][row] * \
                num(w-1) + mat[col-1][row+1]*num(w-2)
        elif row == w-1:
            mat[col][row] = mat[col-1][row] * \
                num(w-1) + mat[col-1][row-1]*num(w-2)
        else:
            mat[col][row] = mat[col-1][row] * (num(row)*num(w-row-1)) \
                + mat[col-1][row-1]*(num(row-1)*num(w-row-1))\
                + mat[col-1][row+1]*(num(row)*num(w-row-2))
print(mat[h][k-1] % 1000000007)

Solution (Python):
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])

Solution (Python):
h, w, K = map(int, input().split())

mod = 1000000007


count_pattern = [0 for i in range(9)]
count_pattern_boundary = [0 for i in range(9)]
for i in range(9):
    for j in range(2**i):
        bin_str = '{:b}'.format(j)
        flag = True
        for k in range(len(bin_str)-1):
            if bin_str[k]=='1' and bin_str[k+1]=='1':
                flag = False
                break
        if flag:
            count_pattern[i] += 1
            if bin_str[-1]!='1':
                count_pattern_boundary[i] += 1




count = [[0 for i in range(w)] for j in range(h+1)]
count[0][0] = 1
if w!=1:
    for i in range(h):
        j = 0
        count[i+1][j] = count[i][j]*count_pattern[w-j-2] + count[i][j+1]*count_pattern_boundary[w-j-2]
        for j in range(1, w-1):
            count[i+1][j] = count[i][j-1]*count_pattern_boundary[j-1]*count_pattern[w-j-2]\
                    + count[i][j+1]*count_pattern[j-1]*count_pattern_boundary[w-j-2]\
                    + count[i][j]*count_pattern[j-1]*count_pattern[w-j-2]
        j = w-1
        count[i+1][j] = count[i][j]*count_pattern[j-1] + count[i][j-1]*count_pattern_boundary[j-1]
else:
    for i in range(h):
        count[i+1][0] = count[i][0]
print(count[h][K-1]%mod)

Solution (Python):
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 b in range(1<<(W-1)):
        if '11' in bin(b):
            continue
        b <<= 1
        for k in range(W):
            if b & (1<<k):
                dp[i+1][k] += dp[i][k-1]
            elif b & (1<<(k+1)):
                dp[i+1][k] += dp[i][k+1]
            else:
                dp[i+1][k] += dp[i][k]
            dp[i+1][k] %= mod

print(dp[i+1][K])

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


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


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


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

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

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

        dp[i][j] = tmp

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

Solution (Python):
import numpy as np
MOD = 1000000007

def phi(i, m):
    if (i > 0) and (m[i-1] == 1):
        return i-1
    elif (i < len(m)) and (m[i] == 1):
        return i+1
    else:
        return i

def ok(m):
    for i in range(len(m) - 1):
        if (m[i] == 1) and (m[i+1] == 1):
            return False
    return True

def solve(H, W, K):
    M = []
    for bitmask in range(2**(W-1)):
        m = []
        for w in range(W-1):
            m.append(bitmask % 2)
            bitmask /= 2
        M.append(m)
    M = filter(ok, M)
    dp = np.zeros((H+1, W), dtype=np.int64)
    dp[0, K-1] = 1
    for h in range(H):
        for i in range(W):
            for m in M:
                j = phi(i, m)
                dp[h+1, i] = (dp[h+1, i] + dp[h, j]) % MOD
    return dp[H, 0]

H, W, K = map(int, raw_input().split())
print(solve(H, W, K))

Solution (Python):
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)

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

fibo=[1,1,2]
for i in range(W):
    fibo.append(fibo[-1]+fibo[-2])

mod=1000000007
    
f=[[1 if i==1 else 0 for i in range(W+2)]]
for i in range(H):
    for j in range(W):
        f.append([(f[-1][j]*fibo[j-1]*fibo[W-j]+f[-1][j-1]*fibo[j-2]*fibo[W-j]\
                  +f[-1][j+1]*fibo[j-1]*fibo[W-j-1])% mod\
                     if (j>=1 and j<=W) else 0 for j in range(W+2)])     

print f[H][K]

Solution (Python):
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])

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

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


dp[0][1]=1


h=0
for h in range(H):
	for t in range(2**(W-1)):
		s=str(bin(t))[2:]
		if len(s)<W: s=(W-len(s)-1)*"0"+s

		v=0
		for i,x in enumerate(s):
			x=int(x)
			if x==0:
				v=0
			elif x==1:
				v+=1
				if v==2:
					break
		else:
		
			V=[0 for w  in range(W+1)]	
			for k,x in enumerate(s):
				k+=1
				if x=="1":
				
					dp[h+1][k]+=dp[h][k+1]
					V[k]=1
				
					dp[h+1][k+1]+=dp[h][k]
					V[k+1]=1
			for k in range(1,W+1):
				if V[k]==0:
				
					dp[h+1][k]+=dp[h][k]
								
										

	
				

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

Solution (Python):
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)

Solution (Python):
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])

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

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

mod = int(1e9 + 7)

for i in range(H):
    for j in range(W):
        for bit in range(2**(W-1)):
            is_valid = True
            for k in range(W-2):
                if (bit >> k & 1) and ((bit >> (k + 1)) & 1):
                    is_valid = False
            if not is_valid:
                continue

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

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

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

dp[0][0] = 1
for i in range(1,W):
    dp[0][i] = 0

for h in range(H):
    for w in range(W):
        
        for j in range((1<<W-1)):
            ok = True
            for k in range(1,W-1):
                if (j>>k)%2 == 1 and (j>>k-1)%2 == 1:
                    ok = False 
                    break
            if ok :
                
                if w < W-1 and (j>>w)%2 == 1:
                    dp[h+1][w+1] += dp[h][w]
                    dp[h+1][w+1] = dp[h+1][w+1]%mod
                
                elif w > 0 and (j>>w-1)%2 == 1:
                    dp[h+1][w-1] += dp[h][w]
                    dp[h+1][w-1] = dp[h+1][w-1]%mod
                else:
                    dp[h+1][w] += dp[h][w]
                    dp[h+1][w] = dp[h+1][w]%mod

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

Solution (Python):
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])

Solution (Python):
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)

Solution (Python):


"""
参考：https://misteer.hatenablog.com/entry/ABC113
・DPとビット全検索
"""

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

K -= 1
MOD = 10 ** 9 + 7

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

dp[0][0] = 1

for h in range(1, H+1):
    
    for b in range(1 << (W-1)):
        
        s = format(b, 'b')
        if s.count('11'):
            continue
        
        perm = [0] * W
        for i in range(W):
            perm[i] = i
        
        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])

Solution (Python):

def DP(H, W, K):
    res = [[0 for i in range(W)] for j in range(H+1)]
    res[0][0] += 1
    for step in range(1, H+1):
        for i in range(2**(W-1)):
            s = "{:08b}".format(i)[::-1]


            if '11' in s:
                continue
            for x in range(0, W):
                if x == 0:
                    if s[x] == '0':
                        res[step][x] += res[step-1][x]
                    elif s[x] == '1':
                        res[step][x+1] += res[step-1][x]
                elif x == W-1:
                    if s[x-1] == '0':
                        res[step][x] += res[step-1][x]
                    elif s[x-1] == '1':
                        res[step][x-1] += res[step-1][x]
                else:
                    
                    if s[x] == '0' and s[x-1] == '0':
                        res[step][x] += res[step-1][x]
                    elif s[x] == '1':
                        res[step][x+1] += res[step-1][x]
                    elif s[x-1] == '1':
                        res[step][x-1] += res[step-1][x]

        for i in range(W):
            res[step][i] = res[step][i] % MOD
    return res[step][K-1]


H, W, K = map(int, input().split(' '))
MOD = 1000000007
print(DP(H, W, K))

Solution (Python):

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)

Solution (Python):
import itertools

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

if K - 1 > H:
    print(0)
    exit(0)
if W == 1:
    print(1)
    exit(0)

R = []
for r in itertools.product( [0,1], repeat=(W-1) ):
    if 1 not in list(map(lambda i : r[i]*r[i+1], range(len(r)-1)) ):
        R.append(r)


M = [ (
    len( list( filter( lambda r:r[0]==0, R) ) ),
    len( list( filter( lambda r:r[0]==1, R) ) ),
    0
) ]
for c in range(1,W-1):
    M.append((
        len( list( filter( lambda r:r[c]==0 and r[c-1]==0, R) ) ),
        len( list( filter( lambda r:r[c]==1, R) ) ),
        len( list( filter( lambda r:r[c-1]==1, R) ) )
    ))
M.append((
    len( list( filter( lambda r:r[W-2]==0, R) ) ),
    0,
    len( list( filter( lambda r:r[W-2]==1, R) ) )
))

count = [1] + [0]*(W-1)
for h in range(H):
    count_ = [0] * W
    for num,c in zip(count, range(len(count))):
        for m,n in zip(M[c], [0,+1,-1]):
            if c+n >= 0 and c+n < W:
                count_[c+n] += num * m
    count = count_
        
print(count_[K-1]%p)

Solution (Python):
H, W, K = (int(i) for i in input().split())

if W == 1:
    print(1)

else:

    wnum = [0]*(W-1)
    for i in range(W-1):
        wsum = 0
        for j in range(2**(W-1)):
            bit = format(j, "0{}b".format(W-1))
            cc = 0
            for k in range(W-2):
                if bit[k] == "1" and bit[k + 1] == "1":
                    break
            else:
                if bit[i] == "1":
                    wnum[i] += 1
                wsum += 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 1 <= j <= W-2:
                dp[i+1][j] = dp[i][j-1] * wnum[j-1] + dp[i][j+1] * wnum[j] + dp[i][j] * (wsum-wnum[j-1]-wnum[j])
            elif j == 0:
                dp[i+1][j] = dp[i][j+1] * wnum[j] + dp[i][j] * (wsum-wnum[j])
            else:
                dp[i+1][j] = dp[i][j-1] * wnum[j-1] + dp[i][j] * (wsum-wnum[j-1])
            dp[i+1][j] = dp[i+1][j] % 1000000007
    print(dp[H][K-1])

Solution (Python):
H,W,K = map(int,input().split(" "))
dp = [ [0]*W for _ in range(H+1) ]
dp[0][0] = 1
mod = 10**9+7

for i in range(1,H+1):
    for j in range(W):
        l,m,r = 0,0,0
        for k in range(1<<(W-1)):
            flg = True
            for bit in range(W-2):
                if (k >> bit) & (k >> (bit+1)) & 1:
                    flg =  False
                    break
            if flg:
                if j < (W-1) and (k >> (W - j - 2)) & 1:
                    r += 1
                if (j == (W-1) or ((k >> (W - j - 2)) & 1 == 0)) and (j == 0 or ((k >> (W - j - 1)) & 1 == 0)):
                    m += 1
                if j > 0 and (k >> (W - j - 1)) & 1:
                    l += 1

        if j > 0:
            dp[i][j] += l * dp[i-1][j-1]
        dp[i][j] += m * dp[i-1][j]
        if j < (W-1):
            dp[i][j] += r*dp[i-1][j+1]
        dp[i][j] %= mod
print(dp[-1][K-1]%mod)

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


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


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

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


for i in range(1, H + 1):
    for j in range(W):
        tmp = 0
        
        tmp += dp[i - 1][j] * pattern(j - 1) * pattern(W - j - 2) % mod

        
        if j > 0:
            tmp += dp[i - 1][j - 1] * pattern(j - 2) * pattern(W - j - 2) % mod

        
        if j < W - 1:
            tmp += dp[i - 1][j + 1] * pattern(j - 1) * pattern(W - j - 3) % mod

        dp[i][j] += tmp

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

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


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


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

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


for i in range(1, H + 1):
    for j in range(W):
        tmp = 0
        
        tmp = (tmp + dp[i - 1][j] * (pattern(j - 1) * pattern(W - j - 2))) % mod

        
        if j > 0:
            tmp = (tmp + dp[i - 1][j - 1] * (pattern(j - 2) * pattern(W - j - 2))) % mod

        
        if j < W - 1:
            tmp = (tmp + dp[i - 1][j + 1] * (pattern(j - 1) * pattern(W - j - 3))) % mod

        dp[i][j] += tmp

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

Solution (Python):

H,W,K = list(map(int, input().split() ))
mod = int(1e9+7) 




def disp(dp):
    for i in range(H+1):
        print(i, end=" ")
        for j in range(W):
            print(dp[i][j],end=", ")
        print("")


dp = [[0] * W for h 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-1):
                if (k&(1<<l)!=0) and (k&(1<<(l+1))!=0):
                    ok = False
            
            if ok:
                if j>0 and k&(1<<(j-1)): 
                    dp[i+1][j-1] += dp[i][j]
                    dp[i+1][j-1] %= mod
                    dp[i+1][j-1] = int(dp[i+1][j-1])

                elif j<W and k&(1<<(j)):   
                    dp[i+1][j+1] += dp[i][j]
                    dp[i+1][j+1] %= mod
                    dp[i+1][j+1] = int(dp[i+1][j+1])
                else:
                    dp[i+1][j] += dp[i][j]
                    dp[i+1][j] %= mod
                    dp[i+1][j] = int(dp[i+1][j])
                
                
            else:
                continue

       



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

Solution (Python):
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)