题目描述

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

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

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

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

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

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

输入格式

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

$H$ $W$ $K$

输出格式

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

题目大意

阿弥陀籤是日本一项古老的占卜方式。

为了制作一份阿弥陀籤，我们需要绘制 $W$ 条竖线，然后再绘制一些横线连接它们。每条竖线的长度为 $(H + 1) \text{ cm}$，它们被横线连接的位置一定会在距离顶端 $1, 2, 3, \ldots, H \text{ cm}$ 中的一处。

我们称一个阿弥陀籤是合法的，当且仅当其能满足以下条件：

• 不存在两条端点重合的横线。
• 一条横线的两端点必须在同一高度。
• 一条横线连接的需要是相邻的两条竖线。

请找到满足如下条件的合法阿弥陀籤的数量，对 $10 ^ 9 + 7$ 取模：如果我们从最左侧的竖线顶部出发往下，策略是在每次遇到横线时都选择经过它，最终到达从左到右第 $K$ 条竖线的底部。

举例来说，在下图的阿弥陀籤中，我们最终会到达从左到右第四条竖线的底部。

1 3 2

1

1 3 1

2

2 3 3

1

2 3 1

5

7 1 1

1

15 8 5

437760187

提示

制約

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

Sample Explanation 1

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

Sample Explanation 2

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

Sample Explanation 3

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

Sample Explanation 4

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

Sample Explanation 5

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

Sample Explanation 6

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