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: Runtime Error

Solution code:
def fib(W):
    a, b = 1, 1
    n = [a, b]
    while W > len(n):
        a, b = b, b + a
        n.append(b)
    return n
H, W, K = map(int, input().split())
f = fib(W)
r = [1] + [0] * (W - 1)
for i in range(H):
    tmp = [0] * W
    for j in range(W):
        if j == 0:
            tmp[j] = r[j] * f[W - j - 1] + r[j + 1] * f[W - j - 2]
        elif j == W - 1:
            tmp[j] = r[j] * f[j] + r[j - 1] * f[j - 1]
        else:
            tmp[j] = r[j] * f[j] * f[W - j - 1] + r[j + 1] * f[W - j - 2] * f[j] + r[j - 1] * f[W - j - 1] * f[j - 1]
    r = tmp
print(r[K - 1] % 1000000007)

Submission status: Runtime Error

Solution code:
def fib(W):
    a, b = 1, 1
    n = [a, b]
    while W > len(n):
        a, b = b, b + a
        n.append(b)
    return n
H, W, K = map(int, input().split())
f = fib(W)
r = [1] + [0] * (W - 1)
for i in range(H):
    tmp = [0] * W
    for j in range(W):
        if j == 0:
            tmp[j] = r[j] * f[W - j - 1] + r[j + 1] * f[W - j - 2]
        elif j == W - 1:
            tmp[j] = r[j] * f[j] + r[j - 1] * f[j - 1]
        else:
            tmp[j] = r[j] * f[j] * f[W - j - 1] + r[j + 1] * f[W - j - 2] * f[j] + r[j - 1] * f[W - j - 1] * f[j - 1]
    r = tmp
print(r[K - 1] % 1_000_000_007)

Submission status: Runtime Error

Solution code:
import itertools

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

if K - 1 > H:
    print(0)
    exit(0)

R = []
for r in itertools.product( [0,1], repeat=(W-1) ):
    if 1 not in list(map(lambda i : r[i]*r[i+1], range(len(r)-1)) ):
        R.append(r)


M = [ (
    len( list( filter( lambda r:r[0]==0, R) ) ),
    len( list( filter( lambda r:r[0]==1, R) ) ),
    0
) ]
for c in range(1,W-1):
    M.append((
        len( list( filter( lambda r:r[c]==0 and r[c-1]==0, R) ) ),
        len( list( filter( lambda r:r[c]==1, R) ) ),
        len( list( filter( lambda r:r[c-1]==1, R) ) )
    ))
M.append((
    len( list( filter( lambda r:r[W-2]==0, R) ) ),
    0,
    len( list( filter( lambda r:r[W-2]==1, R) ) )
))

count = [1] + [0]*(W-1)
for h in range(H):
    count_ = [0] * W
    for num,c in zip(count, range(len(count))):
        for m,n in zip(M[c], [0,+1,-1]):
            if c+n >= 0 and c+n < W:
                count_[c+n] += num * m
    count = count_
        
print(count_[K-1]%p)

Submission status: Runtime Error

Solution code:
import itertools

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

if K - 1 > H:
    print(0)
    exit(0)

R = []
for r in itertools.product( [0,1], repeat=(W-1) ):
    if 1 not in list(map(lambda i : r[i]*r[i+1], range(len(r)-1)) ):
        R.append(r)


M = [ (
    len( list( filter( lambda r:r[0]==0, R) ) ),
    len( list( filter( lambda r:r[0]==1, R) ) ),
    0
) ]
for c in range(1,W-1):
    M.append((
        len( list( filter( lambda r:r[c]==0 and r[c-1]==0, R) ) ),
        len( list( filter( lambda r:r[c]==1, R) ) ),
        len( list( filter( lambda r:r[c-1]==1, R) ) )
    ))
M.append((
    len( list( filter( lambda r:r[W-2]==0, R) ) ),
    0,
    len( list( filter( lambda r:r[W-2]==1, R) ) )
))

print(R)
print(M)

count = [1] + [0]*(W-1)
for h in range(H):
    count_ = [0] * W
    for num,c in zip(count, range(len(count))):
        for m,n in zip(M[c], [0,+1,-1]):
            if c+n >= 0 and c+n < W:
                count_[c+n] += num * m
    count = count_
        
print(count_[K-1]%p)

Submission status: Runtime Error

Solution code:
H, W, K = map(int, input().split())
r = []
tmp = []
for i in range(W):
    r.append(0)
    tmp.append(0)
r[0] = 1
p = [1, 2, 4, 7, 12, 20]
ans = 0
for j in range(H):
    if W == 1 and K == 1:
        ans = 1
        break
    for i in range(W):
        u = i
        v = (W - 1) - i
        a, b, c, d = 1, 1, 1, 1
        if u >= 2:
            a += p[u - 2] 
        if v >= 2:
            b += p[v - 2]
        if u - 1 >= 2:
            c += p[u - 3]
        if v - 1 >= 2:
            d += p[v - 3]
        if i == 0:
            tmp[i] = r[i] * a * b + r[i + 1] * a * d
        elif i == (W - 1):
            tmp[i] = r[i - 1] * c * b + r[i] * a * b
        else:
            tmp[i] = r[i - 1] * c * b  + r[i] * a * b + r[i + 1] * a * d
    for i in range(len(tmp)):
        r[i] = tmp[i]
ans = r[K - 1] % 1_000_000_007
print(ans)

Submission status: Runtime Error

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:
				break
		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: Runtime Error

Solution code:
def count(length, on):
    """Count of possible amida patterns"""
    if length < 0:
        return 1
    if length == 0:
        return 1
    ret = count(length - 1, False)
    if not on:
        ret += count(length - 1, True)
    return ret


# for i in range(1, 9):
#     print(count(i, True) + count(i, False))


if __name__ == '__main__':
    H, W, K = map(int, input().split())

    # Count
    B = [0 for _ in range(W)]
    B[0] = 1
    for j in range(H):
        C = [0 for _ in range(W)]
        for i in range(W):
            left_off = count(i - 1, False)
            left_on = count(i - 1, True)
            right_off = count(W - i - 2, False)
            right_on = count(W - i - 2, True)
            # print(i, left_off, left_on, right_off, right_on)

            if B[i] > 0:
                C[i] += B[i] * (left_off * right_off)

            if i > 0 and B[i - 1] > 0:
                C[i] += B[i - 1] * (left_on * right_off)

            if i < W - 1 and B[i + 1] > 0:
                C[i] += B[i + 1] * (left_off * right_on)

        B = [ci for ci in C]
        # print(B)

    MOD = 1_000_000_007
    ANS = C[K - 1] % MOD
    print(ANS)

Submission status: Runtime Error

Solution code:
def count(length, on):
    """Count of possible amida patterns"""
    if length < 0:
        return 1
    if length == 0:
        return 1
    ret = count(length - 1, False)
    if not on:
        ret += count(length - 1, True)
    return ret


# for i in range(1, 9):
#     print(count(i, True) + count(i, False))


if __name__ == '__main__':
    H, W, K = map(int, input().split())

    # Count
    B = [0 for _ in range(W)]
    B[0] = 1
    for j in range(H):
        C = [0 for _ in range(W)]
        for i in range(W):
            left_off = count(i - 1, False)
            left_on = count(i - 1, True)
            right_off = count(W - i - 2, False)
            right_on = count(W - i - 2, True)
            print(i, left_off, left_on, right_off, right_on)

            if B[i] > 0:
                C[i] += B[i] * (left_off * right_off)

            if i > 0 and B[i - 1] > 0:
                C[i] += B[i - 1] * (left_on * right_off)

            if i < W - 1 and B[i + 1] > 0:
                C[i] += B[i + 1] * (left_off * right_on)

        B = [ci for ci in C]
        # print(B)

    MOD = 1_000_000_007
    ANS = C[K - 1] % MOD
    print(ANS)

Submission status: Runtime Error

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)) % 1_000_000_007
    if search_range < end_w:
        search_range += 1

print(ans[height][k])

Submission status: Runtime Error

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] % 1_000_000_007)

Submission status: Runtime Error

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

# 範囲外を0としたいので, wを両端1つずつ多く取る
# 初期値を入れるため, hも1つ多く取る
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] % 1_000_000_007)

Submission status: Runtime Error

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

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

for i in range(1,h):
    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: Runtime Error

Solution code:
H, W, K = [int(_) for _ in input().split()]
fib = [1, 1, 2, 3, 5 ,8, 13, 21]
dp = [[1] + [0] * (W - 1)]
for j in range(1, H + 1):
    dp.append([0] * W)
    for i in range(W):
        if i == 0:
            dp[j][i] = (dp[j - 1][i] * fib[i] * fib[W - i - 1] + dp[j - 1][i + 1] * fib[i] * fib[W - i - 2]) % 1000000007
        elif i == W - 1:
            dp[j][i] = (dp[j - 1][i] * fib[i] * fib[W - i - 1] + dp[j - 1][i - 1] * fib[i - 1] * fib[W - i - 1]) % 1000000007
        else:
            dp[j][i] = (dp[j - 1][i] * fib[i] * fib[W - i - 1] + dp[j - 1][i + 1] * fib[i] * fib[W - i - 2] + dp[j - 1][i - 1] * fib[i - 1] * fib[W - i - 1]) % 1000000007
print(dp[H][K - 1])

Submission status: Runtime Error

Solution code:
h, w, k = map(int, input().split())
a = [0]*(w-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: Runtime Error

Solution code:
h, w, k = map(int, input().split())
a = [0]*(w-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)
        tmp[i] %= m
    dp, tmp = tmp, dp
print(dp[k-1])

Submission status: Runtime Error

Solution code:
import numpy as np
from numpy.linalg import matrix_power
H,W,K=map(int,input().split())
def c(i,j):
    f=[1,1,2,3,5,8,13,21]
    a=0
    if i==j+1: a=f[j]*f[W-i-1]
    if j in (i,i+1): a=f[i]*f[W-j-1]
    return(a)
def mp(m,n,p):
    a = m%p
    if n==0:
        return(np.identity(m.diagonal().size,dtype='int32'))
    if n==1:
        return(a)
    else:
        q,r=divmod(n,2)
        x=np.matmul(a,a)%p
        if r==1:
            return(np.matmul(a,mp(x,q,p))%p)
        else:
            return(mp(x,q,p)%p)

m=mp(np.array([[c(i,j) for i in range(W)] for j in range(W)]),H,1000000007)
x=np.array([[c(i,j) for i in range(W)] for j in range(W)])
print(m[0,K-1])

Submission status: Runtime Error

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

def amida(h,w,k):
    memo=[[-1 for _ in range(w)] for _ in range(h)]
    memo[0][0]=amida_h1_total(w-1)
    if w>1:
        memo[0][1]=amida_h1_total(w-2)
    for i in range(2,w):
        memo[0][i]=0
    def _amida(h,k):
        if k<=0 or k>w:
            return 0
        if memo[h-1][k-1]>=0:
            return memo[h-1][k-1]
        memo[h-1][k-1]=sum((_amida(h-1,k-1)*amida_h1_total(k-2)*amida_h1_total(w-k),
                            _amida(h-1,k)  *amida_h1_total(k-1)*amida_h1_total(w-k),
                            _amida(h-1,k+1)*amida_h1_total(k-1)*amida_h1_total(w-k-1)))%1000000007
        return memo[h-1][k-1]
    return _amida(h,k)
print(amida(h,w,k))

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;

int main() {
    int h, w, k;
    cin >> h >> w >> k;
    if (w == 1) {
        cout << 1 << endl;
        return 0;
    }
    k--;
    long t[h + 1][w];
    fill(t[0] + 1, t[0] + w, 0);
    t[0][0] = 1;
    for (int i = 1; i <= h; i++) {
        fill(t[i], t[i] + w, 0);
    }
    for (int i = 1; i <= h; i++) {
        for (int k = 0; k < (2 << (w - 2)); k++) {
            bool flag = true;
            for (int l = 1; l < w - 1; l++) {
                if ((k & (1 << l)) && k & (1 << (l - 1))) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                if (k & 1) {
                    t[i][0] = (t[i][0] + t[i - 1][1]) % MOD;
                } else {
                    t[i][0] = (t[i][0] + t[i - 1][0]) % MOD;
                }
            }
        }
        for (int j = 1; j < w - 1; j++) {
            for (int k = 0; k < (2 << (w - 2)); k++) {
                bool flag = true;
                for (int l = 1; l < w - 1; l++) {
                    if ((k & (1 << l)) && k & (1 << (l - 1))) {
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                    if (k & (1 << (j - 1))) {
                        t[i][j] = (t[i][j] + t[i - 1][j - 1]) % MOD;
                    } else if (k & (1 << j)) {
                        t[i][j] = (t[i][j] + t[i - 1][j + 1]) % MOD;
                    } else {
                        t[i][j] = (t[i][j] + t[i - 1][j]) % MOD;
                    }
                }
            }
        }
        for (int k = 0; k < (2 << (w - 2)); k++) {
            bool flag = true;
            for (int l = 1; l < w - 1; l++) {
                if ((k & (1 << l)) && k & (1 << (l - 1))) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                if (k & (1 << (w - 2))) {
                    t[i][w - 1] = (t[i][w - 1] + t[i - 1][w - 2]) % MOD;
                } else {
                    t[i][w - 1] = (t[i][w - 1] + t[i - 1][w - 1]) % MOD;
                }
            }
        }
    }
    cout << t[h][k] << endl;
    return 0;
}

Submission status: Runtime Error

Solution code:
# encoding: utf-8
H, W, K = map(int, input().split())

raw_route = [0] * W # 0 in unused
possible_route = 0

for i in range(2 ** (W - 1)):
    # check
    i_tmp = i
    last = 0
    for j in range(W - 1):
        if i_tmp % 2 == last == 1: break
        last = i_tmp % 2
        i_tmp = i_tmp // 2
    else:
        # valid drawing
        i_tmp = i
        for j in range(W - 1):
            if i_tmp % 2 == 1: raw_route[j + 1] += 1
            i_tmp = i_tmp // 2
        possible_route += 1

# print("#", raw_route)

DP = [[None] * W for i in range(H)]

def draw(depth, clm):
    # done
    if depth == H + 1: return 1
    # running
    if DP[depth - 1][clm - 1] != None: return DP[depth - 1][clm - 1]
    ## param
    range_min = K - (H - depth)
    range_max = K + (H - depth)
    ## calc ans
    ans = 0
    # print("##", depth, clm, (range_min, range_max))
    ### go straight
    if range_min <= clm <= range_max:
        if clm == 1: ans += (possible_route - raw_route[clm]) * draw(depth + 1, clm)
        elif clm == W: ans += (possible_route - raw_route[clm - 1]) * draw(depth + 1, clm)
        else: ans += (possible_route - raw_route[clm - 1] - raw_route[clm]) * draw(depth + 1, clm)
    ### go left
    if range_min <= clm - 1 and 1 <= clm - 1: ans += raw_route[clm - 1] * draw(depth + 1, clm - 1)
    ### go right
    if clm + 1 <= range_max and clm + 1 <= W: ans += raw_route[clm] * draw(depth + 1, clm + 1)
    ## end
    if DP[depth - 1][clm - 1] == None: DP[depth - 1][clm - 1] = ans % (10 ** 9 + 7)
    return ans % (10 ** 9 + 7)

print(draw(1, 1))

Submission status: Runtime Error

Solution code:
# encoding: utf-8
H, W, K = map(int, input().split())

raw_route = [0] * W # 0 in unused
possible_route = 0

for i in range(2 ** (W - 1)):
    # check
    i_tmp = i
    last = 0
    for j in range(W - 1):
        if i_tmp % 2 == last == 1: break
        last = i_tmp % 2
        i_tmp = i_tmp // 2
    else:
        # valid drawing
        i_tmp = i
        for j in range(W - 1):
            if i_tmp % 2 == 1: raw_route[j + 1] += 1
            i_tmp = i_tmp // 2
        possible_route += 1

# print("#", raw_route)            
            
def draw(depth, clm):
    # done
    if depth == H + 1: return 1
    # running
    ## param
    range_min = K - (H - depth)
    range_max = K + (H - depth)
    ## calc ans
    ans = 0
    # print("##", depth, clm, (range_min, range_max))
    ### go straight
    if range_min <= clm <= range_max:
        if clm == 1: ans += (possible_route - raw_route[clm]) * draw(depth + 1, clm)
        elif clm == W: ans += (possible_route - raw_route[clm - 1]) * draw(depth + 1, clm)
        else: ans += (possible_route - raw_route[clm - 1] - raw_route[clm]) * draw(depth + 1, clm)
    ### go left
    if range_min <= clm - 1 and 1 <= clm - 1: ans += raw_route[clm - 1] * draw(depth + 1, clm - 1)
    ### go right
    if clm + 1 <= range_max and clm + 1 <= W: ans += raw_route[clm] * draw(depth + 1, clm + 1)
    ## end
    return ans % (10 ** 9 + 7)

print(draw(1, 1))

Submission status: Runtime Error

Solution code:
import numpy as np
def main():
	x  = 1000000007
	buf = input().split()
	h = int(buf[0])
	w = int(buf[1])
	k = int(buf[2])
 
	dpp = np.zeros((w+1, 3), dtype="int")
	dpp[0][0] = 1
	dpp[0][2] = 1
	dpp[1][0] = 1
	dpp[1][2] = 1
	for i in range(2, w+1):
		dpp[i][0] = dpp[i-1][0]+dpp[i-1][1]
		dpp[i][1] = dpp[i-1][0]
		dpp[i][2] = dpp[i][0] + dpp[i][1]
	#print(dpp)
 
	dp = np.zeros((h+1, w+2), dtype="int")
	dp[0][1] = 1
	for row in range(1, h+1):
		for col in range(1, w+1):
			dp[row][col] = ((dp[row-1][col-1]*dpp[col-2][2]*dpp[w-col][2])%x + (dp[row-1][col]*dpp[col-1][2]*dpp[w-col][2])%x + (dp[row-1][col+1]*dpp[col-1][2]*dpp[w-col-1][2])%x)%x
	#print(dp)
	print(dp[h][k]%x)
 
 
 
 
 
main()

Submission status: Runtime Error

Solution code:
import itertools

def pr(l):
    res = 1
    for i in l:
        res *= i
    return res


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

# 一本道全列挙→生き残ったやつに関して正しいあみだくじを計算
roads = []
for i in itertools.product((-1, 0, 1), repeat=H):
    w = 1
    for ii in i:
        w += ii
        if w < 1 or W < w:
            break
    
    if w == K:
        roads.append(i)

cnt = 0
for road in roads:
    w = 0
    h = 0
    t = [[0 for _ in range(W)] for _ in range(H)]
    for i in road:
        t[h][w] = 1
        if i == -1:
            t[h][w-1] = 1
            w -= 1
        elif i == 1:
            t[h][w+1] = 1
            w += 1
        h += 1
    
    cnt_l = []    
    for line in t:
        renzoku = 0
        for j in line:
            if j == 0:
                renzoku += 1
            else:
                cnt_l.append(renzoku)
                renzoku = 0
        cnt_l.append(renzoku)   
                
    lll = [cnt_d[n] for n in cnt_l if n not in [0, 1]]
    cnt += pr(lll)

print(cnt)

Submission status: Runtime Error

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

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

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 or j == 0 or j == w:
            continue
        if abs(i - j) <= 1:
            ptn[i][j] = 1


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


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 or j == 0 or j == w:
                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[1][k] % 1000000007)

Submission status: Runtime Error

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

FILL = [1, 2]
MOD = 1_000_000_007

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: Runtime Error

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

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

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 or j == 0 or j == w:
            continue
        if abs(i - j) <= 1:
            ptn[i][j] = 1


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


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 or j == 0 or j == w:
                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[1][k])

Submission status: Runtime Error

Solution code:
# encoding: utf-8
import sys
sys.setrecursionlimit(10000)

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

raw_route = [0] * W # 0 in unused
possible_route = 0

for i in range(2 ** (W - 1)):
    # check
    i_tmp = i
    last = 0
    for j in range(W - 1):
        if i_tmp % 2 == last == 1: break
        last = i_tmp % 2
        i_tmp = i_tmp // 2
    else:
        # valid drawing
        i_tmp = i
        for j in range(W - 1):
            if i_tmp % 2 == 1: raw_route[j + 1] += 1
            i_tmp = i_tmp // 2
        possible_route += 1

# print("#", raw_route)            
            
def draw(depth, clm):
    # done
    if depth == H + 1: return 1
    # running
    ## param
    range_min = K - (H - depth)
    range_max = K + (H - depth)
    ## calc ans
    ans = 0
    # print("##", depth, clm, (range_min, range_max))
    ### go straight
    if range_min <= clm <= range_max: ans += (possible_route - raw_route[clm - 1] - raw_route[clm]) * draw(depth + 1, clm)
    ### go left
    if range_min <= clm - 1 and 1 <= clm - 1: ans += raw_route[clm - 1] * draw(depth + 1, clm - 1)
    ### go right
    if clm + 1 <= range_max and clm + 1 <= W: ans += raw_route[clm] * draw(depth + 1, clm + 1)
    ## end
    return ans % (10 ** 9 + 7)

print(draw(1, 1))

Submission status: Runtime Error

Solution code:
# encoding: utf-8
H, W, K = map(int, input().split())

raw_route = [0] * W # 0 in unused
possible_route = 0

for i in range(2 ** (W - 1)):
    # check
    i_tmp = i
    last = 0
    for j in range(W - 1):
        if i_tmp % 2 == last == 1: break
        last = i_tmp % 2
        i_tmp = i_tmp // 2
    else:
        # valid drawing
        i_tmp = i
        for j in range(W - 1):
            if i_tmp % 2 == 1: raw_route[j + 1] += 1
            i_tmp = i_tmp // 2
        possible_route += 1

# print("#", raw_route)            
            
def draw(depth, clm):
    # done
    if depth == H + 1: return 1
    # running
    ## param
    range_min = K - (H - depth)
    range_max = K + (H - depth)
    ## calc ans
    ans = 0
    # print("##", depth, clm, (range_min, range_max))
    ### go straight
    if range_min <= clm <= range_max: ans += (possible_route - raw_route[clm - 1] - raw_route[clm]) * draw(depth + 1, clm)
    ### go left
    if range_min <= clm - 1 and 1 <= clm - 1: ans += raw_route[clm - 1] * draw(depth + 1, clm - 1)
    ### go right
    if clm + 1 <= range_max and clm + 1 <= W: ans += raw_route[clm] * draw(depth + 1, clm + 1)
    ## end
    return ans % (10 ** 9 + 7)

print(draw(1, 1))

Submission status: Runtime Error

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

DP = [[0 for i in range(W)]for j in range(2)]

t = [0 for i in range(W+10)]

t[1] = 1
t[2] = 2
for i in range(2,W+8):
    t[i+1] = t[i] + t[i-1]

#print(t)
n = 0
DP[0][0] = 1
for i in range(H):
    if W == 1:
        break
    DP[not(n)][0] = (DP[n][0] * t[W-1] + DP[n][1] * t[W-2]) % 1000000007
    for i in range(1,W-1):
        DP[not(n)][i] =( DP[n][i-1] *t[W - (i+1)] + DP[n][i]*(t[i-1] + t[W-i]) + DP[n][i+1]*t[i-2] ) % 1000000007
    
    DP[not(n)][W-1] = (DP[n][W-2]*t[W-2] + DP[n][W-1] * t[W-1]) % 1000000007
    n = not(n)
print(DP[n][K])

Submission status: Runtime Error

Solution code:
import numpy as np
MOD = 10**9+7
h, w, k = map(int, input().split())

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

patterns = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

for i in range(1, h+1):
    # most left
    dp[i][0] = (dp[i-1][0]*patterns[1:][w-2]%MOD + dp[i-1][1]*patterns[w-2]%MOD)%MOD
    for j in range(1, w-1):
        npath = dp[i-1][j-1]*(patterns[j-1]*patterns[1:][w-j-2])%MOD\
                + dp[i-1][j]*(patterns[1:][j-1]*patterns[1:][w-j-2])%MOD\
                + dp[i-1][j+1]*(patterns[1:][j-1]*patterns[w-j-2])%MOD
        dp[i][j] = npath%MOD
    dp[i][w-1] = (dp[i-1][w-2]*patterns[w-2]%MOD + dp[i-1][w-1]*patterns[1:][w-2]%MOD)%MOD

# for p in dp: print(p)

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

Submission status: Runtime Error

Solution code:

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


amida = [0 for i in range(8)]
amida[0]=1
amida[1]=2
amida[2]=3
amida[3]=5
amida[4]=8
amida[5]=13
amida[6]=21
amida[7]=34

def amida_num(k,l):
    return amida[max(k,0)]*amida[max(l,0)]


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 j in range(W):
        if j==0:
            dp[i][j]=dp[i-1][j+1]*amida_num(0,W-3) + dp[i-1][j]* amida_num(0,W-2)
        elif j==W-1:
            dp[i][j]=dp[i-1][j-1]*amida_num(0,W-3) + dp[i-1][j]* amida_num(0,W-2)
        else:
            dp[i][j]=dp[i-1][j-1]*amida_num(j-2,W-j-2) + dp[i-1][j]*amida_num(j-1,W-j-2) + dp[i-1][j+1]*amida_num(j-1,W-j-3)

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