Problem:


Score: 400 points

Problem Statement

Amidakuji is a traditional method of lottery in Japan.

To make an amidakuji, we first draw W parallel vertical lines, and then draw horizontal lines that connect them. The length of each vertical line is H+1 [cm], and the endpoints of the horizontal lines must be at 1, 2, 3, ..., or H [cm] from the top of a vertical line.

A valid amidakuji is an amidakuji that satisfies the following conditions:

No two horizontal lines share an endpoint.

The two endpoints of each horizontal lines must be at the same height.

A horizontal line must connect adjacent vertical lines.

Find the number of the valid amidakuji that satisfy the following condition, modulo 1\ 000\ 000\ 007: if we trace the path from the top of the leftmost vertical line to the bottom, always following horizontal lines when we encounter them, we reach the bottom of the K-th vertical line from the left.

For example, in the following amidakuji, we will reach the bottom of the fourth vertical line from the left.

Constraints

H is an integer between 1 and 100 (inclusive).

W is an integer between 1 and 8 (inclusive).

K is an integer between 1 and W (inclusive).

Input

Input is given from Standard Input in the following format:

H W K

Output

Print the number of the amidakuji that satisfy the condition, modulo 1\ 000\ 000\ 007.

Sample Input 1

1 3 2

Sample Output 1

1

Only the following one amidakuji satisfies the condition:

Sample Input 2

1 3 1

Sample Output 2

2

Only the following two amidakuji satisfy the condition:

Sample Input 3

2 3 3

Sample Output 3

1

Only the following one amidakuji satisfies the condition:

Sample Input 4

2 3 1

Sample Output 4

5

Only the following five amidakuji satisfy the condition:

Sample Input 5

7 1 1

Sample Output 5

1

As there is only one vertical line, we cannot draw any horizontal lines. Thus, there is only one amidakuji that satisfies the condition: the amidakuji with no horizontal lines.

Sample Input 6

15 8 5

Sample Output 6

437760187

Be sure to print the answer modulo 1\ 000\ 000\ 007.



Sample input:
1 3 2


Sample output:
1

Submission status: Wrong Answer

Solution code:
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)
    print(DP[H-1][K-1])

Submission status: Wrong Answer

Solution code:
from numpy import matrix

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

F = [[0] * W for i in range(W)] #a→bへの写像の個数

def dfs(i, T, flag):
    if i >= W-1:
        for j, t in enumerate(T):
            F[j][t] += 1
        return None
    
    dfs(i+1, T[:], False)
    if not flag:
        T[i], T[i+1] = T[i+1], T[i]
        dfs(i+1, T[:], True)

dfs(0, [i for i in range(W)], False)

F = matrix(F)
A = matrix([[0] * W for i in range(H+1)]) #(h, w)の場合の数
A.itemset(0, 1)

print((A * F ** H)[:, K-1].sum() % p)

Submission status: Wrong Answer

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

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


def f(x):
    lst = [1, 2, 3, 5, 8, 13, 21]
    if 0 <= x < 7:
        return lst[x]
    else:
        return 1


ptn = [[0] * (w + 2) for _ in range(w + 2)]
for i in range(w + 2):
    for j in range(w + 2):
        if i == 0 or i == w + 1 or j == 0 or j == w + 1:
            continue
        elif i == j:
            ptn[i][j] = f(i-2)*f(w-i-1)
        elif i == j + 1:
            ptn[i][j] = f(i-3)*f(w-i-1)
        elif i == j - 1:
            ptn[i][j] = f(i-2)*f(w-i-2)
print(ptn)


for _ in range(h - 1):
    temp = [[0] * (w + 2) for _ in range(w + 2)]
    for i in range(w + 2):
        for j in range(w + 2):
            if i == 0 or i == w + 1 or j == 0 or j == w + 1:
                continue
            else:
                temp[i][j] = ptn[i-1][j]*f(i-3)*f(w-i-1) + ptn[i][j]*f(i-2)*f(w-i-1) + ptn[i+1][j]*f(i-2)*f(w-i-2)

    ptn = temp; print(ptn)

print(ptn[1][k] % 1000000007)

Submission status: Wrong Answer

Solution code:
import numpy as np
H, W, K = map(int, input().split())
p = 10**9 + 7
r = [1, 1, 2, 3, 5, 8, 13, 21, 34]
dp = np.zeros([H + 1, W], dtype=int)
dp[0, 0] = 1
for h in range(H):
    for w in range(W):
        if w != 0:
            dp[h+1, w] += ((dp[h, w-1] * r[w-1])%p * r[W-1-w])%p
        dp[h+1, w] = ((dp[h, w] * r[w])%p * r[W-1-w])%p
        if w != W-1:
            dp[h+1, w] += ((dp[h, w+1] * r[w])%p * r[W-2-w])%p
        dp[h+1, w] = dp[h+1, w]%p
print(dp[H, K-1])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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


def f(x):
    lst = [1, 2, 3, 5, 7, 13, 19]
    if 0 <= x < 7:
        return lst[x]
    else:
        return 1


ptn = [[0] * (w + 2) for _ in range(w + 2)]
for i in range(w + 2):
    for j in range(w + 2):
        if i == 0 or i == w+1 or j == 0 or j == w+1:
            continue
        elif i == j:
            ptn[i][j] = f(i-2)*f(w-i-1)
        elif i == j + 1:
            ptn[i][j] = f(i-3)*f(w-i-1)
        elif i == j -1:
            ptn[i][j] = f(i-2)*f(w-i-2)
print(ptn)


for _ in range(h - 1):
    temp = [[0] * (w + 2) for _ in range(w + 2)]
    for i in range(w + 2):
        for j in range(w + 2):
            if i == 0 or i == w+1 or j == 0 or j == w+1:
                continue
            else:
                temp[i][j] = ptn[i-1][j]*f(i-3)*f(w-i-1) + ptn[i][j]*f(i-2)*f(w-i-1) + ptn[i+1][j]*f(i-2)*f(w-i-2)

    ptn = temp; print(ptn)

print(ptn[1][k] % 1000000007)

Submission status: Wrong Answer

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

s = [1,1,2,3,6,8,13,21]

def n(a,b,c):
	if c == 0:
		if a == b:
			r = s[b]*s[W-b-1]
		elif a== b+1:
			r = s[b]*s[W-b-2]
		elif a==b-1:
			r = s[b-1]*s[W-b-1]
		else:
			r = 0
	else:
		if b == 0:
			r = n(a,b,c-1)*s[b]*s[W-b-1] + n(a,b+1,c-1)*s[b]*s[W-b-2]
		elif b == W-1:
			r = n(a,b,c-1)*s[b]*s[W-b-1] + n(a,b-1,c-1)*s[b-1]*s[W-b-1]
		else:
			r = n(a,b,c-1)*s[b]*s[W-b-1] + n(a,b+1,c-1)*s[b]*s[W-b-2] + n(a,b-1,c-1)*s[b-1]*s[W-b-1]
	return(r)

ans = n(0,K-1,H-1)%(1000000007)

print(ans)

Submission status: Wrong Answer

Solution code:
"""
https://abc113.contest.atcoder.jp/tasks/abc113_d
"""

FILL = [1, 2]
MOD = 1000000007

def fill_row(size):
  if size < 0 :
    return 0
  elif size < len(FILL):
    return FILL[size]
  else:
    res = (fill_row(size - 1) + fill_row(size - 2)) % MOD # ye its fibonacci
    FILL.append(res) # the other inds should be filled in by the other calls
    return res

def solve(poses, lines, dest):
  table = [[[None for _ in range(lines + 1)] for _ in range(lines + 1)] for _ in range(poses + 1)]

  def _solve_one(poses, curr, dest):
    if poses == 0: # no more rows left to move
      if curr == dest:
        return 1
      else:
        return 0
    elif poses == 1: # just one row left
      if curr == dest: # already in the right spot, no need to move
        return fill_row(curr - 1) + fill_row(lines - curr - 2) # |?|?| | |?|?|
      elif curr == dest - 1: # move one the the right
        return fill_row(curr - 1) + fill_row(lines - curr - 3) # |?|?| |-| |?|
      elif curr == dest + 1: # one to the left
        return fill_row(curr - 2) + fill_row(lines - curr - 2) # |?| |-| |?|?|
      else:
        return 0
    else:
      res = solve_one(poses - 1, curr, dest) * (fill_row(curr - 1) + fill_row(lines - curr - 2))
      if curr > 0:
        res += solve_one(poses - 1, curr - 1, dest) * (fill_row(curr - 2) + fill_row(lines - curr - 2))
      if curr < lines - 1:
        res += solve_one(poses - 1, curr + 1, dest) * (fill_row(curr - 1) + fill_row(lines - curr - 3))
      return res
  
  def solve_one(poses, curr, dest):
    if table[poses][curr][dest] is None:
      table[poses][curr][dest] = _solve_one(poses, curr, dest)
    return table[poses][curr][dest]
  
  return solve_one(poses, 0, dest)

h, w, k = map(int, input().split())
print(solve(h, w, k - 1))

Submission status: Wrong Answer

Solution code:
H, W, K = map(int, input().split())
D = dict()
pattern = ['']

for i in range(W-1):
    new_pattern = []
    for p in pattern:
        if p == '' or p[-1] == '0':
            new_pattern.append(p + '1')
            new_pattern.append(p + '0')
        elif p[-1] == '1':
            new_pattern.append(p + '0')
    pattern = new_pattern

pattern_count = dict()

for i in range(0, W):
    if i - 1 < 0:
        pattern_count[(i, i-1)] = 0
    else:
        pattern_count[(i, i-1)] = len([p for p in pattern if p[i-1] == '1'])

    if i - 1 < 0 and i + 1 >= W:
        pattern_count[(i, i)] = 1
    elif i - 1 < 0:
        pattern_count[(i, i)] = len([p for p in pattern if p[i] != '1'])
    elif i + 1 >= W-1:
        pattern_count[(i, i)] = len([p for p in pattern if p[i-1] != '1'])
    else:
        pattern_count[(i, i)] = len([p for p in pattern if p[i-1] != '1' and p[i] != '1'])

    if i + 1 >= W:
        pattern_count[(i, i+1)] = 0
    else:
        pattern_count[(i, i+1)] = len([p for p in pattern if p[i] == '1'])


def f(h, w, k):
    if (h, w, k) in D.keys():
        return D[(h, w, k)]

    if k < 1 or k > W:
        return 0

    if h <= 0:
        if k == 1:
            return 1
        else:
            return 0

    result = 0

    p_l = f(h-1, w, k-1)
    p_m = f(h-1, w, k)
    p_r = f(h-1, w, k+1)

    result += (p_l * pattern_count[(k-1, k-2)])
    result += (p_m * pattern_count[(k-1, k-1)])
    result += (p_r * pattern_count[(k-1, k)])
    result = result % 1000000007

    D[(h, w, k)] = result

    return result

print(f(H, W, K))

Submission status: Wrong Answer

Solution code:
from itertools import product

MOD = 10 ** 9 + 7

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

pats = []
for pat in product(range(2), repeat=(W - 1)):
    for i in range(W - 2):
        if pat[i] and pat[i + 1]:
            break
    else:
        pats.append(pat)

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

for i in range(H):
    for pat in pats:
        for j in range(W - 1):
            if pat[j] == 0:
                # 横線なし
                dp[i + 1][j] += dp[i][j]
                dp[i + 1][j + 1] += dp[i][j + 1]
            else:
                # 横線あり
                dp[i + 1][j] += dp[i][j + 1]
                dp[i + 1][j + 1] += dp[i][j]
    for j in range(W):
        dp[i + 1][j] %= MOD

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

Submission status: Wrong Answer

Solution code:
quotient = 1000000007

def main():
    H, W, K = list(map(int, input().rstrip().split()))
    if W == 1:
        print(1)
        return
    
    upstream_k = [0]
    for h in range(H):
        temp_list = []
        for k in upstream_k:
            temp_list.append(k)
            if k > 0: # 左にシフト可能
                temp_list.append(k-1)
            if k < W-1:
                temp_list.append(k+1)
        upstream_k = temp_list
    
    num = upstream_k.count(K-1)
    
    #  無関係なノードの可能性
    ind_num = W - K
    if ind_num == 2:
        a = 2 ** H - 1
        num += a
    
    print(num % quotient)
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np

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

if w == 1:
    print(1)
    
elif w == 2:
    a = (1, 1)
    b = (1, 1)
    nex = [a, b]
elif w == 3:
    a = (2, 1, 0)
    b = (1, 1, 1)
    c = (0, 1, 2)
    nex = [a, b, c]
elif w == 4:
    a = (3, 2, 0, 0)
    b = (2, 2, 1, 0)
    c = tuple(reversed(b))
    d = tuple(reversed(a))
    nex = [a, b, c, d]
elif w == 5:
    a = (5, 3, 0, 0, 0)
    b = (3, 3, 2, 0, 0)
    c = (0, 2, 4, 2, 0)
    d = tuple(reversed(b))
    e = tuple(reversed(a))
    nex = [a, b, c, d, e]
elif w == 6:
    a = (8, 5, 0, 0, 0, 0)
    b = (5, 5, 3, 0, 0, 0)
    c = (0, 3, 6, 4, 0, 0)
    d = tuple(reversed(c))
    e = tuple(reversed(b))
    f = tuple(reversed(a))
    nex = [a, b, c, d, e, f]
elif w == 7:
    a = (13, 8, 0, 0, 0, 0, 0)
    b = (8, 8, 5, 0, 0, 0, 0)
    c = (0, 5, 10, 4, 0, 0, 0)
    d = (0, 0, 4, 6, 4, 0, 0)
    e = tuple(reversed(c))
    f = tuple(reversed(b))
    g = tuple(reversed(a))
    nex = [a, b, c, d, e, f, g]
else:
    a = (21, 13, 0, 0, 0, 0, 0, 0)
    b = (13, 13, 8, 0, 0, 0, 0, 0)
    c = (0, 8, 16, 10, 0, 0, 0, 0)
    d = (0, 0, 10, 15, 9, 0, 0, 0)
    e = tuple(reversed(d))
    f = tuple(reversed(c))
    g = tuple(reversed(b))
    h1 = tuple(reversed(a))
    nex = [a, b, c, d, e, f, g, h1]

if w != 1:
    nex = np.array(nex)
    num = [0 for _ in range(w)]
    num[k-1] = 1
    num = np.array(num)
    cache = np.array([0 for _ in range(w)])

    for i in range(h):
        for j in range(w):
            cache[j] = np.dot(nex[j], num) % 1000000007
        num = cache

    print(num[0])

Submission status: Wrong Answer

Solution code:
# your code goes here
mp={-2:1,-1:1,0:1}
def func(xx,mp):
    if mp.get(xx,0) : return mp[xx]
    mp[xx]=(func(xx-1,mp)+func(xx-2,mp))%1000000007
    return mp[xx]
h,w,k= map(int, input().split())
if w == 1:
    print('1')
    exit(0)
DT = [0 for i in range(w)]
CR =  [0 for i in range(w)]
DT [0]=1
#print(sum(DT),sum(CR))
for _ in range(h):
    for i in range(w-2):
        CR[i]+=DT[i+1]*func(w-4,mp)
        CR[i+1]+=DT[i+1]*func(w-3,mp)
        CR[i+2]+=DT[i+1]*func(w-4,mp)
    CR[0]+=DT[0]*func(w-2,mp)
    CR[1]+=DT[0]*func(w-3,mp)
    CR[-2]+=DT[-1]*func(w-3,mp)
    CR[-1]+=DT[-1]*func(w-2,mp)
    for i in range(w):
        DT[i]=CR[i]%1000000007
        CR[i]=0
    #print(sum(DT))
    #print(DT)
print(DT[k-1])

Submission status: Wrong Answer

Solution code:
import numpy as np
(H, W, K) = map(int, input().split())
M = 1000000007
F = np.zeros((H+1,W+2),dtype=np.int64)

F[0,1] = 1
for h in range(1,H+1):
    for w in range(1,W+1):
        if w==1 or w==W:
            c = W-1 + (W==1)
        else:
            c = W-2
        F[h,w] = (F[h-1,w-1] + F[h-1,w+1] + F[h-1,w]*c) % M
print(F[H,K])

Submission status: Wrong Answer

Solution code:
M = 10 ** 9 + 7

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

    init_fib(w)

    dp = [[None for _ in range(w)] for _ in range(h + 1)]
    for i in range(w):
        dp[0][i] = 0
    dp[0][k] = 1

    for i in range(1, h + 1):
        for j in range(w):
            x = 0
            if j != 0 and dp[i-1][j-1] != 0:
                left = j - 1
                right = w - j - 1
                t = fib(left) * fib(right) % M
                x += t * dp[i-1][j-1] % M
            if j + 1 < w and dp[i-1][j+1] != 0:
                left = j
                right = w - j - 2
                t = fib(left) * fib(right) % M
                x += t * dp[i-1][j+1] % M

            if dp[i-1][j] != 0:
                left = j
                right = w - j - 1
                t = fib(left) * fib(right) % M
                x += t * dp[i-1][j] % M
            
            dp[i][j] = x

    print(dp[h][0])

T = []
def init_fib(n):
    global T
    T.append(1)
    T.append(1)

    for i in range(2, n + 1):
        T.append(T[-1] + T[-2])

def fib(n):
    return T[n]

main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
A = [1, 2, 3, 5, 8, 13, 21]
MOD = 10**9 + 7
H, W, K = map(int, input().split())
W -= 1
K -= 1
if W == 0:
    if K in [0, 1]:
        print(1)
    else:
        print(0)
    exit()
dp = [[0] * (W + 1) for _ in range(H + 1)]
dp[0][0] = 1
for i in range(1, H + 1):
    for j in range(i + 1):
        for k in [-1, 0, 1]:
            if j + k < 0 or W <= j + k: continue
            if j < 0 or W < j: continue
            if k == -1:
                left = max(0, j - 2 - 1)
                right = max(0, W - j - 1)
            elif k == 0:
                left = max(0, j - 2)
                right = max(0, W - j - 1)
            elif k == 1:
                left = max(0, j - 2)
                right = max(0, W - j - 1 - 1)
            dp[i][j] += dp[i - 1][j + k] * A[left] * A[right]
print(dp[H][K] % MOD)

Submission status: Wrong Answer

Solution code:
def com(x,y):
    a=1
    b=1
    y=min(y,x-y)
    for i in range(x,x-y,-1):
        a*=i
    for i in range(1,y+1):
        b*=i
    return a//b
def cal(x):
    res=1+x
    for i in range(1,(x+1)//2):
        res+=com(x-i,i+1)
    return res
    
h,w,k=map(int,input().split())
if h+1<k:
    print(0)
elif w==1:
    print(1)
else:
    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):
            #print(i,j)
            dp[i+1][j]+=dp[i][j]*(cal(j-1)+cal(w-j-2))
            #print(cal(j-1),cal(w-j-2),0)
            if j+1<w:
                dp[i+1][j+1]+=dp[i][j]*(cal(j-1)+cal(w-j-3))
                #print(dp[i+1][j+1],i+1,j+1)
                #print(cal(j-1),cal(w-j-3))
            if j-1>=0:
                dp[i+1][j-1]+=dp[i][j]*(cal(j-2)+cal(w-j-2))
                #print(cal(j-2),cal(w-j-2),1)
            #print(dp)
    print(dp[h][k-1]%(10**9+7))

Submission status: Wrong Answer

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

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

multi = [
  1, # 0
  2, # 1
  3, # 2
  5, # 3
  8, # 4
  13,# 5
  20 # 6
]

def f(num, l, r):
  left = max(0, l)
  right = num-1 - min(r, num-1)
  return multi[left] * multi[right]

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

print(dp[H][0])

Submission status: Wrong Answer

Solution code:
H, W, K = map(int, input().split())
mod = 10 ** 9 + 7
inv_3 = 333333336
F = [1, 1, 2, 3, 5, 8, 13, 21, 34]

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

if W > 1:
    for h in range(1, H + 1):
        for w in range(min(h + 1, W)):
            if w == 0:
                P[h][w] = (P[h - 1][w] * 2 + P[h - 1][w + 1]) * inv_3 % mod
            elif w == W - 1:
                P[h][w] = (P[h - 1][w - 1] + P[h - 1][w] * 2) * inv_3 % mod
            else:
                P[h][w] = (P[h - 1][w - 1] + P[h - 1][w] + P[h - 1][w + 1]) * inv_3 % mod

    print(P[H][K - 1] * pow(F[W], H, mod) % mod)
else:
    print(1)

Submission status: Wrong Answer

Solution code:
from itertools import product
import numpy as np
MOD = 1000000007

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

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

for n in range(2**(W-1)):
  memo = [0]*W
  for i,e in enumerate(map(lambda x: x=='1',bin(n)[:1:-1])):
    if e:
      if memo[i] == 0:
        memo[i] = 1
        memo[i+1] = -1
      else:
        memo = None
        break

  if memo is not None:
    for i,d in enumerate(memo):
      transition[i][i+d] += 1


transition = np.array(transition,dtype=np.int64) % MOD


dp = np.zeros((W,1),dtype=np.int64)
dp[0,0] = 1
for b in map(lambda x: x=='1', bin(H)[:1:-1]):
  if b:
    np.dot(transition, dp, out=dp)
    dp %= MOD
  np.dot(transition, transition, out=transition)
  transition %= MOD

print(dp[K,0])

Submission status: Wrong Answer

Solution code:
M = 10 ** 9 + 7

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

    init_fib(w)

    dp = [[None for _ in range(w)] for _ in range(h + 1)]
    for i in range(w):
        dp[0][i] = 0
    dp[0][k] = 1

    for i in range(1, h + 1):
        for j in range(w):
            x = 0
            if j != 0 and dp[i-1][j-1] != 0:
                left = j - 1
                right = w - j - 1
                t = fib(left) * fib(right) % M
                x += t * dp[i-1][j-1] % M
            if j + 1 < w and dp[i-1][j+1] != 0:
                left = j
                right = w - j - 2
                t = fib(left) * fib(right) % M
                x += t * dp[i-1][j+1] % M

            left = j
            right = w - j - 1
            t = fib(left) * fib(right) % M
            x += t * dp[i-1][j] % M
            
            dp[i][j] = x

    print(dp[h][0])

T = []
def init_fib(n):
    global T
    T.append(1)
    T.append(1)

    for i in range(2, n + 1):
        T.append(T[-1] + T[-2])

def fib(n):
    return T[n]

main()

Submission status: Wrong Answer

Solution code:
print(1)

Submission status: Wrong Answer

Solution code:
H, W, K = map(int, input().split())
D = dict()
pattern = ['']

for i in range(W-1):
    new_pattern = []
    for p in pattern:
        if p == '' or p[-1] == '0':
            new_pattern.append(p + '1')
            new_pattern.append(p + '0')
        elif p[-1] == '1':
            new_pattern.append(p + '0')
    pattern = new_pattern

pattern_count = dict()

for i in range(0, W):
    if i - 1 < 0:
        pattern_count[(i, i-1)] = 0
    else:
        pattern_count[(i, i-1)] = len([p for p in pattern if p[i-1] == '1'])

    if i - 1 < 0 and i + 1 >= W:
        pattern_count[(i, i)] = 1
    elif i - 1 < 0:
        pattern_count[(i, i)] = len([p for p in pattern if p[i] != '1'])
    elif i + 1 >= W-1:
        pattern_count[(i, i)] = len([p for p in pattern if p[i-1] != '1'])
    else:
        pattern_count[(i, i)] = len([p for p in pattern if p[i-1] != '1' and p[i] != '1'])

    if i + 1 >= W:
        pattern_count[(i, i+1)] = 0
    else:
        pattern_count[(i, i+1)] = len([p for p in pattern if p[i] == '1'])


def f(h, w, k):
    if (h, w, k) in D.keys():
        return D[(h, w, k)]

    if k < 1 or k > W:
        return 0

    if h <= 0:
        if k == 1:
            return 1
        else:
            return 0

    result = 0

    p_l = f(h-1, w, k-1)
    p_m = f(h-1, w, k)
    p_r = f(h-1, w, k+1)

    if p_l > 0:
        result += (p_l * pattern_count[(k-1, k-2)])
        result = result % 1000000007
    if p_m > 0:
        result += (p_m * pattern_count[(k-1, k-1)])
        result = result % 1000000007
    if p_r > 0:
        result += (p_r * pattern_count[(k-1, k)])
        result = result % 1000000007

    D[(h, w, k)] = result

    return result

print(f(H, W, K))

Submission status: Wrong Answer

Solution code:
print(0)

Submission status: Wrong Answer

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

S = [0]*W
S[0] = 1
if W > 1:
    for i in range(H):
        T = [0]*W
        for P in product((0, 1), repeat=W-1):
            if any(P[i] == P[i+1] == 1 for i in range(W-2)):
                continue
            for i in range(W-1):
                if P[i]:
                    T[i+1] += S[i]
                    T[i] += S[i+1]
                else:
                    T[i] += S[i]
            if not P[W-2]:
                T[W-1] += S[W-1]
        S = T
        for i in range(W):
            S[i] %= MOD
print(S[K-1])

Submission status: Wrong Answer

Solution code:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict, Counter
from bisect import bisect
import functools

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

H, W, K = reads()
P = 10**9 + 7

M = W + 100
fib = [0] * M
fib[0] = fib[1] = 1
for i in range(M-2):
  fib[i+2] = (fib[i] + fib[i+1]) % P

@functools.lru_cache(100000)
def solve(h, k):
  if h == 0:
    return 1 if k == 1 else 0
  if k == 1:
    return (solve(h-1, 1) * fib[W-1] + solve(h-1, 2) * fib[W-2]) % P
  elif k == W:
    return (solve(h-1, W) * fib[W-1] + solve(h-1, W-1) * fib[W-2]) % P
  else:
    return (solve(h-1, k) * fib[k-1] * fib[W-k]
      + solve(h-1, k-1) * fib[k-2] * fib[W-k]
      + solve(h-1, k+1) * fib[k-1] * fib[W-k-1]) % P

print(solve(H, K))

Submission status: Time Limit Exceeded

Solution code:
# coding: UTF-8
import sys
#sys.setrecursionlimit(n)
import heapq
import re
import bisect
import random
import math
import itertools
from collections import defaultdict, deque
from copy import deepcopy
from decimal import *

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 memo[x][y]:
        return memo[x][y]
#    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))

Submission status: Time Limit Exceeded

Solution code:
def solve(string):
    h, w, k = map(int, string.split())
    c = [1, 1]
    for _ in range(1, 7):
        i, j = c[-2:]
        c.append(i + j)

    def rec(pos, depth):
        if depth == h:
            return 1 if pos == 1 else 0
        ans = rec(pos, depth + 1) * c[pos - 1] * c[w - pos]
        if pos < w:
            ans += rec(pos + 1, depth + 1) * c[pos - 1] * c[w - pos - 1]
        if pos > 1:
            ans += rec(pos - 1, depth + 1) * c[pos - 2] * c[w - pos]
        return ans

    return str(rec(k, 0) % (10**9 + 7))


if __name__ == '__main__':
    print(solve(input()))

Submission status: Time Limit Exceeded

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

def dfs(i, j):
    cnt = 0
    if i == h + 1:
        if j == k:
            return 1
        else:
            return 0
    if j == 1:
        cnt += dfs(i + 1, j) 
        cnt += dfs(i + 1, j + 1)
    elif j == w:
        cnt +=  dfs(i + 1, j) 
        cnt += dfs(i + 1, j - 1)
    else:
        cnt += dfs(i + 1, j)
        cnt += dfs(i + 1, j + 1) 
        cnt += dfs(i + 1, j - 1)        
    return cnt

if w == 1:
    print(1)
else:
    print(dfs(0, 0) % mod)

Submission status: Time Limit Exceeded

Solution code:
def compute_patterns(n):
    memo = {}
    def compute(n):
        if n in memo:
            return memo[n]
        if n == 2:
            return 2
        if n <= 1:
            return 1
        ret = compute(n-1) + compute(n-2)
        memo[n] = ret
        return ret
    return compute(n)


def gen_patterns(c, h, w, k):
    if h == 1:
        if c == k:
            yield [(c-1, w-c)]
        elif c+1 == k:
            yield [(c-1, w-c-1)]
        elif c-1 == k:
            yield [(c-2, w-c)]
        else:
            yield None
    else:
        for p in gen_patterns(c, h-1, w, k):
            if p is None:
                yield None
            else:
                yield [(c-1, w-c)] + p
        if c != 1:
            for p in gen_patterns(c-1, h-1, w, k):
                if p is None:
                    yield None
                else:
                    yield [(c-2, w-c)] + p
        if c != w:
            for p in gen_patterns(c+1, h-1, w, k):
                if p is None:
                    yield None
                else:
                    yield [(c-1, w-c-1)] + p


def main():
    H, W, K = list(map(int, input().split(' ')))
    ret = 0
    for p in gen_patterns(1, H, W, K):
        if p is None:
            continue
        r = 1
        for i in range(len(p)):
            r *= compute_patterns(p[i][0])
            r %= 1000000007
            r *= compute_patterns(p[i][1])
            r %= 1000000007
        ret += r
    print(ret % 1000000007)



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
S = list(map(int,input().split()))
H = S[0]
W = S[1]
K = S[2]

def f(h,w,k):
    fib = [1,2,3,5,8,13,21,34,55,1]
    if h == 0 and k == 1:
        return 1
    elif h == 0 and not k == 1:
        return 0
    else:
        if not(k == 1 or k == w):
            return (fib[w-k-1]*fib[k-3]*f(h-1,w,k-1) + fib[k-1]*fib[w-k-1]*f(h-1,w,k) + fib[k-1]*fib[w-k-2]*f(h-1,w,k))
        elif k==1:
            return (fib[w-2]*f(h-1,w,k) + fib[w-3]*f(h-1,w,k+1))
        elif k == w:
            return (fib[w-3]*f(h-1,w,k-1) + fib[w-2]*f(h-1,w,k))

if W == 1:
    answer = 1
else:
    answer = f(H,W,K) % 1000000007
print(answer)

Submission status: Time Limit Exceeded

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

honsu=w


a = 0
def amida(h,w):
  global a
  if h == 0 and w == k:
    return 1
  if h ==0:
    return 0
  if not(1<=w<=honsu):
    return 0
  com1 = fib(honsu-w+1)*fib(w-1)*amida(h-1,w-1)
  com2 = fib(honsu-w+1)*fib(w)*amida(h-1,w) 
  com3 = fib(honsu-w)*fib(w)*amida(h-1,w+1)   
  
  return com1+com2+com3
  
fib_memo = {}
def fib(n):
    if n < 3: return 1
    if n not in fib_memo:
        fib_memo[n] = fib(n-1) + fib(n-2)
    return fib_memo[n]

print(amida(h,1)%1000000007)

Submission status: Time Limit Exceeded

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

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

mod=1000000007
    
def f(H,K):
    if H==0:
        if K==1:
            return 1
        else:
            return 0
    else:
        if K==0 or K==W+1:
            return 0
        else:
            return (f(H-1,K)*fibo[K-1]*fibo[W-K]\
                    +f(H-1,K-1)*fibo[K-2]*fibo[W-K]\
                    +f(H-1,K+1)*fibo[K-1]*fibo[W-K-1])%mod
            
print f(H,K)

Submission status: Time Limit Exceeded

Solution code:
h, w, k = map(int, raw_input().split())
arr = [1, 2, 3, 5, 8, 13, 21, 34]


def p(num):
    return max(0, num)


def dp(i, j):

    if i == 0:
        if j == 0:
            r = 1
        else:
            r = 0
    else:
        y = dp(i - 1, j)
        if j - 1 < 0:
            x = 0
        else:
            x = dp(i - 1, j - 1)
        if j + 1 > w - 1:
            z = 0
        else:
            z = dp(i - 1, j + 1)
        r = x * arr[p(j-2)] * arr[p(w-j-2)] + \
            y * arr[p(j-1)] * arr[p(w-j-2)] + \
            z * arr[p(j-1)] * arr[p(w-j-3)]

    return r % (10**9+7)

print dp(h, k-1)

Submission status: Time Limit Exceeded

Solution code:
a,b,c=map(int,input().split())
e=0
f=[[1,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],[12,8,8,5,10,6,9,6,10,5,8,8,12],[21,13,13,8,16,10,15,9,15,10,16,8,13,13,21]]
if b==1:
    print(1)
else:
    d=k[b-2]
    for i in range(0,a):
        l=len(f)
        for j in range(0,l):
            f.append([f[j][0],f[j][1]*d[2*(f[j][0]-1)]])
            if f[j][0]-1>0 and f[j][0]-1>=c-(a-i):
                f.append([f[j][0]-1,f[j][1]*d[1+2*(f[j][0]-2)]])
            if f[j][0]+1<=b and f[j][0]+1<=c+(a-i):
                f.append([f[j][0]+1,f[j][1]*d[2*(f[j][0]-1)+1]])
            j+=1
        else:
            del f[:l]
    else:
        for i in range(0,len(f)):
            if f[i][0]==c:
                e+=f[i][1]
        print(e%(10**9+7))