{"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 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.\nA _valid amidakuji_ is an amidakuji that satisfies the following conditions:\n\n*   No two horizontal lines share an endpoint.\n*   The two endpoints of each horizontal lines must be at the same height.\n*   A horizontal line must connect adjacent vertical lines.\n\n![image](https://img.atcoder.jp/ghi/6b3e1470b9c551e0b7cfdcd802f300b3.png)\nFind 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.\nFor example, in the following amidakuji, we will reach the bottom of the fourth vertical line from the left.\n![image](https://img.atcoder.jp/ghi/d40ccbb88ee2ac60a6239c11b16ceb40.png)\n\n## Constraints\n\n*   $H$ is an integer between $1$ and $100$ (inclusive).\n*   $W$ is an integer between $1$ and $8$ (inclusive).\n*   $K$ is an integer between $1$ and $W$ (inclusive).\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$H$ $W$ $K$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc113_d","tags":[],"sample_group":[["1 3 2","1\n\nOnly the following one amidakuji satisfies the condition:\n![image](https://img.atcoder.jp/ghi/c68c6daccfc4cba8bc94af5f1a80ef2f.png)"],["1 3 1","2\n\nOnly the following two amidakuji satisfy the condition:\n![image](https://img.atcoder.jp/ghi/4be150946de8bef9b14d9bc17814d963.png)"],["2 3 3","1\n\nOnly the following one amidakuji satisfies the condition:\n![image](https://img.atcoder.jp/ghi/9b2e9f49832458c3488b1e04afd51ed4.png)"],["2 3 1","5\n\nOnly the following five amidakuji satisfy the condition:\n![image](https://img.atcoder.jp/ghi/bf6ec766f8923ac2f082f538a6c736b6.png)"],["7 1 1","1\n\nAs 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."],["15 8 5","437760187\n\nBe sure to print the answer modulo $1\\ 000\\ 000\\ 007$."]],"created_at":"2026-03-03 11:01:14"}}