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: import numpy as np
  from numpy.linalg import matrix_power
  
  H, W, K = map(int, input().split())
  
  
  def c(i, j):
      f = [1, 1, 2, 3, 5, 8, 13, 21]
      a = 0
      if i == j + 1:
          a = f[j] * f[W - i - 1]
      if j in (i, i + 1):
          a = f[i] * f[W - j - 1]
      return a
  
  
  def mp(m, n, p):
      a = m % p
      if n == 0:
          return np.identity(m.diagonal().size, dtype="int32")
      if n == 1:
          return a
      else:
          q, r = divmod(n, 2)
          x = np.matmul(a, a) % p
          if r == 1:
              return np.matmul(a, mp(x, q, p)) % p
          else:
              return mp(x, q, p) % p
  
  
  m = mp(np.array([[c(i, j) for i in range(W)] for j in range(W)]), H, 1000000007)
  x = np.array([[c(i, j) for i in range(W)] for j in range(W)])
  print(m[0, K - 1])
  
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."}]