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

Solution (Python):

import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    H,W,K=map(int,input().split())
    dpdp=[[0]*2 for _ in range(W)]
    dpdp[0][0]=1
    for i in range(W-1):
        dpdp[i+1][0]=dpdp[i][0]+dpdp[i][1]
        dpdp[i+1][1]=dpdp[i][0]
    
    dp=[[0]*W for _ in range(H+1)]
    dp[0][0]=1
    for i in range(H):
        for j in range(W):
            if j==0 or j==W-1:
                dp[i+1][j]+=dp[i][j]*(sum(dpdp[W-2]))
            else:
                dp[i+1][j]+=dp[i][j]*(sum(dpdp[max(j-1,0)])*sum(dpdp[max(W-2-j,0)]))
            dp[i+1][j]%=MOD
            if j<=W-2:
                dp[i+1][j+1]+=dp[i][j]*(sum(dpdp[max(j-1,0)])*sum(dpdp[max(W-3-j,0)]))
                dp[i+1][j+1]%=MOD
            if j>=1:
                dp[i+1][j-1]+=dp[i][j]*(sum(dpdp[max(j-2,0)])*sum(dpdp[max(W-2-j,0)]))
                dp[i+1][j-1]%=MOD
    print(dp[-1][K-1])

if __name__ == '__main__':
    main()

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

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

for i in range(1, h+1):
    for j in range(w):
        left, center, right = 0, 0, 0

        for k in range(2**(w-1)):
            invalid = False
            for l in range(1, w-1):
                if k >> l & 1 and k >> (l-1) & 1:
                    invalid = True

            if invalid:
                continue

            no_line = True

            if j > 0:
                if k >> (j-1) & 1:
                    left += 1
                    no_line = False

            if j < w-1:
                if k >> j & 1:
                    right += 1
                    no_line = False

            if no_line:
                center += 1

        if j > 0:
            dp[i][j] += dp[i-1][j-1] * left

        if j < w-1:
            dp[i][j] += dp[i-1][j+1] * right

        dp[i][j] += dp[i-1][j] * center
        dp[i][j] %= mod

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

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

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

possible = []
for i in range(1<<(W-1)):
  b = bin(i)[2:]
  flag = 1
  for j in range(len(b)-1):
    if b[j] == b[j+1] == "1":
      flag = 0
  if flag:
    possible.append(int(b,2))

def amida(b):
  ret = [i for i in range(W)]
  for i in range(W-1):
    if b>>i & 1:
      ret[i],ret[i+1] = ret[i+1],ret[i]
  return ret

ans = [0 for i in range(W)]
ans[0] = 1

for _ in range(H):
  new_ans = [0 for i in range(W)]
  for b in possible:
    for i in range(W):
      new_ans[i] = (new_ans[i] + ans[amida(b)[i]])%MOD
  ans = new_ans
  
print(ans[K-1])

Solution (Python):






import sys
input = sys.stdin.readline

import math
import bisect
from collections import deque
from fractions import gcd
from functools import lru_cache






MOD = 10**9+7
INF = float('inf')






def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr


def lcm(a, b):
    return a * b // gcd (a, b)


def bit_count(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count





H,W,K = inputIL()

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

possible = []
for i in range(1<<(W-1)):
  b = bin(i)[2:]
  flag = 1
  for j in range(len(b)-1):
    if b[j] == b[j+1] == "1":
      flag = 0
  if flag:
    possible.append(int(b,2))

def amida(b):
  ret = [i for i in range(W)]
  for i in range(W-1):
    if b>>i & 1:
      ret[i],ret[i+1] = ret[i+1],ret[i]
  return ret

ans = [0 for i in range(W)]
ans[0] = 1


for _ in range(H):
  new_ans = [0 for i in range(W)]
  for b in possible:
    for i in range(W):
      new_ans[i] = (new_ans[i] + ans[amida(b)[i]])%MOD
  ans = new_ans
  
print(ans[K-1])

Solution (Python):
H, W, K = map(int, input().split())
mod = 1000000007
K -= 1

Hikikata = [1] * (W + 10)
Hikikata[0] = 1
Hikikata[1] = 2
for i in range(2, W+1):
    Hikikata[i] = Hikikata[i-1] + Hikikata[i-2]
    Hikikata[i] %= mod

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

DP[0][K] = 1
for i in range(1, H + 1):
    for j in range(W):
        DP[i][j] = DP[i-1][j] * (Hikikata[j-1] * Hikikata[W-j-2]) % mod + DP[i-1][j-1] * (Hikikata[j-2] * Hikikata[W-j-2]) % mod + DP[i-1][j+1] * (Hikikata[j-1] * Hikikata[W-j-3]) % mod
        DP[i][j] %= mod

print(DP[H][0])

Solution (Python):
import sys

def comb(n, r, mod=None):
    if r == 0 or r == n:
        return 1
    r = min([r, n-r])
    x, y = 1, 1
    ans = 1
    for i in range(1, r+1):
        if mod:
            x *= n+1-i
            y *= i
            x %= mod
            y %= mod
        else:
            ans *= n+1-i
            ans //= i
    ans = x*pow(y, mod-2, mod)%mod if mod else ans
    return ans


def main():
    h, w, k = map(int, input().split())
    mod = pow(10,9)+7
    
    if w == 1:
        print(1)
        sys.exit()
    
    comb_list = [[0]*11 for _ in range(11)]
    for i in range(11):
        for j in range(11):
            if i >= j:
                comb_list[i][j] = comb(i, j)
    
    key_list = [1]*10
    for i in range(1, 10):
        key = 0
        for j in range(1, 10):
            if i < j*2-1:
                break
            key += comb_list[i-j+1][j]
        key_list[i] += key
    
    
    dp = [[0]*w for _ in range(h)]
    for i in range(h):
        if i == 0:
            dp[0][0] = key_list[w-2]
            dp[0][1] = key_list[w-3] if w != 2 else 1
            continue
        if w == 2:
            dp[i][0] = (dp[i-1][0]+dp[i-1][1])%mod
            dp[i][1] = (dp[i-1][0]+dp[i-1][1])%mod
            continue
            
        for j in range(w):
            if j == 0:
                dp[i][j] = (dp[i-1][j]*key_list[w-2]+dp[i-1][j+1]*key_list[w-3])%mod
            elif j == w-1:
                dp[i][j] = (dp[i-1][j]*key_list[w-2]+dp[i-1][j-1]*key_list[w-3])%mod
            else:
                dp[i][j] = 0
                dp[i][j] += (dp[i-1][j-1]*key_list[max([0, j-2])]*key_list[max([0, w-2-j])])%mod
                dp[i][j] += (dp[i-1][j]*key_list[max([0, j-1])]*key_list[max([0, w-2-j])])%mod
                dp[i][j] += (dp[i-1][j+1]*key_list[max([0, j-1])]*key_list[max([0, w-3-j])])%mod
                dp[i][j] %= mod
    print(dp[h-1][k-1])
                                                                           

if __name__ == "__main__":
    main()

Solution (Python):
import itertools


def amida_patterns(w):
    
    ret = list()
    for bars in itertools.product([0, 1], repeat=w-1):
        if sum([b * bb for b, bb in zip(bars[1:], bars[:-1])]) > 0:
            continue
        location = list(range(w))
        for i in range(w):
            if i > 0 and bars[i - 1] == 1:
                location[i] = i - 1
            elif i < w - 1 and bars[i] == 1:
                location[i] = i + 1
        ret.append(location)
    return ret


def main():
    MOD = 10**9 + 7
    H, W, K = list(map(int, input().split(' ')))
    ap_list = amida_patterns(W)
    dp = [[0 for _ in range(W)] for _ in range(H + 1)]
    dp[0][0] = 1
    for h in range(1, H + 1):
        for a in ap_list:
            for w in range(W):
                dp[h][a[w]] += dp[h - 1][w]
                dp[h][a[w]] %= MOD
    print(dp[H][K - 1])


if __name__ == '__main__':
    main()

Solution (Python):
from itertools import product

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

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


def check_valid_bridge(bridge):
    for i in range(1, w-1):
        if bridge[i-1] and bridge[i]:
            return False
    return True

for t in range(1, h + 1):
    for i in range(1, w + 1):
        X, Y, Z = 0, 0, 0
        if w != 1:
            p = product([True, False], repeat=w-1)            
            for bridge in p:
                if check_valid_bridge(bridge):
                    if i > 1 and bridge[i-2]:
                        X += 1
                    elif i < w and bridge[i-1]:
                        Y += 1
                    elif (i == 1 and not bridge[i-1]) or (i == w and not bridge[i-2]) or (1 < i < w and not bridge[i-2] and not bridge[i-1]):
                        Z += 1
        else:
            Z = 1
        
        pattern_1 = dp[t-1][i-1] * X if i > 1 else 0
        pattern_2 = dp[t-1][i+1] * Y if i < w else 0
        pattern_3 = dp[t-1][i] * Z
        dp[t][i] = (pattern_1 + pattern_2 + pattern_3) % mod



print(dp[h][k])

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

def main():
    H, W, K = map(int, readline().rstrip().split())
    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 k in range(2**(W-1)):
                b = bin(k)[2:].zfill(W-1)
                
                flg = True
                for l in range(W-2):
                    if b[l] == b[l+1] == '1':
                        flg = False
                        break
                if not flg:
                    continue
                if j >= 1 and b[j-1] == '1':
                    
                    dp[i+1][j-1] += dp[i][j]
                    dp[i+1][j-1] %= MOD
                elif j <= W-2 and b[j] == '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])
    

if __name__ == '__main__':
    main()

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

def main():
    H, W, K = map(int, readline().rstrip().split())
    
    dp = [[0] * W for _ in range(H+1)]
    dp[0][0] = 1
    for i in range(H):
        for j in range(W):
            for k in range(2**(W-1)):
                b = bin(k)[2:].zfill(W-1)
                
                flg = True
                for l in range(W-2):
                    if b[l] == b[l+1] == '1':
                        flg = False
                        break
                if not flg:
                    continue
                if j >= 1 and b[j-1] == '1':
                    
                    dp[i+1][j-1] += dp[i][j]
                    dp[i+1][j-1] %= MOD
                elif j <= W-2 and b[j] == '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])
    

if __name__ == '__main__':
    main()

Solution (Python):
inf = 10**15
mod = 10**9+7

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

dp = [[0 for j in range(w+1)]for i in range(h+1)]
dp[0][1] = 1
for i in range(h):
    for x in range(2**(w-1)):
        flag = True
        count = 0
        tmp = x
        for l in range(w-1):
            if ((tmp >> l) & 1):
                count+=1
                if count == 2:
                    flag = False
            else:
                count=0
        if flag:
            zeroflag = True
            for j,y in enumerate(range(w-1)):
                if ((x >> y) & 1):  
                    dp[i+1][j+1] += dp[i][j+2]
                    dp[i+1][j+2] += dp[i][j+1]
                    zeroflag = False
                else:
                    if zeroflag:
                        dp[i+1][j+1] += dp[i][j+1]
                    else:
                        zeroflag = True
            if zeroflag:
                dp[i+1][-1] += dp[i][-1]
    for g in range(1,w+1):
        dp[i+1][g] = dp[i+1][g] % mod
print(dp[h][k])

Solution (Python):
fib = [1, 1, 2, 3, 5, 8, 13, 21]
mod = 1000000007
h, w, k = map(int, input().split())
k -= 1
p = [0] * w
p[0] = 1
for i in range(h):
  q = [0] * w
  for j in range(w):
    if j > 0:
      q[j] += p[j - 1] * fib[j - 1] * fib[w - 1 - j]
    if j < w - 1:
      q[j] += p[j + 1] * fib[j] * fib[w - j - 2]
    if 0 < j < w - 1:
      q[j] += p[j] * fib[j] * fib[w - j - 1]
    elif j > 0:
      q[j] += p[j] * fib[j]
    elif j < w - 1:
      q[j] += p[j] * fib[w - j - 1]
    else:
      q[j] += p[j]
    q[j] %= mod
  p = q
print(p[k])

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

p=[-1]*(w+1)
p[0]=1
p[1]=2
def pat(x):
    if x<0 or x>=w:
        return 1
    else:
        if p[x]!=-1:
            return p[x]
        else:
            p[x]=pat(x-2)+pat(x-1)
            return p[x]
        
for j in range(1):
    0
mo=10**9 +7

a=[[0 for i in range(w)] for i in range(h+1)]
a[0]=[1]+[0]*(w-1)
for i in range(1,h+1):
    
    
    for j in range(0,w):
        if j>0: a[i][j]+=a[i-1][j-1]*pat(j-2)*pat(w-j-2)
        a[i][j]+=a[i-1][j]*pat(j-1)*pat(w-1-j-1)
        if j<w-1: a[i][j]+=a[i-1][j+1]*pat(j-1)*pat(w-j-3)
print(a[h][k-1] % mo)

Solution (Python):
H, W, K = map(int, input().split())
h_lines = (1, 1, 2, 3, 5, 8, 13, 21, 34)
MOD = 10 ** 9 + 7

dp = [[0] * 8 for _ in range(H + 1)]
dp[0][0] = 1
for h in range(H):
    for w in range(W):
        dp[h + 1][w] = dp[h][w] * h_lines[w] * h_lines[W - w - 1]
        if w > 0:
            dp[h + 1][w] += dp[h][w - 1] * h_lines[w - 1] * h_lines[W - w - 1]
        if w < W - 1:
            dp[h + 1][w] += dp[h][w + 1] * h_lines[w] * h_lines[W - w - 2]
        dp[h + 1][w] %= MOD
print(dp[H][K - 1])

Solution (Python):

from itertools import product
import sys

try:
    from typing import List, Tuple
except ImportError:
    pass


MOD = 1000000007  


def isvalid(ptn: "Tuple[bool]"):
    return not any(h1 and h2 for h1, h2 in zip(ptn, ptn[1:]))


def solve(H: int, W: int, K: int):
    validptns = [
        ptn
        for ptn in product((False, True), repeat=W - 1)
        if isvalid(ptn)
    ]  
    dp = [1 if i == K - 1 else 0 for i in range(W)]  
    for _ in range(H):
        newdp = [0] * W  
        for ptn in validptns:
            for s in range(W):
                t = s
                if s < W - 1 and ptn[s]:
                    t = s + 1
                elif s > 0 and ptn[s - 1]:
                    t = s - 1
                newdp[t] += dp[s]
                newdp[t] %= MOD
        dp = newdp

    print(dp[0])


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  
    W = int(next(tokens))  
    K = int(next(tokens))  
    solve(H, W, K)


if __name__ == '__main__':
    main()

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


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

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

dp[0][0]=1


zentan1=[0]*(w-1)
zentan2=[0]*(w)

for i in range(2**(w-1)):
    if "11" not in str(bin(i)):
        
        s=(str(bin(i))[2:]).zfill(w-1)
        for index,ss in enumerate(s):        
            
            if ss=="1":
                zentan1[index]+=1
            else:
                if index==0:
                    zentan2[index]+=1
                elif index==len(s)-1:
                    zentan2[index+1]+=1
                    if s[index-1]=="0":
                        zentan2[index]+=1
                else:
                    if s[index-1]=="0":
                        zentan2[index]+=1
        
        






        """
        j=0
        while j<w-1:
            
            if i>>j & 1:
                
                zentan1[j]+=1
            j+=1
        """




for i in range(1,h+1):
    x=0
    while x<w:
        for index,mv in enumerate([-1,0,1]):
            if 0<= x+mv < w:
                if index==1:
                    dp[i][x]+=dp[i-1][x+mv]*zentan2[x]
                elif index==0:
                    dp[i][x]+=dp[i-1][x+mv]*zentan1[x-1]
                elif index==2:
                    dp[i][x]+=dp[i-1][x+mv]*zentan1[x]

        x+=1
    
print(dp[h][k-1]%MOD)

Solution (Python):
import sys

input = sys.stdin.readline


def main():
    H, W, K = [int(x) for x in input().split()]
    MOD = 10 ** 9 + 7

    if W == 1:
        print(1)
        return

    cnt = [0] * (W - 1)
    cntz = [0] * W
    for i in range(2 ** (W - 1)):
        tmp = [0] * (W - 1)
        for j in range(W - 1):
            if i >> j & 1:
                tmp[j] += 1
        
        for j, k in zip(tmp, tmp[1:]):
            if j == k == 1:
                break
        else:
            
            for j in range(W - 1):
                cnt[j] += tmp[j]
            for j in range(W):
                if j == 0:
                    if tmp[j] == 0:
                        cntz[j] += 1
                elif j == W - 1:
                    if tmp[j - 1] == 0:
                        cntz[j] += 1
                else:
                    if tmp[j] == tmp[j - 1] == 0:
                        cntz[j] += 1

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

    for j in range(H):
        for i in range(W):
            if i == 0:
                dp[j + 1][i] += dp[j][i] * cntz[i]
                dp[j + 1][i + 1] += dp[j][i] * cnt[i]
                dp[j + 1][i] %= MOD
                dp[j + 1][i + 1] %= MOD
            elif i == W - 1:
                dp[j + 1][i] += dp[j][i] * cntz[i]
                dp[j + 1][i - 1] += dp[j][i] * cnt[i - 1]
                dp[j + 1][i] %= MOD
                dp[j + 1][i - 1] %= MOD
            else:
                dp[j + 1][i] += dp[j][i] * cntz[i]
                dp[j + 1][i + 1] += dp[j][i] * cnt[i]
                dp[j + 1][i - 1] += dp[j][i] * cnt[i - 1]
                dp[j + 1][i] %= MOD
                dp[j + 1][i + 1] %= MOD
                dp[j + 1][i - 1] %= MOD

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


if __name__ == '__main__':
    main()

Solution (Python):

"""
問題：
W本長さHの棒に任意に横線を引く時に、
1からスタートしてkにたどり着くあみだくじの通り数を求めよ
ただし、横線には以下の制約がある
同じ高さに何本引いても良いが、その端点が隣接してはいけない
同じ高さ同士にしか引けない
隣り合う棒にしか引けない
解法：
dpを用いて解く。
dp[i][j]:高さiの状態にいる時の、棒jにたどり着く通り数
dp[i+1][j-1],dp[i+1][j],dp[i+1][j+1]の三通りの遷移について、
(これは横線は必ず端点を共有しないことから言える)
それぞれあり得る通り数を全探索して足していった結果が答え。
最終的にd[h][k]が答え
"""
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
mod = 10**9+7
h,w,g = map(int,readline().split())

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

def func(x):
    if x <= 0:
        return 1
    return func(x-2) + func(x-1)

for i in range(h):
    for j in range(w):
        for k in range(-1,2): 
            if not 0 <= j + k < w:
                continue
            
            if k == -1:
                l = max(0,j-2)
                r = max(0,w-1-(j+1))
            elif k == 0:
                l = max(0,j-1)
                r = max(0,w-1-(j+1))
            else:
                l = max(0,j-1)
                r = max(0,w-1-(j+2))
            dp[i+1][j+k] += dp[i][j]*func(l)*func(r)
            dp[i+1][j+k] %= mod


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

Solution (Python):
h,w,k=map(int,input().split())
mod=10**9+7
dp=[[0]*w for _ in range(h+1)] 
dp[0][0]=1
for hi in range(1,h+1):
    for i in range(2**(w-1)):
        idx1=[]
        idx2=[]
        ok=True
        for j in range(w-1):
            if (i>>j)&1:
                idx1.append(j)
                idx2.append(j)
                idx2.append(j+1)
        if len(idx1)>=2:
            for j in range(len(idx1)-1):
                if idx1[j+1]==idx1[j]+1:
                    ok=False
        if not ok:
            continue
        idx1=set(idx1)
        idx2=set(idx2)
        for wi in range(w):
            if wi in idx1:
                dp[hi][wi]+=dp[hi-1][wi+1]
                dp[hi][wi+1]+=dp[hi-1][wi]
                dp[hi][wi]%=mod
                dp[hi][wi+1]%=mod
            if wi not in idx2:
                dp[hi][wi]+=dp[hi-1][wi]
                dp[hi][wi]%=mod
print(dp[h][k-1])

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

mod = 10 ** 9 + 7

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

n_join = [0 for i in range(w-1)]
n_unjoin = [0 for i in range(w-1)]
cnt = 0

for i in range(2 ** (w-1)):
    p = 0
    f = 1
    tmp_join = []
    tmp_unjoin = []
    for j in range(w-1):
        c = i & (1 << j)
        if c:
            tmp_join.append(j)
        if not (c or p):
            tmp_unjoin.append(j)
        if p and c:
            f = 0
            break
        p = c
    if f:
        cnt += 1
        for j in tmp_join:
            n_join[j] += 1
        for j in tmp_unjoin:
            n_unjoin[j] += 1

n_unjoin.append(cnt - n_join[-1])

dp = [[0 for j in range(w)] for i in range(h)]
dp[0][0] = n_unjoin[0]
dp[0][1] = n_join[0]

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

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq
MOD = 10**9 + 7
LI = lambda : [int(x) for x in sys.stdin.readline().split()]

H,W,K = LI()

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

good = []
for ami in range(2**(W-1)):
    b = 1
    m = -2
    for i in range(W-1):
        if b & ami:
            if i <= m + 1:
                break
            m = i
        b <<= 1
    else:
        s = []
        b = 1
        for i in range(W):
            s.append(ami & b > 0)
            b <<= 1
        good.append([0] + s + [0])

for i in range(H):
    for ami in good:
        for j in range(W):
            if ami[j] == 0 and ami[j+1] == 0:
                dp[i+1][j] = (dp[i+1][j] + dp[i][j]) % MOD
            elif ami[j] == 1:
                dp[i+1][j-1] = (dp[i+1][j-1] + dp[i][j]) % MOD
            else:
                dp[i+1][j+1] = (dp[i+1][j+1] + dp[i][j]) % MOD

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

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq
MOD = 10**9 + 7
LI = lambda : [int(x) for x in sys.stdin.readline().split()]

H,W,K = LI()

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

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

good = []
for ami in range(2**(W-1)-1):
    b = 1
    m = -2
    for i in range(W-1):
        if b & ami:
            if i <= m + 1:
                break
            m = i
        b <<= 1
    else:
        s = []
        b = 1
        for i in range(W):
            s.append(ami & b > 0)
            b <<= 1
        good.append([0] + s + [0])

for i in range(H):
    for ami in good:
        for j in range(W):
            if ami[j] == 0 and ami[j+1] == 0:
                dp[i+1][j] = (dp[i+1][j] + dp[i][j]) % MOD
            elif ami[j] == 1:
                dp[i+1][j-1] = (dp[i+1][j-1] + dp[i][j]) % MOD
            else:
                dp[i+1][j+1] = (dp[i+1][j+1] + dp[i][j]) % MOD

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

Solution (Python):
w = [1, 2]
for i in range(6):
    w.append(w[-2] + w[-1])
H, W, K = map(int,input().split())
mod = 10 ** 9 + 7
dp = [[0 for i in range(W)] for j in range(H+1)]
dp[0][0] = 1
for i in range(H):
    for j in range(W):
        if j >= 1:
            k = 1
            if j - 2 >= 0:
                k *= w[j - 2]
            if W - j - 2 >= 0:
                k *= w[W - j - 2]
            dp[i+1][j-1] += k * dp[i][j]
            dp[i+1][j-1] %= mod
        k = 1
        if j - 1 >= 0:
            k *= w[j - 1]
        if  W - j - 2 >= 0:
            k *= w[W - j - 2]
        dp[i+1][j] += k * dp[i][j]
        dp[i+1][j] %= mod
        if j <= W - 2:
            k = 1
            if j - 1 >= 0:
                k *= w[j - 1]
            if W - j - 3 >= 0:
                k *= w[W - j - 3]
            dp[i+1][j+1] += k * dp[i][j]
            dp[i+1][j+1] %= mod

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

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

MOD = 10 ** 9 + 7
dp = [[0] * W for _ in range(H + 1)]
dp[0][0] = 1
for i in range(H):
    for j in range(W):
        for k in range(1 << (W - 1)):
            
            ok = True
            for l in range(W - 2):
                if (k >> l) & 1 and (k >> (l + 1) & 1):
                    ok = False

            if not ok:
                continue

            if j > 0 and k >> (j - 1) & 1:
                dp[i + 1][j - 1] += dp[i][j]
                dp[i + 1][j - 1] %= MOD
            elif j < W - 1 and k >> j & 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[-1][K - 1])

Solution (Python):
h,w,k=map(int,input().split())
dp=[0]*(w)
l=[1,1,2,3,5,8,13,21,34]




dp[0]=1
mod=10**9+7
r=[0]*w
for i in range(h):
    for i in range(w):
        r[i]=dp[i]*l[i]*l[w-1-i]
        if i>=1:
            r[i]+=dp[i-1]*l[i-1]*l[w-1-i]
        if i<=w-2:
            r[i]+=dp[i+1]*l[i]*l[w-2-i]
        r[i]%=mod
    dp,r=r,dp

print(dp[k-1])

Solution (Python):
'''Yoshichiの日記
あみだくじ。
0本目からスタートし、W本の長さH + 1までにを任意の線を引いた時
K本目にたどり着くパターンは何パターンあるか答えよ。
現在の位置状態での線の引き方を全列挙し、DP(メモ化再帰)を用いて答える。
x → 現在の位置
y → 現在の進み具合
for分のi → 現在の位置にいる時の線の配置状態(1が隣接へつながっているとき)
for分のj → NGパターンの列挙(隣へ繋がっているかつ、
                   次の隣へも線が引かれている状態)
'''
from collections import defaultdict
h, w, k = map(int, input().split())
memo = defaultdict(lambda:defaultdict(int))
def dfs(x, y):
    if y == h:
        if x == k - 1:
            return 1
        else:
            return 0
    if y in memo[x]:
        return memo[x][y]
    ans = 0
    for i in range(1 << w - 1):
        flg = True
        for j in range(w - 2):
            if i & (1 << j) and i & (1 << j + 1):
                flg = False
                break
        if flg:
            nx = x
            if x > 0 and i & (1 << x - 1):
                nx = x - 1
            elif i & (1 << x):
                nx = x + 1
            ans += dfs(nx, y + 1)
            ans %= 1000000000 + 7
    memo[x][y] = ans
    return ans
print(dfs(0, 0))

Solution (Python):
'''3/18 AtCoder（漸化式dp）
一番左の棒からスタートして、K番目の棒に到達するようなあみだくじは
何通り作れますかという趣旨の問題
まず、この問題を解くうえで一番重要なのは、
「ある高さh、棒jに至る経路の総数を求める漸化式が立てられる」ということ
高さh、棒jに至る経路の総数をdp[h][j]とすれば、
高さh-1からこの位置に至ることができるのは、
棒j-1,j,j+1のいずれかしかない
さらに、そこに至る経路数というのは結局
「ほかの棒にどんな風に架け橋（横棒）がかかっているか」の場合の数なので、
それをdp[h-1][j-1],dp[h-1][j],dp[h-1][j+1]にかけていく必要がある
例えば、dp[h-1][j]を見てみる　これは、同じ棒から下ってくることを
意味しているが、換言すれば「高さi-1とiには、棒jから伸びる横棒はない」
ということである
つまり、この高さにおける横棒の架かり方というのは
「棒1~j-1までの架かり方」と「棒j+1~棒Wまでの架かり方」の
二パターンしかないということになる
ある高さにおける横棒のかかり方も漸化式で求められる　
高さhにおける(横一列にかけ橋が並んでいる状況を考える）、
n本の棒の間にかかる橋の場合の数の総数をf(n)と置くと、
f(n) = f(n-1)+f(n-2)と書くことができる
これは、f(n)が
①n本目とn-1本目の棒の間に橋が架かっていない→場合の数はf(n-2)と同じ
②n本目とn-1本目の棒の間に橋が架かっている→場合の数はf(n-1)と同じ
の二パターンの合計だからである
だから、dp[h-1][j]に掛ける数はいくつかということを考えたら、
j-1本の棒の間にかかる橋の場合の数f(j-1)と、
W-j本の棒の間にかかる橋の場合の数f(W-j)本ということになる　
これと同様に、残り二本に対してもいくつかければよいかを考えて、
dp[h][j]]に対する漸化式を立てればよい
'''
H,W,K = map(int,input().split())
dp = []
for i in range(H+1): 
  L = [0]*W
  dp.append(L)
fb = [1,1] 
for i in range(W-2):
  fb.append(fb[i]+fb[i+1])
dp[0][0] = 1 
if W != 1: 
  for i in range(1,H+1):
    for j in range(W): 
      if 1 <= j <= W-2:
        dp[i][j] = dp[i-1][j-1]*fb[j-1]*fb[W-j-1]+dp[i-1][j]*fb[j]*fb[W-j-1]+dp[i-1][j+1]*fb[j]*fb[W-j-2]
      elif j == 0:
        dp[i][j] = dp[i-1][j]*fb[W-1]+dp[i-1][j+1]*fb[W-2]
      else:
        dp[i][j] = dp[i-1][j]*fb[W-1]+dp[i-1][j-1]*fb[W-2]
else:
  dp[H][0] = 1
print(dp[H][K-1]%(10**9+7))

Solution (Python):

import sys

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

MOD = 10 ** 9 + 7
H, W, K = lr()
cases = [1] * 10  
cases[-1] = 0 
for i in range(2, 9):
    cases[i] = cases[i-2] + cases[i-1]

dp = [0] * W
dp[0] = 1
for i in range(H):
    prev = dp[:]
    for j in range(W):
        left = j; right = W-(j+1)
        dp[j] *= cases[left] * cases[right]
        if j > 0:
            dp[j] += prev[j-1] * cases[left-1] * cases[right]
        if j < W-1:
            dp[j] += prev[j+1] * cases[left] * cases[right-1]
        dp[j] %= MOD
        
answer = dp[K-1] % MOD
print(answer)