分数: 400 点
问题陈述
Amidakuji 是日本的一种传统彩票方法。
为了制作amidakuji,我们首先绘制 W 平行的垂直线,然后绘制连接它们的水平线。每条垂直线的长度为 H+1 [cm],水平线的端点必须位于 1, 2, 3, ..., or H 距离顶部垂直线 [cm]。
A 有效的amidakuji 是满足以下条件的amidakuji:
- 没有两条水平线共享一个端点。
- 每条水平线的两个端点必须处于相同高度。
- 水平线必须连接相邻的垂直线。

求满足以下条件的有效阿德库吉数,取模 1\ 000\ 000\ 007:如果我们沿着最左边垂直线的顶部到底部的路径,当遇到水平线时始终遵循水平线,我们就会到达底部 K从左侧算起第 3 条垂直线。
例如,在下面的 amakuji 中,我们将到达左起第四条垂直线的底部。

约束
- H 是介于 1 和 100 (含)。
- W 是介于 1 和 8 (含)。
- K 是介于 1 和 W (含)。
输入
输入由标准输入按以下格式给出:
H W K
输出
打印满足条件的amidakuji的数量,模 1\ 000\ 000\ 007.
示例输入 1
1 3 2
示例输出 1
1
只有以下一位amidakuji满足条件:

示例输入 2
1 3 1
示例输出 2
2
只有以下两个amidakuji满足条件:

示例输入 3
2 3 3
示例输出 3
1
只有以下一位amidakuji满足条件:

示例输入 4
2 3 1
示例输出 4
5
只有以下五位阿甘寺满足条件:

示例输入 5
7 1 1
示例输出 5
1
由于只有一条垂直线,因此我们无法绘制任何水平线。因此,满足条件的阿甘寺只有一种:没有横线的阿甘寺。
示例输入 6
15 8 5
示例输出 6
437760187
请务必打印答案模数 1\ 000\ 000\ 007.