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:
import sys
input=sys.stdin.readline
INF = 10**9
MOD = 10**9 + 7

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

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

    for i in range(h):
        for bit in range(1<<(w-1)):
            flag = False
            before = -2
            line = [0] * (w-1)
            for j in range(w-1):
                if (bit>>j)&1:
                    if  before + 1 == j:
                        flag = True
                        break
                    
                    else:
                        before = j
                        line[j] = 1
  

            if flag:
                continue

            j = 0
            while j < w:
                if j == w-1:
                    dp[i+1][j] += dp[i][j]
                    dp[i+1][j] %= MOD
                    break
                if line[j]:
                    dp[i+1][j] += dp[i][j+1]
                    dp[i+1][j] %= MOD
                    dp[i+1][j+1] += dp[i][j]
                    dp[i+1][j+1] %= MOD
                    j += 2
                else:
                    dp[i+1][j] += dp[i][j]
                    dp[i+1][j] %= MOD
                    j += 1

    print(dp[-1][k-1]%MOD)
if __name__=='__main__':
    main()

Submission status: Accepted

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

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

up = [0] * W
right = [0] * W
left = [0] * W

for b in range(1 << (W - 1)):
    bridge = bin(b)[2:].zfill(W - 1)
    if "11" in bridge:
        continue

    # 左の棒
    if bridge[0] == "0":
        up[0] += 1
    else:
        right[0] += 1

    # 右の棒
    if bridge[-1] == "0":
        up[W - 1] += 1
    else:
        left[W - 1] += 1

    # 真ん中
    for i in range(1, W - 1):
        if bridge[i - 1] == "0" and bridge[i] == "1":
            right[i] += 1
        elif bridge[i - 1] == "1" and bridge[i] == "0":
            left[i] += 1
        else:
            up[i] += 1

up = [0] + up + [0]
right = [0] + right + [0]
left = [0] + left + [0]

dp = [0] * (W + 2)
dp[K] = 1
for _ in range(H):
    newDP = [0] * (W + 2)
    for i in range(1, W + 1):
        newDP[i] += dp[i - 1] * right[i - 1]
        newDP[i] += dp[i] * up[i]
        newDP[i] += dp[i + 1] * left[i + 1]
        newDP[i] %= mod
    dp = newDP

ans = dp[1]
print(ans)

Submission status: Accepted

Solution code:
from itertools import product

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

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

pats = [pat for pat in product([1, 0], repeat=w-1)]

for i in range(1, h + 1):
	for j in range(w):
		for pat in pats:
			valid = True
			for e1, e2 in zip(pat, pat[1:]):
				if e1 and e2:
					valid = False

			if not valid:
				continue

			if j - 1 >= 0 and pat[j-1]:
				dp[i][j] += dp[i-1][j-1]

			elif j <= w - 2 and pat[j]:
				dp[i][j] += dp[i-1][j+1]

			else:
				dp[i][j] += dp[i-1][j]

			dp[i][j] %= mod

ans = dp[h][k-1]
print(ans)
#print(*dp, sep="\n")

Submission status: Accepted

Solution code:
from itertools import product

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

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

pats = [pat for pat in product([1, 0], repeat=w-1)]

for i in range(h):
	for j in range(w):
		for pat in pats:
			valid = True
			for e1, e2 in zip(pat, pat[1:]):
				if e1 and e2:
					valid = False

			if not valid:
				continue

			if j - 1 >= 0 and pat[j-1]:
				dp[i+1][j-1] += dp[i][j]
				dp[i+1][j-1] %= mod

			elif j <= w - 2 and pat[j]:
				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

ans = dp[h][k-1]
print(ans)
#print(*dp, sep="\n")

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
def main():
    H, W, K = map(int, input().split())
    u = [1] + [0] * (W - 1)
    mod = 10**9 + 7
    def cw(n):
        if n == 0:
            return 0
        if n == 1:
            return 2
        return cw(n - 2) + cw(n - 1) 
    CW = [1, 2, 3, 5, 8, 13, 21, 34, 55, 1, 1, 1]

    for _ in range(H):
        v = [0] * W
        for w in range(W):
            t = 0
            if w >= 1:
                t += u[w - 1] * CW[w - 2] * CW[W - w - 2]
            t += u[w] *     CW[w - 1] * CW[W - w - 2]
            if w < W - 1:
                t += u[w + 1] * CW[w - 1] * CW[W - w - 3]
            v[w] = t % mod
        u = v
    print(u[K - 1])

main()

Submission status: Accepted

Solution code:
from itertools import product
def main():
    h, w, k = map(int, input().split())
    dp = [[0 for j in range(w)] for i in range(h+1)]
    dp[0][0] = 1
    p = []
    for q in product(("-", " "), repeat=w-1):
        f = True
        for j in range(len(q)-1):
            if q[j] == "-" and q[j+1] == "-":
                f = False
        if f:
            p.append(q)
    MOD = 10**9 + 7
    for i in range(1, h+1):
        for q in p:
            for j in range(w):
                if 0 < j and q[j-1] == "-":
                    dp[i][j] += dp[i-1][j-1]
                    dp[i][j] %= MOD
                if j < w-1 and q[j] == "-":
                    dp[i][j] += dp[i-1][j+1]
                    dp[i][j] %= MOD
                if w == 1 or  (0 < j < w-1 and q[j-1] == " " and q[j] == " "):
                    dp[i][j] += dp[i-1][j]
                    dp[i][j] %= MOD
                elif j == 0 and 1 < w and q[j] == " ":
                    dp[i][j] += dp[i-1][j]
                    dp[i][j] %= MOD
                elif j == w-1 and 1 < w and q[j-1] == " ":
                    dp[i][j] += dp[i-1][j]
                    dp[i][j] %= MOD
    print(dp[h][k-1])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
h,w,k=map(int,input().split())
mod=10**9+7
if w==1:
  print(1)
  sys.exit()
b=[]
for i in range(2**(w-1)):
  b.append(format(i,'0'+str(w-1)+'b'))
l=[]
for i in range(len(b)):
  ct=0
  for j in range(w-2):
    if b[i][j]!='1' or b[i][j+1]!='1':
      ct+=1
  if ct==w-2:
    l.append(b[i])

count=[[0,0,0] for i in range(w)]
for i in range(len(l)):
  if l[i][0]=='0':
    count[0][1]+=1
  if l[i][0]=='1':
    count[0][2]+=1
  if l[i][-1]=='1':
    count[-1][0]+=1
  if l[i][-1]=='0':
    count[-1][1]+=1
  for j in range(w-2):
    if l[i][j:j+2]=='10':
      count[j+1][0]+=1
    if l[i][j:j+2]=='00':
      count[j+1][1]+=1
    if l[i][j:j+2]=='01':
      count[j+1][2]+=1

dp=[[0 for i in range(w)] for j in range(h+1)]
dp[0][0]=1
for i in range(h+1):
  for j in range(w):
    dp[i][j]+=dp[i-1][j]*count[j][1]
    dp[i][j]%=mod
    if j-1>=0:
      dp[i][j]+=dp[i-1][j-1]*count[j-1][2]
      dp[i][j]%=mod
    if j+1<=w-1:
      dp[i][j]+=dp[i-1][j+1]*count[j+1][0]
      dp[i][j]%=mod
print(dp[h][k-1]%mod)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

def f(n):
    if n<=1:
        return 1
    sm = 2
    for i in range(1,n-1):
        sm += f(n-i-1)
    #ddprint(f"f({n})={sm}")
    return sm

h,w,k = inm()
d = [[0]*(w+2) for i in range(h+1)]
d[0][1] = 1
for i in range(h):
    d[i][0] = d[i][w+1] = 0
    for j in range(1,w+1):
        x = d[i][j]
        #ddprint(f"i {i} j {j} 0inc {x*f(j-1)*f(w-j)}")
        #ddprint(f"i {i} j {j} minc {x*f(j-2)*f(w-j)}")
        #ddprint(f"i {i} j {j} pinc {x*f(j-1)*f(w-j-1)}")
        d[i+1][j] = (d[i+1][j]+x*f(j-1)*f(w-j))%R
        d[i+1][j-1] = (d[i+1][j-1]+x*f(j-2)*f(w-j))%R
        d[i+1][j+1] = (d[i+1][j+1]+x*f(j-1)*f(w-j-1))%R
if DBG:
    for i in range(h+1):
        print(d[i])
print(d[h][k])

Submission status: Accepted

Solution code:
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

H, W, K = lr()
MOD = 10 ** 9 + 7
dp = [[0] * W for _ in range(H+1)]
dp[0][0] = 1
ladder = [[0] * 2 for _ in range(15)] #あえて多めに用意
ladder[1][0] = 1
for i in range(2, 9):
    ladder[i][0] = ladder[i-1][0] + ladder[i-1][1]
    ladder[i][1] = ladder[i-1][0]

ladder = [max(1, x+y) for x, y in ladder]

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

print(dp[H][K-1] % MOD)
# 52

Submission status: Accepted

Solution code:
h,w,k = map(int, input().split())
mod = 10**9+7
row_amida = []
def make_amida(pre, li):
	if len(li) == w-1:
		row_amida.append(li)
	else:
		if pre == 0:
			make_amida(1, li + [1])
		make_amida(0, li + [0])
make_amida(0,[])
dp = [[0 for i in range(w+1)] for j in range(h+1)]
dp[0][1] = 1 #dp[i][j] := i行目まで決めたときのj列目にたどり着くあみだの本数
for i in range(1,h+1):
	for j in range(1,w+1):
		left_to_cur = 0
		up_to_cur = 0
		right_to_cur = 0
		for p in range(len(row_amida)):
			upflag = True
			if j != 1 and row_amida[p][j-2] == 1:
				left_to_cur += 1
				upflag = False
			if j != w and row_amida[p][j-1] == 1:
				right_to_cur += 1
				upflag = False
			if upflag:
				up_to_cur += 1
		if j != 1:
			left_to_cur = (left_to_cur * dp[i-1][j-1]) % mod
		if j != w:
			right_to_cur = (right_to_cur * dp[i-1][j+1]) % mod
		up_to_cur = (up_to_cur * dp[i-1][j]) % mod
		dp[i][j] = right_to_cur + left_to_cur + up_to_cur
		dp[i][j] %= mod
print(dp[-1][k])

Submission status: Accepted

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

valid_connections = []
for i in range(2 ** (w - 1)):
    if '11' not in bin(i):
        valid_connections.append(i)

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

for i in range(h):
    for j in range(w):
        for connection in valid_connections:
            if connection & (1 << j):
                dp[i + 1][j + 1] += dp[i][j]
                dp[i + 1][j + 1] %= MOD
            elif connection & (1 << max(j - 1, 0)):
                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])

Submission status: Accepted

Solution code:
#113_D
H,W,K=map(int,input().split())
K-=1
Mod=10**9+7

#row全探索
Row=[]
for i in range(2**(W-1)):
    row=[]
    flg=True
    for j in range(W-1):
        if j>0:
            if (i>>j)&1 and (i>>(j-1))&1:
                flg=False
        row.append((i>>j)&1)
    if flg:
        Row.append(row)
        
Count=[0 for _ in range(W-1)]
for row in Row:
    for i in range(W-1):
        Count[i]+=row[i]

dp=[[0 for _ in range(W)] for _ in range(H+1)]
dp[0][K]=1
if W==1:
    print(1)
    
else:
    for h in range(1,H+1):
        for x in range(W):
            if x==0:
                dp[h][x]=dp[h-1][x]*(len(Row)-Count[x])+dp[h-1][x+1]*Count[x]
            elif x==W-1:
                dp[h][x]=dp[h-1][x]*(len(Row)-Count[x-1])+dp[h-1][x-1]*Count[x-1]
            else:
                dp[h][x]=dp[h-1][x]*(len(Row)-Count[x]-Count[x-1])+dp[h-1][x+1]*Count[x]+dp[h-1][x-1]*Count[x-1]

    print(dp[H][0]%Mod)

Submission status: Accepted

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

fib = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
mod = 10 ** 9 + 7
'''
端にいてそのまま下にいくときfib[W+1]
端にいて右か左にいくときfib[W]
中にいて下に行くとき
'''
if W == 1:
    print(1)
    exit()

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] * fib[W - 1] + dp[h - 1][w + 1] * fib[W - 2]
        elif w == W - 1:
            dp[h][w] = dp[h - 1][w] * fib[W - 1] + dp[h - 1][w - 1] * fib[W - 2]
        else:
            dp[h][w] = dp[h - 1][w] * fib[w] * fib[W - 1 - w] + dp[h - 1][w + 1] * fib[W - w - 2] * fib[w] + dp[h - 1][
                w - 1] * fib[
                           w - 1] * fib[W - 1 - w]
        dp[h][w] %= mod

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

Submission status: Accepted

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

mod = 10**9+7
dp = [["0"]*(W+2) for _ in range(H+1)]
for h in range(H+1):
    dp[h][0] = 0
    dp[h][W+1] = 0
for w in range(W+2):
    dp[0][w] = 0
dp[0][1] = 1

cmb = [1, 2, 3, 5, 8, 13, 21, 34]
def f(h, w):
    if dp[h][w] != "0":
        return dp[h][w]
    dp[h][w] = 0
    dp[h][w] += f(h-1, w-1)*cmb[max(0, w-3)]*cmb[max(0, W-w-1)]
    dp[h][w] += f(h-1, w)*cmb[max(0, w-2)]*cmb[max(0, W-w-1)]
    dp[h][w] += f(h-1, w+1)*cmb[max(0, w-2)]*cmb[max(0, W-w-2)]
    dp[h][w] %= mod
    return dp[h][w]

print(f(H, K))

Submission status: Accepted

Solution code:
import itertools


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

DP = [0] * w
DP[0] = 1
mod = 10**9 + 7

patterns = []

for line_count in range(w):
    candidates = itertools.combinations(range(w-1), line_count)

    for pattern in candidates:
        usable = True
        prev = 10

        for num in pattern:
            if num == prev + 1:
                usable = False
                break
            else:
                prev = num

        if usable:
            patterns.append(pattern)

for i in range(h):
    next_DP = [0] * w

    for pattern in patterns:
        straight = set(range(w))
        for line in pattern:
            next_DP[line] += DP[line+1]
            next_DP[line] %= mod
            next_DP[line+1] += DP[line]
            next_DP[line+1] % mod
            straight.discard(line)
            straight.discard(line+1)

        for line in straight:
            next_DP[line] += DP[line]
            next_DP[line] %= mod

    DP = next_DP.copy()

ans = DP[k-1]
print(ans%mod)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7
fib = [1, 1, 2, 3, 5, 8, 13, 21, 34]

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

dp = [0] * W
dp[0] = 1

for _ in range(H):

    T = [0] * W

    for i in range(W):
        if 0 < i:
            T[i] += dp[i - 1] * fib[i - 1] * fib[W - i - 1]

        T[i] += dp[i] * fib[i] * fib[W - i - 1]

        if i < W - 1:
            T[i] += dp[i + 1] * fib[i] * fib[W - i - 2]

        T[i] %= mod

    dp = T

print(dp[K - 1])

Submission status: Accepted

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

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

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

for i in range(h):
    for j in range(w):
        for bit in range(1<<(w-1)):
            ok = True
            for _ in range(w-2):
                if not (bit + (bit<<1) == bit ^ (bit<<1)):
                    ok = False
            if not ok:
                continue
            ni = i+1; nj = j
            if (bit>>j) & 1:
                nj = j+1
            elif j > 0 and (bit>>(j-1)) & 1:
                nj = j-1
            dp[ni][nj] += dp[i][j]
            dp[ni][nj] %= MOD           

ans = dp[h][k]
ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9+7
h, w, K = map(int, input().split())
n = w-1
dp = [[0] * w for _ in range(h+1)]
dp[0][0] = 1

def judge(edge):
    for i in range(1, n):
        if edge[i] and edge[i-1]: return False
    return True

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

            dp[i][j] %= MOD

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

Submission status: Accepted

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

Submission status: Accepted

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

pat = set()


def make_pat(v):
    if v in pat: return
    a = v
    while a > 0:
        if a & 1 and a & 2:
            return
        a = a >> 1

    pat.add(v)
    for i in range(W - 1):
        a = 1 << i
        if a & v: continue
        make_pat(a | v)


make_pat(0)
# print(pat)

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

dp[0][0] = 1
MOD = 10 ** 9 + 7

for i in range(H):
    for line in pat:
        for j in range(W):
            # j 番目の棒を考える
            if line & (1 << j):  # 右側
                dp[i + 1][j + 1] += dp[i][j] % MOD
            elif j > 0 and line & (1 << (j - 1)):  # 左側
                dp[i + 1][j - 1] += dp[i][j] % MOD
            else:
                dp[i + 1][j] += dp[i][j] % MOD
print(dp[H][K - 1] % MOD)

Submission status: Accepted

Solution code:
# D - Number of Amidakuji

import itertools

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

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

# move[i][j] 左iから左jに移動できる横棒のパターン数
move = [[0]*W for _ in range(W)]
for horizontal_line_pattern in list(itertools.product([0,1], repeat=W-1)):
    for i in range(W-2):
        if horizontal_line_pattern[i] == 1 and horizontal_line_pattern[i+1] == 1:
            break
    else:
        for i in range(W-1):
            if horizontal_line_pattern[i] == 1:
                move[i][i+1] += 1
                move[i+1][i] += 1
            else:
                if i == 0:
                    move[0][0] += 1
                elif i == W-2:
                    move[W-1][W-1] += 1
                try:
                    if horizontal_line_pattern[i+1] == 0:
                        move[i+1][i+1] += 1
                except IndexError:
                    pass

# dp[i][j] 0段目左0から辿るとi段目の移動の後で左jに到達するようなアミダクジのパターン数
dp = [[0]*W for _ in range(H+1)]
dp[0][0] = 1

for i in range(1, H+1):
    for j in range(W):
        for k in [-1, 0, 1]:
            try:
                dp[i][j] += dp[i-1][j+k] * move[j][j+k]
                dp[i][j] %= MOD
            except IndexError:
                pass

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

Submission status: Accepted

Solution code:
#遅くなるけど実装や思考が楽?なパターン，各Hで2^7を試す

import itertools

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

#隣り合うとこ路に線を引く場合にfalse
def check(L):
    n=len(L)
    for i in range(1,n):
        if L[i]==1 and L[i-1]==1:
            return False
    return True
        


#高さiまででj番目の通り数
dp=[[0]*W for _ in range(H+1)]
dp[0][0]=1#高さ0では1に行けるのが1通り
mod=10**9+7

for i in range(H):
    for ite in itertools.product([0,1], repeat=(W-1)):
        ite=list(ite)
        ite.append(0)
        if check(ite):
            flag=0
            for j in range(W):
                if flag==1:
                    dp[i+1][j-1]+=dp[i][j]
                    dp[i+1][j-1]%=mod
                    flag=0
                elif ite[j]==1:
                    dp[i+1][j+1]+=dp[i][j]
                    dp[i+1][j+1]%=mod
                    flag=1
                else:
                    dp[i+1][j]+=dp[i][j]
                    dp[i+1][j]%=mod
                    
print(dp[-1][K-1])

Submission status: Accepted

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

#横棒設置可能箇所（目的とする縦棒に関与しない）がi本であるときに，横棒を置ける通り数
a=[1]*max((W-1),1)
for i in range(W-1):
    a[i]+=i#横線を1本引く
    if i-2>0:#2本引く
        a[i]+=((i-1)*(i-2))//2
        if i==5:#3本引く
            a[i]+=1
        elif i==6:#3本引く*4パターン
            a[i]+=4
    
mod=10**9+7    

#高さiまででj番目の通り数
dp=[[0]*W for _ in range(H+1)]
dp[0][0]=1#高さ0では1に行けるのが1通り

for i in range(H):
    for j in range(W):
        for k in range(-1,2,1):#両隣+自身
            if j+k>=0 and j+k<W:
                l=min(j,j+k)
                r=max(j,j+k)
                dp[i+1][j+k]+=dp[i][j]*a[max(0,l-1)]*a[max(0,(W-1)-r-1)]#通り数*左の冗長*右の冗長
                dp[i+1][j+k]%=mod
                
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()

root = []
for i in range(2 ** (W - 1)):
  flag = 1
  for j in range(1, W - 1):
    if ((i >> j) & 1) & (i >> (j - 1) & 1):
      flag = 0
      break
  if flag:
    root.append(i)

swap = [[j for j in range(W)] for _ in range(len(root))]
for i in range(len(root)):
  for j in range(W - 1):
    if (root[i] >> j) & 1:
      swap[i][j], swap[i][j + 1] =  swap[i][j + 1], swap[i][j]
#for i in range(len(root)):
#  print(swap[i])
  
dp = [[0 for _ in range(W)] for _ in range(H + 1)]
dp[0][0] = 1

for i in range(H):
  for s in swap:
    for j in range(W):
      dp[i + 1][s[j]] = (dp[i + 1][s[j]] + dp[i][j]) % MOD
#for i in range(H + 1):
#  print(dp[i])

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

Submission status: Accepted

Solution code:
def pow(x,m):
    if m==0:
        return 1
    if m==1:
        return x
    if m%2==0:
        return (pow(x,m//2)**2)%p
    else:
        return (x*(pow(x,(m-1)//2)**2)%p)%p
def V(n):
    if n<=0:return 1
    if n==1:return 2
    if n==2:return 3
    cnt = n+1
    for k in range(2,(n+1)//2+1):
        cnt = (cnt+((A[n-k+1]*B[k])%p*B[n-2*k+1])%p)%p
    return cnt
        
p = 10**9+7
H,W,K = map(int,input().split())
A = [1 for _ in range(W+1)]
for i in range(2,W+1):
    A[i] = (A[i-1]*i)%p
B = [1 for _ in range(W+1)]
B[W] = pow(A[W],p-2)
for i in range(W-1,1,-1):
    B[i] = ((i+1)*B[i+1])%p
dp = [[0 for _ in range(W+2)] for _ in range(H+1)]
dp[1][1] = V(W-2)
if W>=2:
    dp[1][2] = V(W-3)
for h in range(2,H+1):
    for k in range(1,W+1):
        dp[h][k] = ((dp[h-1][k-1]*V(k-3)*V(W-k-1))%p+(dp[h-1][k]*V(k-2)*V(W-k-1))%p+(dp[h-1][k+1]*V(k-2)*V(W-k-2))%p)%p
print(dp[H][K])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

for i in range(H):
    for j in range(W):
        dp[i][j] %= MOD
        here = dp[i][j]
        for d in range(2 ** (W - 1)):
            d = format(d, '0' + str(W - 1) + 'b')
            if not d.count('11'):
                if j == 0:
                    if d[j] == '1':
                        dp[i + 1][j + 1] += here
                    else:
                        dp[i + 1][j] += here
                elif j == W - 1:
                    if d[j - 1] == '1':
                        dp[i + 1][j - 1] += here
                    else:
                        dp[i + 1][j] += here
                else:
                    if d[j - 1] == '1':
                        dp[i + 1][j - 1] += here
                    elif d[j] == '1':
                        dp[i + 1][j + 1] += here
                    else:
                        dp[i + 1][j] += here

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

Submission status: Accepted

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

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

pat = [0] * W
for i in range(2 ** (W - 1)):
    j = bin(i)
    if not str(j).count('11'):
        pat[len(j) - 2] += 1
for i in range(W - 1):
    pat[i + 1] += pat[i]
pat[0] = 1

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

for i in range(H):
    for j in range(W):
        k = j + 1
        if k == 1:
            dp[i + 1][j] += dp[i][j] * pat[max(0, W - 1 - 1)]
            dp[i + 1][j] += dp[i][j + 1] * pat[max(0, W - 1 - 2)]
        elif 1 < k < W:
            dp[i + 1][j] += dp[i][j] * pat[max(0, j - 1)] * pat[max(0, W - k - 1)]
            dp[i + 1][j] += dp[i][j - 1] * pat[max(0, j - 2)] * pat[max(0, W - k - 1)]
            dp[i + 1][j] += dp[i][j + 1] * pat[max(0, j - 1)] * pat[max(0, W - k - 2)]
        else:
            dp[i + 1][j] += dp[i][j] * pat[max(0, W - 1 - 1)]
            dp[i + 1][j] += dp[i][j - 1] * pat[max(0, W - 1 - 2)]

        dp[i+ 1][j] %= MOD

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

Submission status: Accepted

Solution code:
MOD = 10**9+7

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

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

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

for i in range(1,H+1):
    for j in range(W):
        dp[i][j] += dp[i-1][j]*F[j]*F[W-j-1]
        if j != W-1:
            dp[i][j] += dp[i-1][j+1]*F[j]*F[W-j-2]
        if j != 0:
            dp[i][j] += dp[i-1][j-1]*F[j-1]*F[W-j-1]
        dp[i][j] %= MOD
        
print(dp[H][K-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def p_d():
    H, W, K = map(int, input().split())
    mod = 10 ** 9 + 7
    dp = [0] * W
    dp[0] = 1
    fib = [1, 1]
    for i in range(2, W):
        fib.append(fib[i - 2] + fib[i - 1])
    some = [0] * W
    for i in range(W):
        some[i] = fib[i] * fib[W - i - 1]
    some_2 = [0] * (W - 1)
    for i in range(W - 1):
        some_2[i] = fib[i] * fib[W - i - 2]
    for i in range(1, H + 1):
        w = 0
        NEXT = [0] * W
        for j in range(W):
            if j > 0:
                NEXT[j - 1] += dp[j] * some_2[j - 1]
                NEXT[j - 1] %= mod
            if j < W - 1:
                NEXT[j + 1] += dp[j] * some_2[j]
                NEXT[j + 1] %= mod
            if dp[j] > 0:
                NEXT[j] += dp[j] * some[j]
                NEXT[j] %= mod
            w += 1
        dp = NEXT
    print(dp[K - 1] % mod)


if __name__ == '__main__':
    p_d()

Submission status: Accepted

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