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: """3/18 AtCoder（漸化式dp）
  一番左の棒からスタートして、K番目の棒に到達するようなあみだくじは
  何通り作れますかという趣旨の問題
  まず、この問題を解くうえで一番重要なのは、
  「ある高さh、棒jに至る経路の総数を求める漸化式が立てられる」ということ
  高さh、棒jに至る経路の総数をdp[h][j]とすれば、
  高さh-1からこの位置に至ることができるのは、
  棒j-1,j,j+1のいずれかしかない
  さらに、そこに至る経路数というのは結局
  「ほかの棒にどんな風に架け橋（横棒）がかかっているか」の場合の数なので、
  それをdp[h-1][j-1],dp[h-1][j],dp[h-1][j+1]にかけていく必要がある
  例えば、dp[h-1][j]を見てみる　これは、同じ棒から下ってくることを
  意味しているが、換言すれば「高さi-1とiには、棒jから伸びる横棒はない」
  ということである
  つまり、この高さにおける横棒の架かり方というのは
  「棒1~j-1までの架かり方」と「棒j+1~棒Wまでの架かり方」の
  二パターンしかないということになる
  ある高さにおける横棒のかかり方も漸化式で求められる　
  高さhにおける(横一列にかけ橋が並んでいる状況を考える）、
  n本の棒の間にかかる橋の場合の数の総数をf(n)と置くと、
  f(n) = f(n-1)+f(n-2)と書くことができる
  これは、f(n)が
  ①n本目とn-1本目の棒の間に橋が架かっていない→場合の数はf(n-2)と同じ
  ②n本目とn-1本目の棒の間に橋が架かっている→場合の数はf(n-1)と同じ
  の二パターンの合計だからである
  だから、dp[h-1][j]に掛ける数はいくつかということを考えたら、
  j-1本の棒の間にかかる橋の場合の数f(j-1)と、
  W-j本の棒の間にかかる橋の場合の数f(W-j)本ということになる　
  これと同様に、残り二本に対してもいくつかければよいかを考えて、
  dp[h][j]]に対する漸化式を立てればよい
  """
  
  H, W, K = map(int, input().split())
  dp = []
  for i in range(H + 1):  # 高さ0の分を余分に持っておく
      L = [0] * W
      dp.append(L)
  fb = [1, 1]  # フィボナッチ（f(n)=f(n-1)+f(n-2)）
  for i in range(W - 2):
      fb.append(fb[i] + fb[i + 1])
  dp[0][0] = 1  # 左端の棒の高さ0は初期位置なので1に
  if W != 1:  # 棒が一本以上あるときは
      for i in range(1, H + 1):
          for j in range(W):  # 棒が左端、右端、それ以外で場合分け
              if 1 <= j <= W - 2:
                  dp[i][j] = (
                      dp[i - 1][j - 1] * fb[j - 1] * fb[W - j - 1]
                      + dp[i - 1][j] * fb[j] * fb[W - j - 1]
                      + dp[i - 1][j + 1] * fb[j] * fb[W - j - 2]
                  )
              elif j == 0:
                  dp[i][j] = dp[i - 1][j] * fb[W - 1] + dp[i - 1][j + 1] * fb[W - 2]
              else:
                  dp[i][j] = dp[i - 1][j] * fb[W - 1] + dp[i - 1][j - 1] * fb[W - 2]
  else:
      dp[H][0] = 1
  print(dp[H][K - 1] % (10**9 + 7))  # 高さH（一番下）、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."}]