Contest Duration: - (local time) (100 minutes) Back to Home
D - Number of Amidakuji /

Time Limit: 2 sec / Memory Limit: 1024 MB

﻿配点: 400

### 問題文

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

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

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

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

### 制約

• H1 以上 100 以下の整数
• W1 以上 8 以下の整数
• K1 以上 W 以下の整数

### 入力

H W K


### 入力例 1

1 3 2


### 出力例 1

1


### 入力例 2

1 3 1


### 出力例 2

2


### 入力例 3

2 3 3


### 出力例 3

1


### 入力例 4

2 3 1


### 出力例 4

5


### 入力例 5

7 1 1


### 出力例 5

1


### 入力例 6

15 8 5


### 出力例 6

437760187


Score: 400 points

### Problem Statement

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, modulo 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.

### Constraints

• H is an integer between 1 and 100 (inclusive).
• W is an integer between 1 and 8 (inclusive).
• K is an integer between 1 and W (inclusive).

### Input

Input is given from Standard Input in the following format:

H W K


### Output

Print the number of the amidakuji that satisfy the condition, modulo 1\ 000\ 000\ 007.

### Sample Input 1

1 3 2


### Sample Output 1

1


Only the following one amidakuji satisfies the condition:

### Sample Input 2

1 3 1


### Sample Output 2

2


Only the following two amidakuji satisfy the condition:

### Sample Input 3

2 3 3


### Sample Output 3

1


Only the following one amidakuji satisfies the condition:

### Sample Input 4

2 3 1


### Sample Output 4

5


Only the following five amidakuji satisfy the condition:

### Sample Input 5

7 1 1


### Sample Output 5

1


As there is only one vertical line, we cannot draw any horizontal lines. Thus, there is only one amidakuji that satisfies the condition: the amidakuji with no horizontal lines.

### Sample Input 6

15 8 5


### Sample Output 6

437760187


Be sure to print the answer modulo 1\ 000\ 000\ 007.