Number of Amidakuji

AtCoder

IDabc113_d

Time2000ms

Memory256MB

Difficulty—

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. ![image](https://img.atcoder.jp/ghi/6b3e1470b9c551e0b7cfdcd802f300b3.png) 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. ![image](https://img.atcoder.jp/ghi/d40ccbb88ee2ac60a6239c11b16ceb40.png) ## 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$ [samples]

Samples

Input #1

1 3 2

Output #1

1

Only the following one amidakuji satisfies the condition:
![image](https://img.atcoder.jp/ghi/c68c6daccfc4cba8bc94af5f1a80ef2f.png)

Input #2

1 3 1

Output #2

2

Only the following two amidakuji satisfy the condition:
![image](https://img.atcoder.jp/ghi/4be150946de8bef9b14d9bc17814d963.png)

Input #3

2 3 3

Output #3

1

Only the following one amidakuji satisfies the condition:
![image](https://img.atcoder.jp/ghi/9b2e9f49832458c3488b1e04afd51ed4.png)

Input #4

2 3 1

Output #4

5

Only the following five amidakuji satisfy the condition:
![image](https://img.atcoder.jp/ghi/bf6ec766f8923ac2f082f538a6c736b6.png)

Input #5

7 1 1

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.

Input #6

15 8 5

Output #6

437760187

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

API Response (JSON)

{
  "problem": {
    "name": "Number of Amidakuji",
    "description": {
      "content": "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 li",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc113_d"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Amidakuji is a traditional method of lottery in Japan.\nTo make an amidakuji, we first draw $W$ parallel vertical lines, and then draw horizontal lines that connect them. The length of each vertical li...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments