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.



Sample input:
1 3 2


Sample output:
1

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10**5)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

h,w,k = li()
MOD = 10**9+7

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

nex_list = []
for i in range(1<<(w-1)):
    if not "11" in bin(i)[2:]:
        nex_list.append(i)
        
for hi in range(1,h+1):
    for bit in nex_list:
        changed = [0]*w

        for i, b in enumerate(bin(bit)[2:].zfill(w-1)):
            
            if b == "1":
                cnt[hi][i] += cnt[hi-1][i+1]
                cnt[hi][i+1] += cnt[hi-1][i]
                changed[i] = 1
                changed[i+1] = 1
        for j,c in enumerate(changed):
            if c == 0:
                cnt[hi][j] += cnt[hi-1][j]
                
    for wj in range(w):
        cnt[hi][wj] %= MOD
        
print(cnt[h][k-1])

Submission status: Accepted

Solution code:
def memoize(f):
    cache = {}
    def helper(*args):
        if args not in cache:
            cache[args] = f(*args)
        return cache[args]
    return helper

@memoize
def line_num(n):
    if n<=0:
        return 1
    elif n==1:
        return 2
    elif n==2:
        return 3
    else:
        return line_num(n-1) + line_num(n-2)

@memoize
def ans(h,w,k):
    if w==1:
        return 1
    elif h==1: # w>=2
        if k == 1:
            return line_num(w-2)
        elif k == 2:
            return line_num(w-3)
        else:
            return 0
    else:
        if k==1:
            return ans(h-1,w,k)*line_num(w-2) + ans(h-1,w,k+1)*line_num(w-3)
        elif k==w:
            return ans(h-1,w,k)*line_num(w-2) + ans(h-1,w,k-1)*line_num(w-3)
        else:
            a = ans(h-1,w,k)*(line_num(k-2)*line_num(w-k-1))
            b = ans(h-1,w,k-1)*(line_num(k-3)*line_num(w-k-1))
            c = ans(h-1,w,k+1)*(line_num(k-2)*line_num(w-k-2))
            return a+b+c

M = 1000000007

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

print(ans(h,w,k) % M)

Submission status: Accepted

Solution code:
import numpy as np

def getN():
    return int(input())


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


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

h, w, k = getList()
ns = [1,1,2,3,5,8,13,21]

trans = np.zeros([w,w], dtype=np.int64)
inipos = np.zeros([w], dtype=np.int64)
inipos[0] = 1
for i in range(w):
    trans[i][i] = ns[i] * ns[w-i-1]
    if i < w-1:
        trans[i][i+1] = ns[i] * ns[w-i-2]
    if i > 0:
        trans[i][i-1] = ns[i-1] * ns[w-i-1]

#print(inipos)
#print(trans)
for i in range(h):
    inipos = (np.dot(trans,inipos))
    #inipos = list(map(lambda x:x%1000000007, inipos))
    temp = [num % 1000000007 for num in inipos]
    inipos = temp

print(inipos[k-1])

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
lp = []
for i in range(pow(2, W-1)):
    if not(any((i >> j) & (i >> (j+1)) for j in range(W))):
        lp.append(i)
llp = len(lp)
d = [0] * W
for n in range(W):
    d[n] = len(list(filter(lambda x: (x >> n) & 1, lp)))

p =  1000000007
def gf_inv(n):
    return pow(n, p - 2, p)

dp = [[0] * 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] * (llp - d[w])
            if W != 1:
                dp[h][w] += dp[h-1][w+1] * d[w]
        elif w == W - 1:
            dp[h][w] = dp[h-1][w] * (llp - d[w-1]) + dp[h-1][w-1] * d[w-1]
        else:
            dp[h][w] = (
                    dp[h-1][w] * (llp - d[w-1] - d[w]) +
                    dp[h-1][w-1] * d[w-1] +
                    dp[h-1][w+1] * d[w]
            )
        dp[h][w] %= p
print(dp[H][K-1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import defaultdict
def inpl(): return list(map(int, input().split()))

MOD = 10**9 + 7

H, W, K = inpl()
cost = [[0]*(W) for _ in range(W)]

# 棒を移動するときの倍率
for i in range(W):
    for j in range(-1, 2):
        k = i + j
        if k < 0 or k >= W:
            continue
        q = [0] * (W-1) # "."*(W-1)
        if j == -1:
            if i > 0:
                q[i-1] = 1
            if i > 1:
                q[i-2] = 2
            if i < W - 1:
                q[i] = 2
        elif j == 0:
            if i > 0:
                q[i-1] = 2
            if i < W - 1:
                q[i] = 2
        else:
            if i < W - 1:
                q[i] = 1
            if i < W - 2:
                q[i+1] = 2
            if i > 0:
                q[i-1] = 2
        pattern = 0
        Q = [q*1]
        #print(i, k, j,  q)
        while Q:
            p = Q.pop()
            if not 0 in p:
                pattern += 1
                continue
            s = p.index(0)
            q = p*1
            q[s] = 2
            Q.append(q)
            p[s] = 1
            if s < W - 2:
                p[s+1] = 2
            Q.append(p)
        cost[i][k] = pattern

DP = [1] + [0]*(W-1)
for _ in range(H):
    DP2 = [0]*(W)
    for i in range(W):
        for j in range(max(0, i-1), min(W, i+2)):
            DP2[j] = (DP2[j] + (DP[i] * cost[i][j])%MOD)%MOD
    DP = DP2

print(DP2[K-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
MOD = 10**9+7
h, w, k = map(int, input().split())

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

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

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

for i in range(1, h+1):
    # most left
    dp[i][0] = (dp[i-1][0]*patterns[1:][w-2]%MOD + dp[i-1][1]*patterns[w-2]%MOD)%MOD
    for j in range(1, w-1):
        npath = dp[i-1][j-1]*(patterns[j-1]*patterns[1:][w-j-2])%MOD\
                + dp[i-1][j]*(patterns[1:][j-1]*patterns[1:][w-j-2])%MOD\
                + dp[i-1][j+1]*(patterns[1:][j-1]*patterns[w-j-2])%MOD
        dp[i][j] = npath%MOD
    dp[i][w-1] = (dp[i-1][w-2]*patterns[w-2]%MOD + dp[i-1][w-1]*patterns[1:][w-2]%MOD)%MOD

# for p in dp: print(p)

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

Submission status: Accepted

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

MOD = 10 ** 9 + 7

if w == 1:
    print(1)
    exit()
elif w == 2:
    print(2 ** (h - 1))
    exit()


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

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

def other(a, b):
    if b == 0:
        return br[a-1] * br[w-a-2]
    elif b == 1:
        if a == 1:
            return br[w-3]
        else:
            return br[a-2] * br[w-a-2]
    else:
        if a == w-2:
            return br[w-3]
        else:
            return br[j-1] * br[w-a-3]


k -= 1
dp[0][0] = 1

for i in range(1, h + 1):
    for j in range(1, w - 1):
        dp[i][j] = dp[i-1][j] * other(j, 0)
        dp[i][j] += dp[i-1][j-1] * other(j, 1)
        dp[i][j] += dp[i-1][j+1] * other(j, 2)
        dp[i][j] %= MOD
    dp[i][0] = dp[i-1][0] * br[w-2] + dp[i-1][1] * br[w-3]
    dp[i][0] %= MOD
    dp[i][w-1] = dp[i-1][w-1] * br[w-2] + dp[i-1][w-2] * br[w-3]
    dp[i][w-1] %= MOD

print(dp[h][k])

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
p = 10 ** 9 + 7
G = [[0 for j in range(W)] for i in range(W)]
for pat in range(2 ** (W - 1)):
  P = [0] * (W - 1)
  for i in range((W - 1)):
    P[i] = pat % 2
    pat //= 2
  for i in range(W - 2):
    if P[i] and P[i + 1]:
      break
  else:
    for i in range(W - 1):
      if P[i] == 1:
        G[i][i + 1] += 1
        G[i + 1][i] += 1
      else:
        if i == 0 or P[i - 1] == 0:
          G[i][i] += 1
        if i == W - 2:
          G[W - 1][W - 1] += 1
HG = [[G[i][j] for j in range(W)] for i in range(W)]
for h in range(H - 1):
  _HG = [[0 for j in range(W)] for i in range(W)]
  for i in range(W):
    for j in range(W):
      for k in range(W):
        _HG[i][j] += HG[i][k] * G[k][j]
      _HG[i][j] %= p
  HG = [[_HG[i][j] for j in range(W)] for i in range(W)]
print(HG[0][K - 1] if W > 1 else 1)

Submission status: Accepted

Solution code:
H, W, K = map( int, input().split())
C = [1, 1, 2, 3, 5, 8, 13, 21] #0に横棒が隣接している
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])

Submission status: Accepted

Solution code:
import math

def main():
    buf = input()
    buflist = buf.split()
    H = int(buflist[0])
    W = int(buflist[1])
    K = int(buflist[2]) - 1 # zero indexing

    pattern_list = []
    create_pattern(pattern_list, [], W-1, 0)
    prob = [1]
    for i in range(W-1):
        prob.append(0)
    for i in range(H):
        new_prob = []
        for j in range(W):
            new_prob.append(0)
        for j in range(W):
            for k in pattern_list:
                if j in k:
                    new_prob[j+1] += prob[j]
                elif j-1 in k:
                    new_prob[j-1] += prob[j]
                else:
                    new_prob[j] += prob[j]
        prob = list(new_prob)
    print(prob[K] % 1000000007)


def create_pattern(pattern_list, pattern, W, C):
    pattern_list.append(pattern)
    if len(pattern) == 0:
        for i in range(W):
            new_pattern = list(pattern)
            new_pattern.append(i)
            create_pattern(pattern_list, new_pattern, W, i)
    else:
        for i in range(C+2, W):
            new_pattern = list(pattern)
            new_pattern.append(i)
            create_pattern(pattern_list, new_pattern, W, i)


def nCr(n, r):
    f = math.factorial
    return f(n) // f(r) // f(n-r)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
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 = {} #d[h, s, g]
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])

Submission status: Accepted

Solution code:
h,w,k = (int(i) for i in input().split())
mod = 10**9+7
if w==1: print(1)
elif w==2: print((2**(h-1))%mod)
else:
	dp = [[0]*w for i in range(h+1)]
	dp[0][0],z = 1,[1,2,3,5,8,13,21]
	def f(x,a):
		if a==0:
			if x==0 or x==w-1: return z[w-2]
			else: return z[x-1]*z[w-x-2]
		elif a==1:
			if x==0: return 0
			elif x==w-1 or x==1: return z[w-3]
			else: return z[x-2]*z[w-x-2]
		else:
			if x==w-1: return 0
			elif x==0 or x==w-2: return z[w-3]
			else: return z[x-1]*z[max(0,w-x-3)]
	for i in range(h):
		for j in range(w):
			if j!=0 and j!=w-1: dp[i+1][j] = (dp[i][j]*f(j,0)+dp[i][j-1]*f(j,1)+dp[i][j+1]*f(j,2))%mod
			elif j==0: dp[i+1][j] = (dp[i][j]*f(j,0)+dp[i][j+1]*f(j,2))%mod
			else: dp[i+1][j] = (dp[i][j]*f(j,0)+dp[i][j-1]*f(j,1))%mod
	print(dp[-1][k-1])

Submission status: Accepted

Solution code:
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#

"""
abc113 D
"""

h, w, k = map(int, input().split())
cut = 10**9+7

if w == 1:
    if k == 1:
        print(1)
        exit()
    if k != 1:
        print(0)
        exit()

anslili = [[0]*(w+1) for i in range(h+1)]
anslili[0][1] = 1

amidahornot = [0, 1]
amidahorput = [0, 0]
for i in range(1, w+2):
    n, p = amidahornot[i], amidahorput[i]
    amidahornot.append(n+p)
    amidahorput.append(n)
amidahor = [amidahornot[i]+amidahorput[i] for i in range(w+2)]
amidahor[0] = 1

for y in range(1, h+1):
    anslili[y][1] = (anslili[y-1][1]*amidahor[w-1] + anslili[y-1][2] * amidahor[w-2]) % cut
    for x in range(2, w):
        anslili[y][x] = (anslili[y-1][x-1]*amidahor[x-2]*amidahor[w-x] + anslili[y-1][x+1]*amidahor[x-1]*amidahor[w-x-1] + anslili[y-1][x]*amidahor[x-1]*amidahor[w-x]) % cut
    anslili[y][w] = (anslili[y-1][w]*amidahor[w-1] + anslili[y-1][w-1] * amidahor[w-2]) % cut

print(anslili[h][k])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
H,W,K=map(int,input().split())#高さ,縦線,Kへたどり着く
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
#print(NOW)
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)

print(NOW[K]%mod)

Submission status: Accepted

Solution code:
H, W, K = [int(a) for a in input().split()]

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


pat_suc = [1] if W == 1 else [1] + [0 for i in range(W-1)]
for h in range(H):
    if h == H-1:
        if K == 0:
            if W > 1:
                ret = pat_suc[0] * fib[W - 1] + pat_suc[1] * fib[W - 2]
            else:
                ret = pat_suc[0] * fib[W - 1]
        elif W > 1 and K == W-1:
            ret = pat_suc[W-1] * fib[W - 1] + pat_suc[W-2] * fib[W - 2]
        else:
            ret = pat_suc[K] * fib[K] * fib[W-K-1] + pat_suc[K-1] * fib[K-1] * fib[W-K-1] + pat_suc[K+1] * fib[K] * fib[W-K-2]
    else:
        bef_suc = pat_suc
        if W == 1:
            continue
        elif W == 2:
            pat_suc = [sum(bef_suc), sum(bef_suc)]
        else:
            pat_suc = [bef_suc[0] * fib[W-1] + bef_suc[1] * fib[W-2]] + [bef_suc[i] * fib[i] * fib[W-i-2] + bef_suc[i+1] * fib[i+1] * fib[W-i-2] + bef_suc[i+2] * fib[i+1] * fib[W-i-3] for i in range(W-2)] + [bef_suc[W-1] * fib[W-1] + bef_suc[W-2] * fib[W-2]]
    pat_suc = [a % 1000000007 for a in pat_suc]


print(str(ret % 1000000007))

Submission status: Accepted

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


amida = [0 for i in range(8)]
amida[0]=1
amida[1]=2
amida[2]=3
amida[3]=5
amida[4]=8
amida[5]=13
amida[6]=21
amida[7]=34

def amida_num(k,l):
    return amida[max(k,0)]*amida[max(l,0)]


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

dp[0][0] = 1

if W!=1:
    for i in range(1,H+1):
        for j in range(W):
            if j==0:
                dp[i][j]=dp[i-1][j+1]*amida_num(0,W-3) + dp[i-1][j]* amida_num(0,W-2)
            elif j==W-1:
                dp[i][j]=dp[i-1][j-1]*amida_num(0,W-3) + dp[i-1][j]* amida_num(0,W-2)
            else:
                dp[i][j]=dp[i-1][j-1]*amida_num(j-2,W-j-2) + dp[i-1][j]*amida_num(j-1,W-j-2) + dp[i-1][j+1]*amida_num(j-1,W-j-3)
    print(dp[H][K-1]%(10**9+7))
else:
    print(1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
import itertools
import math

H,W,K=[int(x) for x in input().split()]

AtoB=[[0]*W for i in range(W)]

for bs in itertools.product(*([[True,False]]*(W-1))):
    if any(bs[i] and bs[i+1] for i in range(len(bs)-1)):
        continue
    for j in range(W):
        if j-1>=0 and bs[j-1]:
            AtoB[j][j-1]+=1
        elif j<W-1 and bs[j]:
            AtoB[j][j+1]+=1
        else:
            AtoB[j][j]+=1

c=[0]*W
c[0]=1
for k in range(H):
    newc=[0]*W
    for j in range(W):
        newc[j] = c[j] * AtoB[j][j]
        if j-1>=0:
            newc[j]+=c[j-1]*AtoB[j-1][j]
        if j<W-1:
            newc[j]+=c[j+1]*AtoB[j+1][j]
    c=newc

print(c[K-1] % 1000000007)

Submission status: Accepted

Solution code:
mod=1000000007
l=['0', '1', '10', '100', '101', '1000', '1001', '1010', '10000', '10001', '10010', '10100', '10101', '100000', '100001', '100010', '100100', '100101', '101000', '101001', '101010', '1000000', '1000001', '1000010', '1000100', '1000101', '1001000', '1001001', '1001010', '1010000', '1010001', '1010010', '1010100', '1010101']
s=input().split()
h,w,k=int(s[0]),int(s[1]),int(s[2])
res=[1]+[0]*(w-1)
for i in range(h):
    newres=[0]*w
    for s in l:
        if len(s)==w:
            break
        s="0"+"0"*(w-1-len(s))+s+"0"
        for i in range(w):
            if s[i]=="0" and s[i+1]=="0":
                newres[i]+=res[i]
                newres[i]%=mod
            elif s[i]=="0" and s[i+1]=="1":
                newres[i+1]+=res[i]
                newres[i+1]%=mod
            elif s[i]=="1" and s[i+1]=="0":
                newres[i-1]+=res[i]
                newres[i-1]%=mod
    res=newres
if w==1:
    print(1)
else:
    print(res[k-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
MODN = int(1e9+7)

# A[i][j] i=Hまでで、j=Kにいける通り数（MOD）
A = [[0] * (W+2) for i in range(H+1)]

A[0][1] = 1

# N本の縦棒にひとつの高さで引ける組み合わせ数
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])

Submission status: Accepted

Solution code:
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)
	print(dp[H][k-1])

Submission status: Accepted

Solution code:
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 edges in product((False,True),repeat=W-1):

  flag = False
  for e in edges:
    if flag and e:
      break
    flag = e
  else:
    flag = False

  if flag:
    continue

  memo = list(range(W))

  for i,e in enumerate(edges):
    if e:
      memo[i] = i+1
      memo[i+1] = i
  for i,j in enumerate(memo):
    transition[i][j] += 1


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


dp = np.zeros((W,1),dtype=np.int64)
dp[0,0] = 1

for h in range(H):
  dp = transition.dot(dp) % MOD

print(dp[K,0])

Submission status: Accepted

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


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


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

Submission status: Accepted

Solution code:
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 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[-1][K])

Submission status: Accepted

Solution code:
mod = 10**9 + 7

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

    if w == 1:
        return 1

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

    for i in range(h):
        nx = [0 for _ in range(w)]

        for mask in range(1<<(w-1)):
            bar = [0 for _ in range(w-1)]
            for j in range(w-1):
                bar[j] = (mask>>j&1)

            valid = True
            for j in range(w-2):
                if bar[j] == 1 and bar[j+1] == 1:
                    valid = False

            if not valid:
                continue

            for j in range(w):
                if j>0 and bar[j-1]:
                    nx[j-1] += dp[j]
                    nx[j-1] %= mod
                elif j+1<w and bar[j]:
                    nx[j+1] += dp[j]
                    nx[j+1] %= mod
                else:
                    nx[j] += dp[j]
                    nx[j] %= mod

        dp = nx

    return dp[k]

if __name__ == '__main__':
    print(main())

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18
MOD = 10 ** 9 + 7

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

DP = [0] * W
DP[K - 1] = 1
for i in range(H):
    DP_ = [0] * W
    for j in range(2 ** (W - 1)):
        B = [0] * (W - 1)
        ls = list(DP)
        for k in range(W - 1):
            if j & (1 << k):
                B[k] = 1
                hoge = ls[k]
                ls[k] = ls[k + 1]
                ls[k + 1] = hoge
        flag = False
        for k in range(W - 2):
            if B[k] and B[k + 1]:
                flag = True
        if flag:
            continue
        for k in range(W):
            DP_[k] += ls[k]
            DP_[k] %= MOD
    DP = DP_

print DP[0]

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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]

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

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

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

Submission status: Runtime Error

Solution code:
"""
memo1[i] => i列目とi+1列目の間に横棒があるような場合の数
memo2[i] => i列目の両サイドに横棒がないような場合の数
"""
if W == 1:
    print(1)
    exit()
H,W,K = map(int,input().split())
mod = 10**9 +7
memo1 = [0]*(W-1)
memo2 = [0]*W
for i in range(2**(W-1)):
    #bin(i)が横棒の配置パターンを表す
    binI = format(i,"0"+str(W-1)+"b")
    #パターンが正しいかを確かめる
    for j in range(W-2):
        if binI[j]=="1" and binI[j+1]=="1":
            break
    else:
        for j in range(W-1):
            if binI[j] == "1":
                memo1[j] += 1
        if binI[0] == "0":
            memo2[0] += 1
        if binI[-1] == "0":
            memo2[-1] += 1
        for j in range(1,W-1):
            if binI[j-1]=="0" and binI[j]=="0":
                memo2[j] += 1


#dp[i][j] => i回目の移動が終わったタイミングで、j列目にいるような場合の数
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]*memo2[j]
        dp[i+1][j] %= mod

        #右に移動する場合の数
        if j != W-1:
            dp[i+1][j+1] += dp[i][j]*memo1[j]
            dp[i+1][j+1] %= mod

        #左に移動する場合の数
        if j != 0:
            dp[i+1][j-1] += dp[i][j]*memo1[j-1]
            dp[i+1][j-1] %= mod

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