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):
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b



def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)



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


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

    num = [[0] * 9 for _ in range(9)]
    for b in range(2 ** (W - 1)):
        b = bin(b)[2:].zfill(W - 1)
        ok = True
        for i in range(len(b) - 1):
            if b[i] == "1" and b[i + 1] == "1":
                ok = False
        if ok:
            p = list(range(W))
            for i in range(len(b)):
                if b[i] == "1":
                    p[i], p[i + 1] = p[i + 1], p[i]

            for i in range(W):
                num[i][p[i]] += 1

    dp = [[0] * (W + 1) for _ in range(H + 1)]
    dp[0][0] = 1
    for y in range(H):
        for x in range(W):
            for i in range(W):
                dp[y + 1][i] += dp[y][x] * num[x][i]
                dp[y + 1][i] %= MOD

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


if __name__ == '__main__':
    main()

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

mod = 10**9 + 7

def cpst(s, n):
    a = '0' * (n-len(s))
    return a + s

def makeb(n):
    l = []
    for i in range(2**n):
        tmp = bin(i)[2:]
        l.append(cpst(tmp, n))
    return l

tmp_bits = makeb(w-1)
bits = []
for x in tmp_bits:
    flag = True
    for i in range(w-2):
        if x[i] == '1' and x[i+1] == '1':
            flag = False
            break
    if flag:
        bits.append(x)

table = [[0,0,0] for _ in range(w)]

for x in bits:
    for i,y in enumerate(x):
        if y == '1':
            table[i][2] += 1
            table[i+1][0] += 1
        else:
            if i == 0:
                table[0][1] += 1
            else:
                if x[i-1] == '0':
                    table[i][1] += 1
            if i == w-2:
                table[w-1][1] += 1

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

for i in range(h):
    for j in range(w):
        if j == 0:
            if w != 1:
                add = dp[i][j]*table[j][1] + dp[i][j+1]*table[j+1][0]
            else:
                add = dp[i][j]*table[j][1]
        elif j == w-1:
            add = dp[i][j]*table[j][1] + dp[i][j-1]*table[j-1][2]
        else:
            add = dp[i][j]*table[j][1] + dp[i][j-1]*table[j-1][2] + dp[i][j+1]*table[j+1][0]
        dp[i+1][j] = (dp[i+1][j] + add) % mod

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

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

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

case = []

def createCase(s):
    if (len(s) == w-1):
        case.append(s)
        return
    if len(s) != 0 and s[-1] == "1" :
        createCase(s+"0")
    else:
        createCase(s+"0")
        createCase(s+"1")

createCase("")

for i in range(len(case)):
    case[i] = "0"+case[i]+"0"



move = [[0]*3 for _ in range(w)]

for i in range(w):
    for j in case:
        if j[i] == j[i+1] == "0":
            move[i][1] += 1
        if j[i+1] == "1":
            move[i][2] += 1
        if j[i] == "1":
            move[i][0] += 1



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

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

dp[0][0] = fib[w-1]
dp[0][1] = fib[w-2]

for i in range(1, h):
    dp[i][0] = (dp[i-1][0]*move[0][1] + dp[i-1][1]*move[1][0]) % 1000000007
    for j in range(1, w-1):
        dp[i][j] = (dp[i-1][j]*move[j][1] + dp[i-1][j-1]*move[j-1][2] + dp[i-1][j+1]*move[j+1][0]) % 1000000007
    dp[i][-1] = (dp[i-1][-2]*move[-2][2] + dp[i-1][-1]*move[-1][1]) % 1000000007



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

Solution (Python):
def run(H, W, K):
    
    dp = {(1, 0): 1}
    for w in range(2, W+1):
        dp[(w, 0)] = 0
    
    for h in range(0, H+1):
        dp[(0, h)] = 0
        dp[(W+1, h)] = 0
    
    for h in range(1, H+1):
        for w in range(1, W+1):
            '''
            hの位置で他の線のパターンを計算
            w-1からwの線があるとき
            1からw-2までw-3本の線が引ける、w+1からWまでW-w-1本の線が引ける
            1本なら2パターン、2本なら3パターン、3本なら5パターン、4本なら1+4+3=8パターン
            5本なら1+5+6+1=13パターン、6本なら1+6+10+4=21、7本なら1+7+15+10+1=34パターン
            ''' 
            a = get_coef(w-3, W-w-1)
            b = get_coef(w-2, W-w-1)
            c = get_coef(w-2, W-w-2)
            dp[(w, h)] = (a*dp[(w-1, h-1)] + b*dp[(w, h-1)] + c*dp[(w+1, h-1)]) % 1000000007
    
    return dp[K, H]


def get_coef(w_l, w_r):
    coef = [1, 2, 3, 5, 8, 13, 21, 34]
    if w_l < 0:
        w_l = 0
    if w_r < 0:
        w_r = 0
    return coef[w_l]*coef[w_r]


def main():
    H, W, K = map(int, input().split())
    print(run(H, W, K))


if __name__ == '__main__':
    main()

Solution (Python):
h, w, k = map(int, input().split())
fib = [0, 1, 1, 2, 3, 5, 8, 13, 21]
dp = [[0] * (w + 2) for i in range(h + 1)]
dp[0][1] = 1

for j in range(h):
    for l in range(1, w + 1):
        dp[j + 1][l] = fib[l] * fib[w - l + 1] * dp[j][l] + fib[l - 1] * fib[w - l + 1] * dp[j][l - 1] + fib[l] * fib[w - l] * dp[j][l + 1]

print(dp[h][k] % 1000000007)

Solution (Python):
from collections import Counter

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

MOD = 1000000007

pats = [[0]]

for i in range(1, W):
    pats = [p + [i] for p in pats] + [p[:-1] + [i, i - 1] for p in pats if p[-1] == i - 1]

iws = [Counter(r) for r in zip(*pats)]

rs = [1] + [0] * (W - 1)

for j in range(H):
    rs = [sum(rs[i] * iw[i] for i in iw) % MOD for iw in iws]

print(rs[K - 1])

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

MOD = 1000000007

pats = [[0]]

for i in range(1, W):
    pats = [p + [i] for p in pats] + [p[:-1] + [i, i - 1] for p in pats if p[-1] == i - 1]

rs = [1] + [0] * (W - 1)

for j in range(H):
    rs = [sum(rs[p[i]] for p in pats) % MOD for i in range(W)]

print(rs[K - 1])

Solution (Python):

h,w,k = map(int, input().split())
k -= 1
mod = 1000000007

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

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

for hi in range(1,h+1):
    for b in range(2**(w-1)):
        judge = False
        for i in range(w-2):
            if (b>>i)&3 == 3:
                judge = True
                break
        if judge:
            continue

        perm = [i for i in range(w)]
        for i in range(w-1):
            if (b>>i)&1==1:
                perm[i],perm[i+1] = perm[i+1],perm[i]
        for i in range(w):
            dp[hi][perm[i]]  = (dp[hi][perm[i]]+dp[hi-1][i])%mod

print(dp[h][k])

Solution (Python):
h,w,k = map(int,input().split())
mod = 10 ** 9 + 7
if w == 1:
  print(1)
  exit()
lis = [[0 for i in range(w)] for s in range(h+1)]
lis[0][0] = 1
dp1 = [0]
dp2 = [1]
for i in range(1,w-1):
  dp1.append(dp2[i-1])
  dp2.append(dp2[i-1] + dp1[i-1])
dp1.insert(0,0)
dp2.insert(0,0)
dp = [dp1[i] + dp2[i] for i in range(w)]
for i in range(h):
  for j in range(w):
    if j == 0 or j == w-1:num = dp[w-1]
    else:num = dp[j] * dp[w-j-1]
    lis[i+1][j] += num * lis[i][j] % mod
    if j != 0:
      lis[i+1][j-1] += max(1,dp[j-1]) * max(1,dp[w-j-1]) * lis[i][j] % mod
    if j != w-1:
      lis[i+1][j+1] += max(1,dp[j]) * max(1,dp[w-j-2]) * lis[i][j] % mod
print(lis[h][k-1] % mod)

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

num = [[0 for _ in range(W)] for _ in range(W)]
for value in range(2**(W-1)):
    bit = [False for _ in range(W-1)]
    for d in range(W-1):
        bit[d] = (2**d & value) > 0
    duplicate = False
    for d in range(1,W-1):
        if bit[d] and bit[d-1]:
            duplicate = True
            break
    if duplicate:
        continue
    
    for x in range(W):
        num[x][x] += 1
    for d in range(W-1):
        if bit[d]:
            num[d][d+1] += 1
            num[d+1][d] += 1
            num[d][d] -= 1
            num[d+1][d+1] -= 1

dp = [[0 for _ in range(W)] for _ in range(H+1)]
dp[0][0] = 1
for h in range(1,H+1):
    for k in range(W):
        for j in range(W):
            dp[h][k] += (dp[h-1][j]*num[j][k])%MOD
            dp[h][k] %= MOD
print(dp[H][K-1])

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

bit = []
for i in range(1 << (W - 1)):
    flag = True
    for j in range(W - 1):
        if i & 1 << j and i & 1 << (j + 1):
            flag = False
            break

    if flag:
        bit.append(i)

MOD = 10 ** 9 + 7
dp = [[0] * W for i in range(H + 1)]
dp[0][0] = 1
for i in range(H):
    for j in range(W):
        for k in bit:
            ne = j
            if k & 1 << j:
                ne = j + 1
            elif j - 1 >= 0 and k & 1 << (j - 1):
                ne = j - 1

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

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

Solution (Python):
def amida(arr, rest):
    num=0
    if rest<1:
        return 1

    num+=amida(arr, rest-2)
    arr[-rest-1]+=num
    num+=amida(arr, rest-1)
    return num

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

arr=[0 for i in range(W+2)]
arr[1]=1

line=[0 for i in range(W+1)]
sum_=amida(line,W-1)

for i in range(H):
    tmp=arr[:]
    for j in range(1,W+1):
        arr[j]=(tmp[j]*(sum_-line[j]-line[j-1])+tmp[j+1]*line[j]+tmp[j-1]*line[j-1])%(10**9+7)
print(arr[K])

Solution (Python):
from itertools import product
H, W, K = map(int, input().split())
A = [[0 for j in range(W+1)] for i in range(H+1)]
M = 10 ** 9 + 7
A[0][1] = 1


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

cache = {}


def xyz(x):
    x -= 2
    if cache.get(x) is not None:
        return cache[x]
    X, Y, Z = 0, 0, 0
    for i in product('01', repeat=W-1):
        s = ''.join(i)
        if s.find('11') != -1:
            continue
        if x == -1:
            if s[0] == '1':
                Z += 1
            else:
                Y += 1
            continue
        if W - 2 == x:
            if s[-1] == '1':
                X += 1
            else:
                Y += 1
            continue
        t = s[x:x+2]
        if t == '10':
            X += 1
        elif t == '01':
            Z += 1
        else:
            Y += 1
    cache[x] = (X, Y, Z)
    return X, Y, Z


for h in range(H+1):
    for x in range(1, W+1):
        if H < h + 1:
            continue
        X, Y, Z = xyz(x)
        A[h + 1][x - 1] += (X * A[h][x]) % M
        A[h + 1][x] += (Y * A[h][x]) % M
        if W < x + 1:
            continue
        A[h + 1][x + 1] += (Z * A[h][x]) % M


print(A[H][K] % M)

Solution (Python):
h, w, k = map(int, input().split())
li = [1]+[0]*(w-1)
if w == 1:
    print(1)
else:
    for i in range(h):
        t = li.copy()
        if w == 2:
            li[0] = (t[0] + t[1]) % 1000000007
            li[1] = (t[0] + t[1]) % 1000000007
        elif w == 3:
            li[0] = (2*t[0] + t[1]) % 1000000007
            li[1] = (t[0] + t[1] + t[2]) % 1000000007
            li[2] = (t[1] + 2 * t[2]) % 1000000007
        elif w == 4:
            li[0] = (3*t[0] + 2*t[1]) % 1000000007
            li[1] = (2*t[0] + 2*t[1] + t[2]) % 1000000007
            li[2] = (t[1] + 2*t[2] + 2*t[3]) % 1000000007
            li[3] = (2*t[2] + 3 * t[3]) % 1000000007
        elif w == 5:
            li[0] = (5 * t[0] + 3*t[1]) % 1000000007
            li[1] = (3 * t[0] + 3*t[1] + 2*t[2]) % 1000000007
            li[2] = (2 * t[1] + 4*t[2] + 2*t[3]) % 1000000007
            li[3] = (2 * t[2] + 3 * t[3] + 3 * t[4]) % 1000000007
            li[4] = (3 * t[3] + 5 * t[4]) % 1000000007
        elif w == 6:
            li[0] = (8 * t[0] + 5 * t[1]) % 1000000007
            li[1] = (5 * t[0] + 5 * t[1] + 3 * t[2]) % 1000000007
            li[2] = (3 * t[1] + 6 * t[2] + 4 * t[3]) % 1000000007
            li[3] = (4 * t[2] + 6 * t[3] + 3 * t[4]) % 1000000007
            li[4] = (3 * t[3] + 5 * t[4] + 5 * t[5]) % 1000000007
            li[5] = (5 * t[4] + 8 * t[5]) % 1000000007
        elif w == 7:
            li[0] = (13 * t[0] + 8 * t[1]) % 1000000007
            li[1] = (8 * t[0] + 8 * t[1] + 5 * t[2]) % 1000000007
            li[2] = (5 * t[1] + 10 * t[2] + 6 * t[3]) % 1000000007
            li[3] = (6 * t[2] + 9 * t[3] + 6 * t[4]) % 1000000007
            li[4] = (6 * t[3] + 10 * t[4] + 5 * t[5]) % 1000000007
            li[5] = (5 * t[4] + 8 * t[5] + 8 * t[6]) % 1000000007
            li[6] = (8 * t[5] + 13 * t[6]) % 1000000007
        else:
            li[0] = (21 * t[0] + 13 * t[1]) % 1000000007
            li[1] = (13 * t[0] + 13 * t[1] + 8 * t[2]) % 1000000007
            li[2] = (8 * t[1] + 16 * t[2] + 10 * t[3]) % 1000000007
            li[3] = (10 * t[2] + 15 * t[3] + 9 * t[4]) % 1000000007
            li[4] = (9 * t[3] + 15 * t[4] + 10 * t[5]) % 1000000007
            li[5] = (10 * t[4] + 16 * t[5] + 8 * t[6]) % 1000000007
            li[6] = (8 * t[5] + 13 * t[6] + 13 * t[7]) % 1000000007
            li[7] = (13 * t[6] + 21 * t[7]) % 1000000007
    print(li[k - 1])

Solution (Python):
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(1,h+1): 
    for p in range(2**(w-1)):
        bit = list(str(bin(p)))
        bit.pop(0)
        bit.pop(0)
        for a in range(w-1-len(bit)):
            bit.insert(0,"0")
        temp = True
        for a in range(w-2):
            if bit[a] == "1" and bit[a] == bit[a+1]:
                temp = False
        if temp:
            mix = [b for b in range(w)]
            for a in range(w-1):
                if bit[a] == "1":
                    mix[a],mix[a+1] = mix[a+1],mix[a]
            for b in range(w):
                dp[i][b] += dp[i-1][mix[b]]
                dp[i][b] = dp[i][b]%mod
print(dp[h][k-1])

Solution (Python):
H,W,K=[int(i) for i in input().split()]
Fn=[1,1,2,3,5,8,13,21,0]
ans=[]
ans0=[0 for i in range(W+2)]
ans0[1]=1
ans.append(ans0)
for i in range(1,H+1):
    ansi=[0 for i in range(W+2)]
    for j in range(1,W+1):
        ansi[j-1]+=ans[i-1][j]*Fn[j-2]*Fn[W-j]
        ansi[j]+=ans[i-1][j]*Fn[j-1]*Fn[W-j]
        ansi[j+1]+=ans[i-1][j]*Fn[j-1]*Fn[W-j-1]
    for j in range(W+2):
        ansi[j]%=1000000007
    ans.append(ansi)
print(ans[H][K])

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

validBit = []
for i in range(1<<(W-1)):
    valid = True
    for j in range(W-1):
        if ((i>>j)&1) == 1 and ((i>>(j+1))&1) == 1:
            valid = False
    if valid:
        validBit.append(i)

mod = 1000000007
dp = [[0] * W for i in range(H+1)]
dp[0][0] = 1

for i in range(H):
    for j in range(W):
        if dp[i][j] == 0:
            continue
        for k in validBit:
            nj = j
            if ((k >> j) & 1) == 1:
                nj = j + 1
            elif j > 0 and (k >> (j-1) & 1) == 1:
                nj = j - 1

            dp[i+1][nj] = (dp[i+1][nj] + dp[i][j])%mod

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

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

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

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

base = [[0] * W for _ in range(W)]

for bit in range(2 ** (W - 1)):
    temp = [(bit & (1 << i) != 0) for i in range(W - 1)]
    before = False
    is_ok = True
    for line in temp:
        if line:
            if before:
                is_ok = False
                break
            else:
                before = True
        else:
            before = False
    
    if is_ok:
        before = False
        for i, line in enumerate(temp):
            if line:
                base[i][i + 1] += 1
                base[i + 1][i] += 1
                before = True
            else:
                if not before:
                    base[i][i] += 1

                before = False

        if not temp[-1]:
            base[-1][-1] += 1
dp = [[0] * W for _ in range(H + 1)]
dp[0][0] = 1
for i in range(1, H + 1, 1):
    for j in range(W):
        for k in range(W):
            dp[i][j] = (dp[i][j] + dp[i - 1][k] * base[k][j]) % mod

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

Solution (Python):
h,w,kk = map(int,input().split())
dp = [[[] for j in range(w)] for i in range(h+1)]


for i in range(h+1):
        for j in range(w):
                dp[i][j] = 0
dp[0][0]=1
mod = 1000000007

for i in range(1,h+1):
        for j in range(1<<(w-1)):
                yoko = [False for loo in range(w)]
                for k in range((w-1)):
                        yoko[k] = True if ((j>>k)&1) else False
                
                ok = True
                for l in range(w-2):
                        if(yoko[l]==True and yoko[l+1]==True):
                                ok = False
                if(not ok):
                        continue
                
                for l in range(w):
                        if(l==0):
                                if(yoko[l]):
                                        dp[i][l] += dp[i-1][l+1]
                                else:
                                        dp[i][l] += dp[i-1][l]
                                dp[i][l]%=mod
                                continue
                        if(l==w-1):
                                if(yoko[l-1]):
                                        dp[i][l] += dp[i-1][l-1]
                                else:
                                        dp[i][l] += dp[i-1][l]
                                dp[i][l]%=mod                                
                                continue

                        if(yoko[l-1] or yoko[l]):
                                if(yoko[l-1]):
                                        dp[i][l]+= dp[i-1][l-1]
                                else:
                                        dp[i][l]+= dp[i-1][l+1]
                        else:
                                dp[i][l] += dp[i-1][l]
                        dp[i][l]%=mod
                        
print(dp[h][kk-1])

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


A = [[0] * (W+2) for i in range(H+1)]

A[0][1] = 1


def multip(N):
  tempa = [1,1,1,2,3,5,8,13,21,34,55]
  return(tempa[N+1])
  
for i in range(1,H+1):
  for j in range(1,W+2):
    if j < 1 or j > W:
      A[i][j] = 0
    else:
      A[i][j] = (A[i-1][j-1]*(multip(j-2) * multip(W-j)) + A[i-1][j]*(multip(j-1) * multip(W-j))+ A[i-1][j+1]*(multip(j-1) * multip(W-j-1))) % MODN
      
print(A[H][K])

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

h,w,k = map(int,input().split())
fibonacchi =[1, 1, 2, 3, 5, 8, 13, 21, 34]
dp = [[0] * (w + 1) for _ in range(h + 1)]
dp[0][1] = 1
for i in range(h):
  for j in range(w+1):
    
    
    
    
    if j >= 2:
      dp[i+1][j-1] += (fibonacchi[j-2]*fibonacchi[w-j])*dp[i][j]
      dp[i+1][j-1]%=mod

    
    
    
    
    if j <= w-1:
      dp[i+1][j+1] += (fibonacchi[j-1]*fibonacchi[w-j-1])*dp[i][j]
      dp[i+1][j+1]%=mod

    
    
    
    
    dp[i+1][j] += (fibonacchi[j-1]*fibonacchi[w-j])*dp[i][j]
    dp[i+1][j] %=mod

print(dp[h][k])

Solution (Python):
import sys
mod = pow(10, 9) + 7
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

NNN = (10**2)
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

for i in range( 2, NNN + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )


def erabu(aW):
    r = 0
    for i in range(aW // 2 + 1 + 1):
        sp = aW - (2*i -1)
        r += cmb(sp+i+1-1, sp, mod)
    return r

N, W, K = [int(x) for x in input().strip().split(" ")]
hasi = 0
cc = []
if W == 1:
    if K == 1:
        print(1)
    else:
        print(0)
    sys.exit()
elif W == 2:
    cccl = [1, 1]
    cc = [1, 1]
elif W == 3:
    cccl = [1, 1, 1]
    cc = [2, 1, 2]
elif W >= 4:
    aW = W - 1
    hW = aW - 2
    nhW = aW - 3
    cc = []
    cccl = []
    for w in range(W):
        nn = max(W - 1 - w - 1, 0)
        nnn = max((W - 1) - nn - 2, 0)
        if w == W -1:
            nnn += 1
        cc.append(erabu(nn) * erabu(nnn))
        cccl.append(erabu(nn) * erabu(nnn-1))

cccl[0] = 0
cccr = cccl[::-1]
d = [[1] + [0 for x in range(W-1)]] + [[0] * W for _ in range(N)]
for i in range(N):
    i += 1
    for j in range(W):
        d[i][j] = (d[i-1][j] * cc[j]) % mod
        if j != 0:
            d[i][j] = (d[i][j] + (d[i-1][j-1] * cccl[j]) )% mod
        if j != W-1:
            d[i][j] = (d[i][j] + (d[i-1][j+1] * cccr[j])) % mod

print(d[N][K-1])

Solution (Python):
import sys
mod = pow(10, 9) + 7
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

NNN = (10**2)
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

for i in range( 2, NNN + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )


def erabu(aW):
    r = 0
    for i in range(aW // 2 + 1 + 1):
        sp = aW - (2*i -1)
        r += cmb(sp+i+1-1, sp, mod)
    return r

N, W, K = [int(x) for x in input().strip().split(" ")]
hasi = 0
cc = []
if W == 1:
    if K == 1:
        print(1)
    else:
        print(0)
    sys.exit()
elif W == 2:
    cccl = [1, 1]
    cc = [1, 1]
elif W == 3:
    cccl = [1, 1, 1]
    cc = [2, 1, 2]
elif W >= 4:
    aW = W - 1
    hW = aW - 2
    nhW = aW - 3
    cc = []
    cccl = []
    for w in range(W):
        nn = max(W - 1 - w - 1, 0)
        nnn = max((W - 1) - nn - 2, 0)
        if w == W -1:
            nnn += 1
        cc.append(erabu(nn) * erabu(nnn))
        cccl.append(erabu(nn) * erabu(nnn-1))

cccl[0] = 0
cccr = cccl[::-1]
d = [[1] + [0 for x in range(W-1)]] + [[0] * W for _ in range(N)]
for i in range(N):
    i += 1
    for j in range(W):
        d[i][j] = (d[i-1][j] * cc[j]) % mod
        if j != 0:
            d[i][j] = (d[i][j] + (d[i-1][j-1] * cccl[j]) )% mod
        if j != W-1:
            d[i][j] = (d[i][j] + (d[i-1][j+1] * cccr[j])) % mod

print(d[N][K-1])

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

h,w,k = map(int,input().split())
k = k-1
dp = [0]*1000 
dp[0]=1
dp[1]=1
dp[2]=2

for i in range(3,1000):
  dp[i] = (dp[i-1]+dp[i-2])%mod
  
  
  

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

dp2[0][0] = 1
for i in range(h):
  for j in range(w):
    
    
    
    

    dp2[i+1][j] = (dp2[i+1][j]+dp2[i][j]*dp[j]%mod*dp[w-j-1]%mod)%mod

    
    
    
    
    
    if (j-1>=0):
      dp2[i+1][j-1]=(dp2[i+1][j-1]+dp2[i][j]*dp[j-1]%mod*dp[w-j-1]%mod)%mod

    
    
    
    
    

    if (j+1<w):
      dp2[i+1][j+1]=(dp2[i+1][j+1]+dp2[i][j]*dp[j]%mod*dp[w-j-2]%mod)%mod


print(dp2[h][k])

Solution (Python):
a,b,c=map(int,input().split())
s=[[0]*b for i in range(a+1)]
s[0][0]=1
k=[[1,1,1],[2,1,1,1,2],[3,2,2,1,2,2,3],[5,3,3,2,4,2,3,3,5],[8,5,5,3,6,4,6,3,5,5,8],[13,8,8,5,10,6,9,6,10,5,8,8,13],[21,13,13,8,16,10,15,9,15,10,16,8,13,13,21]]
if b==1:
    print(1)
elif c-a>=2:
    print(0)    
else:
    d=k[b-2]
    for i in range(1,a+1):
        s[i][b-1]=s[i-1][b-1]*d[2*(b-1)]+s[i-1][b-2]*d[2*(b-1)-1]
        for j in range(0,b-1):
            if j==0:
                s[i][0]=s[i-1][0]*d[0]+s[i-1][1]*d[1]
            else:    
                s[i][j]=s[i-1][j-1]*d[2*j-1]+s[i-1][j]*d[2*j]+s[i-1][j+1]*d[2*j+1]
    print(s[a][c-1]%(10**9+7))

Solution (Python):
from itertools import product


def violates(w_flags):
    prev_flag = w_flags[0]
    for flag in w_flags[1:]:
        if flag and prev_flag:
            return True
        prev_flag = flag
    return False


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

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

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

for h in range(1, H + 1):
    for w_flags in product((False, True), repeat=W-1):
        if violates(w_flags):
            continue
        for w in range(W):
            if w == 0:
                if w_flags[0]:
                    dp[h][0] += dp[h - 1][1]
                else:
                    dp[h][0] += dp[h - 1][0]
            elif w == W - 1:
                if w_flags[W - 2]:
                    dp[h][W - 1] += dp[h - 1][W - 2]
                else:
                    dp[h][W - 1] += dp[h - 1][W - 1]
            else:
                if w_flags[w - 1] == True:
                    dp[h][w] += dp[h - 1][w - 1]
                elif w_flags[w] == True:
                    dp[h][w] += dp[h - 1][w + 1]
                else:
                    dp[h][w] += dp[h - 1][w]
            dp[h][w] %= MOD

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

Solution (Python):

import collections
H, W, K = map(int, input().split())
MOD = 10**9 + 7
F = [1,1,2,3,5,8,13,21,34]
c1 = collections.Counter([1])

for i in range(H):
    tmp = collections.Counter()
    for c in c1:
        if c > 1:
            tmp[c-1] += c1[c] * F[max([0, c-2])] * F[W-c]

        tmp[c] += c1[c] * F[c-1] * F[W-c]

        if c < W:
            tmp[c+1] += c1[c] * F[c-1] * F[W-c-1]

    c1 = collections.Counter(tmp)
    



ans = c1[K]
print(ans%MOD)

Solution (Python):
H, W, K = map(int, input().split())
mod = 7 + 10**9
No = [1 for i in range(7)] 
No[1], No[2], No[3], No[4] = 2, 3, 5, 8
No[5], No[6]= 13, 21

if W == 1:
    print(1)
else:
    DP = [[0 for w in range(W)] for h in range(H)]
    DP[0][0], DP[0][1] = No[max(0, W-2)], No[max(0, W-3)]
    for h in range(1, H):
        for w in range(W):
            if w == 0:
                left = 0
                up = DP[h-1][0] * No[max(0, W-2)] % mod
                right = DP[h-1][1] * No[max(0, W-3)] % mod
            elif w == W-1:
                left = DP[h-1][W-2] * No[max(0, W-3)] % mod
                up = DP[h-1][W-1] * No[max(0,W-2)] % mod
                right = 0
            else:
                left = DP[h-1][w-1] * No[max(0, w-2)] * No[max(0, W-w-2)] % mod
                up = DP[h-1][w] * No[max(0, w-1)] * No[max(0, W-w-2)] % mod
                right = DP[h-1][w+1] * No[max(0, w-1)] * No[max(0, W-w-3)] % mod
            DP[h][w] = (left+up+right) % mod
    print(DP[H-1][K-1])

Solution (Python):
def inpl(): return [int(i) for i in input().split()]

H, W, K = inpl()

if W == 1:
    print(1)
else:
    mod = 10**9 + 7
    S = [[0 for _ in range(W)] for _ in range(H+1)]
    S[0][0] = 1
    
    dpy = [0 for _ in range(W-1)]
    dpn = [0 for _ in range(W-1)]
    dpy[0] = 0
    dpn[0] = 1
    dpy = [0]
    dpn = [1]
    for i in range(1,W-1):
        dpy.append(dpn[i-1])
        dpn.append(dpn[i-1] + dpy[i-1])
    dpy = [0]+dpy
    dpn = [0]+dpn
    dp = [dpy[i] + dpn[i] for i in range(W)]
    for i in range(H):
       for j in range(W):
           if j == 0 or j == W-1:
               c = dp[W-1]
           else:
               c = dp[j]*dp[W-j-1]
           S[i+1][j] += c*S[i][j] % mod
           if  j != 0 :
              S[i+1][j-1] += max(1,dp[j-1])*max(1,dp[W-j-1])*S[i][j] %mod
           if j != W-1 :
               S[i+1][j+1] += max(1,dp[j])*max(1,dp[W-j-2])*S[i][j]  %mod
    print(S[H][K-1]%mod)

Solution (Python):
def main():
    """
    input:
        1 <= H <= 100
        1 <= W <= 8
        1 <= K <= W

    output:
        数列の項の最大公約数の最大値
    """
    H, W, K = map(int, input().split())

    
    ans = editorial(H, W, K)
    print(ans)


def editorial(H, W, K):
    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):
            k_max = 1 << (W - 1)
            for k in range(k_max):
                
                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 >= 1 and k >> (j - 1) & 1:  
                    a = j - 1
                elif j <= W - 2 and (k >> j) & 1:  
                    a = j + 1
                else:  
                    a = j

                dp[i + 1][a] += dp[i][j]
                dp[i + 1][a] %= mod

    return dp[H][K - 1]


if __name__ == '__main__':
    main()

Solution (Python):
def d_number_of_amidakuji(H, W, K):
    
    MOD = 10**9 + 7
    fibonacci = [1, 1, 2, 3, 5, 8, 13, 21, 34]  

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

H, W, K = [int(i) for i in input().split()]
print(d_number_of_amidakuji(H, W, K))