题目描述

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, mod $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.

Amidakuji 是日本的一种传统彩票方法。

要制作一个 Amidakuji，我们首先要画出 $W$ 条平行的垂直线，然后画出连接它们的水平线。每条竖线的长度为 $H+1$ 。\水平线的端点必须位于从 $1, 2, 3, ...,$ 或 $H$ 开始的位置。\厘米）处。

有效的 amidakuji 是满足以下条件的 amidakuji：

• 没有两条水平线共用一个端点。
• 每条水平线的两个端点必须位于同一高度。
• 一条水平线必须连接相邻的垂直线。

求满足以下条件的有效idakuji 的数目，模为 $1\ 000\ 000\ 007$ ：如果我们从最左边的垂直线的顶端开始追踪路径到底部，遇到水平线时总是沿着水平线走，那么我们就会到达从左边开始的第 $K$ 条垂直线的底部。

例如，在下面的 amidakuji 中，我们将到达左起第四条竖线的底部。

输入格式

输入内容按以下格式标准输入：

$H$ $W$ $K$

输出格式

打印满足条件的 amidakuji 个数，取模 $1\ 000\ 000\ 007$ 。

样例 #1

样例输入 #1

1 3 2

样例输出 #1

1

样例 #2

样例输入 #2

1 3 1

样例输出 #2

2

样例 #3

样例输入 #3

2 3 3

样例输出 #3

1

样例 #4

样例输入 #4

2 3 1

样例输出 #4

5

样例 #5

样例输入 #5

7 1 1

样例输出 #5

1

样例 #6

样例输入 #6

15 8 5

样例输出 #6

437760187

说明

数据规模与约定

• $H$ 是介于 $1$ 和 $100$ （含）之间的整数。
• $W$ 是介于 $1$ 和 $8$ （含）之间的整数。
• $K$ 是介于 $1$ 和 $W$ （含）之间的整数。

样例 $1$ 解释

只有以下一个 amidakuji 符合条件：

样例 $2$ 解释

只有下面两个amidakuji满足条件：

样例 $3$ 解释

只有下面一个 amidakuji 符合条件：

样例 $4$ 解释

只有以下五个 amidakuji 符合条件：

样例 $5$ 解释

由于只有一条垂直线，我们无法绘制任何水平线。因此，只有一个 amidakuji 满足条件：没有水平线的 amidakuji。

样例 $6$ 解释

请务必打印出答案的模数 $1\ 000\ 000\ 007$ 。