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:
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)


memo = {}

def gen_patterns(c, h, w, k):
    if (c, h) in memo:
        yield memo[(c,h)]
    elif 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:
                memo[(c,h)] = [(c-1, w-c)] + p
                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:
                    memo[(c,h)] = [(c-2, w-c)] + p
                    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:
                    memo[(c,h)] = [(c-1, w-c-1)] + p
                    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: Wrong Answer

Solution code:
import itertools
h,W,K = map(int, input().split())
k = K-1
w = W-1
if k > h * (w // 2 + w % 2):
  print(0)
p = [list(i) for i in list(itertools.permutations(range(W), W)) if i[k] == 0]
print(len(p))

Submission status: Wrong Answer

Solution code:
from functools import lru_cache

input_lst = list(map(int, input().split()))
h, w, k = input_lst[0], input_lst[1], input_lst[2]

def row_comb(w):
    if w <= 0:
        return 0
    if w == 1:
        return 1
    if w == 2:
        return 2
    else:
        return row_comb(w-2)+row_comb(w-1)

@lru_cache(maxsize=1000)
def trio(h,w):
    if h == 0:
        return [1] + [0 for i in range(10)]
    else:
        lst = []
        for i in range(1, w+1):
            if i == 1:
                lst.append(trio(h-1,w)[0] * row_comb(w-1) + trio(h-1,w)[1] * row_comb(w-2))
            elif i == w:
                lst.append(trio(h-1,w)[w-1] * row_comb(w-1) + trio(h-1,w)[w-2] * row_comb(w-2))
            elif i == 2:
                lst.append(trio(h-1,w)[0] * row_comb(w-2) + trio(h-1,w)[2] * row_comb(w-3) + trio(h-1,w)[1] * row_comb(w-2))
            elif i == w-1:
                lst.append(trio(h-1,w)[w-1] * row_comb(w-2) + trio(h-1,w)[w-3] * row_comb(w-3) + trio(h-1,w)[w-2] * row_comb(w-2))
            elif i > 2 and i < w-1:
                a = row_comb(i-2) * row_comb(w-i)
                b = row_comb(i-1) * row_comb(w-i-1)
                c = row_comb(i-1) * row_comb(w-i)
                lst.append(trio(h-1,w)[i-2] * a + trio(h-1,w)[i] * b + trio(h-1,w)[i-1] * c)
        lst = lst + [0 for i in range(10)]
        return lst
    
print(trio(h, w)[k-1] % 1000000007)

Submission status: Wrong Answer

Solution code:
def main():
    H, W, K = list(map(int, input().split()))
    dp = [[0 for _ in range(W)] for _ in range(H + 1)]
    dp[0][0] = 1

    for i in range(H):
        for j in range(1 << (W - 1)):
            if '11' in bin(j):
                continue
            j <<= 1
            for w in range(W):
                if j & (1 << w):
                    dp[i + 1][w] += dp[i][w - 1]
                elif j & (1 << (w + 1)):
                    dp[i + 1][w] += dp[i][w + 1]
                else:
                    dp[i + 1][w] += dp[i][w]
                dp[i + 1][w] %= (10 ** 9 + 7)

    for a in dp:
        print(a)
    print(dp[H][K - 1])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    H, W, K = list(map(int, input().split()))
    dp = [[0 for _ in range(W)] for _ in range(H + 1)]
    dp[0][0] = 1

    for i in range(H):
        for j in range(1 << (W - 1)):
            if '11' in bin(j):
                continue
            j <<= 1
            for k in range(W):
                if j & (1 << k):
                    dp[i + 1][k] += dp[i][k - 1]
                elif j & (1 << (k + 1)):
                    dp[i + 1][k] += dp[i][k + 1]
                else:
                    dp[i + 1][k] += dp[i][k]
                dp[i + 1][k] %= (10 * 9 + 7)

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Jan  5 10:49:47 2019

@author: Yamazaki Kenichi
"""

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

def r(x):
    if x<=1:
        return 1
    if x==2:
        return 2
    return  r(x-1)+r(x-2)
r1=[r(i) for i in range(W)]
r1.append(1)
r1.append(1)

def n(h,k):
    if h==1:
        if k ==1:
            return r1[W-1]
        elif k == 2:
            return r1[W-2]
        else:
            return 0
    if k == 1:
        return (n(h-1,k)*r1[k-1]*r1[W-k]+n(h-1,k+1)*r1[k-1]*r1[W-k-1])
    elif k <W:
        return n(h-1,k-1)*r1[k-2]*r1[W-k]+n(h-1,k)*r1[k-1]*r1[W-k]+n(h-1,k+1)*r1[k-1]*r1[W-k-1]
    elif k >= W:
        return n(h-1,k-1)*r1[k-2]*r1[W-k]+n(h-1,k)*r1[k-1]*r1[W-k]
print(n(H,K)%1000000007)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
H,W,K = map(int,input().split())
mod = 10**9+7
NOW = defaultdict(int)
VAR = {}
VAR[-2] = 1
VAR[-1] = 1
VAR[0] = 1
VAR[1] = 1
VAR[2] = 2
for i in range(3,W+1) :
    VAR[i] = VAR[i-1]+VAR[i-2]
NOW[1] = 1
for i in range(H) :
    NEXT = defaultdict(int)
    for j in NOW :
        if (j <= 0) or (j > W) :
            continue
        x = NOW[j]
        NEXT[j-1] = (NEXT[j-1]+x*VAR[j-2]*VAR[W-j])%mod
        NEXT[j] = (NEXT[j]+VAR[j-1]*VAR[W-j])%mod
        NEXT[j+1] = (NEXT[j+1]+VAR[j-1]*VAR[W-j-1])%mod
    NOW = NEXT
print(NOW[K]%mod)

Submission status: Wrong Answer

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

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


dp[0][1]=1


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

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

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

Submission status: Wrong Answer

Solution code:
mod=1000000007
def fibo(a):
    if a==0:
        return 1
    elif a==1:
        return 2
    else:
        return fibo(a-1)+fibo(a-2)

def amida(h,w,H,W,K,dp):
    j=0
    i=0
    k=0
    if h>=0 and dp[h][w]!=-1:
        return dp[h][w]
    else:
        if (W-4)>=0:
            j=fibo(W-3)
            i=fibo(W-2)
        if W==1:
            k=1
        if h>=0 and (H+1-h)>=abs(K-w):
            if w==1:
                if h==1:
                    dp[h][w]=k+i
                    return dp[h][w]%mod
                elif h==0:
                    dp[h][w]=1
                    return dp[h][w]
                elif w==W:
                    dp[h][w]=amida(h-1,w,H,W,K,dp)%mod
                    return dp[h][w]
                else:
                    dp[h][w]=(amida(h-1,w,H,W,K,dp)+amida(h-1,w+1,H,W,K,dp)+i)%mod
                    return dp[h][w]
            elif w==W:
                if w==1:
                    dp[h][w]=amida(h-1,w,H,W,K,dp)
                    return dp[h][w]%mod
                else:
                    dp[h][w]=(amida(h-1,w,H,W,K,dp)+amida(h-1,w-1,H,W,K,dp)+i)%mod
                    return dp[h][w]
            else:
                dp[h][w]=(amida(h-1,w,H,W,K,dp)+amida(h-1,w+1,H,W,K,dp)+amida(h-1,w-1,H,W,K,dp)+j)%mod
                return dp[h][w]
        else:
            return 0

H,W,K=map(int,input().split())
dp=[[-1 for j in range(W+1)]for i in range(H+1)]
print(amida(H,K,H,W,K,dp)%mod)

Submission status: Wrong Answer

Solution code:
def fibo(a):
    if a==0:
        return 1
    elif a==1:
        return 2
    else:
        return fibo(a-1)+fibo(a-2)

def amida(h,w,H,W,K,dp):
    j=0
    i=0
    k=0
    if h>=0 and dp[h][w]!=-1:
        return dp[h][w]
    else:
        if (W-3)>0:
            j=fibo(W-3)
            i=fibo(W-2)
        if (W-3)==0 and w!=W:
            i=2
        if w==W:
            k=1
        if h>=0 and (H+1-h)>=abs(K-w):
            if w==1:
                if h==1:
                    dp[h][w]=k+i
                    return dp[h][w]
                elif h==0:
                    dp[h][w]=1
                    return dp[h][w]
                elif w==W:
                    dp[h][w]=amida(h-1,w,H,W,K,dp)
                    return dp[h][w]
                else:
                    dp[h][w]=amida(h-1,w,H,W,K,dp)+amida(h-1,w+1,H,W,K,dp)+i
                    return dp[h][w]
            elif w==W:
                if w==1:
                    dp[h][w]=amida(h-1,w,H,W,K,dp)
                    return dp[h][w]
                else:
                    dp[h][w]=amida(h-1,w,H,W,K,dp)+amida(h-1,w-1,H,W,K,dp)+i
                    return dp[h][w]
            else:
                dp[h][w]=amida(h-1,w,H,W,K,dp)+amida(h-1,w+1,H,W,K,dp)+amida(h-1,w-1,H,W,K,dp)+j
                return dp[h][w]
        else:
            return 0

H,W,K=map(int,input().split())
dp=[[-1 for j in range(W+1)]for i in range(H+1)]
print(amida(H,K,H,W,K,dp))

Submission status: Wrong Answer

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

if W == 1:
    print(1)

else:

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

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

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

Submission status: Wrong Answer

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

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

mod = 1000000007

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

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

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

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

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

Submission status: Wrong Answer

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

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

mod = 1000000007

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
height, width, k = map(int, input().split())

ans = [[0] * (width + 2) for i in range(height + 1)]
start_w = 1
end_w = width
start_h = 0
ans[start_h][start_w] = 1
search_range = start_w + 1 if end_w > 1 else 1
f = [0] * (width + 2)
f[0], f[1], f[2] = 1, 1, 1


def det_unused(n, m=0):
    front = n - (start_w + 1)
    rear = end_w - (n + 1)

    if m == -1:
        front -= 1
    elif m == 1:
        rear -= 1

    ret = int(calc(front) * calc(rear))
    return ret


def calc(n):
    if n < 1:
        return 1
    return calc_f(n+2)


def calc_f(n):
    if f[n] == 0:
        f[n] = calc_f(n - 1) + calc_f(n - 2)
    return f[n]


for h in range(1, height + 1):
    for w in range(1, search_range + 1):
        prev_ans = ans[h - 1]
        ans[h][w] = prev_ans[w] * det_unused(w) + prev_ans[w - 1] * det_unused(w, -1) + prev_ans[w + 1] * det_unused(w, 1)
    if search_range < end_w:
        search_range += 1

print(ans[height][k])

Submission status: Wrong Answer

Solution code:
MOD = 1000000007


def main():
    H, W, K = map(int, input().split())
    dp = [[0] * W] * (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 (ok):
                    if 1 <= j and (k >> (j - 1)) & 1:
                        dp[i + 1][j - 1] = dp[i + 1][j - 1] + dp[i][j] % MOD
                    elif j <= W and (k >> (j + 1)) & 1:
                        dp[i + 1][j + 1] = dp[i + 1][j + 1] + dp[i][j] % MOD
                    else:
                        dp[i + 1][j] = dp[i + 1][j] + dp[i][j] % MOD

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

main()

Submission status: Wrong Answer

Solution code:
import itertools

def fibonacci(n):
    if (n == 0):
        f_n = 1
    elif (n == 1):
        f_n = 1
    else:
        f_n = fibonacci(n-1) + fibonacci(n-2)

    return f_n

def X_amida_number(W, W_i):
    x_amida = "0" * (W - 1)
    left_x_amida = x_amida[:(W_i-2)] if(W_i-2 >= 0) else ""
    right_x_amida = x_amida[(W_i+1):]

    return fibonacci(len(left_x_amida) + 1) * fibonacci(len(right_x_amida) + 1)

def Y_amida_number(W, W_i):
    y_amida = "0" * (W - 1)
    left_y_amida = y_amida[:W_i-1] if(W_i-1 >= 0) else ""
    right_y_amida = y_amida[W_i+1:]

    return fibonacci(len(left_y_amida) + 1) * fibonacci(len(right_y_amida) + 1)

def Z_amida_number(W, W_i):
    z_amida = "0" * (W - 1)
    left_z_amida = z_amida[:W_i-1] if(W_i-1 >= 0) else ""
    right_z_amida = z_amida[W_i+2:]

    return fibonacci(len(left_z_amida) + 1) * fibonacci(len(right_z_amida) + 1)

def amida_all(amida_list, W):
    for i, j in itertools.product(range(W), range(3)):
        if(j == 0):
            amida_list[i][j] = X_amida_number(W, i)
        elif(j == 1):
            amida_list[i][j] = Y_amida_number(W, i)
        else:
            amida_list[i][j] = Z_amida_number(W, i)

    return amida_list

H, W, K = map(int, input().split())
amida_list = [[0]*3 for i in range(W)]
amida_list = amida_all(amida_list, W)
print(amida_list)

seed_dp_array = [0 for i in range(W)]
dp_array = [list(seed_dp_array) for i in range(H + 1)]
dp_array[0][0] = 1

for H_i, W_i in itertools.product(range(1, H + 1), range(W)):
    if (W_i == 0):
        if(W == 1):
            dp_array[H_i][0] = dp_array[H_i - 1][W_i] * amida_list[W_i][1]
        else:
            dp_array[H_i][0] = dp_array[H_i - 1][W_i] * amida_list[W_i][1] + dp_array[H_i - 1][W_i + 1] * amida_list[W_i][2]
    elif (W_i == (W - 1)):
        dp_array[H_i][W - 1] = dp_array[H_i - 1][W_i - 1] * amida_list[W_i][0] + dp_array[H_i - 1][W_i] * amida_list[W_i][1]
    else:
        dp_array[H_i][W_i] = dp_array[H_i - 1][W_i - 1] * amida_list[W_i][0] + dp_array[H_i - 1][W_i] * amida_list[W_i][1] + dp_array[H_i - 1][W_i + 1] * amida_list[W_i][2]

print(dp_array[H][K - 1] % 1000000007)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
import copy

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def power_func(a,b,p):
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p

def calc_pattern_num(src, dst, W):
    if W == 1:
        if src == dst :
            return 1
        else:
            return 0

    count = 0
    for i in range(2**(W - 1)):
        is_OK = True
        for j in range((W - 1)):
            if j > 0:
                if ((i >> j) & 0x01)==1 and ((i >> j - 1)& 0x01) == 1:
                    is_OK = False
                    break

            if src - 1 == dst:
                if dst == j:
                    if ((i >> j) & 0x01) == 1:
                        pass
                    else:
                        is_OK = False
                        break
            elif src + 1 == dst:
                if src == j:
                    if ((i >> j) & 0x01) == 1:
                        pass
                    else:
                        is_OK = False
                        break
            elif src == dst:
                if src == j or src - 1 == j:
                    if ((i >> j) & 0x01) == 0 and ((i >> max(0,(j-1))) & 0x01) == 0:
                        pass
                    else:
                        is_OK = False
                        break
        if is_OK == True:
            count += 1
    return count


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [H, W, K] = [long(input_raw[0]), long(input_raw[1]), long(input_raw[2])]
##    field1 = [[[] for i in range(W)] for i in range(H)]
##    for i in range(H):
##        for j in range(W):
##            if j + 1 < W and i % 2 == 0:
##                field1[i][j].append((i, j + 1))
##            if j - 1 >= 0 and i % 2 == 1:
##                field1[i][j].append((i, j - 1))
##            if i + 1 < H:
##                field1[i][j].append((i + 1, j))

    dp = [[0 for j in range(W)] for i in range(H + 1)]
    dp[0][0] = 1
    p = 1000000007
    for i in range(H):
        for j in range(W):
            dp[i + 1][j] = (dp[i + 1][j] + ((calc_pattern_num(j, j, W) * dp[i][j]) % p)) % p
            if j + 1 < W:
                dp[i + 1][j + 1] = (dp[i + 1][j + 1] + ((calc_pattern_num(j, j + 1, W) * dp[i][j]) % p)) % p
            if j - 1 >= 0:
                dp[i + 1][j - 1] = (dp[i + 1][j - 1] + ((calc_pattern_num(j, j - 1, W) * dp[i][j]) % p)) % p

    print dp[H][K - 1]


##    field2 = [[[] for i in range(W)] for i in range(H)]
##    for i in range(H):
##        for j in range(W):
##            if j + 1 < W and i % 2 == 1:
##                field2[i][j].append((i, j + 1))
##            if j - 1 >= 0 and i % 2 == 0:
##                field2[i][j].append((i, j - 1))
##            if i + 1 < H:
##                field2[i][j].append((i + 1, j))
##
##    dp2 = [[0 for j in range(W)] for i in range(H)]
##    dp2[0][0] = 1
##
##    for i in range(H):
##        for j in range(W):
##            for adj in field2[i][j]:
##                dp2[adj[0]][adj[1]] = (dp2[adj[0]][adj[1]] + dp2[i][j]) % (1000000007)
##
##    print power_func(2, (dp1[H -1][K - 1] + dp2[H -1][K - 1]) , 1000000007) - 1


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

for i in range(1,h+1):
    for j in range(w):
        if j==0:
            mat[i][j]=mat[i-1][j]+mat[i-1][j+1]
        elif j==w-1:
            mat[i][j]=mat[i-1][j]+mat[i-1][j-1]
        else:
            mat[i][j]=mat[i-1][j]+mat[i-1][j-1]+mat[i-1][j+1]

print(mat[h-1][k-1] % 1000000007)

Submission status: Wrong Answer

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

lis = [0]*(w-1)
n = 0
for i in range(2**(w-1)):
    
    tmp = bin(i)[2:].zfill(w-1)
    if '11' in tmp:continue
    n += 1
    for j in range(w-1):
        lis[j] += int(tmp[j])


res = [1]+[0]*(w-1)
for i in range(h):
    res2 = res.copy()
    for j in range(w):
        if j == 0:
            a=0
            x = 0
        else:
            a = lis[j-1]
            x = res[j-1]
        if j== w-1:
            b = 0
            y = 0
        else:
            b = lis[j]
            y = res[j+1]
        res2[j] = x*a + res[j]*(n - a - b) + y*b
    res = res2
print(res[k-1])

Submission status: Wrong Answer

Solution code:
high,wide,end=map(int,input().split())

dp=[[[-1,-1,-1] for i in range(wide)] for j in range(high)]

#fit 0
wide-=1
high-=1
end-=1
def NegativeZero(x):
    if x<0:
        return 0
    else:
        return x

def MakePatternLeft(y):
    return pow(2,NegativeZero(y-1))

def MakePatternRight(z):
    return pow(2,NegativeZero(wide-z-1))


def amida(h,w,f):
    dp[h][w][2]=MakePatternLeft(w)*MakePatternRight(w)
    if f == 1: #go straight
        if h==high and w==end:
            dp[h][w][f]=1
        elif h==high:
            dp[h][w][f]=0
        else: #sum under
            if dp[h+1][w][1] == -1:
                amida(h+1,w,1)
            if dp[h+1][w][0] == -1:
                amida(h+1,w,0)
            dp[h][w][f]=dp[h+1][w][0]+dp[h+1][w][1]*dp[h+1][w][2]
    else: #f==0 go side
        dp[h][w][f]=0
        if w-1>=0: #sum left
            if dp[h][w-1][1]==-1:
                amida(h,w-1,1)
            dp[h][w][f]+=dp[h][w-1][1]*MakePatternLeft(w-1)*MakePatternRight(w)
        if w+1<=wide: #sum right
            if dp[h][w+1][1]==-1:
                amida(h,w+1,1)
            dp[h][w][f]+=dp[h][w+1][1]*MakePatternLeft(w)*MakePatternRight(w+1)


amida(0,0,0)
amida(0,0,1)

print((dp[0][0][0]+dp[0][0][1]*dp[0][0][2])%1000000007)

Submission status: Wrong Answer

Solution code:
high,wide,end=map(int,input().split())

dp=[[[-1,-1,-1] for i in range(wide)] for j in range(high)]

#fit 0
wide-=1
high-=1
end-=1
def NegativeZero(x):
    if x<0:
        return 0
    else:
        return x

def MakePatternLeft(y):
    if y==0:
        return pow(2,0) 
    if y==1:
        return pow(2,0) 
    else:
        return pow(2,NegativeZero(y-2))

def MakePatternRight(z):
    if z==wide:
        return pow(2,0) 
    if z==wide-1:
        return pow(2,0) 
    else:
        return pow(2,NegativeZero(wide-z-1))


def amida(h,w,f):
    dp[h][w][2]=MakePatternLeft(w)*MakePatternRight(w)
    if f == 1: #go straight
        if h==high and w==end:
            dp[h][w][f]=1
        elif h==high:
            dp[h][w][f]=0
        else: #sum under
            if dp[h+1][w][1] == -1:
                amida(h+1,w,1)
            if dp[h+1][w][0] == -1:
                amida(h+1,w,0)
            dp[h][w][f]=(dp[h+1][w][0]+dp[h+1][w][1])*dp[h+1][w][2]
    else: #f==0 go side
        dp[h][w][f]=0
        if w-1>=0: #sum left
            if dp[h][w-1][1]==-1:
                amida(h,w-1,1)
            dp[h][w][f]+=dp[h][w-1][1]*MakePatternLeft(w-1)*MakePatternRight(w)
        if w+1<=wide: #sum right
            if dp[h][w+1][1]==-1:
                amida(h,w+1,1)
            dp[h][w][f]+=dp[h][w+1][1]*MakePatternLeft(w)*MakePatternRight(w+1)
    dp[h][w][f]%=1000000007
    dp[h][w][2]%=1000000007

amida(0,0,0)
amida(0,0,1)

print((dp[0][0][0]*MakePatternLeft(0)*MakePatternRight(1)+dp[0][0][1]*dp[0][0][2])%1000000007)

Submission status: Wrong Answer

Solution code:
h, w, k = map(int, input().split())
a = [0]*(w-1) + [1,1]
for i in range(w-1):
    a[i] = a[i-1] + a[i-2]
dp = [0]*(w+1)
tmp = [0]*(w+1)
dp[0] = 1
for _ in range(1, h+1):
    for i in range(w):
        tmp[i] = (dp[i]*a[i-1]*a[w-i-2]
            + dp[i+1]*a[i-1]*a[w-i-3]
            + dp[i-1]*a[i-2]*a[w-i-2]) % (10**9+7)
    dp, tmp = tmp, dp
print(dp[k-1])

Submission status: Wrong Answer

Solution code:
def comb(n):
  if n % 2 == 0:
    N = n / 2
    num = 2 ** N + 2 ** N - 1
  else:
    N = ( n + 1 ) / 2
    num = 2 ** N + 2 ** ( N - 1 ) - 1
  return int(num)

d = 1000000007

h, w, k = [int(i) for i in input().split()]
kuji = [0 for i in range(w)]
kuji[0] = 1
print(kuji)
for i in range(h):

  kuji2 = [0 for i in range(w)]
  for j in range(w):
    kuji2[j] = kuji[j] * max(comb(w-(j+1)-1), 1) * max(comb(j-1), 1)
    if j >= 1:
      kuji2[j] += kuji[j-1] * max(comb(w-(j+1)-1), 1) * max(comb(j-2), 1)
    if j <= w-2:
      kuji2[j] += kuji[j+1] * max(comb(w-(j+1)-2), 1) * max(comb(j-1), 1)
  for j in range(w):
      kuji[j] = kuji2[j] 
#  print(kuji)
print(kuji[k-1] % d)

Submission status: Wrong Answer

Solution code:
import math
mod = 1000000007 

def pow(n):
	if (n <= 0):
		return 1
	if (n == 1):
		return 2
	z = int(math.floor(n / 2))
	t = pow(z)
	if (n % 2 == 0):
		return t * t % mod
	return t * t % mod * 2 % mod

s = input().split()
h = int(s[0])
w = int(s[1])
k = int(s[2])
x = [[] for i in range(h + 1)]
for i in range(h + 1):
	for j in range(w):
		x[i].append(0)
x[0][0] = 1
if (w != 1):
	for i in range(h):
		for j in range(w):
			if (j == 0):
				x[i + 1][j] = (pow(w - 2) * x[i][j] % mod + pow(w - 3) * x[i][j + 1] % mod) % mod
			elif (j == w - 1):
				x[i + 1][j] = (pow(w - 2) * x[i][j] % mod + pow(w - 3) * x[i][j - 1] % mod) % mod
			else:
				x[i + 1][j] += (pow(w - 4) * x[i][j - 1]) % mod
				x[i + 1][j] += (pow(w - 4) * x[i][j + 1]) % mod
				x[i + 1][j] %= mod
				x[i + 1][j] += (pow(w - 5) * x[i][j]) % mod
				x[i + 1][j] %= mod
else:
	x[h][k - 1] = 1
print(x[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()
lis = [[0 for i in range(w)] for s in range(h+1)]
lis[0][0] = 1
dp1 = [0 for i in range(w-1)]
dp2 = [0 for i in range(w-1)]
dp1[0] = 0
dp2[0] = 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)

Submission status: Wrong Answer

Solution code:
MOD = 1000000007
H,W,K=map(int,input().split())
##Precalculation            
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:
        break
    ##No Duplicate Assured
    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
##Time to Dynamic Programming YEAHHHHHH##
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])

Submission status: Wrong Answer

Solution code:
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))

Submission status: Wrong Answer

Solution code:
a,b,c=map(int,input().split())
s=[[0]*b for i in range(a+1)]
s[0][0]=1
print(s)
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))