D - Number of Amidakuji

得分：400点

题目描述

阿美达桔(Amidakuji)是日本的一种传统抽奖方法。

为了制作一个阿美达桔，首先我们需要画出$W$条平行的竖线，然后再画出连接它们的横线。每条竖线的长度为$H+1$[cm]，横线的端点必须在竖线的顶端到底端的$1，2，3，...，$或$H$[cm]处。

一个有效的阿美达桔是满足以下条件的阿美达桔：

• 没有两条横线共用一个端点。
• 每条横线的两个端点必须在相同的高度。
• 每条横线必须连接相邻的竖线。

求满足以下条件的有效阿美达桔的数目，结果需对$1\ 000\ 000\ 007$取模：如果我们从最左边的竖线的顶端开始追踪，遇到横线时始终按照横线的方向到达相邻的竖线，要求到达左起第$K$条竖线的底端。

例如，在以下的阿美达桔中，我们将到达左起第四条竖线的底端。

约束条件

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

---

输入

从标准输入中获得输入，格式如下：

$H$ $W$ $K$

输出

输出满足条件的阿美达桔的数目，结果需对$1\ 000\ 000\ 007$取模。

---

1 3 2

1

只有以下一种阿美达桔满足条件：

---

1 3 1

2

以下两种阿美达桔满足条件：

---

2 3 3

1

只有以下一种阿美达桔满足条件：

---

2 3 1

5

以下五种阿美达桔满足条件：

---

7 1 1

1

因为只有一条竖线，我们无法画出任何横线。因此，只有一种满足条件的阿美达桔：没有横线的阿美达桔。

---

15 8 5

437760187

请务必对答案对$1\ 000\ 000\ 007$取模。