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):
import itertools

def fibonacci(n):
    if (n == 0):
        f_n = 1
    elif (n == 1):
        f_n = 1
    else:
        f_n = fibonacci(n-1) + fibonacci(n-2)

    return f_n

def X_amida_number(W, W_i):
    x_amida = "0" * (W - 1)
    left_x_amida = x_amida[:(W_i-2)] if(W_i-2 >= 0) else ""
    right_x_amida = x_amida[(W_i+1):]

    return fibonacci(len(left_x_amida) + 1) * fibonacci(len(right_x_amida) + 1)

def Y_amida_number(W, W_i):
    y_amida = "0" * (W - 1)
    left_y_amida = y_amida[:W_i-1] if(W_i-1 >= 0) else ""
    right_y_amida = y_amida[W_i+1:]

    return fibonacci(len(left_y_amida) + 1) * fibonacci(len(right_y_amida) + 1)

def Z_amida_number(W, W_i):
    z_amida = "0" * (W - 1)
    left_z_amida = z_amida[:W_i-1] if(W_i-1 >= 0) else ""
    right_z_amida = z_amida[W_i+2:]

    return fibonacci(len(left_z_amida) + 1) * fibonacci(len(right_z_amida) + 1)

def amida_all(amida_list, W):
    for i, j in itertools.product(range(W), range(3)):
        if(j == 0):
            amida_list[i][j] = X_amida_number(W, i)
        elif(j == 1):
            amida_list[i][j] = Y_amida_number(W, i)
        else:
            amida_list[i][j] = Z_amida_number(W, i)

    return amida_list

H, W, K = map(int, input().split())
amida_list = [[0]*3 for i in range(W)]
amida_list = amida_all(amida_list, W)

seed_dp_array = [0 for i in range(W)]
dp_array = [list(seed_dp_array) for i in range(H + 1)]
dp_array[0][0] = 1

for H_i, W_i in itertools.product(range(1, H + 1), range(W)):
    if (W_i == 0):
        if(W == 1):
            dp_array[H_i][0] = dp_array[H_i - 1][W_i] * amida_list[W_i][1]
        else:
            dp_array[H_i][0] = dp_array[H_i - 1][W_i] * amida_list[W_i][1] + dp_array[H_i - 1][W_i + 1] * amida_list[W_i][2]
    elif (W_i == (W - 1)):
        dp_array[H_i][W - 1] = dp_array[H_i - 1][W_i - 1] * amida_list[W_i][0] + dp_array[H_i - 1][W_i] * amida_list[W_i][1]
    else:
        dp_array[H_i][W_i] = dp_array[H_i - 1][W_i - 1] * amida_list[W_i][0] + dp_array[H_i - 1][W_i] * amida_list[W_i][1] + dp_array[H_i - 1][W_i + 1] * amida_list[W_i][2]

print(dp_array[H][K - 1] % 1000000007)

Solution (Python):
import itertools

def amida_counter(H_i_amida_list):
    counter = 0

    for amida_bin in range(2**len(H_i_amida_list)):
        if (("11" in format(amida_bin, "b")) == False):
            counter += 1

    return counter

def amida_number(left_amida, right_amida):
    left_counter = amida_counter(left_amida) if(len(left_amida) > 0) else 1
    right_counter = amida_counter(right_amida) if(len(right_amida) > 0) else 1

    return (left_counter * right_counter)

def X_amida_number(W, W_i):
    x_amida = "0" * (W - 1)
    left_x_amida = x_amida[:(W_i-2)] if(W_i-2 >= 0) else ""
    right_x_amida = x_amida[(W_i+1):]

    return amida_number(left_x_amida, right_x_amida)

def Y_amida_number(W, W_i):
    y_amida = "0" * (W - 1)
    left_y_amida = y_amida[:W_i-1] if(W_i-1 >= 0) else ""
    right_y_amida = y_amida[W_i+1:]

    return amida_number(left_y_amida, right_y_amida)

def Z_amida_number(W, W_i):
    z_amida = "0" * (W - 1)
    left_z_amida = z_amida[:W_i-1] if(W_i-1 >= 0) else ""
    right_z_amida = z_amida[W_i+2:]

    return amida_number(left_z_amida, right_z_amida)

def amida_all(amida_list, W):
    for i, j in itertools.product(range(W), range(3)):
        if(j == 0):
            amida_list[i][j] = X_amida_number(W, i)
        elif(j == 1):
            amida_list[i][j] = Y_amida_number(W, i)
        else:
            amida_list[i][j] = Z_amida_number(W, i)

    return amida_list

H, W, K = map(int, input().split())
amida_list = [[0]*3 for i in range(W)]
amida_list = amida_all(amida_list, W)

seed_dp_array = [0 for i in range(W)]
dp_array = [list(seed_dp_array) for i in range(H + 1)]
dp_array[0][0] = 1

for H_i, W_i in itertools.product(range(1, H + 1), range(W)):
    if (W_i == 0):
        if(W == 1):
            dp_array[H_i][0] = dp_array[H_i - 1][W_i] * amida_list[W_i][1]
        else:
            dp_array[H_i][0] = dp_array[H_i - 1][W_i] * amida_list[W_i][1] + dp_array[H_i - 1][W_i + 1] * amida_list[W_i][2]
    elif (W_i == (W - 1)):
        dp_array[H_i][W - 1] = dp_array[H_i - 1][W_i - 1] * amida_list[W_i][0] + dp_array[H_i - 1][W_i] * amida_list[W_i][1]
    else:
        dp_array[H_i][W_i] = dp_array[H_i - 1][W_i - 1] * amida_list[W_i][0] + dp_array[H_i - 1][W_i] * amida_list[W_i][1] + dp_array[H_i - 1][W_i + 1] * amida_list[W_i][2]

print(dp_array[H][K - 1] % 1000000007)

Solution (Python):
import itertools

def amida_counter(H_i_amida_list):
    counter = 0

    for amida_bin in range(2**len(H_i_amida_list)):
        if (("11" in format(amida_bin, "b")) == False):
            counter += 1

    return counter

def amida_number(left_amida, right_amida):
    left_counter = amida_counter(left_amida) if(len(left_amida) > 0) else 1
    right_counter = amida_counter(right_amida) if(len(right_amida) > 0) else 1

    return (left_counter * right_counter)

def X_amida_number(W, W_i):
    x_amida = "0" * (W - 1)
    left_x_amida = x_amida[:(W_i-2)] if(W_i-2 >= 0) else ""
    right_x_amida = x_amida[(W_i+1):]

    return amida_number(left_x_amida, right_x_amida)

def Y_amida_number(W, W_i):
    y_amida = "0" * (W - 1)
    left_y_amida = y_amida[:W_i-1] if(W_i-1 >= 0) else ""
    right_y_amida = y_amida[W_i+1:]

    return amida_number(left_y_amida, right_y_amida)

def Z_amida_number(W, W_i):
    z_amida = "0" * (W - 1)
    left_z_amida = z_amida[:W_i-1] if(W_i-1 >= 0) else ""
    right_z_amida = z_amida[W_i+2:]

    return amida_number(left_z_amida, right_z_amida)

H, W, K = map(int, input().split())
seed_dp_array = [0 for i in range(W)]
dp_array = [list(seed_dp_array) for i in range(H + 1)]
dp_array[0][0] = 1

for H_i, W_i in itertools.product(range(1, H + 1), range(W)):
    if (W_i == 0):
        if(W == 1):
            dp_array[H_i][0] = dp_array[H_i - 1][W_i] * Y_amida_number(W, W_i)
        else:
            dp_array[H_i][0] = dp_array[H_i - 1][W_i] * Y_amida_number(W, W_i) + dp_array[H_i - 1][W_i + 1] * Z_amida_number(W, W_i)
    elif (W_i == (W - 1)):
        dp_array[H_i][W - 1] = dp_array[H_i - 1][W_i - 1] * X_amida_number(W, W_i) + dp_array[H_i - 1][W_i] * Y_amida_number(W, W_i)
    else:
        dp_array[H_i][W_i] = dp_array[H_i - 1][W_i - 1] * X_amida_number(W, W_i) + dp_array[H_i - 1][W_i] * Y_amida_number(W, W_i) + dp_array[H_i - 1][W_i + 1] * Z_amida_number(W, W_i)

print(dp_array[H][K - 1] % 1000000007)

Solution (Python):
def amida_counter(H_i_amida_list):
    counter = 0

    for amida_bin in range(2**len(H_i_amida_list)):
        if (("11" in format(amida_bin, "b")) == False):
            counter += 1

    return counter

def amida_number(left_amida, right_amida):
    left_counter = amida_counter(left_amida) if(len(left_amida) > 0) else 1
    right_counter = amida_counter(right_amida) if(len(right_amida) > 0) else 1

    return (left_counter * right_counter)

def X_amida_number(W, W_i):
    x_amida = "0" * (W - 1)
    left_x_amida = x_amida[:(W_i-2)] if(W_i-2 >= 0) else ""
    right_x_amida = x_amida[(W_i+1):]

    return amida_number(left_x_amida, right_x_amida)

def Y_amida_number(W, W_i):
    y_amida = "0" * (W - 1)
    left_y_amida = y_amida[:W_i-1] if(W_i-1 >= 0) else ""
    right_y_amida = y_amida[W_i+1:]

    return amida_number(left_y_amida, right_y_amida)

def Z_amida_number(W, W_i):
    z_amida = "0" * (W - 1)
    left_z_amida = z_amida[:W_i-1] if(W_i-1 >= 0) else ""
    right_z_amida = z_amida[W_i+2:]

    return amida_number(left_z_amida, right_z_amida)

H, W, K = map(int, input().split())
seed_dp_array = [0 for i in range(W)]
dp_array = [list(seed_dp_array) for i in range(H + 1)]
dp_array[0][0] = 1

for H_i in range(1, H + 1):
    for W_i in range(W):
        if (W_i == 0):
            if(W == 1):
                dp_array[H_i][0] = dp_array[H_i - 1][W_i] * Y_amida_number(W, W_i)
            else:
                dp_array[H_i][0] = dp_array[H_i - 1][W_i] * Y_amida_number(W, W_i) + dp_array[H_i - 1][W_i + 1] * Z_amida_number(W, W_i)
        elif (W_i == (W - 1)):
            dp_array[H_i][W - 1] = dp_array[H_i - 1][W_i - 1] * X_amida_number(W, W_i) + dp_array[H_i - 1][W_i] * Y_amida_number(W, W_i)
        else:
            dp_array[H_i][W_i] = dp_array[H_i - 1][W_i - 1] * X_amida_number(W, W_i) + dp_array[H_i - 1][W_i] * Y_amida_number(W, W_i) + dp_array[H_i - 1][W_i + 1] * Z_amida_number(W, W_i)

print(dp_array[H][K - 1] % 1000000007)

Solution (Python):
import sys
from collections import deque
import copy

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def power_func(a,b,p):
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p

def calc_pattern_num(src, dst, W):
    if W == 1:
        if src == dst :
            return 1
        else:
            return 0

    count = 0
    for i in range(2**(W - 1)):
        is_OK = True
        for j in range((W - 1)):
            if j > 0:
                if ((i >> j) & 0x01)==1 and ((i >> j - 1)& 0x01) == 1:
                    is_OK = False
                    break

            if src - 1 == dst:
                if dst == j:
                    if ((i >> j) & 0x01) == 1:
                        pass
                    else:
                        is_OK = False
                        break
            elif src + 1 == dst:
                if src == j:
                    if ((i >> j) & 0x01) == 1:
                        pass
                    else:
                        is_OK = False
                        break
            elif src == dst:
                if src == j or src - 1 == j:
                    if ((i >> j) & 0x01) == 0 :
                        pass
                    else:
                        is_OK = False
                        break
        if is_OK == True:
            count += 1
    return count


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [H, W, K] = [long(input_raw[0]), long(input_raw[1]), long(input_raw[2])]










    dp = [[0 for j in range(W)] for i in range(H + 1)]
    dp[0][0] = 1L
    p = 1000000007L
    for i in range(H):
        for j in range(W):
            dp[i + 1][j] = (dp[i + 1][j] + ((calc_pattern_num(j, j, W) * dp[i][j])) % p) % p
            if j + 1 < W:
                dp[i + 1][j + 1] = (dp[i + 1][j + 1] + ((calc_pattern_num(j, j + 1, W) * dp[i][j])) % p) % p
            if j - 1 >= 0:
                dp[i + 1][j - 1] = (dp[i + 1][j - 1] + ((calc_pattern_num(j, j - 1, W) * dp[i][j])) % p) % p

    print dp[H][K - 1]























if __name__ == '__main__':
    main()

Solution (Python):
MOD = 10 ** 9 + 7


def main():
    h, w, k = map(int, input().split())

    dp = [[0 for j in range(w)] for i in range(h+1)]
    dp[0][0] = 1
    for i in range(h):
        for j in range(w):
            for l in range(2**(w-1)):
                for m in range(w-2):
                    if (l >> m) & 1 and (l >> (m+1) & 1):
                        break
                else:
                    if j < w - 1 and (l >> j) & 1:
                        dp[i+1][j+1] += dp[i][j]
                        dp[i+1][j+1] %= MOD
                    elif 0 < j and (l >> (j-1)) & 1:
                        dp[i+1][j-1] += dp[i][j]
                        dp[i+1][j-1] %= MOD
                    else:
                        dp[i+1][j] += dp[i][j]
                        dp[i+1][j] %= MOD

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


if __name__ == '__main__':
    main()

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


fib = [1, 1, 2, 3, 5, 8, 13, 21, 34]

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

for h in range(1, H + 1):
    for w in range(1, W + 1):
        dp[h][w] = dp[h - 1][w] * fib[w - 1] * fib[W - w]
        if w > 1:
            dp[h][w] += dp[h - 1][w - 1] * fib[w - 2] * fib[W - w]
        if w < W:
            dp[h][w] += dp[h - 1][w + 1] * fib[w - 1] * fib[W - w - 1]
        dp[h][w] %= mod

print(dp[H][K])

Solution (Python):
MOD = 10 ** 9 + 7


def main():
    h, w, k = map(int, input().split())

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

    cnt, valid = [0] * (w-1), []
    for i in range(2**(w-1)):
        c = [0] * (w-1)
        for j in range(w-1):
            if (i >> j) & 1:
                c[j] = 1

                if 0 < j and c[j-1] == 1:
                    break

        else:
            valid.append(c)
            for j in range(w-1):
                if c[j] == 1:
                    cnt[j] += 1

    num, ans = len(valid), 0
    for v in valid:
        dp = [[0] * w for i in range(h + 1)]
        if v[0]:
            dp[1][1] += 1
        else:
            dp[1][0] += 1

        for i in range(2, h+1):
            for j in range(w):
                com = num
                if 0 < j:
                    dp[i][j] = (dp[i][j]+dp[i-1][j-1]*cnt[j-1]) % MOD
                    com -= cnt[j-1]
                if j < w - 1:
                    dp[i][j] = (dp[i][j]+dp[i-1][j+1]*cnt[j]) % MOD
                    com -= cnt[j]
                dp[i][j] = (dp[i][j]+dp[i-1][j]*com) % MOD

        ans = (ans+dp[h][k-1]) % MOD

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
H, W, K = [int(_) for _ in input().split()]

if W == 1:
    print(1)
else:
    def fib(j):
        if j == 0 or j == 1:
            return 1
        else:
            count = 0
            for num in range(2 ** (j - 1)):
                bit = str(bin(num))
                flag = 1
                for i in range(2, len(bit) - 1):
                    if bit[i] == '1' and bit[i + 1] == '1':
                        flag = 0
                count += flag
            return count
    dp = [[1] + [0] * (W - 1)]
    for j in range(1, H + 1):
        dp.append([0] * W)
        for i in range(W):
            if i == 0:
                dp[j][i] = (dp[j - 1][i] * fib(i) * fib(W - i - 1) + dp[j - 1][i + 1] * fib(i) * fib(W - i - 2)) % 1000000007
            elif i == W - 1:
                dp[j][i] = (dp[j - 1][i] * fib(i) * fib(W - i - 1) + dp[j - 1][i - 1] * fib(i - 1) * fib(W - i - 1)) % 1000000007
            else:
                dp[j][i] = (dp[j - 1][i] * fib(i) * fib(W - i - 1) + dp[j - 1][i + 1] * fib(i) * fib(W - i - 2) + dp[j - 1][i - 1] * fib(i - 1) * fib(W - i - 1)) % 1000000007
    print(dp[H][K - 1])

Solution (Python):
H, W, K = [int(_) for _ in input().split()]
fib = [1, 1, 2, 3, 5 ,8, 13, 21]
dp = [[1] + [0] * (W - 1)]
if W == 1:
    print(1)
else:
    for j in range(1, H + 1):
        dp.append([0] * W)
        for i in range(W):
            if i == 0:
                dp[j][i] = (dp[j - 1][i] * fib[i] * fib[W - i - 1] + dp[j - 1][i + 1] * fib[i] * fib[W - i - 2]) % 1000000007
            elif i == W - 1:
                dp[j][i] = (dp[j - 1][i] * fib[i] * fib[W - i - 1] + dp[j - 1][i - 1] * fib[i - 1] * fib[W - i - 1]) % 1000000007
            else:
                dp[j][i] = (dp[j - 1][i] * fib[i] * fib[W - i - 1] + dp[j - 1][i + 1] * fib[i] * fib[W - i - 2] + dp[j - 1][i - 1] * fib[i - 1] * fib[W - i - 1]) % 1000000007
    print(dp[H][K - 1])

Solution (Python):
def X_amida_number(W, W_i):
    x_amida = "0" * (W - 1)

    if (W_i-2 >= 0):
        left_x_amida = x_amida[:(W_i-2)]
    else:
        left_x_amida = ""

    right_x_amida = x_amida[(W_i+1):]

    if(len(left_x_amida) > 0):
        left_counter = 0

        for left_bin in range(2**len(left_x_amida)):
            if (("11" in format(left_bin, "b")) == False):
                left_counter += 1
    else:
        left_counter = 1

    if(len(right_x_amida) > 0):
        right_counter = 0

        for right_bin in range(2**len(right_x_amida)):
            if (("11" in format(right_bin, "b")) == False):
                right_counter += 1

    else:
        right_counter = 1

    return (left_counter * right_counter)

def Y_amida_number(W, W_i):
    y_amida = "0" * (W - 1)

    if (W_i-1 >= 0):
        left_y_amida = y_amida[:W_i-1]
    else:
        left_y_amida = ""

    right_y_amida = y_amida[W_i+1:]

    if(len(left_y_amida) > 0):
        left_counter = 0

        for left_bin in range(2**len(left_y_amida)):
            if (("11" in format(left_bin, "b")) == False):
                left_counter += 1
    else:
        left_counter = 1

    if(len(right_y_amida) > 0):
        right_counter = 0

        for right_bin in range(2**len(right_y_amida)):
            if (("11" in format(right_bin, "b")) == False):
                right_counter += 1
    else:
        right_counter = 1

    return (left_counter * right_counter)

def Z_amida_number(W, W_i):
    z_amida = "0" * (W - 1)

    if (W_i-1 >= 0):
        left_z_amida = z_amida[:W_i-1]
    else:
        left_z_amida = ""

    right_z_amida = z_amida[W_i+2:]

    if(len(left_z_amida) > 0):
        left_counter = 0

        for left_bin in range(2**len(left_z_amida)):
            if (("11" in format(left_bin, "b")) == False):
                left_counter += 1
    else:
        left_counter = 1

    if(len(right_z_amida) > 0):
        right_counter = 0

        for right_bin in range(2**len(right_z_amida)):
            if (("11" in format(right_bin, "b")) == False):
                right_counter += 1
    else:
        right_counter = 1

    return (left_counter * right_counter)


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

seed_dp_array = [0 for i in range(W)]
dp_array = [list(seed_dp_array) for i in range(H + 1)]
dp_array[0][0] = 1

for H_i in range(1, H + 1):
    for W_i in range(W):
        if (W_i == 0):
            if(W == 1):
                dp_array[H_i][0] = dp_array[H_i - 1][W_i] * Y_amida_number(W, W_i)
            else:
                dp_array[H_i][0] = dp_array[H_i - 1][W_i] * Y_amida_number(W, W_i) + dp_array[H_i - 1][W_i + 1] * Z_amida_number(W, W_i)
        elif (W_i == (W - 1)):
            dp_array[H_i][W - 1] = dp_array[H_i - 1][W_i - 1] * X_amida_number(W, W_i) + dp_array[H_i - 1][W_i] * Y_amida_number(W, W_i)
        else:
            dp_array[H_i][W_i] = dp_array[H_i - 1][W_i - 1] * X_amida_number(W, W_i) + dp_array[H_i - 1][W_i] * Y_amida_number(W, W_i) + dp_array[H_i - 1][W_i + 1] * Z_amida_number(W, W_i)

print(dp_array[H][K - 1] % 1000000007)

Solution (Python):
import sys
import collections
import itertools
import math
import re
from collections import Counter
from collections import deque

MOD = (10 ** 9) + 7

H, W, K = [int(x) for x in input().split()]

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

L = []

ng_mask = 0b11

for i in range(2 ** (W - 1)):
    isOK = True
    for j in range(W - 1 - 1):
        m = ng_mask << j
        if (i & m) == m:
            isOK = False
    if isOK:
        L.append(i)





def getBit(n, i):
    i = i - 1
    tmp = n & (1 << i)
    return tmp != 0


dp[0][1] = 1

for h in range(1, H+1):
    for w in range(1, W+1):
        for l in L:
            d = 0
            if w == 1:
                if w == W:
                    d = dp[h - 1][w]
                else:
                    if getBit(l, w) == False:
                        d = dp[h - 1][w]
                    else:
                        d = dp[h - 1][w + 1]
            elif w == W:
                if getBit(l, w - 1):
                    d = dp[h - 1][w - 1]
                else:
                    d = dp[h - 1][w]
            else:
                if getBit(l, w - 1):
                    d = dp[h - 1][w - 1]
                elif getBit(l, w):
                    d = dp[h - 1][w + 1]
                else:
                    d = dp[h - 1][w]
            dp[h][w] += d

print(dp[H][K] % MOD)

sys.exit(0)

Solution (Python):
high,wide,end=map(int,input().split())

dp=[[[-1,-1,-1] for _ in range(wide)] for _ in range(high)]
fb=[-1 for _ in range(8)]
fb[0]=1
fb[1]=1
def MakeFibo(i):
    if fb[i-1]==-1:
        fb[i-1]=MakeFibo(i-1)
    if fb[i-2]==-1:
        fb[i-2]=MakeFibo(i-2)
    fb[i]=fb[i-1]+fb[i-2]
    return fb[i]
MakeFibo(7)

wide-=1
high-=1
end-=1
mod=10**9+7
def NZ(x):  
    if x<0:
        return 0
    else:
        return x


def amida(h,w,f):
    dp[h][w][2]=fb[NZ(w)]*fb[NZ(wide-w)]
    if f == 1: 
        if h==high and w==end:
            dp[h][w][f]=1
        elif h==high:
            dp[h][w][f]=0
        else: 
            if dp[h+1][w][1] == -1:
                amida(h+1,w,1)
            if dp[h+1][w][0] == -1:
                amida(h+1,w,0)
            dp[h][w][f]=dp[h+1][w][0]+dp[h+1][w][1]*dp[h+1][w][2]
    else: 
        dp[h][w][f]=0
        if w-1>=0: 
            if dp[h][w-1][1]==-1:
                amida(h,w-1,1)
            dp[h][w][f]+=dp[h][w-1][1]*fb[NZ(w-1)]*fb[NZ(wide-w)]
        if w+1<=wide: 
            if dp[h][w+1][1]==-1:
                amida(h,w+1,1)
            dp[h][w][f]+=dp[h][w+1][1]*fb[NZ(w)]*fb[NZ(wide-w-1)]
    dp[h][w][f]%=mod

amida(0,0,0)
amida(0,0,1)

print((dp[0][0][0]+dp[0][0][1]*dp[0][0][2])%mod)

Solution (Python):
h, w, k = map(int, input().split())
dp = [[0] * w for _ in range(h + 1)]
dp[0][0] = 1
fb = (1, 1, 2, 3, 5, 8, 13, 21)
for y in range(1, h + 1):
    for x in range(w):
        if x - 1 >= 0:
            dp[y][x] += dp[y - 1][x - 1] * fb[x - 1] * fb[w - x - 1]
        if x + 1 <= w - 1:
            dp[y][x] += dp[y - 1][x + 1] * fb[x] * fb[w - x - 2]
        dp[y][x] += dp[y - 1][x] * fb[x] * fb[w - x - 1]
        dp[y][x] %= 1000000007
print(dp[h][k - 1])

Solution (Python):
(h, w, k) = list(map(int, input().split()))
n = [0, 1] + [0 for _ in range(w - 1)]
c = {0: 1, 1: 1, 2: 2, 3: 3, 4: 5, 5: 8, 6: 13, 7: 21}
for i in range(h):
    nn = [0 for _ in range(w + 1)]
    for j in range(1, w + 1):
        nn[j] += c[max(0, j - 1)] * n[j]     * c[max(0, w - j)]
    for j in range(2, w + 1):
        nn[j] += c[max(0, j - 2)] * n[j - 1] * c[max(0, w - j)]
    for j in range(1, w):
        nn[j] += c[max(0, j - 1)] * n[j + 1] * c[max(0, w - j - 1)]
    n = nn

print(n[k] % 1000000007)

Solution (Python):
import sys
input=sys.stdin.readline
h,w,k = map(int, input().split())

lis = [0]*(w-1)
n = 0
for i in range(2**(w-1)):
    
    tmp = bin(i)[2:].zfill(w-1)
    if '11' in tmp:continue
    n += 1
    for j in range(w-1):
        lis[j] += int(tmp[j])


res = [1]+[0]*(w-1)
for i in range(h):
    res2 = res.copy()
    for j in range(w):
        if j == 0:
            a=0
            x = 0
        else:
            a = lis[j-1]
            x = res[j-1]
        if j== w-1:
            b = 0
            y = 0
        else:
            b = lis[j]
            y = res[j+1]
        res2[j] = x*a + res[j]*(n - a - b) + y*b
    res = res2
print(res[k-1] % (10**9+7))

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    h,w,k = LI()
    t = [1, 1, 2, 3, 5, 8, 13, 21]
    a = [0] * w
    a[0] = 1
    for i in range(h):
        n = [0] * w
        for j in range(w):
            n[j] = a[j] * t[j] * t[w-j-1] % mod
        for j in range(w-1):
            lr = t[j] * t[w-j-2]
            n[j] += a[j+1] * lr % mod
            n[j+1] += a[j] * lr % mod
        a = n

    return a[k-1] % mod


print(main())

Solution (Python):
h, w, k = map(int, input().split())
dp = [[0] * w for _ in range(h + 1)]
dp[0][0] = 1

fb_dic = {}
def fb(n):
  if n < 0:
    print("error")
    return -1
  if n == 0:
    return 1
  if n == 1:
    return 1
  if n in fb_dic:
    return fb_dic[n]
  ret = fb(n - 1) + fb(n - 2)
  fb_dic[n] = ret
  return ret

for y in range(1, h + 1):
  for x in range(w):
    if x - 1 >= 0:
      dp[y][x] += dp[y - 1][x - 1] * fb(x - 1) * fb(w - x - 1)
    if x + 1 <= w - 1:
      dp[y][x] += dp[y - 1][x + 1] * fb(x) * fb(w - x - 2)
    dp[y][x] += dp[y - 1][x] * fb(x) * fb(w - x - 1)
    dp[y][x] %= 1000000007


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

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):
m = 10**9+7
h, w, k = map(int, input().split())
a = [0]*(w-1) + [1]
for i in range(w-1):
    a[i] = a[i-1] + a[i-2]
dp = [0]*w
tmp = [0]*w
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]
        if i != w-1:
            tmp[i] += dp[i+1]*a[i-1]*a[w-i-3]
        if i != 0:
            tmp[i] += dp[i-1]*a[i-2]*a[w-i-2]
        tmp[i] %= m
    dp, tmp = tmp, dp
print(dp[k-1])

Solution (Python):
h, w, k = map(int, raw_input().split())
arr = [1, 2, 3, 5, 8, 13, 21, 34]


def p(num):
    return max(0, num)

r = [[0 for i in range(w)] for i in range(h+1)]
for i in range(h+1):
    for j in range(w):

        if i == 0:
            if j == 0:
                r[i][j] = 1
            else:
                r[i][j] = 0
        else:
            y = r[i - 1][j]
            if j - 1 < 0:
                x = 0
            else:
                x = r[i - 1][j - 1]
            if j + 1 > w - 1:
                z = 0
            else:
                z = r[i - 1][j + 1]
            r[i][j] = (x * arr[p(j-2)] * arr[p(w-j-2)] + \
                y * arr[p(j-1)] * arr[p(w-j-2)] + \
                z * arr[p(j-1)] * arr[p(w-j-3)]) % (10**9+7)
    

print r[h][k-1]

Solution (Python):

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

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


for b in range(2 ** (W - 1)):
    b = bin(b)[2:].zfill(W - 1)
    
    ok = True
    for i in range(W - 2):
        if b[i] == "1" and b[i + 1] == "1":
            ok = False
    if ok:
        
        p = list(range(W))
        for i in range(W - 1):
            
            
            if b[i] == "1":
                p[i], p[i + 1] = p[i + 1], p[i]
        
        for i in range(W):
            transition[i][p[i]] += 1


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

dp[0][0] = 1

for y in range(H):
    
    for i in range(W):
        
        for x in range(W):
            
            dp[y + 1][i] += dp[y][x] * transition[x][i]
            dp[y + 1][i] %= MOD


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

Solution (Python):

MOD = 7 + 10**9 
H, W, K = map(int,input().split())
dp = [[0 for k in range(W)] for l in range(H+1)]

dp[0][0] = 1
for i in range(H):
    for j in range(W):
        for k in range(1<<(W-1)):
            f = 1
            for l in range(W-2):
                if (k>>l)&1 and (k>>(l+1))&1:
                    f = 0
            if f:
                if 0<j and (k>>(j-1))&1:
                    dp[i+1][j-1] += dp[i][j]
                    dp[i+1][j-1] %= MOD
                elif j <= W-2 and (k>>j)&1:
                    dp[i+1][j+1] += dp[i][j]
                    dp[i+1][j+1] %= MOD
                else:
                    dp[i+1][j] += dp[i][j]
                    dp[i+1][j] %= MOD

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

Solution (Python):
import numpy as np


h, w, k = list(map(int, input().split()))

G = np.array([[[0] * w]* w]*h)






def f(i):
  f_list = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144]
  return f_list[i]

for a in range(w):
  
  
  G[0, a, a] = f(a) * f(w-a-1)
  if a <= w-2:
	  G[0, a, a+1] = f(a) * f(w-a-2)
  if a >= 1:
  	G[0, a, a-1] = f(a-1) * f(w-a-1)

for j in range(1, h):
  for a in range(w):
    for b in range(w):
      G[j, a, b] = G[j-1, a, b] * G[0, b, b]
      if b <= w-2:
        G[j, a, b] += G[j-1, a, b+1] * G[0, b+1, b] 
      if b >= 1:
        G[j, a, b] += G[j-1, a, b-1] * G[0, b-1, b]
      G[j, a, b] = G[j, a, b] % 1000000007




print(G[h-1, 0, k-1])