配点: $400$ 点

問題文

あみだくじは, 日本に古くから伝わる伝統的なくじ引きである.

あみだくじを作るには, まず $W$ 本の平行な縦線を引き, 次にそれらを繋ぐ横線を引いていく. それぞれの縦棒の長さは $H+1$ [cm] であり、横線の端点となれるのは上から $1,2,3,...,H$ [cm] の位置のみである.

ここで,「正しいあみだくじ」とは, 以下のような条件を満たすあみだくじのことである.

• どの $2$ つの横棒も端点を共有しない.
• それぞれの横棒の $2$ つの端点は同じ高さになければならない.
• 横棒は隣り合う縦線を繋がなければならない.

縦棒 $1$ の上端から, 横線があれば必ずそれを通るというルールで下へたどったときに, 最終的にたどり着く縦棒の番号が $K$ となるような「正しいあみだくじ」の本数を $1\ 000\ 000\ 007$ で割った余りを求めなさい.

例として, 以下のあみだくじにおいて, 最終的にたどり着く縦棒の番号は $4$ である.

制約

• $H$ は $1$ 以上 $100$ 以下の整数
• $W$ は $1$ 以上 $8$ 以下の整数
• $K$ は $1$ 以上 $W$ 以下の整数

入力

入力は以下の形式で標準入力から与えられる。

$H$ $W$ $K$

出力

条件を満たすあみだくじの本数を $1\ 000\ 000\ 007$ で割った余りを出力しなさい.

1 3 2

1

以下の $1$ 個のあみだくじのみが条件を満たす.

1 3 1

2

以下の $2$ 個のあみだくじのみが条件を満たす.

2 3 3

1

以下の $1$ 個のあみだくじのみが条件を満たす.

2 3 1

5

以下の $5$ 個のあみだくじのみが条件を満たす.

7 1 1

1

縦線が $1$ 本しかないので, 横線をそもそも引くことができない. よって条件を満たすあみだくじは「一本も横線を引かない」の $1$ 通りしかない.

15 8 5

437760187

答えを $1\ 000\ 000\ 007$ で割った余りを出力すること.