AT_abc113_d [ABC113D] Number of Amidakuji

[problemUrl]: https://atcoder.jp/contests/abc113/tasks/abc113_d あみだくじは, 日本に古くから伝わる伝統的なくじ引きである. あみだくじを作るには, まず $ W $ 本の平行な縦線を引き, 次にそれらを繋ぐ横線を引いていく. それぞれの縦棒の長さは $ H+1 $ \[cm\] であり、横線の端点となれるのは上から $ 1,2,3,...,H $ \[cm\] の位置のみである. ここで,「正しいあみだくじ」とは, 以下のような条件を満たすあみだくじのことである. - どの $ 2 $ つの横棒も端点を共有しない. - それぞれの横棒の $ 2 $ つの端点は同じ高さになければならない. - 横棒は隣り合う縦線を繋がなければならない.  縦棒 $ 1 $ の上端から, 横線があれば必ずそれを通るというルールで下へたどったときに, 最終的にたどり着く縦棒の番号が $ K $ となるような「正しいあみだくじ」の本数を $ 1\ 000\ 000\ 007 $ で割った余りを求めなさい. 例として, 以下のあみだくじにおいて, 最終的にたどり着く縦棒の番号は $ 4 $ である. 

入力は以下の形式で標準入力から与えられる。 > $ H $ $ W $ $ K $

条件を満たすあみだくじの本数を $ 1\ 000\ 000\ 007 $ で割った余りを出力しなさい.

### 制約 - $ H $ は $ 1 $ 以上 $ 100 $ 以下の整数 - $ W $ は $ 1 $ 以上 $ 8 $ 以下の整数 - $ K $ は $ 1 $ 以上 $ W $ 以下の整数 ### Sample Explanation 1 以下の $ 1 $ 個のあみだくじのみが条件を満たす. !\[ \](https://img.atcoder.jp/abc113/c68c6daccfc4cba8bc94af5f1a80ef2f.png) ### Sample Explanation 2 以下の $ 2 $ 個のあみだくじのみが条件を満たす. !\[ \](https://img.atcoder.jp/abc113/4be150946de8bef9b14d9bc17814d963.png) ### Sample Explanation 3 以下の $ 1 $ 個のあみだくじのみが条件を満たす. !\[ \](https://img.atcoder.jp/abc113/9b2e9f49832458c3488b1e04afd51ed4.png) ### Sample Explanation 4 以下の $ 5 $ 個のあみだくじのみが条件を満たす. !\[ \](https://img.atcoder.jp/abc113/bf6ec766f8923ac2f082f538a6c736b6.png) ### Sample Explanation 5 縦線が $ 1 $ 本しかないので, 横線をそもそも引くことができない. よって条件を満たすあみだくじは「一本も横線を引かない」の $ 1 $ 通りしかない. ### Sample Explanation 6 答えを $ 1\ 000\ 000\ 007 $ で割った余りを出力すること.