問題

解法

方針

まず、求める解を漸化式で表します。漸化式から解を求めるのはプログラムで地道に計算します。

ざっくりと漸化式を定義する

縦棒 $j$ の上から $i$ cm目のちょっと下に（上から $i$ cm目の横棒を移動した後ということ）たどり着くことができる高さ $i$ cm目までの正しいあみだくじの本数を $a_{i, j}$ とします。求める解は $a_{H, K}$ です。

初期条件

縦棒1の上端からあみだくじは開始するので、以下が成り立ちます。

$a_{0, 1} = 1$
$a_{0, j} = 0 (j \geq 2)$

また、便宜上、 $j \leq 0$ または $j \geq W + 1$ を満たす $j$ について、 $a_{i, jj}=0$ と定義しておきます。

漸化式

縦棒 $j$ の上から $i$ cm目のちょっと下に（上から $i$ cm目の横棒を移動した後ということ）たどり着くパターンは以下の3通りです。

縦棒 $j - 1$ の上から $i - 1$ cm目のちょっと下（上から $i - 1$ cm目の横棒を移動した後ということ）を通過し、上から $i$ cm目の縦棒 $j-1, j$ を繋ぐ横線をたどってくるパターン
縦棒 $j$ の上から $i - 1$ cm目のちょっと下（上から $i - 1$ cm目の横棒を移動した後ということ）を通過し、そのまま真下にたどってくるパターン
縦棒 $j + 1$ の上から $i - 1$ cm目のちょっと下（上から $i - 1$ cm目の横棒を移動した後ということ）を通過し、上から $i$ cm目の縦棒 $j, j+1$ を繋ぐ横線をたどってくるパターン

また、上記の各パターンについて、上から $i$ cm目の横棒には自由度があることに注意します。例えば、一つ目のパターンでは、縦棒 $j-1, j$ を繋ぐ横線させあれば、縦棒 $j+1, j+2$ を繋ぐ横線があろうがなかろうが構いません（正しいあみだくじとするため、縦棒 $j-2, j-1$ を繋ぐ横線、および、縦棒 $j, j+1$ を繋ぐ横線は引けないことに注意してください）。上記のパターン分けと自由度から以下の形の漸化式を得ます。

$a_{i, j}= c_{1, j-2} c_{j+1, W} a_{i-1, j-1} + c_{1, j-1} c_{j+1, W} a_{i-1, j} + c_{1, j-1} c_{j+2, W} a_{i-1, j+1}$

$c$ は自由度を表す係数です。縦棒 $j$ から縦棒 $j'$ までの間に（正しいあみだくじであるように）横線を引くパターン数を $c_{j, j'}$ で表しています。ただし、 $j \geq j'$ ならば $c_{j, j'} = 1$ とします。

あとは、 $c$ を解析すれば、 $a_{H, K}$ を計算できます。

$c$ を解析する

$j \geq j'$ ならば $c_{j, j'} = 1$ としているので、いったん、 j < j' として議論します。

まず、縦棒 $j, j'$ の間には横線を引けるスペースが $j' - j$ 個あります。スペースの数だけに依存するので、 $c_{j, j'} = F_{j'-j}$ で表せます（スペースの数が $k$ 個のときの横線を引くパターン数を $F_{k}$ で表してます）。

まず、連続したスペースに横線を引けない制約から、 $F_{1}=2, F_{2}=3$ は直ちにわかります。さらに、最も左のスペースに横線を引く場合、その右のスペースに横線は引けないので、 $F_{k}=F_{k-1} + F_{k-2}$ という漸化式を得ます。すなわち、（初期条件は少し異なりますが） $F_{k}$ はフィボナッチ数列です。

さらに、 $j \geq j'$ ならば $c_{j, j'} = 1$ なので、 $F_{k} = 1 (k \leq 0)$ と定義しておくと計算の都合がよいです。

以上より、 $c_{j, j'}$ は上記フィボナッチlikeな値 $F_{j'-j}$ で求められることがわかりました。

求める解のまとめ

以下の漸化式について、 $a_{H, K}$ が求める解です。

$a_{0, 1} = 1$
$a_{0, j} = 0 (j \geq 2)$
$a_{i, j} = 0 (j \leq 0 \lor j \geq W + 1)$
$a_{i, j}= F_{j-3} F_{W-j-1} a_{i-1, j-1} + F_{j-2} F_{W-j-1} a_{i-1, j} + F_{j-2} F_{W - j - 2} a_{i-1, j+1}$

ただし、

$F_{k} = 1 (k \leq 0)$
$F_{k} = F_{k-1, k-2} (k \geq 1)$

です。また、解を出力する際は1000000007の剰余をとることを忘れないように注意してください。

ACしたコード

from functools import lru_cache

H, W, K = map(int, input().split())
def f(k):
  return 1 if k <= 0 else f(k-1) + f(k-2)
@lru_cache(maxsize=H*W)
def a(i, j):
  if j < 1 or j > W or (i == 0 and j != 1):
    return 0
  if i == 0 and j == 1:
    return 1
  return (f(j-3) * f(W-j-1) * a(i-1, j-1) + f(j-2) * f(W - j - 1) * a(i - 1, j) + f(j - 2) * f(W - j - 2) * a(i - 1, j + 1)) % 1000000007
ans = a(H, K)
print(ans)