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 = map(int, input().split())
  MOD = 10**9 + 7
  
  
  L = [0] * (W - 1)
  row = 0
  for i in range(2 ** (W - 1)):
      LL = format(i, "08b")
      Lf = 0
      for j in range(len(LL) - 1):
          if LL[j] == "1" and LL[j + 1] == "1":
              Lf = 1
      if Lf == 0:
          row += 1
          LL = LL[8 - (W - 1) :]
          for k in range(W - 1):
              if LL[k] == "1":
                  L[k] += 1
      # print(LL,Lf)
  
  
  B = []  # Bridge
  for _ in range(W):
      B.append([0, 0, 0])
  
  for i in range(W):
      if i != 0:
          B[i][0] = L[i - 1]
      else:
          B[i][0] = 0
  
      if i != W - 1:
          B[i][2] = L[i]
      else:
          B[i][2] = 0
  
      B[i][1] = row - B[i][0] - B[i][2]
  
  
  A = [[0] * (W + 2)]
  for _ in range(H):
      A.append([0] * (W + 2))
  
  A[0][1] = 1
  
  for i in range(H):
      for j in range(1, W + 1):
          A[i + 1][j - 1] += A[i][j] * (B[j - 1][0])
          A[i + 1][j] += A[i][j] * (B[j - 1][1])
          A[i + 1][j + 1] += A[i][j] * (B[j - 1][2])
  
  print(A[H][K] % MOD)
  
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."}]