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:
# https://misteer.hatenablog.com/entry/ABC113

MOD = 10 ** 9 + 7

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

K -= 1
# 以降縦棒の番号は0-indexedで扱う

dp = [[0 for _ in range(W)] for _ in range(H + 1)]
dp[0][0] = 1
# dp[h][k] = 横線h段からなるあみだくじで、0がkに来るものの数

for h in range(H):
    for b in range(1 << (W - 1)):
        if '11' in bin(b): continue

        perm = [i for i in range(W)]
        # 0-indexedの到達位置

        for i in range(W - 1):
            if (b >> i) & 1:
                perm[i], perm[i + 1] = perm[i + 1], perm[i]

        for i in range(W):
            dp[h + 1][perm[i]] += dp[h][i]
            dp[h + 1][perm[i]] %= MOD

print(dp[H][K])

Submission status: Accepted

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

for h in range(H):
  for b in range(1<<(W-1)):
    if "11" in bin(b):continue
    b<<=1
    for w in range(W):
      if b&(1<<w):
        dp[h+1][w]+=dp[h][w-1]
      elif b&(1<<(w+1)):
        dp[h+1][w]+=dp[h][w+1]
      else:
        dp[h+1][w]+=dp[h][w]
      dp[h+1][w]%=mod
    
print(dp[H][K-1]%mod)

Submission status: Accepted

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

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

dp[0][0] = 1

for i in range(1, H + 1):
    for j in range(W):
        for k in range(2 ** (W - 1)):
            if bin(k).count("11") >= 1:
                continue
            if j + 1 <= W - 1 and (k >> j) & 1:
                dp[i][j] += dp[i - 1][j + 1]
            elif j - 1 >= 0 and (k >> (j - 1)) & 1:
                dp[i][j] += dp[i - 1][j - 1]
            else:
                dp[i][j] += dp[i - 1][j]
        dp[i][j] %= (10 ** 9 + 7)
print(dp[H][K - 1] % (10 ** 9 + 7))

Submission status: Accepted

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

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

dp[0][0] = 1

for i in range(1, H + 1):
    for j in range(W):
        for k in range(2 ** (W - 1)):
            if bin(k).count("11") >= 1:
                continue
            if j + 1 <= W - 1 and (k >> j) & 1:
                dp[i][j] += dp[i - 1][j + 1]
            elif j - 1 >= 0 and (k >> (j - 1)) & 1:
                dp[i][j] += dp[i - 1][j - 1]
            else:
                dp[i][j] += dp[i - 1][j]

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

Submission status: Accepted

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

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


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

    return ret


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

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

Submission status: Accepted

Solution code:
MOD =  1000000007

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

cand = []
for bits in range(1 << (W-1)):
  s = "{:b}".format(bits) 
  if s.count('11') > 0: continue
  while len(s) < W-1:
    s = '0' + s
  cand.append(s)

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

for _ in range(H):
  ndp = [0] * W
  for c in cand:
    for i in range(W):
      if i+1 < W and c[i] == '1':
        ndp[i+1] += dp[i]
      elif i-1 >= 0 and c[i-1] == '1':
        ndp[i-1] += dp[i]
      else:
        ndp[i] += dp[i]
  dp = ndp
  for i in range(W):
    dp[i] %= MOD
print(dp[K-1])

Submission status: Accepted

Solution code:
h, w, K = map(int, input().split())
#h, w, K = 1, 3, 2
mod = 1000000007

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



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

Submission status: Accepted

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

for i in range(H):
    for b in range(1<<(W-1)):
        if '11' in bin(b):
            continue
        b <<= 1
        for k in range(W):
            if b & (1<<k):
                dp[i+1][k] += dp[i][k-1]
            elif b & (1<<(k+1)):
                dp[i+1][k] += dp[i][k+1]
            else:
                dp[i+1][k] += dp[i][k]
            dp[i+1][k] %= mod

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

Submission status: Accepted

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

# dp[i][j]:= 上からi番目, 左からj番目にいる通り数
dp = [[0] * W for i in range(H + 1)]
dp[0][0] = 1


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


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

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

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

        dp[i][j] = tmp

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

Submission status: Accepted

Solution code:
import numpy as np
MOD = 1000000007

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

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

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

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

Submission status: Accepted

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

row = [0, 1]
row_b = [0, 0]
for _ in range(W-1):
    temp = [i + j for i, j in zip(row, row_b)]
    row_b = row
    row = temp
    row.append(row[1])
    row_b.append(0)
row.append(0)
row_b.append(0)
# print(row, row_b)

a = {(0, i): 0 for i in range(W+2)}
a[(0, 1)] = 1
for h in range(1, H+1):
    for w in range(0, W+2):
        if w == 0 or w == W+1:
            a[(h, w)] = 0
        else:
            a[(h, w)] = row_b[w-1]*a[(h-1, w-1)] + row[w]*a[(h-1, w)] + row_b[w]*a[(h-1, w+1)]
        # print(f"({h}, {w}) {a[(h, w)]}")
print(a[(H, K)] % 1000000007)

Submission status: Accepted

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

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

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

print f[H][K]

Submission status: Accepted

Solution code:
def bin_cho(n):
    if n==1:
        return 2
    elif n<=0:
        return 1
    else:
        return bin_cho(n-2)+bin_cho(n-1)

h,w,k=map(int,input().split())
l=[[0]*w for _ in range(h+1)]
l[0][0]=1
for j in range(1,h+1):
    for i in range(w):
        l[j][i]+=l[j-1][i]*bin_cho(w-i-2)*bin_cho(i-1)
        if i-1>=0:
            l[j][i]+=l[j-1][i-1]*bin_cho(w-i-2)*bin_cho(i-2)
        if i+1<=w-1:
            l[j][i]+=l[j-1][i+1]*bin_cho(w-i-3)*bin_cho(i-1)
        l[j][i]%=10**9+7
print(l[h][k-1])

Submission status: Accepted

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

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


dp[0][1]=1


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

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

	#	print "h,s,dp,V::: ",h,s, dp,V
				

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

Submission status: Accepted

Solution code:
from functools import lru_cache

H, W, K = map(int, input().split())
def f(k):
  return 1 if k <= 0 else f(k-1) + f(k-2)
@lru_cache(maxsize=H*W)
def a(i, j):
  if j < 1 or j > W or (i == 0 and j != 1):
    return 0
  if i == 0 and j == 1:
    return 1
  return (f(j-3) * f(W-j-1) * a(i-1, j-1) + f(j-2) * f(W - j - 1) * a(i - 1, j) + f(j - 2) * f(W - j - 2) * a(i - 1, j + 1)) % 1000000007
ans = a(H, K)
print(ans)

Submission status: Accepted

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

ans = [0]*W
buf = [0]*W

fibonacci = [1]*(W+1)

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

ans[0] = 1

if W==1:
    print(1)
else:
    for i in range(H):
        buf[0] = ans[0]*fibonacci[W-1]+ans[1]*fibonacci[W-2]
        buf[W-1] = ans[W-1]*fibonacci[W-1]+ans[W-2]*fibonacci[W-2]
        for j in range(1, W-1):
            buf[j] = ans[j-1]*fibonacci[j-1]*fibonacci[W-j-1] + \
                ans[j]*fibonacci[j] * fibonacci[W-j-1] +\
                ans[j+1]*fibonacci[j]*fibonacci[W-j-2]

        for j in range(W):
            ans[j] = buf[j]%1000000007

    print(ans[K-1])

Submission status: Accepted

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

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

mod = int(1e9 + 7)

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

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

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

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

for i in range(H):
    dp2 = [0] * W
    for b in range(2**(W-1)):
        if '11' in bin(b): continue
        b *= 2
        for j in range(W):
            if b&(1<<j):
                dp2[j] += dp[j-1]
            elif b&(1<<(j+1)):
                dp2[j] += dp[j+1]
            else:
                dp2[j] += dp[j]
            dp2[j] %= MOD
    dp = dp2
print(dp[K-1])

Submission status: Accepted

Solution code:
def fib(W):
    a, b = 1, 1
    n = [a, b]
    while W > len(n):
        a, b = b, b + a
        n.append(b)
    return n
H, W, K = map(int, input().split())
f = fib(W)
r = [1] + [0] * (W - 1)
for i in range(H):
    tmp = [0] * W
    for j in range(W):
        if j == 0:
            tmp[j] = r[j] * f[W - j - 1] + r[j + 1] * f[W - j - 2] if W != 1 else 1
        elif j == W - 1:
            tmp[j] = r[j] * f[j] + r[j - 1] * f[j - 1]
        else:
            tmp[j] = r[j] * f[j] * f[W - j - 1] + r[j + 1] * f[W - j - 2] * f[j] + r[j - 1] * f[W - j - 1] * f[j - 1]
    r = tmp
print(r[K - 1] % 1000000007)

Submission status: Accepted

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

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

H, W, K = map(int, input().split())
# 0-indexed
K -= 1
MOD = 10 ** 9 + 7

dp = [[0] * W for i in range(H+1)]
# 縦棒の長さ0(つまり横棒なし)、一番左の棒を下りてくる1つ
dp[0][0] = 1

for h in range(1, H+1):
    # 縦棒間の数でビット全検索
    for b in range(1 << (W-1)):
        # 横棒が隣接していないチェック
        s = format(b, 'b')
        if s.count('11'):
            continue
        # ある始点の今回の移動先を保持する
        perm = [0] * W
        for i in range(W):
            perm[i] = i
        # 各縦棒間に横棒があるかループ
        for i in range(W-1):
            # あるビットが立っているかどうかで判別
            # (あみだが左始まりだから、ビットも左から始まってると思った方がイメージしやすいかも。
            # それかあみだが右から始まってると思うか。)
            if b >> i & 1:
                # 横棒があればひとつ先とスワップ
                perm[i], perm[i+1] = perm[i+1], perm[i]
        for i in range(W):
            # 前回のW-1ビット分を今回のW-1ビット分の回数足し合わせてくから、最終的に膨大になる
            dp[h][perm[i]] += dp[h-1][i]
            dp[h][perm[i]] %= MOD

print(dp[H][K])

Submission status: Accepted

Solution code:

def DP(H, W, K):
    res = [[0 for i in range(W)] for j in range(H+1)]
    res[0][0] += 1
    for step in range(1, H+1):
        for i in range(2**(W-1)):
            s = "{:08b}".format(i)[::-1]
#            print()
#            print(s)
            if '11' in s:
                continue
            for x in range(0, W):
                if x == 0:
                    if s[x] == '0':
                        res[step][x] += res[step-1][x]
                    elif s[x] == '1':
                        res[step][x+1] += res[step-1][x]
                elif x == W-1:
                    if s[x-1] == '0':
                        res[step][x] += res[step-1][x]
                    elif s[x-1] == '1':
                        res[step][x-1] += res[step-1][x]
                else:
                    # right
                    if s[x] == '0' and s[x-1] == '0':
                        res[step][x] += res[step-1][x]
                    elif s[x] == '1':
                        res[step][x+1] += res[step-1][x]
                    elif s[x-1] == '1':
                        res[step][x-1] += res[step-1][x]
#            print(res[step])
        for i in range(W):
            res[step][i] = res[step][i] % MOD
    return res[step][K-1]


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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import copy
H, W, K = map(int, input().split())

w_list = [None,1]

for i in range(W-1):
	w_list.append(0)

fibo = [1, 1, 2, 3, 5, 8, 13, 21]

if W>=2:
	for step in range(1,H+1):
		w_list_temp = copy.copy(w_list)
		# 1 or W
		w_list[1] = w_list_temp[1] * fibo[W-1] + w_list_temp[2] * fibo[W-2]
		w_list[W] = w_list_temp[W] * fibo[W-1] + w_list_temp[W-1] * fibo[W-2]
		for Ind in range(2,W):
			w_list[Ind] =  w_list_temp[Ind]   * fibo[Ind-1] * fibo[W-(Ind-1)-1] \
						 + w_list_temp[Ind-1] * fibo[Ind-2] * fibo[W-(Ind-1)-1] \
						 + w_list_temp[Ind+1] * fibo[Ind-1] * fibo[W-(Ind-1)-2]

print(w_list[K]%1000000007)

Submission status: Accepted

Solution code:
import itertools

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

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

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


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

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

Submission status: Accepted

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

if W == 1:
    print(1)

else:

    wnum = [0]*(W-1)
    for i in range(W-1):
        wsum = 0
        for j in range(2**(W-1)):
            bit = format(j, "0{}b".format(W-1))
            cc = 0
            for k in range(W-2):
                if bit[k] == "1" and bit[k + 1] == "1":
                    break
            else:
                if bit[i] == "1":
                    wnum[i] += 1
                wsum += 1

    dp = [[0]*W for i in range(H+1)]
    dp[0][0] = 1
    for i in range(H):
        for j in range(W):
            if 1 <= j <= W-2:
                dp[i+1][j] = dp[i][j-1] * wnum[j-1] + dp[i][j+1] * wnum[j] + dp[i][j] * (wsum-wnum[j-1]-wnum[j])
            elif j == 0:
                dp[i+1][j] = dp[i][j+1] * wnum[j] + dp[i][j] * (wsum-wnum[j])
            else:
                dp[i+1][j] = dp[i][j-1] * wnum[j-1] + dp[i][j] * (wsum-wnum[j-1])
            dp[i+1][j] = dp[i+1][j] % 1000000007
    print(dp[H][K-1])

Submission status: Accepted

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

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

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

Submission status: Accepted

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

# 高さiにおいて左からj番目の棒にいる通り数
dp = [[0] * W for i in range(H + 1)]
dp[0][0] = 1


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

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


for i in range(1, H + 1):
    for j in range(W):
        tmp = 0
        # 上からおりてくる
        tmp += dp[i - 1][j] * pattern(j - 1) * pattern(W - j - 2) % mod

        # 左からおりてくる
        if j > 0:
            tmp += dp[i - 1][j - 1] * pattern(j - 2) * pattern(W - j - 2) % mod

        # 右からおりてくる
        if j < W - 1:
            tmp += dp[i - 1][j + 1] * pattern(j - 1) * pattern(W - j - 3) % mod

        dp[i][j] += tmp

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

Submission status: Accepted

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

# 高さiにおいて左からj番目の棒にいる通り数
dp = [[0] * W for i in range(H + 1)]
dp[0][0] = 1


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

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


for i in range(1, H + 1):
    for j in range(W):
        tmp = 0
        # 上からおりてくる
        tmp = (tmp + dp[i - 1][j] * (pattern(j - 1) * pattern(W - j - 2))) % mod

        # 左からおりてくる
        if j > 0:
            tmp = (tmp + dp[i - 1][j - 1] * (pattern(j - 2) * pattern(W - j - 2))) % mod

        # 右からおりてくる
        if j < W - 1:
            tmp = (tmp + dp[i - 1][j + 1] * (pattern(j - 1) * pattern(W - j - 3))) % mod

        dp[i][j] += tmp

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

Submission status: Accepted

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
H,W,K = list(map(int, input().split() ))
mod = int(1e9+7) 
# mod = 1000000007



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


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

# disp(dp)

for i in range(H):
    for j in range(W):
        # disp(dp)
        for k in range((1<<W-1) ):
            # print("k = {}".format(bin(k)))
            ok = True
            for l in range(W-1):
                if (k&(1<<l)!=0) and (k&(1<<(l+1))!=0):
                    ok = False
            
            if ok:
                if j>0 and k&(1<<(j-1)): # to left
                    dp[i+1][j-1] += dp[i][j]
                    dp[i+1][j-1] %= mod
                    dp[i+1][j-1] = int(dp[i+1][j-1])

                elif j<W and k&(1<<(j)):   # to right
                    dp[i+1][j+1] += dp[i][j]
                    dp[i+1][j+1] %= mod
                    dp[i+1][j+1] = int(dp[i+1][j+1])
                else:
                    dp[i+1][j] += dp[i][j]
                    dp[i+1][j] %= mod
                    dp[i+1][j] = int(dp[i+1][j])
                # print("OK")
                
            else:
                continue

       

# print("last disp")
# disp(dp)
print(dp[H][K-1] % mod)
# print(mod)
# print(1000000007)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import copy
h, w, k = map(int, input().split())
ans = [0] + [1] + [0]*w
sequence_list = [1, 1, 2, 3, 5, 8, 13, 21, 34]
move_pattern = {}
for i in range(1, w+1):
  move_pattern[str(i)] = sequence_list[w-i]*sequence_list[i-1]
for i in range(1, w):
  move_pattern[i*11+1] = sequence_list[i-1]*sequence_list[w-i-1]
move_pattern[1] = 0
move_pattern[w*11+1] = 0
for _ in range(h):
  keep_ans = copy.deepcopy(ans)
  for i in range(1, w+1):
    ans[i] = keep_ans[i-1]*move_pattern[i*11-10] + keep_ans[i]*move_pattern[str(i)] + keep_ans[i+1]*move_pattern[i*11+1]
print(ans[k]%1000000007)

Submission status: Accepted

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

mod = 1000000007
fibonacci = [1,1,2,3,5,8,13,21]
Amida = [ [0] * W for h in range(H+1)]

for h in range(H+1):
    if W == 1:
        break
    for w in range(W):
        if h == 0:
            if w == 0:
                Amida[h][w] = 1
            else:
                break
        elif w == 0:
            Amida[h][w] = fibonacci[W-2] * Amida[h-1][w+1] + fibonacci[W-1] * Amida[h-1][w]
        elif w == W-1:
            Amida[h][w] = fibonacci[W-2] * Amida[h-1][w-1] + fibonacci[W-1] * Amida[h-1][w]
        else:
            Amida[h][w] += (fibonacci[w-1] * fibonacci[W-w-1] * Amida[h-1][w-1])
            Amida[h][w] += (fibonacci[w] * fibonacci[W-w-1] * Amida[h-1][w])
            Amida[h][w] += fibonacci[w] * fibonacci[W-w-2] * Amida[h-1][w+1]
        Amida[h][w] = Amida[h][w] % 1000000007

if W == 1:
    if K == 1:
        print(1)
    else:
        print(0)
else:
    print(Amida[H][K-1])

Submission status: Accepted

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

fibonacci = [1,1,2,3,5,8,13,21]

Amida = [ [0] * W for h in range(H+1)]

for h in range(H+1):
	if W == 1:
		break
	for w in range(W):
		if h == 0:
			if w == 0:
				Amida[h][w] = 1
			else:
				break
		elif w == 0:
			Amida[h][w] = fibonacci[W-2] * Amida[h-1][w+1] + fibonacci[W-1] * Amida[h-1][w]
		elif w == W-1:
			Amida[h][w] = fibonacci[W-2] * Amida[h-1][w-1] + fibonacci[W-1] * Amida[h-1][w]
		else:
			Amida[h][w] += (fibonacci[w-1] * fibonacci[W-w-1] * Amida[h-1][w-1])
			Amida[h][w] += (fibonacci[w] * fibonacci[W-w-1] * Amida[h-1][w])
			Amida[h][w] += fibonacci[w] * fibonacci[W-w-2] * Amida[h-1][w+1]

		Amida[h][w] = Amida[h][w] % 1000000007

if W == 1:
	if K == 1:
		print(1)
	else:
		print(0)
else:
	print(Amida[H][K-1])

Submission status: Accepted

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

mod = 1000000007

fibonacci = [1,1,2,3,5,8,13,21]

Amida = [ [0] * W for h in range(H+1)]

for h in range(H+1):
	if W == 1:
		break
	for w in range(W):
		if h == 0:
			if w == 0:
				Amida[h][w] = 1
			else:
				break
		elif w == 0:
			Amida[h][w] = fibonacci[W-2] * Amida[h-1][w+1] + fibonacci[W-1] * Amida[h-1][w]
		elif w == W-1:
			Amida[h][w] = fibonacci[W-2] * Amida[h-1][w-1] + fibonacci[W-1] * Amida[h-1][w]
		else:
			Amida[h][w] += (fibonacci[w-1] * fibonacci[W-w-1] * Amida[h-1][w-1])
			Amida[h][w] += (fibonacci[w] * fibonacci[W-w-1] * Amida[h-1][w])
			Amida[h][w] += fibonacci[w] * fibonacci[W-w-2] * Amida[h-1][w+1]

		Amida[h][w] = Amida[h][w] % mod

if W == 1:
	if K == 1:
		print(1)
	else:
		print(0)
else:
	print(Amida[H][K-1])

Submission status: Accepted

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

mod = 1000000007

fibonacci = [1,1,2,3,5,8,13,21] # W <= 8なのでこれだけでいい

Amida = [ [0] * W for h in range(H+1)]

for h in range(H+1):
	if W == 1:
		break
	for w in range(W):
		if h == 0:
			if w == 0:
				Amida[h][w] = 1
			else:
				break
		elif w == 0:
			Amida[h][w] = fibonacci[W-2] * Amida[h-1][w+1] + fibonacci[W-1] * Amida[h-1][w]
		elif w == W-1:
			Amida[h][w] = fibonacci[W-2] * Amida[h-1][w-1] + fibonacci[W-1] * Amida[h-1][w]
		else:
			Amida[h][w] += (fibonacci[w-1] * fibonacci[W-w-1] * Amida[h-1][w-1])
			Amida[h][w] += (fibonacci[w] * fibonacci[W-w-1] * Amida[h-1][w])
			Amida[h][w] += fibonacci[w] * fibonacci[W-w-2] * Amida[h-1][w+1]

		Amida[h][w] = Amida[h][w] % mod

if W == 1:
	if K == 1:
		print(1)
	else:
		print(0)
else:
	print(Amida[H][K-1])

Submission status: Accepted

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

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

fibonacci = [1,1,2,3,5,8,13,21] # W <= 8なのでこれだけでいい

Amida = [ [0] * W for h in range(H+1)]

for h in range(H+1):
	if W == 1:
		break
	for w in range(W):
		if h == 0:
			if w == 0:
				Amida[h][w] = 1
			else:
				break
		elif w == 0:
			Amida[h][w] = fibonacci[W-2] * Amida[h-1][w+1] + fibonacci[W-1] * Amida[h-1][w]
		elif w == W-1:
			Amida[h][w] = fibonacci[W-2] * Amida[h-1][w-1] + fibonacci[W-1] * Amida[h-1][w]
		else:
			Amida[h][w] += (fibonacci[w-1] * fibonacci[W-w-1] * Amida[h-1][w-1])
			Amida[h][w] += (fibonacci[w] * fibonacci[W-w-1] * Amida[h-1][w])
			Amida[h][w] += fibonacci[w] * fibonacci[W-w-2] * Amida[h-1][w+1]

		Amida[h][w] = Amida[h][w] % 1000000007

if W == 1:
	if K == 1:
		print(1)
	else:
		print(0)
else:
	print(Amida[H][K-1])

Submission status: Accepted

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

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

mod = 1000000007

fibonacci = [1,1,2,3,5,8,13,21] # W <= 8なのでこれだけでいい

Amida = [ [0] * W for h in range(H+1)]

for h in range(H+1):
	if W == 1:
		break
	for w in range(W):
		if h == 0:
			if w == 0:
				Amida[h][w] = 1
			else:
				break
		elif w == 0:
			Amida[h][w] = fibonacci[W-2] * Amida[h-1][w+1] + fibonacci[W-1] * Amida[h-1][w]
		elif w == W-1:
			Amida[h][w] = fibonacci[W-2] * Amida[h-1][w-1] + fibonacci[W-1] * Amida[h-1][w]
		else:
			Amida[h][w] += (fibonacci[w-1] * fibonacci[W-w-1] * Amida[h-1][w-1])
			Amida[h][w] += (fibonacci[w] * fibonacci[W-w-1] * Amida[h-1][w])
			Amida[h][w] += fibonacci[w] * fibonacci[W-w-2] * Amida[h-1][w+1]

		Amida[h][w] = Amida[h][w] % mod

if W == 1:
	if K == 1:
		print(1)
	else:
		print(0)
else:
	print(Amida[H][K-1])