Problem:
 Score: 400 points    Problem Statement Amidakuji is a traditional method of lottery in Japan.  To make an amidakuji, we first draw W parallel vertical lines, and then draw horizontal lines that connect them. The length of each vertical line is H+1 [cm], and the endpoints of the horizontal lines must be at 1, 2, 3, ..., or H [cm] from the top of a vertical line.  A valid amidakuji is an amidakuji that satisfies the following conditions:   No two horizontal lines share an endpoint.  The two endpoints of each horizontal lines must be at the same height.  A horizontal line must connect adjacent vertical lines.    Find the number of the valid amidakuji that satisfy the following condition, modulo 1\ 000\ 000\ 007 : if we trace the path from the top of the leftmost vertical line to the bottom, always following horizontal lines when we encounter them, we reach the bottom of the K -th vertical line from the left.  For example, in the following amidakuji, we will reach the bottom of the fourth vertical line from the left.       Constraints  H is an integer between 1 and 100 (inclusive).  W is an integer between 1 and 8 (inclusive).  K is an integer between 1 and W (inclusive).         Input Input is given from Standard Input in the following format:  H  W  K       Output Print the number of the amidakuji that satisfy the condition, modulo 1\ 000\ 000\ 007 .        Sample Input 1 1 3 2      Sample Output 1 1  Only the following one amidakuji satisfies the condition:        Sample Input 2 1 3 1      Sample Output 2 2  Only the following two amidakuji satisfy the condition:        Sample Input 3 2 3 3      Sample Output 3 1  Only the following one amidakuji satisfies the condition:        Sample Input 4 2 3 1      Sample Output 4 5  Only the following five amidakuji satisfy the condition:        Sample Input 5 7 1 1      Sample Output 5 1  As there is only one vertical line, we cannot draw any horizontal lines. Thus, there is only one amidakuji that satisfies the condition: the amidakuji with no horizontal lines.       Sample Input 6 15 8 5      Sample Output 6 437760187  Be sure to print the answer modulo 1\ 000\ 000\ 007 .

Solution (Python):







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


'''
DP[i][j]...(0,i]まで考慮したときに、jにたどり着ける通りの数

更新則
if iにおいてjとj+1の間に横棒があったら
DP[i+1][j+1] += D[i][j]
DP[i+1][j] += D[i][j+1]
else
DP[i+1][j] = D[i][j]

for all paterns at i

初期条件
DP[i][j]=0
DP[0][0]=1
'''

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


def iter_p_adic(p, length):
    '''
    連続して増加するp進数をリストとして返す。lengthはリストの長さ
    return
    ----------
    所望のp進数リストを次々返してくれるiterator
    '''
    from itertools import product
    tmp = [range(p)] * length
    return product(*tmp)


def ret_valid_swapset():
    
    for p in iter_p_adic(2, W - 1):
        pre = 0
        skip = False
        for pp in p:
            if pre == 1 and pp == 1:
                skip = True
                break  
            pre = pp
        if skip:
            continue
        yield p


pattern = list(ret_valid_swapset())

DP = [[0] * W for _ in ra(H + 1)]
DP[0][0] = 1
for i in ra(H):
    for p in pattern:
        pre_is_swap = False
        for j, is_swap in enu(p):
            if is_swap:
                DP[i + 1][j + 1] += DP[i][j]
                DP[i + 1][j] += DP[i][j + 1]
            
            elif not pre_is_swap:
                DP[i + 1][j] += DP[i][j]
            pre_is_swap = is_swap
        if not pre_is_swap:  
            DP[i + 1][j + 1] += DP[i][j + 1]

            
    for j in ra(W):
        DP[i + 1][j] %= MOD
print(DP[H][K - 1])

Solution (Python):
from collections import defaultdict

H, W, K = map(int, input().split())
dp1 = [[0]*2 for _ in range(W)]
dp1[0][0] = 1

for i in range(W-1):
    dp1[i+1][0] = dp1[i][0]+dp1[i][1]
    dp1[i+1][1] = dp1[i][0]

d = defaultdict(int)
d[-1] = 1

for i in range(W):
    d[i] = dp1[i][0]+dp1[i][1]

dp2 = [[0]*W for _ in range(H+1)]
dp2[0][0] = 1
MOD = 10**9+7

for i in range(H):
    for j in range(W):
        for k in range(max(0, j-1), min(W-1, j+1)+1):
            l = min(j, k)-1
            r = W-2-max(j, k)
            dp2[i+1][k] += dp2[i][j]*d[l]*d[r]
            dp2[i+1][k] %= MOD

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

Solution (Python):
def isok(n):
    for i in range(w-2):
        if n >> i & 1 and n >> (i+1) & 1:
            return False
    return True
mod = 10**9+7
h,w,k = map(int,input().split())
h += 1
if w == 1:
    print(1)
    exit()
if w == 2:
    print(2**(h-2))
    exit()
dp = [[0]*(w+1) for _ in range(h+1)]
dp[1][1] = 1
amida = [0]*(w)
noamida = [0]*(w+1)
for i in range(2**(w-1)):
    if isok(i):
        for j in range(w-1):
            amida[j+1] += i >> j & 1
        for j in range(w-2):
            if i >> j & 1 == 0 and i >> (j+1) & 1 == 0:
                noamida[j+2] += 1
        if i >> 0 & 1 == 0:
                noamida[1] += 1
        if i >> (w-2) & 1 == 0:
                noamida[w] += 1
for i in range(1,h):
    dp[i+1][1] = (dp[i][2]*amida[1]+dp[i][1]*noamida[1]) % mod
    dp[i+1][w] = (dp[i][w-1]*amida[w-1]+dp[i][w]*noamida[w]) % mod
    for j in range(2,w):
        dp[i+1][j] = (dp[i][j-1]*amida[j-1]+dp[i][j+1]*amida[j]+dp[i][j]*noamida[j]) % mod
print(dp[h][k])

Solution (Python):
h,w,k = map(int,input().split())
k -= 1
dp = [[0]*w for _ in range(h+1)]
dp[0][0] = 1
mod = 10**9 + 7
def cnt(n):
    if n < 0:
        return 1
    if 0 <= n < 3:
        return n + 1
    return n + (n-1)*(n-2)//2 + (n-2)*(n-3)*(n-4)//6 + 1

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

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

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

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

for y in range(1, h+1):
    for i in range(2 ** (w-1)):
        bin_i = str(bin(i))[2:]
        if '11' in bin_i:
            continue
        for j in range(1, w):
            if ((i >> j-1) & 1):
                dp[y][j] += dp[y-1][j-1]
        for j in range(w-1):
            if ((i >> j) & 1):
                dp[y][j] += dp[y-1][j+1]
        for j in range(w):
            f = True
            if j < w:
                f = f and not ((i >> j) & 1)
            if j - 1 >= 0:
                f = f and not ((i >> j-1) & 1)
            if f:
                dp[y][j] += dp[y-1][j]
        for i in range(w):
            dp[y][i] %= MOD

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

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate, groupby
    
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    

    
    mod = 10**9 + 7

    h,w,k = map(int, input().split())
    dp = [[0]*w for _ in range(h+1)]
    dp[0][0] = 1

    pattern = []
    if w > 2:
        for i in range(1<<(w-1)):
            for j in range(w-2):
                if ((i>>j) & 1) and ((i>>(j+1)) & 1):
                    break
            else:
                pattern.append(i)
    else:
        print(1)
        exit()
    
    for i in range(h):
        for j in range(w):
            for p in pattern:
                if j == 0:
                    if p & 1:
                        dp[i+1][j+1] += dp[i][j] % mod
                    else:
                        dp[i+1][j] += dp[i][j] % mod
                elif j == w-1:
                    if (p>>(w-2)) & 1:
                        dp[i+1][j-1] += dp[i][j] % mod
                    else:
                        dp[i+1][j] += dp[i][j] % mod
                else:
                    if (p>>(j-1)) & 1:
                        dp[i+1][j-1] += dp[i][j] % mod
                    elif (p>>j) & 1:
                        dp[i+1][j+1] += dp[i][j] % mod
                    else:
                        dp[i+1][j] += dp[i][j] % mod
    print(dp[-1][k-1] % mod)


if __name__ == '__main__':
    main()

Solution (Python):


from copy import deepcopy
MOD = 10 ** 9 + 7

def main():
    h, w, k = map(int, input().split())
    ways = []
    for way in range(2 ** (w - 1)):
        if isvalid(way):
            ways.append(way)
    dp = [0 for i in range(w)]
    dp[0] = 1
    for i in range(h):
        dppre = deepcopy(dp)
        dp = [0 for i in range(w)]
        for j in range(w):
            for way in ways:
                dp[j] += dppre[apply(way, j)]
                dp[j] %= MOD
    print(dp[k - 1])

def apply(way, fr):
    logic = [False]
    for d in range(8):
        logic.append(bool(way & 1))
        way >>= 1
    if logic[fr]:
        to = fr - 1
    elif logic[fr + 1]:
        to = fr + 1
    else:
        to = fr
    return to

def isvalid(way):
    logic = []
    for d in range(7):
        logic.append(bool(way & 1))
        way >>= 1
    for d in range(6):
        if logic[d] & logic[d + 1]:
            return False
    return True

if __name__ == "__main__":
    main()

Solution (Python):
import sys
import math
import fractions
from collections import deque
from collections import defaultdict
sys.setrecursionlimit(10**7)

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

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


pattern = [0] * (W - 1)
total = 0
for i in range(2 ** (W - 1)):
    bit = format(i, 'b').zfill(W - 1)
    flag = True
    for j in range(W - 1):
        if j >= 1 and bit[j] == bit[j - 1] == "1":
            flag = False
    if flag:
        total += 1
        for j in range(W - 1):
            if bit[j] == "1":
                pattern[j] += 1

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

for i in range(1, H + 1):
    for j in range(W):
        if j == 0:
            dp[i][j] += dp[i - 1][j + 1] * pattern[j]
            dp[i][j] %= 1000000007
            dp[i][j] += dp[i - 1][j] * (total - pattern[j])
            dp[i][j] %= 1000000007
        elif j == W - 1:
            dp[i][j] += dp[i - 1][j - 1] * pattern[j - 1]
            dp[i][j] %= 1000000007
            dp[i][j] += dp[i - 1][j] * (total - pattern[j - 1])
            dp[i][j] %= 1000000007
        else:
            dp[i][j] += dp[i - 1][j + 1] * pattern[j]
            dp[i][j] %= 1000000007
            dp[i][j] += dp[i - 1][j - 1] * pattern[j - 1]
            dp[i][j] %= 1000000007
            dp[i][j] += dp[i - 1][j] * (total - pattern[j - 1] - pattern[j])
            dp[i][j] %= 1000000007

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

Solution (Python):





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

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



dp[0][1] = 1
mod=10**9+7
if w>1:
    for i in range(1,h+1):
        for j in range(2**(w-1)):
            st=format(j,"0%ib"%(w-1))
            flag=True
            for _ in range(w-2):
                if st[_]=="1" and st[_+1]=="1":
                    flag=False
            connect=[False for kyopuro in range(w+1)]
            if flag:
                li=[]
                for ss in range(w-1):
                    if st[ss]=="1":
                        li.append(ss+1)
                        connect[ss+1]=True
                        connect[ss+2]=True

                for some in li:
                    dp[i][some+1]+=dp[i-1][some]
                    dp[i][some+1]%=mod
                    dp[i][some]+=dp[i-1][some+1]
                    dp[i][some]%=mod
                for number in range(1,w+1):
                    if connect[number]==False:
                        dp[i][number]+=dp[i-1][number]
                        dp[i][number]%=mod
    print(dp[h][k]%mod)
                
        
else:
    print(1)

Solution (Python):
h,w,k=map(int,input().split())
mod=10**9+7
dp=[0]*w
dp[0]=1
fib=[1,1,2,3,5,8,13,21,34,55,89]
for _ in range(h):
  t=[0]*w
  for i in range(w):
    if i>0:
      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])

Solution (Python):
import sys
input = sys.stdin.readline
mod = 10**9 + 7

h, w, k = [int(x) for x in input().split()]

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

for i in range(h):
    for j in range(w):
        x = 0 
        y = 0 
        z = 0 
        for l in range(2**(w - 1)):
            l = bin(l)[2:].zfill(w - 1)
            if "11" in l:
                continue
            if j - 1 >= 0 and l[j - 1] == "1":
                y += 1
            elif j + 1 < w and l[j] == "1":
                x += 1
            else:
                z += 1
        if j + 1 < w:
            dp[i + 1][j + 1] += x * dp[i][j]
            dp[i + 1][j + 1] %= mod
        if j - 1 >= 0:
            dp[i + 1][j - 1] += y * dp[i][j]
            dp[i + 1][j - 1] %= mod
        dp[i + 1][j] += z * dp[i][j]
        dp[i + 1][j] %= mod

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

Solution (Python):
import sys
input = sys.stdin.readline
mod = 10**9 + 7

h, w, k = [int(x) for x in input().split()]

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

for i in range(h):
    for j in range(w):
        x = 0 
        y = 0 
        z = 0 
        for l in range(2**(w - 1)):
            l = bin(l)[2:].zfill(w - 1)
            if "11" in l:
                continue
            if j - 1 >= 0 and l[j - 1] == "1":
                y += 1
            elif j + 1 < w and l[j] == "1":
                x += 1
            else:
                z += 1
        if j + 1 < w:
            dp[i + 1][j + 1] += x * dp[i][j]
            dp[i + 1][j + 1] %= mod
        if j - 1 >= 0:
            dp[i + 1][j - 1] += y * dp[i][j]
            dp[i + 1][j - 1] %= mod
        dp[i + 1][j] += z * dp[i][j]
        dp[i + 1][j] %= mod

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

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

fibonacchi=[1 for i in range(0,W+1)]
for i in range(0,W+1):
    if i>=2:
        fibonacchi[i]=fibonacchi[i-1]+fibonacchi[i-2]

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

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

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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

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

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

d[0][0] = 1



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

ans = 0
for i in range(1,h+1):
    for j in range(w):
        if i+1 <= j: continue
        
        d[i][j] += d[i-1][j]*case[max(0,w-j-2)] * case[max(0,j-1)]%p
        
        if j-1>=0:
            d[i][j] += d[i-1][j-1]* case[max(0,w-j-2)] * case[max(0,j-2)]%p
        
        if j+1<=w:
            d[i][j] += d[i-1][j+1]* case[max(0,w-j-3)] * case[max(0,j-1)]%p

print(d[h][k-1]%p)

Solution (Python):





from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math
from fractions import gcd
import sys


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

for h in range(1,H+1):
    for i in range(2**(W-1)):
        
        lst=[i>>m&1 for m in range(W-1)]
        for w in range(len(lst)-1):
            if lst[w]==lst[w+1]==1:
                break
        else:
            
            for w in range(W):
                if w>0 and lst[w-1]:
                    dp[h][w]+=dp[h-1][w-1]
                elif w<len(lst) and lst[w]:
                    dp[h][w]+=dp[h-1][w+1]
                else:
                    dp[h][w]+=dp[h-1][w]
        for _ in range(len(dp[0])):
            dp[h][_]%=mod

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

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



kakekata = [[0] * 10] + [[0] * 10]
kakekata[0][0] = 1
for i in range(8):
    kakekata[0][i + 1] = kakekata[0][i] + kakekata[1][i]
    kakekata[1][i + 1] = kakekata[0][i]


MOD = 10 ** 9 + 7
class modint:
    def __init__(self, x):
        self.x = x.x if isinstance(x, modint) else x % MOD
    def __str__(self): return str(self.x)
    __repr__ = __str__
    def __int__(self): return self.x
    __index__ = __int__
    def __add__(self, other): return modint(self.x + modint(other).x)
    def __sub__(self, other): return modint(self.x - modint(other).x)
    def __mul__(self, other): return modint(self.x * modint(other).x)
    def __pow__(self, other): return modint(pow(self.x, modint(other).x, MOD))
    def __floordiv__(self, other): return modint(self.x * pow(modint(other).x, MOD - 2, MOD))
    def __eq__(self, other): return self.x == modint(other).x
    def __ne__(self, other): return self.x != modint(other).x
    def __inv__(self): return pow(self.x, MOD - 2, MOD)


dp = [[modint(0)] * (W + 2) for h in range(H + 1)]
dp[0][1] += 1
for h in range(H):
    for w in range(1, W + 1):
        
        l, r = w - 1, W - w

        
        dp[h + 1][w] += dp[h][w] * kakekata[0][l] * kakekata[0][r]
        
        dp[h + 1][w + 1] += dp[h][w] * kakekata[0][l] * kakekata[1][r]
        
        dp[h + 1][w - 1] += dp[h][w] * kakekata[1][l] * kakekata[0][r]

print(dp[H][K])

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

def check(bit):
  pre_b = '0'
  for b in bit:
    if b == '1' and pre_b == '1':
      return False
    pre_b = b
  return True


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


lines = [0] * (W+1)
c = 0
for i in range(2**(W-1)):
  if not check(bin(i)[2:]):
    continue
  c += 1
  for w in range(W-1):
    lines[w+1] += (i & 1<<w) > 0



for h in range(H):
  for w in range(1, W+1):
    x, z = lines[w-1], lines[w]
    y = c - x - z
    dp[h+1][w-1] = (dp[h+1][w-1] + dp[h][w]*x % MOD) % MOD
    dp[h+1][w] = (dp[h+1][w] + dp[h][w]*y % MOD) % MOD
    dp[h+1][w+1] = (dp[h+1][w+1] + dp[h][w]*z % MOD) % MOD

print(dp[-1][K])

Solution (Python):
H, W, K = [int(x) for x in input().split()]
p = 10 ** 9 + 7


h1amida = [1, 1, 2] + [None] * 6
for i in range(3, 9):
    h1amida[i] = h1amida[i - 2] + h1amida[i - 1]



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

for k in range(1, W + 1):
    if k == 1:
        dp[1][k] = h1amida[W - 1]
    elif k == 2:
        dp[1][k] = h1amida[W - 2]
    else:
        dp[1][k] = 0

for h in range(2, H + 1):
    for k in range(1, W + 1):
        if k > 1:
            dp[h][k] += (dp[h - 1][k - 1] * h1amida[k - 2] % p) * h1amida[W - k] % p
        dp[h][k] += (dp[h - 1][k] * h1amida[k - 1] % p) * h1amida[W - k] % p
        if k < W:
            dp[h][k] += (dp[h - 1][k + 1] * h1amida[k - 1] % p) * h1amida[W - k - 1] % p
        dp[h][k] %= p

print(dp[H][K])

Solution (Python):
import sys
input = sys.stdin.buffer.readline

def main():
    H,W,K = map(int,input().split())
    fib = [1,1,2,3,5,8,13,21,34]
    MOD = 10**9+7
    
    if W == 1:
        print(1)
    else:
        ans = [0 for _ in range(W)]
        ans[0] = 1
        for _ in range(H):
            use = [0 for _ in range(W)]
            for i in range(W):
                if i == 0:
                    use[i] = ans[i]*fib[W-1]+ans[i+1]*fib[W-2]
                elif i == W-1:
                    use[i] = ans[i]*fib[W-1]+ans[i-1]*fib[W-2]
                else:
                    use[i] = ans[i]*fib[i]*fib[W-i-1]+ans[i-1]*fib[i-1]*fib[W-i-1]+ans[i+1]*fib[i]*fib[W-i-2]
                use[i] %= MOD
            ans = use
        print(ans[K-1])
    
if __name__ == "__main__":
    main()

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

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

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

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

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

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

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

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

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

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

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

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

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

Solution (Python):

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


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)