Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 7)
# import bisect
# import numpy as np
# from collections import deque
from collections import deque
# map(int, sys.stdin.read().split())
import itertools
import heapq


def input():
    return sys.stdin.readline().rstrip()


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    mod = 10 ** 9 + 7
    A.sort()
    A = deque(A)
    #    print(A)
    A_minus = deque([s for s in A if s < 0])
    A_plus = deque([s for s in A if s >= 0])

    #    print(A_plus)
    #    print(A_minus)
    AA = []
    if N == K:
        ans = 1
        for l in range(N):
            ans *= A[l] 
            ans %=mod
        print(ans % mod)

    elif K % 2 == 0:
        while len(A_minus) >= 2:
            a1 = A_minus.popleft()
            a2 = A_minus.popleft()
            AA.append(-a1 * a2)

        while len(A_plus) >= 2:
            a1 = A_plus.pop()
            a2 = A_plus.pop()
            AA.append(-a1 * a2)
        ans = 1
        heapq.heapify(AA)
        for i in range(K // 2):
            ans *= (-1 * heapq.heappop(AA)) % mod
        print(ans % mod)

    elif len(A_plus) == 0:
        ans = 1
        for i in range(K):
            ans *= A_minus.pop() % mod
        print(ans % mod)

    else:
        ans = A_plus.pop()
        while len(A_minus) >= 2:
            a1 = A_minus.popleft()
            a2 = A_minus.popleft()
            AA.append(-a1 * a2)

        while len(A_plus) >= 2:
            a1 = A_plus.pop()
            a2 = A_plus.pop()
            AA.append(-a1 * a2)

        heapq.heapify(AA)
        for i in range(K // 2):
            ans *= (-1 * heapq.heappop(AA)) % mod
        print(ans % mod)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

# import bisect
# import numpy as np
# from collections import deque
from collections import deque
# map(int, sys.stdin.read().split())
# import heapq
import bisect


# def input():
#     return sys.stdin.readline().rstrip()


def main():
    N, K = map(int, input().split())
    A = sorted(list(map(int, input().split())))
    mod = 10 ** 9 + 7

    if N == K:
        ans = 1
        for i in range(N):
            ans *= A[i]
            ans %= mod
        print(ans % mod)



    elif K % 2 == 0:
        ans = 1
        j = 0
        i = N - 1
        for _ in range(K // 2):
            if A[j] * A[j + 1] > A[i] * A[i - 1]:
                ans *= A[j] * A[j + 1]
                ans %= mod
                j += 2
            else:
                ans *= A[i] * A[i - 1]
                ans %= mod
                i -= 2
        print(ans % mod)

    elif A[-1] < 0:
        ans = 1
        for i in range(K):
            ans *= A[-(i + 1)]
            ans %= mod
        print(ans % mod)
    else:
        ans = A[-1]
        j = 0
        i = N - 2
        for _ in range(K // 2):
            if A[j] * A[j + 1] > A[i] * A[i - 1]:
                ans *= A[j] * A[j + 1]
                ans %= mod
                j += 2
            else:
                ans *= A[i] * A[i - 1]
                ans %= mod
                i -= 2
        print(ans % mod)


if __name__ == "__main__":
    main()
### BUGGY CODE ###

s = input()
K = int(input())

memo = set()

result = []
lst = []
for si in s:
    temp = []
    for li in lst:
        ss = li + si
        if ss not in memo:
            temp.append(li + si)
            memo.add(ss)
    temp.append(si)
    result.extend(temp)
    lst = temp

temp = list(set(result))
temp.sort()
print(temp[K - 1])


### FIXED CODE ###

S = input()
K = int(input())

N = len(S)

memo = []
for i in range(N):
    for d in range(1, min(K, N - i) + 1):
        memo.append(S[i:i + d])

print(sorted(set(memo))[K - 1])
### BUGGY CODE ###

input()
S=list(input())
ans=0

for i in range(1000):
    Si=0
    s=list(str(i).zfill(3))
    si=0
    while(Si<len(S)):
        if S[Si] == s[si]:
            si+=1
            if si > 2:
                ans+=1
                break
            Si += 1
            continue
        Si+=1
print(ans)

### FIXED CODE ###

input()
S=list(input())
ans=0

def index(x,l):
    if x in l:
        return l.index(x)
    else:
        return -1

for i in range(1000):
    Si=0
    s=list(str(i).zfill(3))
    si=0
    if index(s[0],S) != -1:
        if index(s[1],S[S.index(s[0])+1:]) != -1:
            if index(s[2],S[S.index(s[0])+1:][S[S.index(s[0])+1:].index(s[1])+1:]) != -1:
                ans += 1
print(ans)
### BUGGY CODE ###

from sys import stdin
input = stdin.readline

N, M, Q = map(int, input().split())

count = [[0]*(N+1) for _ in range(N+1)]
for i in range(M):
    l, r = map(int, input().split())
    count[l][r] += 1

accum = [[0]*(N+1) for _ in range(N+1)]
for i in range(N+1):
    accum[i][0] = count[i][0]
    for j in range(1, N+1):
        accum[i][j] = accum[i][j-1] + count[i][j]

for _ in range(Q):
    p, q = map(int, input().split())
    ans = 0
    for i in range(p, q+1):
        ans += accum[i][q]-accum[i][p-1]
    print(ans)


### FIXED CODE ###

from sys import stdin
#from pprint import pprint
input = stdin.readline

N, M, Q = map(int, input().split())

count = [[0]*(N+1) for _ in range(N+1)]
for i in range(M):
    l, r = map(int, input().split())
    count[l][r] += 1
# pprint(count)

accum = [[0]*(N+1) for _ in range(N+1)]
for i in range(N+1):
    accum[i][0] = count[i][0]
    for j in range(1, N+1):
        accum[i][j] = accum[i][j-1] + count[i][j]
for i in range(1, N+1):
    for j in range(N+1):
        accum[i][j] = accum[i-1][j] + accum[i][j]
# pprint(accum)

test = [[0]*(N+1) for _ in range(N+1)]
for i in range(1, N+1):
    for j in range(1, N+1):
        test[i][j] = accum[j][j] - accum[i-1][j] - \
            accum[j][i-1] + accum[i-1][i-1]
# pprint(test)


for _ in range(Q):
    p, q = map(int, input().split())
    ans = accum[q][q] - accum[p-1][q] - accum[q][p-1] + accum[p-1][p-1]
    print(ans)
### BUGGY CODE ###

n,m = map(int,input().split())
ls = [list(map(int,input().split())) for _ in range(m)]
di = [[] for _ in range(n)]
for i in range(m):
    di[ls[i][0]-1].append(ls[i][1])
    di[ls[i][0]-1].sort()
for k in range(m):
    a = di[ls[k][0]-1].index(ls[k][1])
    q = 10**12 + (ls[k][0])*10**6 +(a+1)
    print(str(q)[1:])
    


### FIXED CODE ###

n,m = map(int,input().split())
ls = [[] for _ in range(n+1)]
di = []
for i in range(m):
    a,b = map(int,input().split())
    ls[a].append([b,i+1])
for j in range(n+1):
    if ls[j] != []:
        ls[j].sort(key=lambda x :x[0])
        for k in range(len(ls[j])):
            di.append([ls[j][k][1],str(10**12+j*10**6+k+1)[1:]])
di.sort(key=lambda x :x[0])
for l in range(m):
    print(di[l][1])
### BUGGY CODE ###

while 1:
	n=input()
	if n==0:break
	hmax=10000
	block=[map(int,raw_input().split()) for i in range(n)]
	field=[[0]*5 for i in range(hmax)]
	for d,p,q in block:
		if d==1:
			for li in range(hmax-1,-1,-1):
				if field[li][q-1:q+p-1]!=[0]*p:
					field[li+1][q-1:q+p-1]=[1]*p
					break
			else:
				field[0][q-1:q+p-1]=[1]*p
		else:
			for li in range(hmax-1,-1,-1):
				if field[li][q-1]!=0:
					for i in range(p):
						field[li+i+1][q-1]=1
					break
			else:
				for i in range(p):
					field[li+i][q-1]=1
		i=0
		while 1:
			if field[i]==[1]*5:
				del field[i]
				hmax-=1
			elif field[i]==[0]*5:
				break
			else:
				i+=1
	print sum([sum(field[li]) for li in range(hmax)])

### FIXED CODE ###

while 1:
	n=input()
	if n==0:break
	hmax=7500
	block=[map(int,raw_input().split()) for i in range(n)]
	field=[[0]*5 for i in range(hmax)]
	top=[0]*5
	for d,p,q in block:
		if d==1:
			h=max(top[q-1:q-1+p])
			field[h][q-1:q-1+p]=[1]*p
			top[q-1:q-1+p]=[max(top)+1]*p
		else:
			h=top[q-1]
			for i in range(p):
				field[h+i][q-1]=1
			top[q-1]=h+p
		h=0
		while 1:
			if field[h]==[1]*5:
				del field[h]
				top=[x-1 for x in top]
			elif field[h]==[0]*5:
				break
			else:
				h+=1
		for w in range(5):
			for h in range(top[w]-1,-2,-1):
				if field[h][w]==1 or h==-1:
					top[w]=h+1
					break
	print sum([sum(field[h]) for h in range(max(top))])
### BUGGY CODE ###

def search_left(ind, alst, a, w):
  doors = []
  for j in range(ind - 1, -1, -1):
    if alst[j] < 0:
     doors.append((j, -alst[j]))
    if alst[j] == 0:
      ret = a
      for pos, lim in doors:
        ret = min(ret, lim - (ind - pos))
      ret = max(0, ret)
      return ret
  return 0

def search_right(ind, alst, a, w):
  doors = []
  for j in range(ind + 1, w):
    if alst[j] < 0:
      doors.append((j, -alst[j]))
    if alst[j] == 0:
      ret = a
      for pos, lim in doors:
        ret = min(ret, lim - (pos - ind))
      ret = max(0, ret)
      return ret
  return 0

def main():
  w = int(input())
  alst = list(map(int, input().split()))
  ans = 0
  for ind, a in enumerate(alst):
    if a > 0:
      ans += max(search_left(ind, alst, a, w), search_right(ind, alst, a, w))
  print(ans)
main() 


### FIXED CODE ###

w = int(input())
alst = list(map(int, input().split()))
INF = 10 ** 20
acc = -INF
left = []
for i in range(w):
  a = alst[i]
  if a == 0:
    acc = INF
  elif a > 0:
    acc -= 1
  elif a < 0:
    acc = min(acc - 1, -a)
  left.append(acc)

acc = -INF
right = []
for i in range(w):
  a = alst[w - i - 1]
  if a == 0:
    acc = INF
  elif a > 0:
    acc -= 1
  elif a < 0:
    acc = min(acc - 1, -a)
  right.append(acc)
right.reverse()

print(sum([max(0, min(alst[i], max(left[i], right[i]))) for i in range(w)]))
### BUGGY CODE ###

N, K = map(int, input().split())
H = list(map(int, input().split()))
dp = [0] * N
for i in range(1, N):
    dp[i] = min([dp[j] + abs(H[i] - H[j]) for j in range(max(i-K, 0), i)])
print(dp[-1])

### FIXED CODE ###

import numpy as np
N, K = map(int, input().split())
H = np.array(list(map(int, input().split())), dtype=int)

dp = np.zeros(N, dtype=int)
for i in range(1, N):
    s = max(i-K, 0)
    dp[i] = (np.abs(H[i] - H[s:i]) + dp[s:i]).min()
print(dp[-1])
### BUGGY CODE ###

from collections import Counter

def main():
    N,P = map(int,input().split())
    S = input()
    ans = 0
    if P == 2 or P == 5:
        for i,s in enumerate(S):
            if int(s) % P == 0:
                ans += i + 1
    else:
        D = [0] * (N+1)
        for i in range(N):
            D[i] = int(S[N-1-i:N+1]) % P
        C = Counter(D)
        ans = sum([c*(c-1)//2 for c in C.values()])
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N,P = map(int,input().split())
    S = input()[::-1]
    ans = 0
    if P == 2 or P == 5:
        for i,s in enumerate(S):
            if int(s) % P == 0:
                ans += N - i
    else:
        mods = [0] * P
        mods[0] = 1
        current = 0
        x = 1
        for s in S:
            current = (current + x * int(s)) % P
            ans += mods[current % P]
            mods[current % P] += 1
            x = x * 10 % P
    print(ans)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

S = input()
Q = int(input())
flag = True
for i in range(Q):
    que = input()
    if len(que) == 1:
        if flag:
            flag = False
        else:
            flag = True
    else:
        if que[2] == '1':
            if flag:
                S = que[4]+S
            else:
                S = S+que[4]
        else:
            if flag:
                S = S+que[4]
            else:
                S = que[4]+S
if flag:
    print(S)
else:
    for i in range(len(S)):
        print(S[len(S)-i-1], end = '')
    print()

### FIXED CODE ###

S = input()
T = ''
Q = int(input())
flag = True
for i in range(Q):
    que = input()
    if len(que) == 1:
        if flag:
            flag = False
        else:
            flag = True
    else:
        if que[2] == '1':
            if flag:
                T = T+que[4]
            else:
                S = S+que[4]
        else:
            if flag:
                S = S+que[4]
            else:
                T = T+que[4]
if flag:
    U = ''
    for i in range(len(T)):
        U += T[len(T)-i-1]
    print(U+S)
else:
    U = ''
    for i in range(len(S)):
        U += S[len(S)-i-1]
    print(U+T)
### BUGGY CODE ###

from collections import deque
N, M = map(int, input().split())
P = list(map(int, input().split()))
K = [[] for _ in range(N)]
for i in range(M):
    x, y = map(int, input().split())
    x, y = x-1, y-1
    K[x].append(y)
    K[y].append(x)
used = [0]*N
OK = [0]*N
Origin = []
for i in range(N):
    P[i] -= 1
    if i == P[i]:
        OK[i] = 1
        Origin.append(i)
ans = 0
for i in range(N):
    c = 0
    if used[i] == 0:
        used[i] = 1
        S = deque([i])
        Enable = Origin.copy()
        Enable.append(i)
        T = OK.copy()
        T[P[i]] = 1
        while S:
            t = S.popleft()
            for j in K[t]:
                if used[j] == 0:
                    used[j] = 1
                    Enable.append(j)
                    T[P[j]] = 1
                    S.append(j)
        Enable = list(set(Enable))
        for j in Enable:
            if T[j] == 1:
                c += 1
        ans = max(ans, c)

print(ans)

### FIXED CODE ###

from collections import deque
N, M = map(int, input().split())
P = list(map(int, input().split()))
K = [[] for _ in range(N)]
for i in range(M):
    x, y = map(int, input().split())
    x, y = x-1, y-1
    K[x].append(y)
    K[y].append(x)
used = [0]*N
OK = []
for i in range(N):
    P[i] -= 1
    if i == P[i]:
        OK.append(i)
ans = 0
for i in range(N):
    if used[i] == 0:
        used[i] = 1
        S = deque([i])
        Enable = [i]
        Origin = [P[i]]
        while S:
            t = S.popleft()
            for j in K[t]:
                if used[j] == 0:
                    used[j] = 1
                    Enable.append(j)
                    Origin.append(P[j])
                    S.append(j)
        T_1 = list(set(OK + Enable))
        T_2 = list(set(OK + Origin))
        ans = max(ans, len(T_1) + len(T_2) - len(set(T_1 + T_2)))

print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a * b // gcd(a, b)

s = set()
for i in range(n):
    pow, cur = 0, a[i]
    while cur % 2 == 0:
        cur //= 2
        pow += 1
    s.add(pow)
if (len(s) > 1):
    print(0)
else:
    l = a[0] // 2
    for i in range(1, n):
        l = lcm(l, a[i] // 2)
    res, cur = 0, l
    while cur <= m:
        res += 1
        cur += 2 * l
    print(m // l - m // (2 * l))

### FIXED CODE ###

from fractions import gcd
n, m = map(int, input().split())
a = [int(i) // 2 for i in input().split()]

def pow2(n):
    cur, res = n, 0
    while cur:
        if cur % 2 == 0:
            cur //= 2
            res += 1
        else:
            return res

def lcm(a, b):
    return a * (b // gcd(a, b))

b = [pow2(i) for i in a]
if (min(b) != max(b)):
    print(0)
    exit(0)
l = 1
for i in range(n):
    l = lcm(l, a[i])
print(m // l - m // (2 * l))
### BUGGY CODE ###

k = int(input())
n = 1
list = []
r = 7
while True:
    r = r % k
    if r == 0:
        print(n)
        break
    elif r in list:
        print(-1)
        break
    else:
        list.append(r)
        r = r * 10 + 7
        n += 1


### FIXED CODE ###

K = int(input())
a = 7
for i in range(K):
  if a % K == 0:
    print(i+1)
    break
  else:
    a = 10*(a%K) + 7
else:
  print(-1)
### BUGGY CODE ###

k,s = map(int,input().split())
ans = 0

for x in range(min(k,s)+1):
    for y in range(min(k,s)+1):
        if 0 <= s - x - y <= min(k,s):
            ans += 1
    
print(ans)

### FIXED CODE ###

k,s = map(int,input().split())
ans = 0

for x in range(min(k,s)+1):
    for y in range(min(k,s)+1):
        if 0 <= s - x - y <= min(k,s):
            ans += 1
    
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys

N=input()
C=map(int, sys.stdin.readline().split())
C.sort()

mod=10**9+7
D=[]
d0=2**(N-1)

#D：係数の配列の作成
for i in range(N):
    if i==0:
        D.append(d0)
    else:
        D.append( (2*D[-1]-d0)/2+d0 )

#Ci*Diを最小にするため、最小のCiに最大のDiを掛けるため、降順ソートする
D.sort(reverse=True)

ans=0
for c,d in zip(C,D):
    ans+=c*d
    ans%=mod

ans=ans*pow(2,N,mod)

print ans%mod


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys

N=input()
C=map(int, sys.stdin.readline().split())
C.sort()

mod=10**9+7
D=[]
d0=pow(2,N-1,mod)

#D：係数の配列の作成
for i in range(N):
    if i==0:
        D.append(d0)
    else:
        next=(2*D[-1]-d0)*pow(2,mod-2,mod)+d0
        D.append(next%mod)

#Ci*Diを最小にするため、最小のCiに最大のDiを掛けるため、Dは配列を逆順にしたものを足し合わせる
#modを取っているので、Dを降順ソートすると順番が崩れる
ans=0
for c,d in zip(C,D[::-1]):
    ans+=c*d
    ans%=mod

ans=ans*pow(2,N,mod)

print ans%mod
### BUGGY CODE ###

INF = 10000000000
dx = [0, 0, 1, -1]
dy = [-1, 1, 0, 0]
 
def dfs(x, y, m):
    if y > N :
        return 0
    if mem[x][y][m] != INF:
        return mem[x][y][m]
    n = INF
    for j in range(2 if m > 0 else 1):
        for i, s in enumerate(st[y + 1 + j]):
            srip = max(0, st[y][x][1] + s[1])
            l = abs(st[y][x][0] - s[0])
            n = min(dfs(i, y + 1 + j, m - j) + srip * l, n)
    mem[x][y][m] = n
    return mem[x][y][m]
 
while True:
    N, M = map(int, input().split())
    if N == 0:
        break
    st = [[[-INF, -INF]] for i in range(N + 3)]
    for s in st[1:-2]:
        v = list(map(int, input().split()))
        del s[0]
        for i in range(1, len(v), 2):
            s.append([v[i], v[i + 1]])
    mem = [[[INF for i in range(M + 1)] for j in range(N + 1)] for k in range(N + 4)]
    print(dfs(0, 0, M))

### FIXED CODE ###

INF = 10000000000
dx = [0, 0, 1, -1]
dy = [-1, 1, 0, 0]
 
def dfs(x, y, m):
    if y > N :
        return 0
    if mem[x][y][m] != INF:
        return mem[x][y][m]
    n = INF
    for j in range(2 if m > 0 else 1):
        for i, s in enumerate(st[y + 1 + j]):
            srip = max(0, st[y][x][1] + s[1])
            l = abs(st[y][x][0] - s[0])
            n = min(dfs(i, y + 1 + j, m - j) + srip * l, n)
    mem[x][y][m] = n
    return mem[x][y][m]
 
while True:
    N, M = map(int, raw_input().split())
    if N == 0:
        break
    st = [[[-INF, -INF]] for i in range(N + 3)]
    for s in st[1:-2]:
        v = list(map(int, raw_input().split()))
        del s[0]
        for i in range(1, len(v), 2):
            s.append([v[i], v[i + 1]])
    mem = [[[INF for i in range(M + 1)] for j in range(N + 1)] for k in range(N + 4)]
    print(dfs(0, 0, M))
### BUGGY CODE ###

def greatest_common_divisor(x, y):
    if x > y:
        max = x
    else:
        max = y
    answer = 0
    for i in range(1, max+1):
        if x % i == 0 and y % i == 0:
            answer = i
    return answer

if __name__ == '__main__':
    x, y = [int(x) for x in input().split()]
    print(greatest_common_divisor(x, y))

### FIXED CODE ###

def greatest_common_division(x, y):
    if x < y:
        x, y = y, x

    if y == 0 or x == y:
        return x
    else:
        return greatest_common_division(y, x % y)

x, y = map(int, input().split())
print(greatest_common_division(x, y))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2000000)
n,u,v=map(int,input().split())
u=u-1
v=v-1
edge=[]
for i in range(n-1):
    a,b=map(int,input().split())
    edge.append((a-1,b-1))
dp1=[-1]*n
dp1[u]=0
dp2=[-1]*n
dp2[v]=0

root=[[] for i in range(n)]
for a,b in edge:
    root[a].append(b)
    root[b].append(a)

def dfs(node,depth,par,dp):
    for vertex in root[node]:
        if vertex == par:
            continue
        dp[vertex]=depth+1
        dfs(vertex,depth+1,node,dp)
dfs(u,0,u,dp1)
dfs(v,0,v,dp2)
buf=-1
buf1=0
#print(dp1,dp2,root)
for i in range(n):
    if dp1[i]<dp2[i] and dp2[i]>buf:
        buf=dp2[i]
        buf1=dp1[i]
print(buf-1)



### FIXED CODE ###

import sys
sys.setrecursionlimit(10**5)
n,u,v=map(int,input().split())
u=u-1
v=v-1
root=[[] for i in range(n)]

for i in range(n-1):
    a,b=map(int,input().split())
    root[a-1].append(b-1)
    root[b-1].append(a-1)

dp=[[-1]*n for i in range(2)]
dp[0][u]=0
dp[1][v]=0
def dfs(node,depth,par,flag):
    for vertex in root[node]:
        if vertex == par or dp[flag][vertex]!=-1:
            continue
        dp[flag][vertex]=depth+1
        dfs(vertex,depth+1,node,flag)
    return
dfs(u,0,u,0)
dfs(v,0,v,1)
buf=-1
buf1=0
#print(dp1,dp2,root)
for i in range(n):
    if dp[0][i]<dp[1][i] and dp[1][i]>buf:
        buf=dp[1][i]
        buf1=dp[0][i]
print(buf-1)
### BUGGY CODE ###

# C-高橋くんとカード
n,a=map(int,input().split())
lists=list(map(int,input().split()))
dp=[[[0 for i in range(2602)] for j in range(51)] for _ in range(51)]
dp[0][0][0]=1
#dp[i][j][k] で0からi番目のカードまでのうちで　ｊ枚を選択して、その時に選んだ数の合計がsとなるような方法の総数を刺すことにする
for i in range(n+1):
    for j in range(n+1):
        for k in range(2602):
            if i>=j and i>=1 and k<lists[i-1]:
                dp[i][j][k]=dp[i-1][j][k]
            elif i>=j and j>=1and k>=lists[i-1]:
                dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k-lists[i-1]]
ans=0
for i in range(1,n+1):
    ans+=dp[n][i][a*i]
print(ans)


### FIXED CODE ###

n,a=map(int,input().split())
lists=list(map(int,input().split()))

for i in range(n):
    lists[i]-=a
answer=0
dp=[[0 for i in range(5001)] for _ in range(51)]
#dp[i][j]で0からi枚目まで好きなように選択してそのそうわがｊ-2500となるような撮り方の総数
#最終的に求めるのはdp[i][0]である

for i in range(n+1):
    for j in range(4951):
        if i>=1 and j>=lists[i-1]:
            dp[i][j]=dp[i-1][j-lists[i-1]]+dp[i-1][j]
        if i>=1 and j<lists[i-1]:
            dp[i][j]=dp[i-1][j]
        else:
            if j==2500 and i==0:
                dp[i][j]=1
            elif j!=2500 and i==0:
                dp[i][j]=0
print(dp[n][2500]-1)
### BUGGY CODE ###

n = int(input())
h = list(map(int,input().split()))
h.insert(0,0)
h.append(0)
temp = []
cnt = 0

while h.count(0) <= n+2:
    for i in range(n+1):
        if h[i] == 0 and h[i+1] != 0:
            temp.append(h[i+1])
            s_ind = i+1
        if h[i] != 0 and h[i+1] != 0:
            temp.append(h[i+1])
        if h[i] != 0 and h[i+1] == 0:
            f_ind = i
            cnt += min(temp)
            temp = [j-min(temp) for j in temp]
            h = [h[k] if k not in range(s_ind,f_ind+1) else temp[k - s_ind] for k in range(n+2)]
            
print(cnt)

### FIXED CODE ###

n = int(input())
h = list(map(int, input().split()))
h = [h[i] if h[i] != 0 else "#" for i in range(n)]

ans = 0
cond = True
while cond:
    for i in range(n):
        if (i == 0 and h[i] != "#") or (h[i-1] == "#" and h[i] != "#"):
            ans += 1
        
        if h[i] != "#":
            h[i] -= 1

    h = [h[i] if h[i] != 0 else "#" for i in range(n)]

    if h.count("#") == n:
        cond = False

print(ans)
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	B
# CreatedDate:  2020-03-07 21:09:01 +0900
# LastModified: 2020-03-07 22:09:06 +0900
#

import collections

def main():
    N,A,B = map(int,input().split())
    count=0
    k=0
    for _ in range(10**100):
        for _ in range(A):
            k+=1
            count+=1
            if k==N:
                print(count)
                return 0
        for _ in range(B):
            k+=1
            if k==N:
                print(count)
                return 0




if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	B
# CreatedDate:  2020-08-30 14:36:32 +0900
# LastModified: 2020-08-30 14:45:15 +0900
#


import os
import sys
# import numpy as np
# import pandas as pd


def main():
    n, a, b = map(int, input().split())
    tmp = n - n // (a+b) * (a+b)
    ans = n//(a+b) * a
    if tmp <= a:
        print(ans+tmp)
    else:
        print(ans+a)


if __name__ == "__main__":
    main()
### BUGGY CODE ###

i, j = map(int,input().split())
ans = 100000000

for m in range(i, j):
  for n in range(m+1, j+1):
    x = m * n % 2019
    if x < ans:
      ans = x

print(ans)

### FIXED CODE ###

i, j = map(int,input().split())
ans = 100000000

for m in range(i, min(j, i+2019)): #高々O(2019**2)
  for n in range(m+1, min(j+1, i+2020)):
    x = m * n % 2019
    if x < ans:
      ans = x

print(ans)