Problem:
 Score: 400 points    Problem 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.    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.       Constraints  H is an integer between 1 and 100 (inclusive).  W is an integer between 1 and 8 (inclusive).  K is an integer between 1 and W (inclusive).         Input Input is given from Standard Input in the following format:  H  W  K       Output Print the number of the amidakuji that satisfy the condition, modulo 1\ 000\ 000\ 007 .        Sample Input 1 1 3 2      Sample Output 1 1  Only the following one amidakuji satisfies the condition:        Sample Input 2 1 3 1      Sample Output 2 2  Only the following two amidakuji satisfy the condition:        Sample Input 3 2 3 3      Sample Output 3 1  Only the following one amidakuji satisfies the condition:        Sample Input 4 2 3 1      Sample Output 4 5  Only the following five amidakuji satisfy the condition:        Sample Input 5 7 1 1      Sample Output 5 1  As there is only one vertical line, we cannot draw any horizontal lines. Thus, there is only one amidakuji that satisfies the condition: the amidakuji with no horizontal lines.       Sample Input 6 15 8 5      Sample Output 6 437760187  Be sure to print the answer modulo 1\ 000\ 000\ 007 .

Solution (Python):
H, W, K = map(int, input().split())
MOD = 10 ** 9 + 7
if W == 1:
    print(1)
    exit()
ladder = W - 1
num_lad = [0] * ladder
limit = 0 
for i in range(2 ** ladder):
    flag = True
    for j in range(ladder-1):
        if (i >> j) & 1 and (i >> j+1) & 1:
            flag = False
    if not flag:
        continue
    limit += 1
    for j in range(ladder):
        
        if ((i >> j) & 1):
            num_lad[j] += 1

dp = [[0] * W for _ in range(H+1)]
dp[0][0] = 1

for i in range(1, H+1):
    for j in range(W):
        if j == 0:
            dp[i][j] = (dp[i-1][j] * (limit - num_lad[0]) + dp[i-1][j+1] * num_lad[0]) % MOD
        elif j == (W-1):
            dp[i][j] = (dp[i-1][j] * (limit - num_lad[ladder-1]) + dp[i-1][j-1] * num_lad[ladder-1]) % MOD
        else:
            dp[i][j] = (dp[i-1][j] * (limit - num_lad[j-1] - num_lad[j]) + \
                    dp[i-1][j+1] * num_lad[j] + dp[i-1][j-1] * num_lad[j-1]) % MOD

print(dp[H][K-1])

Solution (Python):
h,w,k=map(int,input().split())
mod = 10**9+7
l=[]
a=[[0 for i in range(w)] for j in range(w)]

def dsf(i,v):
  if i==w-1:
    t = list()
    for j in range(0,w):
      t.append(j)
    for j in range(w-1):
      if v & 2**(j):
        t[j],t[j+1]=t[j+1],t[j]
    for x in range(w):
      a[x][t[x]] += 1
    l.append(v)
  else:
    dsf(i+1,v)
    if v & 2**(i-1) == 0:
      dsf(i+1,v | 2**i)

if w==1:
  print(1)
  exit()

dsf(1,0)
dsf(1,1)

t=[[0 for i in range(w)] for j in range(2)]
t[0][0]=1

for i in range(h):
  for j in range(w):
    t[(i+1)%2][j] = 0
    t[i%2][j] %= mod
  for j in range(w):
    for x in range(w):
     t[(i+1)%2][x] += t[i%2][ｊ] * a[j][x]

print(t[h%2][k-1]%mod)

Solution (Python):
H, W, K = map(int, input().split())

mod = 10 ** 9 + 7

dp = [0] * W
dp[0] = 1

pattern = []
for i in range(1 << (W - 1)) :
    if '11' in bin(i) :
        continue
    pattern.append(i)

for _ in range(H) :
    dp_ = [0] * W
    for p in pattern :
        for i in range(W) :
            if i != W - 1 and p & (1 << i) :
                dp_[i+1] += dp[i]
                dp_[i+1] %= mod
            elif i != 0 and p & (1 << (i - 1)) :
                dp_[i-1] += dp[i]
                dp_[i-1] %= mod
            else :
                dp_[i] += dp[i]
                dp_[i] %= mod
    
    dp = dp_
    
print(dp[K-1])

Solution (Python):
MOD = 1000000007
H, W, K = map(int,input().split())
K -= 1

f_dic = {}
def f(x):
    if x in f_dic:
        return f_dic[x]
    elif x == 0:
        f_dic[0]=1
        return f_dic[0]
    elif x == 1:
        f_dic[1]=1
        return f_dic[1]
    else:
        f_dic[x] = f(x-1)+f(x-2)
        return f_dic[x]


if W == 1:
    print(1)

else:
    dp = [[0 for j in range(W)] for i in range(H+1)]
    dp[0][0] = 1
    for i in range(H):
        dp[i+1][0] += f(W-1)*dp[i][0]
        dp[i+1][1] += f(W-2)*dp[i][0]
        for j in range(1,W-1):
            dp[i+1][j-1] += f(j-1)*f(W-j-1)*dp[i][j]
            dp[i+1][j]   += f(j)  *f(W-j-1)*dp[i][j]
            dp[i+1][j+1] += f(j)  *f(W-j-2)*dp[i][j]
        dp[i+1][W-2] += f(W-2)*dp[i][W-1]
        dp[i+1][W-1] += f(W-1)*dp[i][W-1]
        for j in range(W):
            dp[i+1][j] %= MOD
    print(dp[H][K])

Solution (Python):
MOD = int(1e9 + 7)

sizeI, sizeJ, targetJ = map(int, input().split())

validRows = [row for row in range(1 << (sizeJ - 1)) if '11' not in bin(row)]

dp = [[0 for _ in range(sizeJ)] for _ in range(sizeI + 1)]
dp[0][0] = 1
for i in range(1, sizeI + 1):
    for j in range(sizeJ):
        for prevRow in validRows:
            if j - 1 >= 0 and (prevRow >> (j - 1)) & 1:
                dp[i][j] += dp[i - 1][j - 1]
            elif (prevRow >> j) & 1:
                dp[i][j] += dp[i - 1][j + 1]
            else:
                dp[i][j] += dp[i - 1][j]
            dp[i][j] %= MOD
print(dp[sizeI][targetJ - 1])

Solution (Python):
f=[0,1,1,2,3,5,8,13,21,34,55,89];h,w,k=map(int,input().split());a=[0]*(w+2);a[1]=1
for i in range(h):a=[0]+[(f[j-1]*f[w-j+1]*a[j-1]+f[j]*f[w-j+1]*a[j]+f[j]*f[w-j]*a[j+1])%(10**9+7)for j in range(1,w+1)]+[0]
print(a[k])

Solution (Python):
H, W, K = list(map(int, input().split(' ')))








mat = []
for i in range(H+1):
    mat.append([0] * (W))
mat[0][0] = 1

def get(h, w):
    if h < 0 or w < 0:
        return 0
    if h >= H or w >= W:
        return 0
    return mat[h][w]

def hoge(w):
    d={1:1, 2:2, 3:3, 4:5, 5:8, 6:13, 7:21}
    return d.get(w, 1)

for i in range(1,H+1):
    for j in range(W):
        mat[i][j] = get(i-1, j-1) * hoge(j-1) * hoge(W-j-1) +\
                    get(i-1, j)   * hoge(j)   * hoge(W-j-1) +\
                    get(i-1, j+1) * hoge(j)   * hoge(W-j-1-1)
print(mat[H][K-1] % 1000000007)

Solution (Python):
MOD = 1000000007
H, W, K = map(int, input().split())
table = [[0, 0, 0] for i in range(9)]

for i in range(2 ** (W-1)):
    n = [i & 2**j for j in range(8)]
    
    for i in range(7):
        if n[i] and n[i+1]:
            break
    else:
        i = 0
        while i < W:
            if not n[i]:
                table[i+1][1] += 1
                i += 1
            else:
                table[i+1][2] += 1
                table[i+2][0] += 1
                i += 2
    
dp = [[0 for i in range(W+2)] for j in range(H+1)]
dp[0][1] = 1

for i in range(1, H+1):
    for j in range(1, W+1):
        a = dp[i-1][j-1] * table[j][0]
        b = dp[i-1][j] * table[j][1]
        c = dp[i-1][j+1] * table[j][2]
        dp[i][j] = (a+b+c) % MOD
            
print(dp[H][K])

Solution (Python):
h, w, k = map(int, input().split())
dp = [1] + [0] * (w - 1)
mod = 1000000007

def mul(a, b):
    newmatrix = [[0] * w for _ in range(w)]
    for i in range(w):
        for j in range(w):
            newmatrix[i][j] = sum(a[i][k] * b[k][j] for k in range(w)) % mod
    return newmatrix

matrix = [[0] * w for _ in range(w)]
for b in range(1 << (w - 1)):
    valid = True
    for i in range(w - 1):
        if (b >> i) & 3 == 3:
            valid = False
    if valid:
        for i in range(w):
            if (b >> i) & 1 != 0:
                matrix[i][i + 1] += 1
            elif i > 0 and (b >> (i - 1)) & 1 != 0:
                matrix[i][i - 1] += 1
            else:
                matrix[i][i] += 1

ret = [[1 if i == j else 0 for i in range(w)] for j in range(w)]
while h > 0:
    if h & 1 == 1:
        ret = mul(ret, matrix)
    matrix = mul(matrix, matrix)
    h //= 2

print(ret[0][k - 1])

Solution (Python):
h, w, k = map(int, input().split())
dp = [1] + [0] * (w - 1)
mod = 1000000007
for _ in range(h):
    newdp = [0] * w
    for b in range(1 << (w - 1)):
        valid = True
        for i in range(w - 1):
            if (b >> i) & 3 == 3:
                valid = False
        if valid:
            for i in range(w):
                if (b >> i) & 1 != 0:
                    newdp[i + 1] = (newdp[i + 1] + dp[i]) % mod
                elif i > 0 and (b >> (i - 1)) & 1 != 0:
                    newdp[i - 1] = (newdp[i - 1] + dp[i]) % mod
                else:
                    newdp[i    ] = (newdp[i    ] + dp[i]) % mod
    dp = newdp
print(dp[k - 1])

Solution (Python):
h,w,k = map(int,input().split())
mod = 10**9+7
g = [[0]*3 for _ in range(w)]
for bit in range(1<<(w-1)):
  f = 0
  for i in range(w-2):
    if bit & (3<<i) == 3<<i:
      f = 1
      break
  if f:
    continue
  neu = [1]*w
  for i in range(w-1):
    if bit&(1<<i):
      g[i][2] += 1
      g[i+1][0] += 1
      neu[i] = 0; neu[i+1] = 0
    g[i][1] += neu[i]
  g[-1][1] += neu[-1]
g = [[0]*3] + g + [[0]*3]
ol = [0]*(w+2)
ol[k] = 1
for _ in range(h):
  new = [0]*(w+2)
  for i in range(1,w+1):
    new[i] = (ol[i-1]*g[i-1][2] + ol[i]*g[i][1] + ol[i+1]*g[i+1][0])%mod
  ol = new
print(ol[1])

Solution (Python):
import sys


H,W,K = [int(_) for _ in input().split()]
l = []
c = 0
if W == 1:
    print(1)
    sys.exit()

l.append([0 for _ in range(W-1)])

for i in range(0, W-1):
    a = [0 for _ in range(W-1)]
    for j in range(0, W-1):
        if j == i:
            a[j] = 1
        else:
            a[j] = 0
    l.append(a)

if W >= 4:
    for i in range(0, W-3):
        for j in range(i+2, W-1):
            a = [0 for _ in range(W-1)]
            for k in range(0, W-1):
                if k == i or k == j:
                    a[k] = 1
                else:
                    a[k] = 0
            l.append(a)

if W >= 6:
    for i in range(0, W-5):
        for j in range(i+2, W-3):
            for k in range(j+2, W-1):
                a = [0 for _ in range(W-1)]
                for p in range(W-1):
                    if p == i or p == j or p == k:
                        a[p] = 1
                    else:
                        a[p] = 0
                l.append(a)

if W == 8:
    l.append([1,0,1,0,1,0,1])


HW = [[0 for _ in range(W)] for _ in range(H+1)]
HW[0][0] = 1

for i in range(0, H):
    for j in range(0,W):
        for k in range(len(l)):
            q = HW[i][j]
            if j == 0:
                if l[k][j] == 1:
                    HW[i+1][j+1] += q
                else:
                    HW[i+1][j] += q
            elif j == W-1:
                if l[k][j-1] == 1:
                    HW[i+1][j-1] += q
                else:
                    HW[i+1][j] += q
            else:
                if l[k][j] == 0 and l[k][j-1] == 0:
                    HW[i+1][j] += q
                elif l[k][j] == 1:
                    HW[i+1][j+1] += q
                else:
                    HW[i+1][j-1] += q
        for x in range(0, W):
            HW[i+1][x] = HW[i+1][x] % 1000000007
  
ans = HW[H][K-1]

print(ans)

Solution (Python):
h,w,k=map(int,input().split())
mod=10**9+7
dp=[[0]*w for i in range(h+1)]
dp[0][0]=1
data=[]
for i in range(2**(w-1)):
    for j in range(1,w-1):
        if (i>>j)&1==(i>>j-1)&1 and (i>>j)&1==1:
            break
    else:
        data.append(i)
for i in range(1,h+1):
    for u in data:
        if u&1==1:
            dp[i][0]=(dp[i][0]+dp[i-1][1])%mod
        else:
            dp[i][0]=(dp[i][0]+dp[i-1][0])%mod
        if w>1:
            if (u>>w-2)&1==1:
                dp[i][w-1]=(dp[i][w-1]+dp[i-1][w-2])%mod
            else:
                dp[i][w-1]=(dp[i][w-1]+dp[i-1][w-1])%mod
        for j in range(1,w-1):
            if (u>>j-1)&1==1:
                dp[i][j]=(dp[i][j]+dp[i-1][j-1])%mod
            elif (u>>j)&1==1:
                dp[i][j]=(dp[i][j]+dp[i-1][j+1])%mod
            else:
                dp[i][j]=(dp[i][j]+dp[i-1][j])%mod
print(dp[h][k-1])

Solution (Python):
import copy

def f(n):
    if n==0:
        return 1
    elif n==1:
        return 2
    else:
        return f(n-1)+f(n-2)

p=10**9+7
H,W,K=map(int,input().split())

if W==1:
    ans=1
else:
    d={}
    for i in range(8):
        d[i]=f(i)
    d[-1]=d[-2]=d[-3]=1

    b=[0 for i in range(W+2)]
    a=[0 for i in range(W+2)]

    b[1]=d[W-2];b[2]=d[W-3]

    for i in range(H-1):
        for k in range(1,W+1):
            a[k]=b[k-1]*d[k-3]*d[W-k-1]
            a[k]+=b[k]*d[k-2]*d[W-k-1]
            a[k]+=b[k+1]*d[k-2]*d[W-k-2]
            a[k]%=p
        b=copy.copy(a)
    
    ans=b[K]

print(ans)

Solution (Python):
h,w,k = map(int, input().split())
k -= 1
mod = 1000000007
 
if w==1:
    print(1)
    exit()
 
dp = [[0 for _ in range(w)] for _ in range(h+1)]
dp[0][0] = 1
 
for hi in range(1,h+1):
    for b in range(2**(w-1)):
        judge = False
        for i in range(w-2):
            if (b>>i)&3 == 3:
                judge = True
                break
        if judge:
            continue
 
        perm = [i for i in range(w)]
        for i in range(w-1):
            if (b>>i)&1==1:
                perm[i],perm[i+1] = perm[i+1],perm[i]
        for i in range(w):
            dp[hi][perm[i]]  = (dp[hi][perm[i]]+dp[hi-1][i])%mod
 
print(dp[h][k])

Solution (Python):
h, w, k = map(int, input().split())
a = [0]*(w-1) + [0,1]
for i in range(w-1):
    a[i] = a[i-1] + a[i-2]
dp = [0]*(w+1)
tmp = [0]*(w+1)
dp[0] = 1
for _ in range(1, h+1):
    for i in range(w):
        tmp[i] = (dp[i]*a[i-1]*a[w-i-2]
            + dp[i+1]*a[i-1]*a[w-i-3]
            + dp[i-1]*a[i-2]*a[w-i-2]) % (10**9+7)
    dp, tmp = tmp, dp
print(dp[k-1])

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
 
    h,w,k = map(int,input().split())
    mod = 10**9+7
 
    if w == 1:
        print(1)
        return
 
    fib = [1,2,3,5]
    for i in range(100):
        fib.append(fib[len(fib)-1]+fib[len(fib)-2])
    fib.append(1)
    fib.append(1)
    fib.append(1)
 
 
    dp = [[0]*w for _ in [0]*h]
    dp[0][0] = fib[w-2]
    dp[0][1] = fib[w-3]
 
    for i in range(1,h):
        for j in range(w):
            dp[i][j] = (dp[i-1][j]*fib[j-1]*fib[w-2-j])%mod
            if j >= 1:
                dp[i][j] = (dp[i][j] + dp[i-1][j-1]*fib[j-2]*fib[w-2-j])%mod
            if j <= w-2:
                dp[i][j] = (dp[i][j] + dp[i-1][j+1]*fib[j-1]*fib[w-3-j])%mod
    
    print(dp[-1][k-1])
 
if __name__ == '__main__':
    main()

Solution (Python):
H, W, K = map(int, input().split())
dp = [[0 for i in range(W)] for j in range(H+1)]
mod = 10**9+7
dp[0][0] = 1

if W == 1:
    print(1)
else:
    for k in range(H):
        for i in range(2**(W-1)):
            b = format(i, "0{}b".format(W-1))
            flag = 1
            for j in range(len(b)-1):
                if b[j+1] == "1" and b[j] == "1":
                    flag = 0
                    break
            if flag == 0:
                continue

            for j in range(len(b)):
                if flag == 0:
                    flag = 1
                    continue
                if b[j] == "1":
                    dp[k+1][j+1] += dp[k][j]
                    dp[k+1][j] += dp[k][j+1]
                    dp[k+1][j+1] %= mod
                    dp[k+1][j] %= mod
                    flag = 0
                else:
                    dp[k+1][j] += dp[k][j]
                    dp[k+1][j] %= mod
            if b[-1] == "0":
                dp[k+1][-1] += dp[k][-1]
                dp[k+1][-1] %= mod
    print(dp[H][K-1])

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline

    h,w,k = map(int,input().split())
    mod = 10**9+7

    if w == 1:
        print(1)
        return

    fib = [1,2,3,5]
    for i in range(100):
        fib.append(fib[len(fib)-1]+fib[len(fib)-2])
    fib.append(1)
    fib.append(1)
    fib.append(1)


    dp = [[0]*w for _ in [0]*h]
    dp[0][0] = fib[w-2]
    dp[0][1] = fib[w-3]

    for i in range(1,h):
        for j in range(w):
            dp[i][j] = (dp[i-1][j]*fib[j-1]*fib[w-2-j])%mod
            if j >= 1:
                dp[i][j] = (dp[i][j] + dp[i-1][j-1]*fib[j-2]*fib[w-2-j])%mod
            if j <= w-2:
                dp[i][j] = (dp[i][j] + dp[i-1][j+1]*fib[j-1]*fib[w-3-j])%mod
    
    print(dp[-1][k-1])

if __name__ == '__main__':
    main()

Solution (Python):
mod = 10**9+7
H, W, K = map(int, input().split())
dp = [[0]*W for j in range(H+1)]
dp[0][0] = 1
if W == 1:
    print(1)
    exit()
for i in range(1, H+1):
    for j in range(1<<(W-1)):
        if any((j>>k) & 1 and j>>((k+1)) & 1 for k in range(W-2)):
            continue
        if j&1:
            dp[i][0] += dp[i-1][1]
        else:
            dp[i][0] += dp[i-1][0]
        dp[i][0] %= mod
        for k in range(1, W-1):
            if (j>>k)&1:
                dp[i][k]+= dp[i-1][k+1]
            elif (j>>(k-1))&1:
                dp[i][k]+= dp[i-1][k-1]
            else:
                dp[i][k]+=dp[i-1][k]
            dp[i][k] %= mod
        if (j>>(W-2))&1:
            dp[i][W-1] += dp[i-1][W-2]
        else:
            dp[i][W-1] += dp[i-1][W-1]
        dp[i][W-1] %= mod           
print(dp[H][K-1])

Solution (Python):
import sys
input = sys.stdin.readline

def main():
    H, W, K = map(int, input().split())
    fib = [1, 1]
    for i in range(W-2):
        fib.append(fib[-2] + fib[-1])
    
    nex = [[0] * W for i in range(W)]
    for i in range(W):
        nex[i][i] = fib[i] * fib[W-1-i]
        if i > 0:
            nex[i][i-1] = fib[i-1] * fib[W-i-1]
        if i < W-1:
            nex[i][i+1] = fib[i] * fib[W-i-2]
    MOD = int(1e9) + 7
    dp = [[0] * W for i in range(H+1)]
    dp[0][0] = 1
    for i in range(H):
        for j in range(W):
            dp[i+1][j] += dp[i][j] * nex[j][j]
            dp[i+1][j] %= MOD
            if j > 0:
                dp[i+1][j-1] += dp[i][j] * nex[j][j-1]
                dp[i+1][j-1] %= MOD
            if j < W-1:
                dp[i+1][j+1] += dp[i][j] * nex[j][j+1]
                dp[i+1][j+1] %= MOD
    print(dp[H][K-1])


if __name__ == "__main__":
    main()

Solution (Python):
from collections import defaultdict

H, W, K = list(map(int, input().split()))

mapping = defaultdict(int)

for source in range(1 << (W - 1)):
    l = [False for _ in range(W - 1)]
    for i in range(W - 1):
        l[i] = bool(source & (1 << i))
    flag = True
    for i in range(W - 2):
        if l[i] and l[i + 1]:
            
            flag = False
            
            break
    if not flag:
       continue

    for i in range(W):
        if i > 0 and l[i - 1]:  
            mapping[i, i - 1] += 1
        elif i < W - 1 and l[i]:  
            mapping[i, i + 1] += 1
        else:
            mapping[i, i] += 1

last = [1] + [0] * (W - 1)
for _ in range(H):
    current = [0] * W
    for (start, dst), count in mapping.items():
        current[dst] += last[start] * count
        current[dst] = current[dst] % (10**9+7)
    last = current
print(last[K - 1] %(10**9+7))

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")


def A():
    x, y = LI()
    print(x+y//2)
    return


def B():
    II()
    t, a = LI()
    h = LI()
    ans = [0,inf]
    for num, i in enumerate(h):
        if ans[1] > abs(t - a - i * 0.006):
            ans = [num, abs(t - a - i * 0.006)]
    print(ans[0] + 1)
    return


def C():
    n, m = LI()
    py = LIR(m)
    pya = py[::1]
    py.sort(key=lambda x: x[1])
    city = [1 for i in range(n)]
    dicity = {}
    for p, y in py:
        dicity[(p,y)] = city[p-1]
        city[p-1] += 1    
    for p, y in pya:
        a = "00000" + str(p)
        a = a[-6:]
        b = "00000" + str(dicity[(p, y)])
        b = b[-6:]
        print(a+b)

    return


def D():
    h, w, k = LI()
    stick = [[0, 0] for i in range(w)]
    stick[0] = [1, 0]
    for i in range(1, w):
        stick[i][0] += stick[i - 1][0] + stick[i - 1][1]
        stick[i][1] += stick[i - 1][0]
    dp1 = [0] * (w + 2)
    dp1[1] = 1
    for i in range(h):
        dp2 = [0] * (w + 2)
        for wi in range(1, w + 1):
            tmp = dp1[wi - 1] * stick[wi - 1][1] * stick[w - wi][0]
            tmp += dp1[wi + 1] * stick[w - wi][1] * stick[wi - 1][0]
            tmp += dp1[wi] * stick[wi - 1][0] * stick[w - wi][0]
            dp2[wi] = tmp
            dp2[wi] %= mod
        dp1 = dp2
    print(dp2[k])

    return


if __name__ == '__main__':
    D()

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce



sys.setrecursionlimit(2147483647)
INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007



def fib(n):
    a, b = 1, 1
    fib_list = [1] * n
    for i in range(n - 2):
        a, b = a + b, a
        fib_list[i + 2] = a
    return fib_list



h, w, k = LI()
L = [0] + fib(w + 1)
dp = [[0] * w for _ in range(h + 1)]
dp[0][0] = 1
for i in range(h):
    for j in range(w):
        dp[i + 1][j - 1] = (dp[i + 1][j - 1] + dp[i][j] * L[j] * L[w - j]) % mod
        if j + 1 < w:
            dp[i + 1][j + 1] = (dp[i + 1][j + 1] + dp[i][j] * L[j + 1] * L[w - j - 1]) % mod
        dp[i + 1][j] = (dp[i + 1][j] + dp[i][j] * L[j + 1] * L[w - j]) % mod



print(dp[-1][k - 1])

Solution (Python):
def main():
    H, W, K = map(int, input().split())

    dp = [[0] * (W + 5) for _ in range(H + 5)]

    dp[0][0] = 1
    MOD = 10**9 + 7

    for h in range(H):
        for j in range(1 << W-1):
            a = str(bin(j))[2:].zfill(W-1)
            if a.count('11') >= 1:
                continue
            for w in range(W):
                if w == 0:
                    
                    if a[w] == '0':
                        dp[h+1][w] += dp[h][w]
                        dp[h+1][w] %= MOD
                    
                    if a[w] == '1':
                        dp[h+1][w+1] += dp[h][w]
                        dp[h+1][w+1] %= MOD
                elif w == W-1:
                    
                    if a[w-1] == '0':
                        dp[h+1][w] += dp[h][w]
                        dp[h+1][w] %= MOD
                    
                    if a[w-1] == '1':
                        dp[h+1][w-1] += dp[h][w]
                        dp[h+1][w-1] %= MOD
                else:
                    
                    if a[w-1] == '1':
                        dp[h+1][w-1] += dp[h][w]
                        dp[h+1][w-1] %= MOD
                    
                    elif a[w] == '1':
                        dp[h+1][w+1] += dp[h][w]
                        dp[h+1][w+1] %= MOD
                    
                    else:
                        dp[h+1][w] += dp[h][w]
                        dp[h+1][w] %= MOD

    print(dp[H][K-1])

                
main()

Solution (Python):
def main():
    H, W, K = map(int, input().split())
    
    if W == 1:
        print(1)
        exit()

    MOD = 10 ** 9 + 7
    dp = [[0] * W for _ in range(H+1)]
    dp[0][0] = 1

    for h in range(H):
        
        for i in range(2 ** (W-1)):
            
            if bin(i).count('11') >= 1:
                continue
            perm = [k for k in range(W)]
            for j in range(W-1):
                if (i >> j) & 1:
                    perm[j], perm[j+1] = perm[j+1], perm[j]

            for j in range(W):
                dp[h+1][perm[j]] += dp[h][j]
                dp[h+1][perm[j]] %= MOD

    print(dp[H][K-1])



main()

Solution (Python):
from itertools import product
H, W, K = map(int, input().split())
MOD = 10 ** 9 + 7

dp = [0] * W
pp = [0] * W

dp[0] = 1

for h in range(1,H+1):
    dp, pp = pp, dp
    dp = [0] * W
    
    for bs in product((0,1), repeat=W-1):
        swaps = []
        throughs = []
        
        valid = True
        for i in range(1,W-1):
            if bs[i] == bs[i-1] == 1:
                valid = False
                break
        if not valid:
            continue
        for i in range(W-1):
            if bs[i]:
                swaps.append((i,i+1))
            else:
                if len(swaps) == 0 or swaps[-1][-1] != i:
                    throughs.append(i)
        if len(swaps) == 0 or swaps[-1][-1] != W-1:
            throughs.append(W-1)
        for s in swaps:
            dp[s[0]] += pp[s[1]]
            dp[s[1]] += pp[s[0]]
            dp[s[0]] %= MOD
            dp[s[1]] %= MOD
        for t in throughs:
            dp[t] += pp[t]
            dp[t] %= MOD

print(dp[K-1])

Solution (Python):
H,W,K = [int(x) for x in input().split()]
dp=[[0]*W for _ in range(H+1)]
dp[0][0]=1
for i in range(H):
  for j in range(W):
    for bit in range(1<<(W-1)):
      flag = 1
      for k in range(W-2):
        if (bit&1<<k) and (bit&1<<k+1):
          flag = 0
      if flag!=1:
        continue
      nj = j
      if (bit&1<<j):
        nj = 1+j
      if j>0 and (bit&1<<(j-1)):
        nj = j-1
      dp[i+1][nj] +=dp[i][j]
      dp[i+1][nj] %=(10**9+7)
print(dp[H][K-1])

Solution (Python):

h,w,k = map(int,input().split())
mod = 10 ** 9 + 7
fib = [1,1,2,3,5,8,13,21,34]
now = [1] + [0] * w
if w > 1:
  for _ in range(h):
    last = now
    now = [0 for _ in range(w)]
    for i in range(w):
      if i == 0:
        now[i] += last[i] * fib[w-1] % mod
        now[i+1] += last[i] * fib[w-2] % mod
      elif i == w-1:
        now[i] += last[i] * fib[w-1] % mod
        now[i-1] += last[i] * fib[w-2] % mod
      else:
        now[i] += last[i] * fib[i] * fib[w-1-i] % mod
        now[i-1] += last[i] * fib[i-1] * fib[w-1-i] % mod
        now[i+1] += last[i] * fib[i] * fib[w-2-i] % mod
  print(now[k-1] % mod)
else:
  print(1)

Solution (Python):
H, W, K = map(int, input().split())

def swap(l, a, b):
    
    l[a], l[b] = l[b], l[a]

def check_row(m):
    l = list(range(W))
    b = 0
    for i in range(W-1):
        c = (m>>i)%2
        
        if b == c == 1:
            return False
        if c == 1:
            swap(l, i, i+1)
        b = c
    return l



dp = [[0 for j in range(W)] for i in range(H+1)]
dp[0][0] = 1

for i in range(1, H+1):
    for j in range(1<<(W-1)):
        r = check_row(j)
        if r == False:
            continue
        
        for k, r_i in enumerate(r):
            
            dp[i][r_i] = (dp[i][r_i] + dp[i-1][k]) % (10**9+7)


print(dp[H][K-1])

Solution (Python):
H,W,K = map(int, input().split())

dp = [[0]*W for _ in range(H+1)]
dp[0][0] = 1
if W==1:
  print(1)
else:
  for i in range(H):
    for j in range(2**(W-1)):
      flag = True
      for k in range(W-1):
        if k != W-2:
          
          if (((j >> k) & 1)&((j >> k+1) & 1)):
            flag = False
            break
      if flag:
        
        l = 0
        while l < W:
          if ((j >> l) & 1):
            dp[i+1][l] += dp[i][l+1]
            dp[i+1][l+1] += dp[i][l]
            l += 1
          else:
            dp[i+1][l] += dp[i][l]
          l += 1
        
        

  print(dp[-1][K-1]%(1000000007))

Solution (Python):
import sys
input = sys.stdin.readline

H,W,K = map(int,input().split())
mod = 1000000007
dp = [[0]*(W+2) for _ in range(H+1)]
dp[0][1]=1
for i in range(1,H+1):
    for j in range(1,W+1):
        x=0
        y=0
        z=0
        for k in range(2**(W-1)):
            tmp = format(k, "b")
            tmp = tmp.zfill(W-1)
            tmp += "0"
            tmp = list(tmp)
            Flag = True
            for l in range(len(tmp)-1):
                if tmp[l] == tmp[l+1] == "1" or (j>=2 and tmp[j-2] != "1"):
                    Flag = False
                    break
            if Flag:
                x+=1
        for k in range(2**(W-1)):
            tmp = format(k, "b")
            tmp = tmp.zfill(W-1)
            tmp += "0"
            tmp = list(tmp)
            Flag = True
            for l in range(len(tmp)-1):
                if tmp[l] == tmp[l+1] == "1" or (j>=2 and tmp[j-2] == "1") or (j>=1 and tmp[j-1] == "1"):
                    Flag = False
                    break
            if Flag:
                y+=1   
        for k in range(2**(W-1)):
            tmp = format(k, "b")
            tmp = tmp.zfill(W-1)
            tmp += "0"
            tmp = list(tmp)
            Flag = True
            for l in range(len(tmp)-1):
                if tmp[l] == tmp[l+1] == "1" or (j>=1 and tmp[j-1] != "1"):
                    Flag = False
                    break
            if Flag:
                z+=1   
        dp[i][j] += x*dp[i-1][j-1]+y*dp[i-1][j]+z*dp[i-1][j+1]
        dp[i][j] %= mod
print(dp[H][K]%mod)

Solution (Python):
MOD = 10**9 + 7
H, W, K = map(int, input().split())
table = [[0, 0, 0] for i in range(9)]

for i in range(2**(W-1)):
    n = [i & 2**j for j in range(8)]
    for i in range(7):
        if n[i] and n[i+1]:
            break
    else:
        i = 0
        while i < W:
            if not n[i]:
                table[i+1][1] += 1
                i += 1
            else:
                table[i+1][2] += 1
                table[i+2][0] += 1
                i += 2
dp = [[0 for i in range(W+2)] for j in range(H+1)]
dp[0][1] = 1

for i in range(1, H+1):
    for j in range(1, W+1):
        a = dp[i-1][j-1] * table[j][0]
        b = dp[i-1][j] * table[j][1]
        c = dp[i-1][j+1] * table[j][2]
        dp[i][j] = (a+b+c) % MOD
print(dp[H][K])