幸运签

题目描述

あみだくじ(Amidakuji,俗称"抽签")是日本自古流传下来的传统抽签方式。

制作一道签,首先要画 $W$ 根互相平行的竖线,然后画连接它们的横线。每根竖线长 $H+1$ [cm],横线的端点只能位于从顶部数起第 $1,2,3,...,H$ [cm] 的位置。

这里,"正确的签"是指满足以下条件的签:

• 任意两根横线不共享端点。
• 每根横线的两个端点必须在同一高度。
• 横线必须连接相邻的两根竖线。

从竖线 $1$ 的上端出发,按照"遇到横线必定通过"的规则向下走,最终到达的竖线编号为 $K$ 的"正确的签"共有多少种?请输出这个数量对 $1\ 000\ 000\ 007$ 取模的结果。

例如,在下图中,最终到达的竖线编号为 $4$。

输入格式

输入按以下格式从标准输入给出:

$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$ 根竖线,因此根本不能画横线。所以满足条件的签只有"一根横线也不画"这一种。

15 8 5

437760187

注意要输出答案对 $1\ 000\ 000\ 007$ 取模的结果。

数据范围

• $H$ 是 $1$ 以上 $100$ 以下的整数
• $W$ 是 $1$ 以上 $8$ 以下的整数
• $K$ 是 $1$ 以上 $W$ 以下的整数