{"raw_statement":[{"iden":"problem statement","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)"},{"iden":"constraints","content":"*   $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)."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$H$ $W$ $K$"},{"iden":"sample input 1","content":"1 3 2"},{"iden":"sample output 1","content":"1\n\nOnly the following one amidakuji satisfies the condition:\n![image](https://img.atcoder.jp/ghi/c68c6daccfc4cba8bc94af5f1a80ef2f.png)"},{"iden":"sample input 2","content":"1 3 1"},{"iden":"sample output 2","content":"2\n\nOnly the following two amidakuji satisfy the condition:\n![image](https://img.atcoder.jp/ghi/4be150946de8bef9b14d9bc17814d963.png)"},{"iden":"sample input 3","content":"2 3 3"},{"iden":"sample output 3","content":"1\n\nOnly the following one amidakuji satisfies the condition:\n![image](https://img.atcoder.jp/ghi/9b2e9f49832458c3488b1e04afd51ed4.png)"},{"iden":"sample input 4","content":"2 3 1"},{"iden":"sample output 4","content":"5\n\nOnly the following five amidakuji satisfy the condition:\n![image](https://img.atcoder.jp/ghi/bf6ec766f8923ac2f082f538a6c736b6.png)"},{"iden":"sample input 5","content":"7 1 1"},{"iden":"sample output 5","content":"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."},{"iden":"sample input 6","content":"15 8 5"},{"iden":"sample output 6","content":"437760187\n\nBe sure to print the answer modulo $1\\ 000\\ 000\\ 007$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}