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:
"""
15,8,5の場合：
何回右に移動するか、何回左に移動するか。
dp[i][j] => i回目下降が終わった時点で、j列目にいる場合の数
memo[j] => 特定の高さを見たときに、j列目とj+1列目の間に横棒があるような横棒配置パターン数
memo2[j] => j列目の左右に横棒がないような場合の数
"""
mod = 10**9 +7
H,W,K = map(int,input().split())
memo = [0]*(W-1)
memo2 = [0]*(W-1)
cnt = 0
for i in range(2**(W-1)):
    binI = format(i,"0"+str(W-1)+"b")
    #パターンの有効性をチェックする
    for j in range(W-2):
        if binI[j] == "1" and binI[j+1] == "1":
            break
    else:
        cnt += 1
        for j in range(W-1):
            if binI[j] == "1":
                memo[j] += 1
        for j in range(1,W-1):
            if binI[j-1]=="0" and binI[j] =="0":
                memo2[j] += 1
dp = [[0]*W for _ in range(H+1)]
dp[0][0] = 1

for i in range(H):
    for j in range(W):
        #右の列に移動する
        if j != W-1:
            dp[i+1][j+1] += memo[j]*dp[i][j]%mod
            dp[i+1][j+1] %= mod
        #左の列に移動する
        if j != 0:
            dp[i+1][j-1] += memo[j-1]*dp[i][j]%mod
            dp[i+1][j-1] %= mod
        #真下に移動する
        if j == 0:
            dp[i+1][j] += (cnt-memo[j])*dp[i][j]%mod
        elif j == W-1:
            dp[i+1][j] += (cnt-memo[j-1])*dp[i][j]%mod
        else:
            dp[i+1][j] += memo2[j]*dp[i][j]%mod
        dp[i+1][j]%=mod

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

Submission status: Runtime Error

Solution code:
import itertools

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

# 縦棒を0-indexで考える
# dp[i][j] := 上から高さi(0,1,...,h)までの横棒を配置した時に、
#             0(問題文では1)からスタートしてjで終わるようなものの個数

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

bridges = list(itertools.product([0, 1], repeat=w - 1))
# print(bridges)

for i in range(h):
    for bridge in bridges:
        
        # 橋が隣り合っていてはいけない
        tf = True
        for j in range(w - 2):
            if bridge[j] == 1 and bridge[j + 1] == 1:
                tf = False
                break
        if tf == False:
            continue

        for j in range(w):
            # 左端について
            if j == 0:
                # 橋がある時、右から流入
                if bridge[0] == 1:
                    dp[i + 1][j] += dp[i][j + 1]
                # 橋がない時、上から流入
                else:
                    dp[i + 1][j] += dp[i][j]

            # 右端について
            elif j == w - 1:
                # 橋がある時、左から流入
                if bridge[-1] == 1:
                    dp[i + 1][j] += dp[i][j - 1]
                # 橋がない時、上から流入
                else:
                    dp[i + 1][j] += dp[i][j]

            #　両端以外について
            else:
                # 両サイドに橋がない場合
                if bridge[j - 1] == 0 and bridge[j] == 0:
                    dp[i + 1][j] += dp[i][j]
                # 左だけ橋がある場合
                elif bridge[j - 1] == 1 and bridge[j] == 0:
                    dp[i + 1][j] += dp[i][j - 1]
                # 右だけ橋がある場合
                elif bridge[j - 1] == 0 and bridge[j] == 1:
                    dp[i + 1][j] += dp[i][j + 1]

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

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

Submission status: Runtime Error

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

WW = [0]*(W+1)
WW[0] = 1
WW[1] = 1
for i in range(2, W+1):
    WW[i] = WW[i-1] + WW[i-2]
DP = [[0]*W for i in range(H+1)]
DP[0][0] = 1
mod = 10**9+7
for i in range(1, H+1):
    for j in range(W):
        if j == 0:
            DP[i][j] = DP[i-1][j]*WW[W-1] + DP[i-1][j+1]*WW[W-2]
        elif j == W-1:
            DP[i][j] = DP[i-1][j]*WW[W-1] + DP[i-1][j-1]*WW[W-2]
        else:
            DP[i][j] = DP[i-1][j]*WW[j]*WW[W-1-j]+DP[i-1][j-1] * \
                WW[j-1]*WW[W-1-j]+DP[i-1][j+1]*WW[j]*WW[W-2-j]

        DP[i][j] %= mod
# print(DP, WW)
print(DP[-1][K-1])

Submission status: Runtime Error

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

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

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

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

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


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

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
from itertools import product
import sys

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


MOD = 1000000007  # type: int


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


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

    print(dp[0])


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


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

    ans = 0
    for i in range(1 << w - 1):
        flg = True
        for j in range(w - 2):
            if i & (1 << j) and i & (1 << j + 1):
                flg = False
                break
        if flg:
            nx = x
            if x > 0 and i & (1 << x - 1):
                nx = x - 1
            elif i & (1 << x):
                nx = x + 1
            ans += dfs(nx, y + 1)
            ans %= 1000000000 + 7
    memo[x][y] = ans
    return ans
print(dfs(0, 0))

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <vector>
#define rep(i,n) for(int (i)=0;(i)<(n);++(i))
#define all(x) (x).begin(),(x).end()
#define dump(x) cout << #x << " = " << (x) << endl

using namespace std;
using ll = long long;
const ll MOD = 1000000007;


int main() {
    int h, w, k;
    cin >> h >> w >> k;
    --k;
    vector<vector<ll>> dp(h + 1, vector<ll>(w, 0));
    dp[0][0] = 1;

    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            for (int bit = 0; bit < 1 << (w - 1); ++bit) {
                bool ok = true;
                for (int k = 0; k < w - 2; ++k) {  // i, i+1, i+2本目がつながっている場合はfalse
                    if ((bit >> k & 1) && (bit >> (k + 1) & 1)) ok = false; 
                }
                if (!ok) continue;

                int nj = j;  // 次にどのポジションにいるか。
                if ((bit >> j) & 1) nj = j + 1;  // 右側とつながっている場合
                else if (j > 0 && ((bit >> (j - 1)) & 1)) nj = j - 1; // 左側とつながっている場合

                dp[i + 1][nj] += dp[i][j];
                dp[i + 1][nj] %= MOD;
            }
        }
    }
    cout << dp[h][k] << endl;
}

Submission status: Runtime Error

Solution code:
h,w,k=map(int,input().split())
mod=10**9+7
fib=[1,1]
for i in range(6):
  fib.append(fib[-2]+fib[-1])
print(fib)
dp=[[0]*w for i in range(h+1)]
dp[0][0]=1
for i in range(h):
  for j in range(w):
    if j==0:
      dp[i+1][j]=(dp[i][j]*fib[j]*fib[w-j-1]+dp[i][j+1]*fib[j]*fib[w-j-2])%(mod)
    elif j==w-1:
      dp[i+1][j]=(dp[i][j-1]*fib[j-1]*fib[w-j-1]+dp[i][j]*fib[j]*fib[w-j-1])%(mod)
    else:
      dp[i+1][j]=(dp[i][j-1]*fib[j-1]*fib[w-j-1]+dp[i][j]*fib[j]*fib[w-j-1]+dp[i][j+1]*fib[j]*fib[w-j-2])%(mod)
print(dp[h][k-1])

Submission status: Runtime Error

Solution code:
import sys

MOD = 10 ** 9 + 7

h, w, k = map(int, sys.stdin.readline().split())

def main():
    ok = []
    for i in range(2 ** (w - 1)):
        prev = False
        for j in range(w-1):
            if i >> j & 1:
                if prev:
                    break
                else:
                    prev = True
            else:
                prev = False
        else:
            ok.append(i)

    lcr = [(letter, 0) for letter in 'lcr']
    a = [dict(lcr) for _ in range(w)]
    for i in ok:
        j = 0
        while j < w:
            if i >> j & 1:
                a[j]['r'] += 1
                a[j+1]['l'] += 1
                j += 2
            else:
                a[j]['c'] += 1
                j += 1

    res = [0] * w
    res[0] = 1
    for _ in range(h):
        nex = [0] * w
        for j in range(w):
            if j == 0:
                nex[j] = res[j] * a[j]['c'] + res[j+1] * a[j]['r']
            elif j < w - 1:
                nex[j] = res[j-1] * a[j]['l'] + res[j] * a[j]['c'] + res[j+1] * a[j]['r']
            else:
                nex[j] = res[j-1] * a[j]['l'] + res[j] * a[j]['c']
        for j in range(w):
            nex[j] %= MOD
        res = nex
        
    return res[k-1]
    
if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Runtime Error

Solution code:
H, W, K = map(int, input().split())
dp = [[0 for i in range(W)] for j in range(H+1)]
mod = 10**9+7
dp[0][0] = 1

for k in range(H):
    for i in range(2**(W-1)):
        b = format(i, "0{}b".format(W-1))
        flag = 1
        for j in range(len(b)-1):
            if b[j+1] == "1" and b[j] == "1":
                flag = 0
                break
        if flag == 0:
            continue

        for j in range(len(b)):
            if flag == 0:
                flag = 1
                continue
            if b[j] == "1":
                dp[k+1][j+1] += dp[k][j]
                dp[k+1][j] += dp[k][j+1]
                dp[k+1][j+1] %= mod
                dp[k+1][j] %= mod
                flag = 0
            else:
                dp[k+1][j] += dp[k][j]
                dp[k+1][j] %= mod
                if j == len(b)-1:
                    dp[k+1][j+1] += dp[k][j+1]
                    dp[k+1][j+1] %= mod
                  
print(dp[H][K-1])

Submission status: Runtime Error

Solution code:
H,W,K = map(int, input().split())
# HとWは道の数を決定
dp = [[0]*W for _ in range(H+1)]
dp[0][0] = 1
if W==1:
  print(1)
else:
  for i in range(H):
    for j in range(2**(W-1)):
      flag = True
      for k in range(W-1):
        if k != W-2:
          # 二桁連続で1の場合は処理を省く
          if (((j >> k) & 1)&((j >> k+1) & 1)):
            flag = False
            break
      if flag:
        #print(bin(j)[2:].zfill(W-1))
        for l in range(W-1):
          if ((j >> l) & 1):
            dp[i+1][l] += dp[i][l+1]
            dp[i+1][l+1] += dp[i][l]
          else:
            dp[i+1][l] += dp[i][l]
        #print(dp[i+1])

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

Submission status: Runtime Error

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

if w == 1:
    print(1)
else:
    acr = []
    for p in range(2**(w-1)):
        det = 0
        pp = p
        exist = [0] * (w-1)
        for i in range(w-1):
            exist[i] = pp % 2
            pp = pp // 2
        for ii in range(w-2):
            if exist[ii] == 1 and exist[ii+1] == 1:
                det = 1
        if det == 0:
            acr.append(exist)

    cur = [0] * w
    cur[0] = 1
    n = [0] * w

    for x in range(len(acr)):
        n[0] = cur[1] * acr[x][0] + cur[0] * (1-acr[x][0])
        for j in range(1,w-1):
            n[j] = cur[j-1] * acr[x][j-1] + cur[j+1] * acr[x][j] + cur[j] * (1-acr[x][j-1])(1-acr[x][j])
        n[w-1] = cur[w-2] * acr[x][w-2] + cur[w-1] * (1-acr[x][w-1])
        cur = n[:]
    print(cur[k-1])

Submission status: Runtime Error

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

ck = [0]*9
ck[0] = 1
for i in range(1,9):
  for j in range(2**(i-1)):
    for k in range(i-1):
      if (j>>k)&(j>>(k+1))==True:
        break
    else:
      ck[i] += 1

mod = 10**9+7
for i in range(1,H+1):
  for j in range(W):
    if j == 0:
      dp[i][j] = dp[i-1][j]*ck[W-2]+dp[i-1][j+1]*ck[W-3]
    elif j == W-1:
      dp[i][j] = dp[i-1][j]*ck[W-2]+dp[i-1][j-1]*ck[W-3] 
    else:
      dp[i][j] = dp[i-1][j+1]*(ck[j-1]+ck[W-j-3])+dp[i-1][j]*(ck[j-1]+ck[W-2-j])+dp[i-1][j-1]*(ck[max(0,j-2)]-1+ck[W-j-2])

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

Submission status: Runtime Error

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

ck = [0]*9
ck[0] = 1
for i in range(1,9):
  for j in range(2**(i-1)):
    for k in range(i-1):
      if (j>>k)&(j>>(k+1))==True:
        break
    else:
      ck[i] += 1
print(ck)

mod = 10**9+7
for i in range(1,H+1):
  for j in range(W):
    if j == 0:
      dp[i][j] = dp[i-1][j]*ck[W-2]+dp[i-1][j+1]*ck[W-3]
    elif j == W-1:
      dp[i][j] = dp[i-1][j]*ck[W-2]+dp[i-1][j-1]*ck[W-3] 
    else:
      dp[i][j] = dp[i-1][j+1]*(ck[j-1]+ck[W-j-3])+dp[i-1][j]*(ck[j-1]+ck[W-2-j])+dp[i-1][j-1]*(ck[max(0,j-2)]-1+ck[W-j-2])

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

Submission status: Runtime Error

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

ck = [0]*9
ck[0] = 1
for i in range(1,9):
  for j in range(2**i):
    for k in range(i-1):
      if k&(k+1)==True:
        break
    else:
      ck[i] += 1

mod = 10**9+7
for i in range(1,H+1):
  for j in range(W):
    if j == 0:
      dp[i][j] = dp[i-1][j]*ck[W-2]+dp[i-1][j+1]*ck[W-3]
    elif j == W-1:
      dp[i][j] = dp[i-1][j]*ck[W-2]+dp[i-1][j-1]*ck[W-3] 
    else:
      dp[i][j] = dp[i-1][j+1]*(ck[j-1]+ck[W-j-3])+dp[i-1][j]*(ck[j-1]+ck[W-2-j])+dp[i-1][j-1]*(ck[max(0,j-2)]-1+ck[W-j-2])

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

Submission status: Runtime Error

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

ck = [0]*9
ck[0] = 1
for i in range(1,9):
  for j in range(2**i):
    for k in range(i-1):
      if k&(k+1)==True:
        continue
    else:
      ck[i] += 1

mod = 10**9+7
for i in range(1,H+1):
  for j in range(W):
    if j == 0:
      dp[i][j] = dp[i-1][j]*ck[W-2]+dp[i-1][j+1]*ck[W-3]
    elif j == W-1:
      dp[i][j] = dp[i-1][j]*ck[W-2]+dp[i-1][j-1]*ck[W-3] 
    else:
      dp[i][j] = dp[i-1][j+1]*(ck[j-1]+ck[W-j-3])+dp[i-1][j]*(ck[j-1]+ck[W-2-j])+dp[i-1][j-1]*(ck[max(0,j-2)]-1+ck[W-j-2])

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

Submission status: Runtime Error

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

ck = [0]*9
for i in range(1,9):
  for j in range(2**i):
    for k in range(i-1):
      if k&(k+1)==True:
        continue
    else:
      ck[i] += 1

mod = 10**9+7
for i in range(1,H+1):
  for j in range(W):
    if j == 0:
      dp[i][j] = dp[i-1][j]*ck[W-2]+dp[i-1][j+1]*ck[W-3]
    elif j == W-1:
      dp[i][j] = dp[i-1][j]*ck[W-2]+dp[i-1][j-1]*ck[W-3] 
    else:
      dp[i][j] = dp[i-1][j+1]*(ck[j+1]+ck[W-j])+dp[i-1][j]*(ck[j]+ck[W-1-j])+dp[i-1][j-1]*(1+ck[j-1]+ck[W-j-2])

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

Submission status: Runtime Error

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

ck = [0]*9
for i in range(1,9):
  for j in range(2**i):
    for k in range(i-1):
      if k&(k+1)==True:
        continue
    else:
      ck[i] += 1

mod = 10**9+7
for i in range(1,H+1):
  for j in range(W):
    if j == 0:
      dp[i][j] = dp[i-1][j]*ck[W-2]+dp[i-1][j+1]*ck[W-3]
    elif j == W-1:
      dp[i][j] = dp[i-1][j]*ck[W-2]+dp[i-1][j-1]*ck[W-3] 
    else:
      dp[i][j] = dp[i-1][j+1]*(ck[j-2]+ck[W-2-j])+dp[i-1][j]*(ck[j-1]+ck[W-1-j])+dp[i-1][j-1]*(ck[j]+ck[W-j])
      
print(dp[H][K-1])

Submission status: Runtime Error

Solution code:
import sys
MOD = 1_000_000_007


def main():
    h, w, k = [int(x) for x in input().split()]
    fibonacci = [1, 2]
    for i in range(w - 2):
        fibonacci.append(fibonacci[i] + fibonacci[i + 1])
    pattern = [0 for _ in range(w)]
    pattern[0] = 1
    for _ in range(h):
        nextp = [0 for _ in range(w)]
        for i in range(w):
            nextp[i] = (pattern[i] * (fibonacci[max(0, i - 1)] * fibonacci[max(0, w - (i + 2))])) % MOD
            if i > 0:
                nextp[i] += (pattern[i - 1] * (fibonacci[max(0, i - 2)] * fibonacci[max(0, w - (i + 2))])) % MOD
            if i < w - 1:
                nextp[i] += (pattern[i + 1] * (fibonacci[max(0, i - 1)] * fibonacci[max(0, w - (i + 3))])) % MOD
            nextp[i] %= MOD
        pattern = nextp
    print(pattern[k-1])


main()

Submission status: Runtime Error

Solution code:
import sys,collections as cl
Max = sys.maxsize
def l():
	return list(map(int,input().split()))
def m():
	return map(int,input().split())
def s(x):
	a = []
	aa = x[i]
	su = 1
	for i in range(len(x)-1):
		if aa == x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a

h,w,k = m()

a = [1,1,2,3,5,8,13]

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

for i in range(h):
	for j in range(w):
		l[i+1][j+1] = (l[i][j]*(a[max(0,j-1)] * a[w - 1 - j]) +l[i][j+1]*(a[j] * a[w - 1 - j]) + l[i][j+2]*(a[j] * a[max(0,w - 2 - j)]))%(10**9+7)
print(l[h][k])

Submission status: Runtime Error

Solution code:
import sys,collections as cl
Max = sys.maxsize
def l():
	return list(map(int,input().split()))
def m():
	return map(int,input().split())
def s(x):
	a = []
	aa = x[i]
	su = 1
	for i in range(len(x)-1):
		if aa == x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a

h,w,k = m()

a = [1,1,2,3,5,8,13]

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

for i in range(h):
	for j in range(w):
		l[i+1][j+1] = l[i][j]*(a[max(0,j-1)] * a[w - 1 - j]) +l[i][j+1]*(a[j] * a[w - 1 - j]) + l[i][j+2]*(a[j] * a[max(0,w - 2 - j)])
print(l[h][k])

Submission status: Runtime Error

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

memo = [-1]*(W+1)
memo[0] = 1
memo[1] = 1
def cnt(n):
	if memo[n] >= 0:
		return memo[n]
	memo[n] = cnt(n-1) + cnt(n-2)
	return memo[n]

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

for i in range(0,H):
	dp[i+1][1] = (dp[i][1]*cnt(W-1)+dp[i][2]*cnt(W-2) % MOD)
	dp[i+1][W] = (dp[i][W]*cnt(W-1)+dp[i][W-1]*cnt(W-2) % MOD)
	for j in range(1,W):
		dp[i+1][j] = (dp[i][j]*cnt(j-1)*cnt(W-j) + dp[i][j-1]*cnt(j-2)*cnt(W-j) + dp[i][j+1]*cnt(j-1)*cnt(W-j-1)) % MOD

print(dp[H][K])

Submission status: Runtime Error

Solution code:
H,W,K=map(int,input().split())
if W==1:
    print(1)
    quit()

INF=1e9+7
dp=[[0]*W for i in range(H+1)]
dp[0][0]=1
d=W-1
a=max(0,d-1)
b=max(0,d-2)
dic={0:0,1:1,2:2,3:4,4:7,5:12,6:20}
a=dic[a]+1
b=dic[b]+1
def func(w):
    c=dic[w-1]+1
    e=dic[d-w-1]+1
    return c*e
def func1(w):
    c=dic[w-1-1]+1
    e=dic[d-w-1]+1
    return c*e
def func2(w):
    c=dic[w-1]+1
    e=dic[d-w-1-1]+1
    return c*e
for i in range(H):
    for w in range(W):
        if w==0:
            dp[i+1][w]=(dp[i][w]*a)+(dp[i][w+1]*b)
            dp[i+1][w]%=INF
        elif w==W-1:
            dp[i+1][w]=(dp[i][w]*a)+(dp[i][w-1]*b)
            dp[i+1][w]%=INF
        elif w==1 :
            dp[i+1][w]=(dp[i][w]*b)+(dp[i][w-1]*b)+(dp[i][w+1]*func2(w))
            dp[i+1][w]%=INF
        elif w==W-2:
            dp[i+1][w]=(dp[i][w]*b)+(dp[i][w-1]*func1(w))+(dp[i][w+1]*b)
            dp[i+1][w]%=INF
        else:
            dp[i+1][w]=(dp[i][w]*func(w))+(dp[i][w-1]*func1(w))+(dp[i][w+1]*func2(w))
            dp[i+1][w]%=INF

print(int(dp[H][K-1]%INF))

Submission status: Runtime Error

Solution code:
from sys import exit
H,W,K = [int(n) for n in input().split()]
memo = [[0 for _ in range(H+1)] for __ in range(W)]
memo[0][0] = 1
for h in range(1,H+1):
    for pt in range((1 << W-1)):#1 == 線あり 0 == 線なし　とする
        pts = bin(pt)[2:]
        pts = pts[::-1]#反転
        if "11" in pts: continue
        # print(pts)
        #各パターンの時の各線の計算
        for i in range(W):
            if i < len(pts) and pts[i] == "1":
                # print(i)
                memo[i][h] += memo[i+1][h-1]
                memo[i+1][h] += memo[i][h-1]
                i+=1#よみとばす
            else:
                memo[i][h] += memo[i][h-1]
        for wt in range(0,W):
            # print(memo[wt])
print(memo[K-1][H])
    # for wt in range(0,W):
    #     print(memo[wt])
        # for i in range(0,N):
        #     if(bit & (1 << i)):#1が一本たっていて、iだけ横にシフトするものとマスクとの共通部分
        #         print(i)
            # print("BIT:", end="")
            # print(bin(1 << i))
exit()

Submission status: Runtime Error

Solution code:
H,W,K = map(int,input().split())
dp = []
for i in range(H+1):
  L = [0]*W
  dp.append(L)
fb = [1,1]
for i in range(W-2):
  fb.append(fb[i]+fb[i+1])
dp[0][0] = 1
for i in range(1,H+1):
  for j in range(W):
    if 1 <= j <= W-2:
      dp[i][j] = dp[i-1][j-1]*fb[j-1]*fb[W-j-1]+dp[i-1][j]*fb[j]*fb[W-j-1]+dp[i-1][j+1]*fb[j]*fb[W-j-2]
    elif j == 0:
      dp[i][j] = dp[i-1][j]*fb[W-1]+dp[i-1][j+1]*fb[W-2]
    else:
      dp[i][j] = dp[i-1][j]*fb[W-1]+dp[i-1][j-1]*fb[W-2]
print(dp[H][K-1]%(10**9+7))

Submission status: Runtime Error

Solution code:
h,w,k=map(int,input().split())
#a(h,x)
p=[-1]*w
p[0]=1
p[1]=2
def pat(x):
    if x<0 or x>=w:
        return 1
    else:
        if p[x]!=-1:
            return p[x]
        else:
            return pat(x-2)+pat(x-1)
        
for j in range(1):
    0
mo=10**9 +7

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

Submission status: Runtime Error

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

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

    

for i in range(1,H+1):
    for x in range(2**(W-1)):           
        Alloc = [0]*9
        tmp = x
        for y in range(1,8):  
            Alloc[y] = tmp%2
            tmp //= 2 
        for y in range(0,9):
            if Alloc[y] == 1 and Alloc[y+1] == 1:
                break
        else:   
            for j in range(1,9):  
                if Alloc[j-1] == 1: 
                    dp[i][j] += dp[i-1][j-1]
                elif Alloc[j] == 1:
                    dp[i][j] += dp[i-1][j+1]
                else:
                    dp[i][j] += dp[i-1][j]
                dp[i][j] %= 1000000007

print(dp[H][K])

Submission status: Runtime Error

Solution code:
def memorize(func):
    memo = {}
    def wrapper(*args):
        if args not in memo:
            memo[args] = func(*args)
        return memo[args]
    return wrapper

@memorize
def amida(W):   # W本の棒に対する1行アミダの引き方
    if W<2:
        return 1
    else:
        return amida(W-1)+amida(W-2)

@memorize
def amida2(H, W, x):
    if H==0:
        return 1 if x==1 else 0
    a = 0 if x==1 else amida(x-2)*amida(W-x)*amida2(H-1, W, x-1)
    b = amida(x-1)*amida(W-x)*amida2(H-1, W, x, y)
    c = 0 if x==W else amida(x-1)*amida(W-x-1)*amida2(H-1, W, x+1)
    return (a+b+c)%1000000007
print(amida2(*map(int, input().split())))

Submission status: Runtime Error

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

l = [0] * (W+1)
l[0] = 1
l[1] = 1
for i in range(2, W, 1):
  l[i] = l[i-2] + l[i-1]
def lines(N):
  if N >= 0:
    return l[N]
  return 1

def cnt(H, W, K, h, w):
  if h == H and w == K:
    print(h, w, 1)
    return 1
  elif (H - h) < abs(K - w):
    print(h, w, 0)
    return 0
  else:
    print(h, w, "next")
    if w == 0:
      print(lines(W-1), lines(W-2))
      return (cnt(H, W, K, h+1, w) * lines(W-1) + \
              cnt(H, W, K, h+1, w+1) * lines(W-2)) % 1000000007
    elif w == W-1:
      print(lines(W-1), lines(W-2))
      return (cnt(H, W, K, h+1, w) * lines(W-1) + \
              cnt(H, W, K, h+1, w-1) * lines(W-2)) % 1000000007
    else:
      return (cnt(H, W, K, h+1, w) * lines(w-1) * lines(W-w-1) + \
              cnt(H, W, K, h+1, w-1) * lines(w-2) * lines(W-w-1) + \
              cnt(H, W, K, h+1, w+1) * lines(w-1) * lines(W-w-2)) % 1000000007
     
print(cnt(H, W, K-1, 0, 0))

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <string>
#include <algorithm>

typedef long long ll;
const ll INF = (ll)1e18 + 1;
const ll MOD = (ll)1e9 + 7;

// print(x, y, z);
void print(){ std::cout << std::endl; }
template <typename Head> void print(Head&& head) { std::cout << head << std::endl; }
template <typename Head, typename... Tail> void print(Head&& head, Tail&&... tail)
{
  std::cout << head << " ";
  print(std::forward<Tail>(tail)...); // or print(tail...);
}

int main(int argc, char* argv[])
{
  ll H, W, K;
  std::cin >> H >> W >> K;
  K--;

  // dp[h][w] = 横線をh段引いたときに0がwに来る場合の数
  std::vector< std::vector<ll> > dp(H+1, std::vector<ll>(W, 0LL));
  dp[0][0] = 1;

  for (ll h = 0; h < H; h++) {
    for (ll bit = 0; bit < (1 << (W - 1)); bit++) {
      // 2 つの横線がつながっていないか調べる
      bool judge = true;
      for (ll line = 0; line < W - 2; line++) {
	if ((1 << line & bit) && (1 << (line + 1) & bit)) judge = false;
      }
      if (!judge) continue;

      // あみだ処理
      std::vector<ll> amida(W, 0LL);
      for (ll line = 0; line < W; line++) {
	amida[line] = line;
      }
      for (ll line = 0; line < W-1; line++) {
	if ((1 << line) & bit) std::swap(amida[line], amida[line+1]);
      }

      // 動的計画法の処理
      for (ll line = 0; line < W; line++) {
	dp[h + 1][amida[line]] += dp[h][line];
	dp[h + 1][amida[line]] %= MOD;
      }
    }
  }

  print(dp[H][K]);
  return 0;
}

Submission status: Runtime Error

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(w)]
    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)
        return lst
    
print(trio(h, w)[k-1] % 1000000007)

Submission status: Runtime Error

Solution code:
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(w)]
    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)
        return lst
    
print(trio(h, w)[k-1] % 1000000007)

Submission status: Runtime Error

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

a=[[0]*w for i in range(h+1)]

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]
  

for j in range(w):
  a[0][j]=0
a[0][0]=1

for i in range(1,h+1):
  for j in range(w):
    if j==0:
      a[i][j]=a[i-1][j]*fib(w)+a[i-1][j+1]*fib(w-1)
    elif 1<=j<w-1:
      a[i][j]=a[i-1][j-1]*fib(w-j)*fib(j)+a[i-1][j]*fib(w-j)*fib(j+1)+a[i-1][j+1]*fib(w-j-1)*fib(j+1)
    elif j==w-1:
      a[i][j]=a[i-1][j]*fib(w)+a[i-1][j-1]*fib(w-1)
print(a[h][k-1]%1000000007)