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):
import sys
mod = pow(10, 9) + 7
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

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

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

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


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

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

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

print(d[K-1])

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

Solution (Python):
import numpy as np
H,W,K=map(int,input().split())
A=np.zeros((W,W))
mod=10**9+7
for i in range(1<<(W-1)):
    flag=True
    s=0
    for j in range(W-1):
        if i&(1<<j) and s==0:
            s=1
        elif i&(1<<j) and s==1:
            flag=False
            break
        else:
            s=0
    if flag:
        
        L=[int(i) for i in range(W)]
        for j in range(W-1):
            if i&(1<<j):
                L[j]=j+1
                L[j+1]=j
        for j in range(W):
            A[j][L[j]]+=1
x=np.zeros(W)
x[0]=1
for i in range(H):
    x=np.dot(A,x)
    x%=mod
print(int(x[K-1]))

Solution (Python):
import numpy as np

mod=1000000007
s=input().split()
h,w,k=int(s[0]),int(s[1]),int(s[2])
l=[]
for i in range(2**(w-1)):
    s=bin(i)[2:].zfill(w-1)
    if s.find("11")==-1:
        l.append(s)
mat=np.zeros((w,w),dtype="int64")
for s in l:
    dest=[i for i in range(w)]
    for i in range(w-1):
        if s[i]=="1":
                dest[i],dest[i+1]=dest[i+1],dest[i]
    for i in range(w):
        mat[i][dest[i]]+=1
res=np.zeros(w,dtype="int64")
res[0]=1
for i in range(h):
    res=np.dot(mat,res)
    for i in range(w):
        res[i]%=mod
print(res[k-1])

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

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

Solution (Python):
import numpy as np
(H, W, K) = map(int, input().split())
M = 1000000007
F = np.zeros((H+1,W+2),dtype=np.int64)

def hor_cmb(x):
    if x<=0:
        return 1
    elif x==1:
        return 2
    else:
        return (hor_cmb(x-1) + hor_cmb(x-2))

F[0,1] = 1
for h in range(1,H+1):
    for w in range(1,W+1):
        c = hor_cmb(w-3)*hor_cmb(W-w-1)
        d = hor_cmb(w-2)*hor_cmb(W-w-1)
        e = hor_cmb(w-2)*hor_cmb(W-w-2)
        F[h,w] = (c*F[h-1,w-1] + d*F[h-1,w] + e*F[h-1,w+1]) % M
print(F[H,K])

Solution (Python):
MOD = 10 ** 9 + 7

h, w, k = map(int, input().split())

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

cnts = []
for i in range(w + 1):
    cnt = 0
    for j in range(1 << i):
        if not '11' in bin(j)[2:]: cnt += 1
    cnts.append(cnt)

for i in range(1, h + 1):
    for j in range(1, w + 1):
        dp[j][i] += dp[j][i - 1] * cnts[max(0, w - (j + 1))] * cnts[max(0, (j - 1) - 1)]
        if 1 <= j - 1 <= w:
            dp[j][i] += dp[j - 1][i - 1] * cnts[max(0, w - (j + 1))] * cnts[max(0, (j - 2) - 1)]
        if 1 <= j + 1 <= w:
            dp[j][i] += dp[j + 1][i - 1] * cnts[max(0, w - (j + 2))] * cnts[max(0, (j - 1) - 1)]
        dp[j][i] %= MOD

print(dp[k][h])

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

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

ans = [0] + [1] + [0] * w
n_ans = [a for a in ans]
fact = [1, 2, 3, 5, 8, 13, 21]
mod = 10 ** 9 + 7

for _ in range(h):
    for i in range(1, w + 1):
        
        tmp = fact[max(i - 3, 0)] * fact[max(w - i - 1, 0)]
        
        n_ans[i] = (ans[i - 1] * tmp) % mod

        
        tmp = fact[max(i - 2, 0)] * fact[max(w - i - 1, 0)]
        
        n_ans[i] = (n_ans[i] + ans[i] * tmp) % mod

        
        tmp = fact[max(i - 2, 0)] * fact[max(w - i - 2, 0)]
        
        n_ans[i] = (n_ans[i] + ans[i + 1] * tmp) % mod

        
    ans = [a for a in n_ans]
    


print(ans[k])

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

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

dp = {i: {j: 0 for j in range(1, W+1)} for i in range(H+1)} 

dp[0][1] = 1

n_valid_patterns = {i: -1 for i in range(W+1)}

def valid_patterns(n): 
    if n_valid_patterns[n] != -1:
        return n_valid_patterns[n]
    elif n <= 1:
        return 1
    elif n == 2:
        return 2
    else:
        n_valid_patterns[n] = (valid_patterns(n-2) + valid_patterns(n-1)) % MOD 
        return n_valid_patterns[n]

for i in range(1, H+1):
    for j in range(1, W+1):
        if j > 1: 
            dp[i][j] += dp[i-1][j-1]*(valid_patterns(j-2)*valid_patterns(W-j)) % MOD

        
        dp[i][j] += dp[i-1][j]*(valid_patterns(j-1)*valid_patterns(W-j)) % MOD

        if j < W: 
            dp[i][j] += dp[i-1][j+1]*(valid_patterns(j-1)*valid_patterns(W-j-1)) % MOD

        dp[i][j] %= MOD

print(dp[H][K])

Solution (Python):
import numpy as np
H, W, K = map(int, input().split())
p = 10**9 + 7
r = [1, 1, 2, 3, 5, 8, 13, 21, 34]
dp = np.zeros([H + 1, W], dtype=int)
dp[0, 0] = 1
for h in range(H):
    for w in range(W):
        if w != 0:
            dp[h+1, w] += ((dp[h, w-1] * r[w-1])%p * r[W-1-w])%p
        dp[h+1, w] += ((dp[h, w] * r[w])%p * r[W-1-w])%p
        if w != W-1:
            dp[h+1, w] += ((dp[h, w+1] * r[w])%p * r[W-2-w])%p
        dp[h+1, w] = dp[h+1, w]%p
print(dp[H, K-1])

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

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

Solution (Python):
h,w,k=map(int,input().split())
def amida_h1_total(w):
    if w<0:
        return 0
    if w==0:
        return 1
    return amida_h1_total(w-1)+amida_h1_total(w-2)
def amida(h,w,k):
    memo=[[-1 for _ in range(w)] for _ in range(h)]
    memo[0][0]=amida_h1_total(w-1)
    if w>1:
        memo[0][1]=amida_h1_total(w-2)
    for i in range(2,w):
        memo[0][i]=0
    def _amida(h,k):
        if k<=0 or k>w:
            return 0
        if memo[h-1][k-1]>=0:
            return memo[h-1][k-1]
        memo[h-1][k-1]=sum((_amida(h-1,k-1)*amida_h1_total(k-2)*amida_h1_total(w-k),
                            _amida(h-1,k)  *amida_h1_total(k-1)*amida_h1_total(w-k),
                            _amida(h-1,k+1)*amida_h1_total(k-1)*amida_h1_total(w-k-1)))%1000000007
        return memo[h-1][k-1]
    return _amida(h,k)
print(amida(h,w,k))

Solution (Python):


h, w, k = map(int, input().split())


def f(x):
    lst = [1, 2, 3, 5, 8, 13, 21]
    if 0 <= x < 7:
        return lst[x]
    else:
        return 1


ptn = [[0] * (w + 2) for _ in range(w + 2)]
for i in range(w + 2):
    for j in range(w + 2):
        if i == 0 or i == w + 1 or j == 0 or j == w + 1:
            continue
        elif i == j:
            ptn[i][j] = f(i-2)*f(w-i-1)
        elif i == j + 1:
            ptn[i][j] = f(i-3)*f(w-i-1)
        elif i == j - 1:
            ptn[i][j] = f(i-2)*f(w-i-2)

for _ in range(h - 1):
    temp = [[0] * (w + 2) for _ in range(w + 2)]
    for i in range(w + 2):
        for j in range(w + 2):
            if i == 0 or i == w + 1 or j == 0 or j == w + 1:
                continue
            else:
                temp[i][j] = ptn[i-1][j]*f(i-3)*f(w-i-1) + ptn[i][j]*f(i-2)*f(w-i-1) + ptn[i+1][j]*f(i-2)*f(w-i-2)

    ptn = temp

print(ptn[1][k] % 1000000007)

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

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

memo = {}

def po(x, y):
    if y == h + 1:
        if x == k - 1:
            return 1
        else:
            return 0

    if (x, y) in memo:
        return memo[(x, y)]

    ans = 0
    for i in range(1 << w - 1):
        valid = True
        for j in range(w - 2):
            if i & (1 << j) and i & (1 << j + 1):
                valid = False
                break
        if valid:
            nx = x
            if x > 0 and i & (1 << x - 1):
                nx = x - 1
            if i & (1 << x):
                nx = x + 1
            ans += po(nx, y + 1)
            ans %= 1000000007
    
    memo[(x, y)] = ans
    return ans

print(po(0, 1))

Solution (Python):
l=[[] for i in range(9)]
l[1]=[""]
l[2]=["0","1"]
for i in range(3,9):
    for s in l[i-1]:
        l[i].append("0"+s)
        if s[0]!="1":
            l[i].append("1"+s)

mod=1000000007
s=input().split()
h,w,k=int(s[0]),int(s[1]),int(s[2])
dp=[[0]*(w) for i in range(h+1)]
dp[0][0]=1
for i in range(h):
    for s in l[w]:
        s="0"+s+"0" 
        for j in range(w):
            if s[j]=="0" and s[j+1]=="0": 
                dp[i+1][j]+=dp[i][j]
                dp[i+1][j]%=mod
            if s[j]=="0" and s[j+1]=="1": 
                dp[i+1][j+1]+=dp[i][j]
                dp[i+1][j+1]%=mod
            if s[j]=="1" and s[j+1]=="0": 
                dp[i+1][j-1]+=dp[i][j]
                dp[i+1][j-1]%=mod
print(dp[h][k-1])

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

Solution (Python):
l=[[] for i in range(9)]
l[1]=[""]
l[2]=["0","1"]
for i in range(3,9):
    for s in l[i-1]:
        l[i].append("0"+s)
        if s[0]!="1":
            l[i].append("1"+s)

mod=1000000007
s=input().split()
h,w,k=int(s[0]),int(s[1]),int(s[2])
res=[[0]*(w) for i in range(h+1)]
res[0][0]=1
for i in range(h):
    for s in l[w]:
        s="0"+s+"0" 
        for j in range(w):
            if s[j]=="0" and s[j+1]=="0": 
                res[i+1][j]+=res[i][j]
                res[i+1][j]%=mod
            if s[j]=="0" and s[j+1]=="1": 
                res[i+1][j+1]+=res[i][j]
                res[i+1][j+1]%=mod
            if s[j]=="1" and s[j+1]=="0": 
                res[i+1][j-1]+=res[i][j]
                res[i+1][j-1]%=mod
print(res[h][k-1])

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

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)

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

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


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


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

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

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

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

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

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


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

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

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

print(d[K-1])

Solution (Python):

mp={-6:0,-5:0,-4:0,-3:0,-2:0,-1:1,0:1}
def func(xx):
    if mp.get(xx,0)!=0:
        return mp[xx]
    mp[xx]=(func(xx-1)+func(xx-2))%1000000007
    return mp[xx]
h,w,k= map(int, input().split())
if w == 1:
    print('1')
    exit(0)
DT = [0 for i in range(w)]
CR =  [0 for i in range(w)]
DT [0]=1

for _ in range(h):
    for i in range(w-2):
        CR[i]+=DT[i+1]*func(i-1)*func(w-2-i-1)
        CR[i+1]+=DT[i+1]*func(i)*func(w-2-i-1)
        CR[i+2]+=DT[i+1]*func(i)*func(w-2-i-2)
    CR[0]+=DT[0]*func(w-2)
    CR[1]+=DT[0]*func(w-3)
    CR[-2]+=DT[-1]*func(w-3)
    CR[-1]+=DT[-1]*func(w-2)
    for i in range(w):
        DT[i]=CR[i]%1000000007
        CR[i]=0
    
    
print(DT[k-1])

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

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

transition = [[0]*W for _ in range(W)]

for n in range(2**(W-1)):
  memo = [0]*W
  for i,e in enumerate(map(lambda x: x=='1',bin(n)[:1:-1])):
    if e:
      if memo[i] == 0:
        memo[i] = 1
        memo[i+1] = -1
      else:
        memo = None
        break

  if memo is not None:
    for i,d in enumerate(memo):
      transition[i][i+d] += 1


transition = np.array(transition,dtype=np.int64) % MOD


dp = np.zeros((W,1),dtype=np.int64)
dp[0,0] = 1
for b in map(lambda x: x=='1', bin(H)[:1:-1]):
  if b:
    dp = np.dot(transition, dp)
    dp %= MOD
  transition = np.dot(transition, transition)
  transition %= MOD

print(dp[K,0])

Solution (Python):

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

raw_route = [0] * W 
possible_route = 0

for i in range(2 ** (W - 1)):
    
    i_tmp = i
    last = 0
    for j in range(W - 1):
        if i_tmp % 2 == last == 1: break
        last = i_tmp % 2
        i_tmp = i_tmp // 2
    else:
        
        i_tmp = i
        for j in range(W - 1):
            if i_tmp % 2 == 1: raw_route[j + 1] += 1
            i_tmp = i_tmp // 2
        possible_route += 1



DP = [[None] * W for i in range(H)]

def draw(depth, clm):
    
    if depth == H + 1: return 1
    
    if DP[depth - 1][clm - 1] != None: return DP[depth - 1][clm - 1]
    
    range_min = K - (H - depth)
    range_max = K + (H - depth)
    
    ans = 0
    
    
    if range_min <= clm <= range_max:
        coeff = possible_route
        if clm > 1: coeff -= raw_route[clm - 1]
        if clm < W: coeff -= raw_route[clm]
        ans += coeff * draw(depth + 1, clm)
    
    if range_min <= clm - 1 and 1 <= clm - 1: ans += raw_route[clm - 1] * draw(depth + 1, clm - 1)
    
    if clm + 1 <= range_max and clm + 1 <= W: ans += raw_route[clm] * draw(depth + 1, clm + 1)
    
    if DP[depth - 1][clm - 1] == None: DP[depth - 1][clm - 1] = ans % (10 ** 9 + 7)
    return ans % (10 ** 9 + 7)

print(draw(1, 1))

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

Solution (Python):
import numpy as np
H, W, K = map(int, input().split())
p = 10**9 + 7
r = [1, 1, 2, 3, 5, 8, 13, 21, 34]
dp = np.zeros([H + 1, W], dtype=int)
dp[0, 0] = 1
for h in range(H):
    for w in range(W):
        if w == 0:
            a = 0
        else:
            a = ((dp[h, w-1] * r[w-1])%p * r[W-1-w])%p
        b = ((dp[h, w] * r[w])%p * r[W-1-w])%p
        if w == W-1:
            c = 0
        else:
            c = ((dp[h, w+1] * r[w])%p * r[W-2-w])%p
        dp[h+1, w] = (a+b+c)%p
print(dp[H, K-1])

Solution (Python):
M = 10 ** 9 + 7

def main():
    h, w, k = map(int, input().split())
    k -= 1

    init_fib(w)

    dp = [[None for _ in range(w)] for _ in range(h + 1)]
    for i in range(w):
        dp[0][i] = 0
    dp[0][k] = 1

    for i in range(1, h + 1):
        for j in range(w):
            x = 0
            if j != 0 and dp[i-1][j-1] != 0:
                left = j - 1
                right = w - j - 1
                t = fib(left) * fib(right) % M
                x += t * dp[i-1][j-1] % M
            if j + 1 < w and dp[i-1][j+1] != 0:
                left = j
                right = w - j - 2
                t = fib(left) * fib(right) % M
                x += t * dp[i-1][j+1] % M

            if dp[i-1][j] != 0:
                left = j
                right = w - j - 1
                t = fib(left) * fib(right) % M
                x += t * dp[i-1][j] % M
            
            dp[i][j] = x % M

    print(dp[h][0])

T = []
def init_fib(n):
    global T
    T.append(1)
    T.append(1)

    for i in range(2, n + 1):
        T.append(T[-1] + T[-2])

def fib(n):
    return T[n]

main()

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

Solution (Python):

import numpy as np
def main():
	x  = 1000000007
	buf = input().split()
	h = int(buf[0])
	w = int(buf[1])
	k = int(buf[2])
	
	dpp = np.zeros((w+1, 3), dtype="int")
	dpp[0][0] = 1
	dpp[0][2] = 1
	dpp[1][0] = 1
	dpp[1][2] = 1
	for i in range(2, w+1):
		dpp[i][0] = dpp[i-1][0]+dpp[i-1][1]
		dpp[i][1] = dpp[i-1][0]
		dpp[i][2] = dpp[i][0] + dpp[i][1]
	
	
	dp = np.zeros((h+1, w+2), dtype="int")
	dp[0][1] = 1
	for row in range(1, h+1):
		for col in range(1, w+1):
			dp[row][col] = ((dp[row-1][col-1]*dpp[col-2][2]*dpp[w-col][2])%x + (dp[row-1][col]*dpp[col-1][2]*dpp[w-col][2])%x + (dp[row-1][col+1]*dpp[col-1][2]*dpp[w-col-1][2])%x)%x
	
	print(dp[h][k]%x)
	
	
	
	
	
main()

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

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

mod = 1000000007
dp = [[0 for j in range(w)] for i in range(h)]
dp[0][0] = 1

memo_count_valid_patterns = [0 for i in range(w+1)]


def count_valid_patterns(n):
    
    if n <= 1:
        return 1
    if n == 2:
        return 2
    if memo_count_valid_patterns[n] != 0:
        return memo_count_valid_patterns[n]

    memo_count_valid_patterns[n] = (count_valid_patterns(n - 1) + count_valid_patterns(n - 2)) % mod
    return memo_count_valid_patterns[n]


for i in range(1, h):
    for j in range(w):
        
        if j > 0:
            dp[i][j] += dp[i-1][j-1] * (count_valid_patterns(j-1)*count_valid_patterns(w - j - 1))  
        
        
        dp[i][j] += dp[i-1][j] * (count_valid_patterns(j) * count_valid_patterns(w - j - 1))  

        
        if j < w-1:
            dp[i][j] += dp[i-1][j+1] * (count_valid_patterns(j)*count_valid_patterns(w - j - 2))  

        dp[i][j] %= mod



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

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

A=[[0 for i in range(w)] for j in range(w)]

for i in range(w):
        A[i][i]=1

mod=1000000007

Wlist=[[[-1]],[[-1],[0]],[[-1],[0],[1]]]
for i in range(3,w):
    W=[]
    for j in range(len(Wlist[i-1])):

        if Wlist[i-1][j][-1]!=i-2 : 
            ww=Wlist[i-1][j][:]
            W.append(ww[:])
            ww.append(i-1)
            W.append(ww[:])
        else : 
            ww=Wlist[i-1][j][:]
            W.append(ww[:])
    Wlist.append(W)


Ire=[]
for i in range(len(Wlist[w-1])):
    AA=[j for j in range(w)]
    for j in range(len(Wlist[w-1][i])):
        if Wlist[w-1][i][j]!=-1 :
            t=Wlist[w-1][i][j]
            AA[t]=t+1
            AA[t+1]=t
    Ire.append(AA)



for i in range(h):
    B=[[0 for i in range(w)] for j in range(w)]
    for j in range(len(Ire)):
        for kk in range(w):
            t=Ire[j][kk]
            
            for mm in range(w):
                B[kk][mm]=(B[kk][mm]+A[t][mm])%mod


    
    A=B[:]


print(A[0][k-1])

Solution (Python):
h, w, k = map(int, raw_input().split())
mod = 1000000007

def check(s):
	for i in xrange(1, w):
		if (((s>>i)&1) and ((s>>(i-1))&1)):
			return False
	return True

dp = [[0] * 101 for _ in xrange(101)]

nxt = 0
dp[0][0] = 1;
for i in xrange(1, h+1):
	for pre in xrange(0, w):
		for mask in xrange(0, 1<<(w-1)):
			if check(mask):
				if (((1)&(mask>>pre)) == 1):
					nxt = pre + 1
				elif (pre > 0 and ((mask>>(pre-1))&1) == 1):
					nxt = pre - 1
				else:
					nxt = pre
				dp[i][nxt] += dp[i-1][pre]
				dp[i][nxt] %= mod

print dp[h][k-1]

Solution (Python):


MOD = 1000000007

pattern = [0] * 10
pattern[0] = 1
pattern[1] = 1
for i in xrange(2, 8 + 1):
    pattern[i] = pattern[i-1] + pattern[i-2]

def single_down(idx_from, idx_to, W):
    if idx_from == idx_to:
        return pattern[idx_from - 1] * pattern[W - idx_from]
    else:
        left = min(idx_from, idx_to) - 1
        right = W - max(idx_from, idx_to)
        return pattern[left] * pattern[right]

def main():
    H, W, K = map(int, raw_input().split(" "))

    ptn = [[0] * W]
    ptn[0][0] = 1
    for h in xrange(1, H + 1):
        ptn.append([])
        ptn[h] = [0] * W
        for w in xrange(0, W):
            ptn[h][w] = ptn[h-1][w] * single_down(w+1, w+1, W) % MOD
            if w > 0:
                ptn[h][w] += ptn[h-1][w-1] * single_down(w, w+1, W) % MOD
            if w < W-1:
                ptn[h][w] += ptn[h-1][w+1] * single_down(w+2, w+1, W) % MOD
            ptn[h][w] %= MOD

    print ptn[H][K-1]

if __name__ == '__main__':
    main()

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