output_description: Print the number of the amidakuji that satisfy the condition, modulo 1\ 000\
  000\ 007.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      H W K
attempt: #include <iostream>
  #include <cmath>
  #include <vector>
  #include <map>
  #include <string>
  #include <algorithm>
  
  typedef long long ll;
  const ll INF = (ll)1e18 + 1;
  const ll MOD = (ll)1e9 + 7;
  
  // print(x, y, z);
  void print(){ std::cout << std::endl; }
  template <typename Head> void print(Head&& head) { std::cout << head << std::endl; }
  template <typename Head, typename... Tail> void print(Head&& head, Tail&&... tail)
  {
    std::cout << head << " ";
    print(std::forward<Tail>(tail)...); // or print(tail...);
  }
  
  int main(int argc, char* argv[])
  {
    ll H, W, K;
    std::cin >> H >> W >> K;
    K--;
  
    // dp[h][w] = 横線をh段引いたときに0がwに来る場合の数
    std::vector< std::vector<ll> > dp(H+1, std::vector<ll>(W, 0LL));
    dp[0][0] = 1;
  
    for (ll h = 0; h < H; h++) {
      for (ll bit = 0; bit < (1 << (W - 1)); bit++) {
        // 2 つの横線がつながっていないか調べる
        bool judge = true;
        for (ll line = 0; line < W - 2; line++) {
  	if ((1 << line & bit) && (1 << (line + 1) & bit)) judge = false;
        }
        if (!judge) continue;
  
        // あみだ処理
        std::vector<ll> amida(W, 0LL);
        for (ll line = 0; line < W; line++) {
  	amida[line] = line;
        }
        for (ll line = 0; line < W-1; line++) {
  	if ((1 << line) & bit) std::swap(amida[line], amida[line+1]);
        }
  
        // 動的計画法の処理
        for (ll line = 0; line < W; line++) {
  	dp[h + 1][amida[line]] += dp[h][line];
  	dp[h + 1][amida[line]] %= MOD;
        }
      }
    }
  
    print(dp[H][K]);
    return 0;
  }
  
problem_description: 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.
  
  ![](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.
  
  ![](https://img.atcoder.jp/ghi/d40ccbb88ee2ac60a6239c11b16ceb40.png)
samples: [{"input": "1 3 2", "output": "1\n    \n\nOnly the following one amidakuji satisfies the condition:\n\n![](https://img.atcoder.jp/ghi/c68c6daccfc4cba8bc94af5f1a80ef2f.png)\n\n* * *"}, {"input": "1 3 1", "output": "2\n    \n\nOnly the following two amidakuji satisfy the condition:\n\n![](https://img.atcoder.jp/ghi/4be150946de8bef9b14d9bc17814d963.png)\n\n* * *"}, {"input": "2 3 3", "output": "1\n    \n\nOnly the following one amidakuji satisfies the condition:\n\n![](https://img.atcoder.jp/ghi/9b2e9f49832458c3488b1e04afd51ed4.png)\n\n* * *"}, {"input": "2 3 1", "output": "5\n    \n\nOnly the following five amidakuji satisfy the condition:\n\n![](https://img.atcoder.jp/ghi/bf6ec766f8923ac2f082f538a6c736b6.png)\n\n* * *"}, {"input": "7 1 1", "output": "1\n    \n\nAs there is only one vertical line, we cannot draw any horizontal lines. Thus,\nthere is only one amidakuji that satisfies the condition: the amidakuji with\nno horizontal lines.\n\n* * *"}, {"input": "15 8 5", "output": "437760187\n    \n\nBe sure to print the answer modulo 1\\ 000\\ 000\\ 007."}]