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: H, W, K = [int(x) for x in input().split()]
  p = 10**9 + 7
  
  # H = 1, 縦棒W本のあみだくじの数　→フィボナッチ数列
  h1amida = [1, 1, 2] + [None] * 6
  for i in range(3, 9):
      h1amida[i] = h1amida[i - 2] + h1amida[i - 1]
  
  # dp[h][k] = 縦棒の長さh+1、縦棒の本数W、ゴールの棒kとなるあみだの数
  # dp[0][*]とdp[*][0]はダミー
  dp = [[0 for _ in range(W + 1)] for _ in range(H + 1)]
  
  for k in range(1, W + 1):
      if k == 1:
          dp[1][k] = h1amida[W - 1]
      elif k == 2:
          dp[1][k] = h1amida[W - 2]
      else:
          dp[1][k] = 0
  
  for h in range(2, H + 1):
      for k in range(1, W + 1):
          if k > 1:
              dp[h][k] += (dp[h - 1][k - 1] * h1amida[k - 2] % p) * h1amida[W - k] % p
          dp[h][k] += (dp[h - 1][k] * h1amida[k - 1] % p) * h1amida[W - k] % p
          if k < W:
              dp[h][k] += (dp[h - 1][k + 1] * h1amida[k - 1] % p) * h1amida[W - k - 1] % p
          dp[h][k] %= p
  
  print(dp[H][K])
  
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."}]