Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    s = input()
    if len(s) == 0:
        print(0)

    fix_flag = False; fix_counts = 0
    i = 0
    while True:
        if i >= len(s) - 1:
            if not fix_flag:
                print(fix_counts)
                return
            else:
                fix_flag = False
                i = 0
                continue
        if s[i] != s[i+1]:
            fix_counts += 2
            s = s[:i] + s[i+2:]
            fix_flag = True
        i += 1

if __name__ == '__main__':
    main()

Fixed submission:
def main():
    s = input()
    if len(s) == 0:
        print(0)

    one_counter = 0
    for i in range(len(s)):
        if s[i] == '1':
            one_counter += 1
    zero_counter = len(s) - one_counter
    print(2 * min(zero_counter, one_counter))

if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    s = input()
    if len(s) == 0:
        print(0)

    fix_flag = False; fix_counts = 0
    i = 0
    while True:
        if i >= len(s) - 1:
            if not fix_flag:
                print(fix_counts)
                return
            else:
                fix_flag = False
                i = 0
                continue
        if s[i] != s[i+1]:
            fix_counts += 2
            s = s[:i] + s[i+2:]
            fix_flag = True
        i += 1

if __name__ == '__main__':
    main()

Fixed submission:
def main():
    s = input()
    if len(s) == 0:
        print(0)

    one_counter = 0
    for i in range(len(s)):
        if s[i] == '1':
            one_counter += 1
    zero_counter = len(s) - one_counter
    print(2 * min(zero_counter, one_counter))

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
import numpy as np
N, M, C = list(map(int, input().split()))
B = np.array(list(map(int, input().split())))
A = []

cnt = 0
for _ in range(N):
    if np.array(list(map(int, input().split()))) @ B + C > 0:
        cnt += 1

print(cnt)

Fixed submission:
N, M, C = list(map(int, input().split()))
B = list(map(int, input().split()))
A = []

cnt = 0
for _ in range(N):
    A = list(map(int, input().split()))
    score = C
    for a, b in zip(A, B):
        score += a*b
    if score > 0:
        cnt += 1

print(cnt)
Buggy python submission (verdict: Runtime Error):
import numpy as np
from collections import defaultdict

memo = {}
def dp(v, d, c):
    if memo.get((v, d), False):
        return None

    memo[(v, d)] = True
    if d == 0:
        res[v-1] = c
        return None

    dp(v, d-1, c)
    for e in dic.get(v, []):
        dp(e, d-1, c)


N, M = tuple(map(int, input().split(' ')))

dic = defaultdict(list)

for m in range(M):
    a, b = tuple(map(int, input().split(' ')))
    dic[a].append(b)
    dic[b].append(a)

Q = int(input())

vdc = [None]*Q

for q in range(Q):
    vdc[q] = tuple(map(int, input().split(' ')))

res = np.zeros(N)

for q in range(Q-1, -1, -1):
    v, d, c = vdc[q]
    dp(v, d, c)


for i in range(N):
    print(int(res[i]))


Fixed submission:
import numpy as np


N = int(input())
a = list(map(int, input().split(' ')))
a.sort()

res = 0
for i in range(len(a[N:])):
    if i % 2 == 0:
        res += a[N+i]

print(res)

Buggy python submission (verdict: Runtime Error):
import numpy as np
from numpy import linalg as LA
import math

mat_dic = {}

def f(mat, n):
    if mat_dic.get(n, None) is not None:
        return mat_dic.get(n, None)

    if n == 1:
        return mat

    if int(math.sqrt(n))**2 == n:
        return LA.matrix_power(f(mat, int(math.sqrt(n))), 2)

    return mat.dot(f(mat, n-1))



N, M = tuple(map(int, input().split(' ')))

mat = np.identity(N)
res = np.zeros(N)

for m in range(M):
    a, b = tuple(map(int, input().split(' ')))
    mat[a-1, b-1] = 1
    mat[b-1, a-1] = 1
    mat[a-1, a-1] = 1
    mat[b-1, b-1] = 1

Q = int(input())

for q in range(Q):
    v, d, c = tuple(map(int, input().split(' ')))
    x = f(mat, d)
    res[x[v-1,:] > 0] = c


for i in range(N):
    print(int(res[i]))


Fixed submission:
import numpy as np


N = int(input())
a = list(map(int, input().split(' ')))
a.sort()

res = 0
for i in range(len(a[N:])):
    if i % 2 == 0:
        res += a[N+i]

print(res)

Buggy python submission (verdict: Runtime Error):
import numpy as np


N = int(input())
a = list(map(int, input().split(' ')))
a.sort()

x = []
for n in range(N):
    x.append([])
    for i in range(3):
        x[n].append(0)

for i in range(N*3):
    x[i % N][i // N] = a[i]

for i in range(N-1, -1, -1):
    for j in range(i-1, -1, -1):
        if x[i][1] == x[j][1] and [j][2] < x[i][1] and x[i][2] > x[j][2]:
            x[j][2], x[i][1] = x[i][1], x[j][2]
            break
        else:
            break


res = 0

for n in range(N):
    res += x[n][1]

print(res)


Fixed submission:
import numpy as np


N = int(input())
a = list(map(int, input().split(' ')))
a.sort()

res = 0
for i in range(len(a[N:])):
    if i % 2 == 0:
        res += a[N+i]

print(res)
Buggy python submission (verdict: Runtime Error):
import math

def main():
    N, M = tuple(map(int, input().split(' ')))
    man_list = []
    point_list = []
    for i in range(N):
        man_list.append(tuple(map(int, input().split(' '))))
    for i in range(M):
        point_list.append(tuple(map(int, input().split(' '))))

    result = []
    for i, man in enumerate(man_list):
        a, b = man
        min_ = float('inf')
        for j, point in enumerate(point_list):
            c, d = point
            v = abs(a-c)+ abs(b-d)
            if len(result) < i+1:
                min_ = v
                result.append(j+1)
                continue
            if v < min_:
                result[i] = j+1
                min_ = v


    for r in result:
        print('{}'.format(r))


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    A, B = tuple(map(int, input().split(' ')))
    print('{}'.format((A+B)%24))


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
def main():
    A, B = tuple(map(int, raw_input().split(' ')))
    print('{}'.format((A+B)%24))


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    A, B = tuple(map(int, input().split(' ')))
    print('{}'.format((A+B)%24))


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
def main():
    A, B = raw_input().split(' ')
    print('{}'.format((A+B)%24))


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    A, B = tuple(map(int, input().split(' ')))
    print('{}'.format((A+B)%24))


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):

def main():
    A, B = raw_input()
    print('{}'.format((A+B)%24))


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    A, B = tuple(map(int, input().split(' ')))
    print('{}'.format((A+B)%24))


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
2017/01/07

Fixed submission:
a=input()
print(a.replace("2017","2018"))
Buggy python submission (verdict: Runtime Error):
a,b,c=map(input().split())
A=[a,b,c]
if a<=max(A) and b<=max(A):
    print(a+b)
elif b<=max(A) and c<=max(A):
    print(b+c)
elif c<=max(A) and a<=max(A):
    print(a+c)

Fixed submission:
a,b,c=map(int,input().split())
print(min(a+b,a+c,b+c))
Buggy python submission (verdict: Runtime Error):
#!/usr/bin/env python3

def main():
    [N, K] = list(map(int, input().split()))
    s_list = []
    for i in range(N):
        s_list.append(list(map(int, input().split())))

    s_list.sort(key = lambda v: v[1], reverse = True)
    n_set = set()
    A, B = [0], [0]
    tot_a, tot_b = 0, 0
    for td in s_list:
        if not td[0] in n_set:
            n_set.add(td[0])
            tot_a += td[1]
            A.append(tot_a)
        else:
            tot_b += td[1]
            B.append(tot_b)

    min_n = max(1, K - (len(B) - 1))
    max_x = 0
    for i in range(min_n, len(A)):
        max_x = max(max_x, A[i] +i ** 2 + B[K - i])

    print(max_x)


if __name__ == '__main__':
    main()



Fixed submission:
#!/usr/bin/env python3

def main():
    [N, K] = list(map(int, input().split()))
    s_list = []
    for i in range(N):
        s_list.append(list(map(int, input().split())))

    s_list.sort(key = lambda v: v[1], reverse = True)
    n_set = set()
    A, B = [0], [0]
    tot_a, tot_b = 0, 0
    for td in s_list:
        if not td[0] in n_set:
            n_set.add(td[0])
            tot_a += td[1]
            A.append(tot_a)
        else:
            tot_b += td[1]
            B.append(tot_b)

    min_n = max(1, K - (len(B) - 1))
    max_n = min(K + 1, len(A))
    max_x = 0
    for i in range(min_n, max_n):
        max_x = max(max_x, A[i] + i ** 2 + B[K - i])

    print(max_x)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
#!/usr/bin/env python3

def calc(N, X):
    if X == 0:
        return 0

    Y = 2 ** (N + 1) - 1
    if X == Y:
        return 2 ** N
    elif X == Y - 1:
        return 2 ** N - 1
    elif X < Y - 1:
        return calc(N - 1, X - 1)
    else:
        return 2 ** (N + 1) - 1 - calc(N - 1, 2 ** (N + 2) - 4 - X)

def main():
    [N, X] = list(map(int, input().split()))

    r = calc(N, X)


    print(r)


if __name__ == '__main__':
    main()



Fixed submission:
#!/usr/bin/env python3

def calc(N, X):
    if X == 0:
        return 0
    elif X == 2 ** (N + 2) - 3:
        return 2 ** (N + 1) - 1

    Y = 2 ** (N + 1) - 1
    if X == Y:
        return 2 ** N
    elif X == Y - 1:
        return 2 ** N - 1
    elif X < Y - 1:
        return calc(N - 1, X - 1)
    else:
        return 2 ** (N + 1) - 1 - calc(N - 1, 2 ** (N + 2) - 4 - X)

def main():
    [N, X] = list(map(int, input().split()))

    r = calc(N, X)


    print(r)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
#!/usr/bin/env python3


def dfs(v, adj_list, depth, visited):
    visited[v] = True
    x = depth
    for w in adj_list[v]:
        if not visited[w]:
            x += dfs(w, adj_list, depth + 1, visited)

    return x


def solve(n, d):

    if n < 7:
        print(-1)
        return

    d.sort()
    w = [1] * n
    edges = []
    adj_list = [[] for _ in range(n)]
    for j in range(n - 1, 0, -1):
        di, i = d[j]
        pdi = di - n + 2 * w[i]
        p = None
        lo, hi = 0, j
        while lo < hi:
            mid = (lo + hi) // 2
            xdi, xi = d[mid]
            if xdi == pdi:
                p = xi
                break
            elif xdi < pdi:
                lo = mid + 1
            else:
                hi = mid
        if p is None:
            print(-1)
            return
        u, v = i, p
        if v < u:
            u, v = v, u
        edges.append((u + 1, v + 1))
        adj_list[u].append(v)
        adj_list[v].append(u)
        w[p] += w[i]

    d0, r = d[0]
    visited = [False] * n
    x = dfs(r, adj_list, 0, visited)
    if x != d0:
        print(-1)
        return

    edges.sort()
    for uv in edges:
        u, v = uv
        print('{} {}'.format(u, v))



def main():
    n = input()
    n = int(n)
    d = []
    for i in range(n):
        di = input()
        di = int(di)
        d.append((di, i))


    solve(n, d)


if __name__ == '__main__':
    main()



Fixed submission:
#!/usr/bin/env python3
import sys

sys.setrecursionlimit(101010)

def dfs(v, adj_list, depth, visited):
    visited[v] = True
    x = depth
    for w in adj_list[v]:
        if not visited[w]:
            x += dfs(w, adj_list, depth + 1, visited)

    return x


def solve(n, d):

    if n < 7:
        print(-1)
        return

    d.sort()
    w = [1] * n
    edges = []
    adj_list = [[] for _ in range(n)]
    for j in range(n - 1, 0, -1):
        di, i = d[j]
        pdi = di - n + 2 * w[i]
        p = None
        lo, hi = 0, j
        while lo < hi:
            mid = (lo + hi) // 2
            xdi, xi = d[mid]
            if xdi == pdi:
                p = xi
                break
            elif xdi < pdi:
                lo = mid + 1
            else:
                hi = mid
        if p is None:
            print(-1)
            return
        u, v = i, p
        if v < u:
            u, v = v, u
        edges.append((u + 1, v + 1))
        adj_list[u].append(v)
        adj_list[v].append(u)
        w[p] += w[i]

    d0, r = d[0]
    visited = [False] * n
    x = dfs(r, adj_list, 0, visited)
    if x != d0:
        print(-1)
        return

    edges.sort()
    for uv in edges:
        u, v = uv
        print('{} {}'.format(u, v))



def main():
    n = input()
    n = int(n)
    d = []
    for i in range(n):
        di = input()
        di = int(di)
        d.append((di, i))


    solve(n, d)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
#!/usr/bin/env python3

def main():
    [H, W] = list(map(int, input().split()))
    a = []
    for i in range(H):
        a.append(list(map(int, input().split())))

    moves = []

    for y in range(H):
        for x in range(W - 1):
            if a[y][x] % 2 == 1:
                a[y][x] -= 1
                a[y][x + 1] += 1
                moves.append((y + 1, x + 1, y + 1, x + 2))
        if y != H - 1:
            if a[y][H - 1] % 2 == 1:
                a[y][H - 1] -= 1
                a[y + 1][H - 1] += 1
                moves.append((y + 1, H, y + 2, H))


    print(len(moves))
    for v in moves:
        print('{} {} {} {}'.format(v[0], v[1], v[2], v[3]))


if __name__ == '__main__':
    main()



Fixed submission:
#!/usr/bin/env python3

def main():
    [H, W] = list(map(int, input().split()))
    a = []
    for i in range(H):
        a.append(list(map(int, input().split())))

    moves = []

    for y in range(H):
        for x in range(W - 1):
            if a[y][x] % 2 == 1:
                a[y][x] -= 1
                a[y][x + 1] += 1
                moves.append((y + 1, x + 1, y + 1, x + 2))
        if y != H - 1:
            if a[y][W - 1] % 2 == 1:
                a[y][W - 1] -= 1
                a[y + 1][W - 1] += 1
                moves.append((y + 1, W, y + 2, W))


    print(len(moves))
    for v in moves:
        print('{} {} {} {}'.format(v[0], v[1], v[2], v[3]))


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3

def main():
    na = list(map(int, input().split()))
    N, C = na[0], na[1]

    D = []
    for i in range(C):
        D.append(list(map(int, input().split())))
    c = []
    for i in range(N):
        c.append(list(map(int, input().split())))

    s = []
    s.append([0] * (C + 1))
    s.append([0] * (C + 1))
    s.append([0] * (C + 1))

    for i in range(N):
        for j in range(N):
            for k in range(1, C + 1):
                s[(i + j) % 3][k] += D[c[i][j] -1][k - 1]

    s_min = 500 * 500 * 1000
    for i in range(1, C + 1):
        for j in range(1, C + 1):
            if i == j:
               continue 
            for k in range(1, C + 1):
                if i == k or j == k:
                    continue
                s_min = min(s_min, s[0][i] + s[1][j] + s[2][k])


    print(s_min)


if __name__ == '__main__':
    main()



Fixed submission:
#!/usr/bin/env python3

def main():
    na = list(map(int, input().split()))
    N, C = na[0], na[1]

    D = []
    for i in range(C):
        D.append(list(map(int, input().split())))
    c = []
    for i in range(N):
        c.append(list(map(int, input().split())))

    s = []
    s.append([0] * (C + 1))
    s.append([0] * (C + 1))
    s.append([0] * (C + 1))

    for i in range(N):
        for j in range(N):
            m = (i + j) % 3
            for k in range(1, C + 1):
                s[m][k] += D[c[i][j] -1][k - 1]

    s_min = 500 * 500 * 1000
    for i in range(1, C + 1):
        for j in range(1, C + 1):
            if i == j:
               continue 
            for k in range(1, C + 1):
                if i == k or j == k:
                    continue
                s_min = min(s_min, s[0][i] + s[1][j] + s[2][k])


    print(s_min)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
#!/usr/bin/env python3

def main():
    s = input()
    t = input()

    s_bytes = sorted(s.encode())
    t_bytes = sorted(t.encode(), reverse = True)

    s_len = len(s)
    t_len = len(t)

    gt = s_len < t_len

    for i in range(len(s_bytes)):
        if t_len <= i:
            gt = False
            break
        if s_bytes[i] < t_bytes[i]:
            gt = True
            break
        elif s_bytes[i] > t_bytes[i]:
            gt = False
            break

    print('Yes' if gt else 'No')


if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3

def main():
    sa = input().split(' ')
    a = int(sa[0])
    b = int(sa[1])

    print(int((a + b + 1) / 2))


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
#!/usr/bin/env python3

def main():
    s = input()
    t = input()

    s_bytes = sorted(s.encode())
    t_bytes = sorted(t.encode(), reverse = True)

    s_len = len(s)
    t_len = len(t)

    gt = s_len < t_len

    for i in range(len(s_bytes)):
        if t_len <= i:
            gt = False
            break
        if s_bytes[i] < t_bytes[i]:
            gt = True
            break
        elif s_bytes[i] > t_bytes[i]:
            gt = False
            break

    print('Yes' if gt else 'No')


if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3

def main():
    sa = input().split(' ')
    a = int(sa[0])
    b = int(sa[1])

    print(int((a + b + 1) / 2))


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3


M = 10 ** 9 + 7

def solve(n, m, s, p):

    cnt = [0] * (n + 1)
    c = 0
    for i in range(n):
        cnt[i] = c
        if s[i] == '1':
            c += 1
    cnt[n] = c


    ans = 1
    for sp in p:
        dp = [[0] * (n + 2) for _ in range(n + 2)]
        l0, r0 = sp[0]
        c0 = cnt[l0]
        dp[1][1] = 1
        t0 = 0
        t1 = 0
        r = r0
        for tpl in sp:
            nl, nr = tpl
            nr = max(r, nr)
            nt1 = cnt[nr] - c0
            nt0 = nr - l0 - nt1
            for i in range(max(nl - l0 - t1, 0), t0 + 1):
                for j in range(t1 + 1, nt1 + 1):
                    dp[i + 1][j + 1] = (dp[i + 1][j] + dp[i][j + 1]) % M
            for i in range(t0 + 1, nt0 + 1):
                for j in range(max(nl - l0 - t0, 0), t1 + 1):
                    dp[i + 1][j + 1] = (dp[i + 1][j] + dp[i][j + 1]) % M
            for i in range(t0 + 1, nt0 + 1):
                for j in range(t1 + 1, nt1 + 1):
                    dp[i + 1][j + 1] = (dp[i + 1][j] + dp[i][j + 1]) % M
            t0 = nt0
            t1 = nt1
        ans *= dp[t0 + 1][t1 + 1]
        ans %= M

    return ans


def main():
    n, m = input().split()
    n = int(n)
    m = int(m)
    s = input()
    p = []
    ll = -1
    lr = 0
    for _ in range(m):
        l, r = input().split()
        l = int(l) - 1
        r = int(r)
        r = max(lr, r)
        if l == ll:
            sp.pop()
            sp.append((l, r))
        else:
            if lr <= l:
                sp = []
                p.append(sp)
            sp.append((l, r))
        ll = l
        lr = r

    print(solve(n, m, s, p))


if __name__ == '__main__':
    main()



Fixed submission:
#!/usr/bin/env python3


M = 10 ** 9 + 7


def solve(n, m, s, lst):

    cnt = [0] * n
    t = 0
    for i in range(n):
        if s[i] == '1':
            t += 1
        cnt[i] = t


    dp = [[0] * (n + 1) for _ in range(n + 1)]
    dp[0][0] = 1
    r = 0
    j = 0
    for i in range(n):
        while j < m:
            lj, rj = lst[j]
            if lj <= i:
                r = max(r, rj)
                j += 1
            else:
                break
        if r <= i:
            c = cnt[i]
            if 0 < c:
                dp[i + 1][cnt[i]] = (dp[i][c] + dp[i][c - 1]) % M
            else:
                dp[i + 1][0] = dp[i][0]
        else:
            for k in range(max(0, cnt[r] - r + i), min(i + 1, cnt[r]) + 1):
                if 0 < k:
                    dp[i + 1][k] = (dp[i][k] + dp[i][k - 1]) % M
                else:
                    dp[i + 1][0] = dp[i][0]

    return dp[n][cnt[n - 1]]


def main():
    n, m = input().split()
    n = int(n)
    m = int(m)
    s = input()
    lst = []
    for _ in range(m):
        l, r = input().split()
        l = int(l) - 1
        r = int(r) - 1
        lst.append((l, r))

    print(solve(n, m, s, lst))


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
N, M = map(int, raw_input().split())
if (N+M) % 3 == 0:
	print  "Possible"
	return 0

if (N) % 3 == 0:
	print  "Possible"
	return 0

if (M) % 3 == 0:
	print  "Possible"
	return 0

print "Impossible"

Fixed submission:
N, M = map(int, raw_input().split())
if (N+M) % 3 == 0:
	print  "Possible"

elif (N) % 3 == 0:
	print  "Possible"

elif (M) % 3 == 0:
	print  "Possible"

else:
	print "Impossible"
Buggy python submission (verdict: Runtime Error):
t, x = list(map(int, input()))

print(t/x)

Fixed submission:
t, x = list(map(int, input().split(' ')))

print(t/x)
Buggy python submission (verdict: Time Limit Exceeded):
def compute_patterns(n):
    memo = {}
    def compute(n):
        if n in memo:
            return memo[n]
        if n == 2:
            return 2
        if n <= 1:
            return 1
        ret = compute(n-1) + compute(n-2)
        memo[n] = ret
        return ret
    return compute(n)


def gen_patterns(c, h, w, k):
    if h == 1:
        if c == k:
            yield [(c-1, w-c)]
        elif c+1 == k:
            yield [(c-1, w-c-1)]
        elif c-1 == k:
            yield [(c-2, w-c)]
        else:
            yield None
    else:
        for p in gen_patterns(c, h-1, w, k):
            if p is None:
                yield None
            else:
                yield [(c-1, w-c)] + p
        if c != 1:
            for p in gen_patterns(c-1, h-1, w, k):
                if p is None:
                    yield None
                else:
                    yield [(c-2, w-c)] + p
        if c != w:
            for p in gen_patterns(c+1, h-1, w, k):
                if p is None:
                    yield None
                else:
                    yield [(c-1, w-c-1)] + p


def main():
    H, W, K = list(map(int, input().split(' ')))
    ret = 0
    for p in gen_patterns(1, H, W, K):
        if p is None:
            continue
        r = 1
        for i in range(len(p)):
            r *= compute_patterns(p[i][0])
            r %= 1000000007
            r *= compute_patterns(p[i][1])
            r %= 1000000007
        ret += r
    print(ret % 1000000007)



if __name__ == '__main__':
    main()

Fixed submission:
def f(n):
    memo = {}
    def compute(n):
        if n in memo:
            return memo[n]
        if n == 2:
            return 2
        if n <= 1:
            return 1
        ret = compute(n-1) + compute(n-2)
        memo[n] = ret
        return ret
    return compute(n)


memo = {}

def gen_patterns(c, h, w, k):
    if (c, h) in memo:
        return memo[(c,h)]
    elif h == 1:
        if c == k:
            return f(c-1) * f(w-c) % 1000000007
        elif c+1 == k:
            return f(c-1)* f(w-c-1) % 1000000007
        elif c-1 == k:
            return f(c-2)*f(w-c) % 1000000007
        else:
            return 0
    else:
        ret = 0
        ret += f(c-1) * f(w-c) * gen_patterns(c,h-1,w,k)
        ret = ret % 1000000007
        if c != 1:
            ret += f(c-2)*f(w-c)*gen_patterns(c-1,h-1,w,k)
            ret = ret % 1000000007
        if c != w:
            ret += f(c-1)*f(w-c-1)*gen_patterns(c+1,h-1,w,k)
            ret = ret % 1000000007
        memo[(c,h)] = ret
        return ret


def main():
    H, W, K = list(map(int, input().split(' ')))
    print(gen_patterns(1, H, W, K))



if __name__ == '__main__':
    main()