Harryxun/stf_run huggingface dataset:
D,G = map(int,input().split())
P=[]
C=[]
for _ in range(D):
    p,c = map(int,input().split())
    P.append(p)
    C.append(c)
anss=2**10
for i in range(1 << D):
    ans = 0
    summ = 0
    nokori = set(range(1,D+1))
    for j in range(D):
        if 1 & (i >> j):
            summ += P[j]*100*(j+1)+C[j]
            ans += P[j]
            nokori.discard(j+1)
    if summ < G:
        use = max(nokori)
        n = min(P[use-1],-((G-summ)//(100*use)))
        ans += n
        summ += n* use* 100

    if summ < G:
        summ+=C[use-1]

    if summ >= G:
        anss =min(ans,anss)
        
print(anss

### FIXED CODE ###

d,g = map(int,input().split())
pc = [list(map(int,input().split())) for i in range(d)]

ans = float("inf")


for bit in range(1<<d):
    count = 0
    sum = 0
    nokori = set(range(1,d+1))

    for i in range(d):
        if bit & (1<<i):
            sum +=pc[i][0]*(i+1)*100+pc[i][1]
            count +=pc[i][0]
            nokori.discard(i+1)



    if sum < g:
        use = max(nokori)
        n = min(pc[use-1][0],-(-(g-sum)//(use*100)))
        count += n
        sum += n*use *100

    if sum >= g:
        ans = min(ans,count)
print(ans)
n, m = map(int, input().split())
lst = [list(map(int, input().split())) for i in range(M)]
p = list(map(int, input().split()))
ans = 0

for i in range(2**n):
    bulb = [0] * m
    for j in range(n):
        if i>>j & 1:
            for k in range(m):
                if j+1 in lst[k][1:]:
                    bulb[k] += 1

    flag = True
    for l in range(m):
        if bulb[l] % 2 != p[l]:
            flag = False
    if flag:
        ans += 1

print (ans)


### FIXED CODE ###

n, m = map(int, input().split())
lst = [list(map(int, input().split())) for i in range(m)]
p = list(map(int, input().split()))
ans = 0

for i in range(2**n):
    bulb = [0] * m
    for j in range(n):
        if i>>j & 1:
            for k in range(m):
                if j+1 in lst[k][1:]:
                    bulb[k] += 1

    flag = True
    for l in range(m):
        if bulb[l] % 2 != p[l]:
            flag = False
    if flag:
        ans += 1

print (ans)
N = int(input())
A = list(map(int,input().split()))
n = 0
can = True

while can:
    for i in range(N):
        if A[i]%2 == 0:
            A[i] = int(A[i]/2)
            n += 1

       else:
            can = False
            break

print(n)
        

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
n = 0
F = 0

while 1:
    #すべてが偶数か確認
    for i in range(N):
        if A[i] % 2 == 0:
            continue
        else:
            F = 1
    
    if F == 1 : break 

    for i in range(N):
        A[i] = A[i]/2
    n += 1


print(n)
import math
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return max(0,over//under)

n,k=map(int,input().split())
mod=10**9+7
for i in range(1,k+1):
  print(cmb(k-1,i-1)*cmb(n-k+1,i)%mod)


### FIXED CODE ###

import math
from operator import mul
from functools import reduce

def cmb(n,r):
  if n>=r:
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return max(0,over//under)
  else:
    return 0

n,k=map(int,input().split())
mod=10**9+7
for i in range(1,k+1):
  print(cmb(k-1,i-1)*cmb(n-k+1,i)%mod)
S = input()
if int(s[5]) == 0 and int(s[6]) <= 4 :
    print('Heisei')
else :
    print('TBD')

### FIXED CODE ###

s = input()
if int(s[5]) == 0 and int(s[6]) <= 4 :
    print('Heisei')
else :
    print('TBD')
n = int(input())

edge = [[] for i in range(n)]

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

c = list(map(int, input().split()))

c.sort(reverse=True)

w = [0] * n

w[0] = c.pop(0)

chk = [i for i in edge[0]]
# print(chk)

while chk != []:
    node = chk.pop(0)
    if w[node] == 0:
        w[node] = c.pop(0)
        chk.extend(edge[node])

print(sum(c) - max(c))

print(' '.join(map(str, w)))

### FIXED CODE ###

n = int(input())

edge = [[] for i in range(n)]

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

c = list(map(int, input().split()))

hhh = c.copy()

c.sort(reverse=True)

w = [0] * n

w[0] = c.pop(0)

chk = [i for i in edge[0]]
# print(chk)

while chk != []:
    node = chk.pop(0)
    if w[node] == 0:
        w[node] = c.pop(0)
        chk.extend(edge[node])

print(sum(hhh) - max(hhh))

print(' '.join(map(str, w)))
a = list(map(int, input().split()))
a.sort()
diff1 = a[1] - a[0]
diff2 = a[2] - a[1]
diff3 = a[2] - a[0]
if diff1 % 2 == 0:
    if diff3 % 2 == 0:
        print((diff3 + diff2)//2)
    else:
        print(diff3//2 + diff2//2 + 1)
else:
    if diff3 % 2 == 0:
        print(diff3//2 + diff2//2 + 2)
    else:
        prnit(diff3//2 + diff2//2 + 2)


### FIXED CODE ###

a = list(map(int, input().split()))
a.sort()
diff1 = a[1] - a[0]
diff2 = a[2] - a[1]
diff3 = a[2] - a[0]
if diff1 % 2 == 0:
    if diff3 % 2 == 0:
        print((diff3 + diff2)//2)
    else:
        print(diff3//2 + diff2//2 + 1)
else:
    if diff3 % 2 == 0:
        print(diff3//2 + diff2//2 + 2)
    else:
        print(diff3//2 + diff2//2 + 2)
from collections import deque
queue = deque([])
n = int(input())
for _ in range(n):
    command = input()
    if command == "deleteFirst":
        _ = queue.popleft()
    elif command == "deleteLast":
        _ = queue.pop()
    elif "delete" in command:
        _, x = command.split()
        queue.remove(x)
    else:
        _, x = command.split()
        queue.appendleft(x)
print(" ".join(queue))

### FIXED CODE ###

from collections import deque
queue = deque([])
n = int(input())
for _ in range(n):
    command = input()
    if command == "deleteFirst":
        _ = queue.popleft()
    elif command == "deleteLast":
        _ = queue.pop()
    elif "delete" in command:
        _, x = command.split()
        try:
            queue.remove(x)
        except ValueError:
            pass
    else:
        _, x = command.split()
        queue.appendleft(x)
print(" ".join(queue))
H,W=map(int,input().split())
print('#'*W+2)
for _ in range(H):
    print('#'+input()+'#')
print('#'*W+2)


### FIXED CODE ###

H,W=map(int,input().split())
print('#'*(W+2))
for _ in range(H):
    print('#'+input()+'#')
print('#'*(W+2))
from itertools import permutations

import numpy as np

N = int(input())

xys = []
for _ in range(N):
    xys.append(list(map(int, input().split())))

combs = np.array(list(permutations(xys, N)))
ret = np.array(
    [np.linalg.norm(combs[:, i] - combs[:, i + 1], axis=1) for i in range(N - 1)]
).sum() / len(combs)

print(f"{ret:.10f}")


### FIXED CODE ###

from itertools import permutations

import numpy as np

N = int(input())

xys = []
for _ in range(N):
    xys.append(list(map(int, input().split())))

combs = np.array(list(permutations(xys, N)))
ret = np.array(
    [np.linalg.norm(combs[:, i] - combs[:, i + 1], axis=1) for i in range(N - 1)]
).sum() / len(combs)

print("{:.10f}".format(ret))
# coding: UTF-8
from collections import deque
visited = set()
d = {}
arrow = {}
nodes = deque()

raw = input().split()
N = int(raw[0])
M = int(raw[1])

for i in range(1,N+1):
  arrow[i] = deque()
  d[i] = 0
  nodes.append(i)

for i in range(M):
  raw = list(map(int,input().split()))
  L = raw[0]
  R = raw[1]
  D = raw[2]
  arrow[L].append((R,D))
  arrow[R].append((L,-D))

def dfsl(v):
  #矛盾が見つかればFalseを返す
  visited.add(v)
  while arrow[v]:
    w,cost = arrow[v].pop()
    
    if w not in visited:
      d[w] = d[v] + cost
      return dfsl(w)
    else:
      if d[w] != d[v] + cost:
        return False
  return True

ans = True
while nodes:
  u = nodes.pop()
  if u not in visited:
    d[u] = 0
    ans = dfsl(u)
    if not ans:
      break

for v in range(1,N+1):
  while arrow[v] and not ans:
    w,c = arrow[v].pop()
    if d[w] != d[v] + c:
      ans = False
      break
  

if ans:
  print("Yes")
else:
  print("No")     
      

### FIXED CODE ###

# coding: UTF-8
from collections import deque
N,M = map(int,input().split())
link = [ [] for _ in range(N+1)]
value = [ -1 for _ in range(N+1)]

for _ in range(M):
  L,R,D = map(int,input().split())
  link[L].append((R,D))
  link[R].append((L,-D))

searched = set()
queue = deque()
for u in range(N+1):
  if u not in searched:
    queue.append(u)
    searched.add(u)
    value[u] = 0
    while queue:
      v = queue.popleft()
      for w,d in link[v]:
        if w not in searched:
          value[w] = value[v] + d
          queue.append(w)
          searched.add(w)

#verification
for v in range(N+1):
  for w,d in link[v]:
    if value[w] != value[v] + d:
      print("No")
      exit()
print("Yes")
N, K, Q = map(int, input().split())
A = [list(map(int,input().split()))for i in range(n)]
point_list = [K]*N
for answer in A:
    point_list = list(map(lambda x: x-1, point_list))
    point_list[answer-1] += 1
    
for ans in point_list:
    if ans > 0:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

N, K, Q = map(int, input().split())
A = [int(input()) for i in range(Q)]
seikaisuu = [0]*N
for answer in A:
    seikaisuu[answer-1] += 1
for x in seikaisuu:
    if K > Q - x:
        print("Yes")
    else:
        print("No")
n, m = map(int,input().split())
s = [list(map(int,input().split())) for _ in range(m)]
s.sort(key=lambda x: x[0])
for i in range(1,1000):
    num = str(i)
    count = 0
    if s[-1][0] > len(num):
        continue
    for j in range(m):
        if num[s[j][0]-1] == str(s[j][1]):
            count += 1
        if n == count:
            print(num)
            quit()
print(-1)

### FIXED CODE ###

n, m = map(int,input().split())
sc = [list(map(int,input().split())) for _ in range(m)]

for i in range(10**n):
    i = str(i)
    flag = True
    if len(i) == n:
        for j in range(m):
            if i[sc[j][0]-1] != str(sc[j][1]):
                flag = False
        if flag:
            print(i)
            quit()

print(-1)
N, K = map(int, input().split())
H = list(map(int, input().split()))

for i in range(K):
	H.remove(max(H))
    
print(sum(H))

### FIXED CODE ###

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

H.sort(reverse=True)
print(sum(H[K:]))
from collections import deque

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

nodes = [ [] for i in range(m+1)]

# グラフ生成
for i in range(1, m + 1):
    a, b = map(int, input().split())
    nodes[a].append(b)
    nodes[b].append(a)

ans = [0] * (n+1)

# キュー作成
stk = deque([1])

# BFS 幅優先探索
while stk:
    v = stk.pop()
    for s in nodes[v]:
        # 未到達ノードであれば、キューに追加
        if ans[s] == 0:
            # ひとつ前のノードを記録
            ans[s] = v
            # キューに要素を追加
            stk.appendleft(s)

ans = ans[2:]
 
if 0 in ans:
    print("No")
else:
    print("Yes")
    for i in ans:
        print(i)


### FIXED CODE ###

from collections import deque

n, m = map(int, input().split())
G = [[]for i in range(n+1)]

# グラフ生成
for i in range(m):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)
 
ans = [0]*(n+1)
 
stk = deque([1])
 
# BFS 幅優先探索
while stk:
    v = stk.pop()
    for s in G[v]:
        # 未到達ノードであれば、キューに追加
        if ans[s] == 0:
            ans[s] = v
            stk.appendleft(s)
ans = ans[2:]
 
if 0 in ans:
    print("No")
else:
    print("Yes")
    for i in ans:
        print(i)
a, v = map(int, input().split())
b, w = map(int, input().split())
t = input()

if abs(t * (w - v)) >= abs(b - a):
  print('YES')
else:
  print('NO')

### FIXED CODE ###

a, v = map(int, input().split())
b, w = map(int, input().split())
t = int(input())

if t * (v - w) >= abs(a - b):
  print('YES')
else:
  print('NO')
S=input()
T=input()
S=S[::-1]
if S=T:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

S=input()
T=input()
S=S*2
if T in S:
  print("Yes")
else:
  print("No")
import sys, math, heapq, bisect





if(__name__ == "__main__"):
    """
    N = int( input().strip() )
    Length = list( map(int, input().strip().split() ) )
    """
    H, W, N_bombs= map(int, input().strip().split() )

    H_N_bomb = [ [0, i]  for i in range(H) ]
    W_N_bomb = [ [0, i]  for i in range(W) ]
    bombs = [ [0]*W for _ in range(H)  ]


    for i in range(N_bombs):
        y, x = map(int, input().strip().split() )

        W_N_bomb[x-1][0] += 1
        H_N_bomb[y-1][0] += 1
        bombs[y-1][x-1] = 1


    W_N_bomb.sort(key = lambda x: x[0])
    H_N_bomb.sort(key = lambda x: x[0])
    queues = []


    Ws = [0] * W
    Hs = [0] * H
    for i in range(W):
        Ws[i] = W_N_bomb[i][0]
    for i in range(H):
        Hs[i] = H_N_bomb[i][0]

    pos_x= bisect.bisect_left(Ws, Ws[-1])
    pos_y= bisect.bisect_left(Hs, Hs[-1])
    #print(W_N_bomb, H_N_bomb, pos_x, pos_y)
    for i in range(pos_x, W):
        for j in range(pos_y, H):
            value = Ws[i] + Hs[j]
            pos_i = W_N_bomb[i][1]
            pos_j = H_N_bomb[j][1]
            if(bombs[pos_j][pos_i]==1):
                value -= 1
            heapq.heappush(queues, (-1) * value)
    print(-1 * queues[0])


### FIXED CODE ###

import sys, math, bisect



def solve(W_N, V_N, bombs, H, W):

    max_x = 1
    xs = []
    for i in range(W):
        if(W_N[i] > max_x):
            max_x = W_N[i]
            xs = [i]
        elif(W_N[i] == max_x):
            xs.append(i)
    max_y = 1
    ys = []
    for j in range(H):
        if(V_N[j] > max_y):
            max_y = V_N[j]
            ys = [j]
        elif(V_N[j] == max_y):
            ys.append(j)

    value = max_x + max_y

    for j in ys:

        bombs[j].sort()
        for i in xs:
            index = bisect.bisect_left(bombs[j], i)
            if(index == V_N[j] or i != bombs[j][index]):
                return value
            
    return value-1



if(__name__ == "__main__"):
    """
    N = int( input().strip() )
    Length = list( map(int, input().strip().split() ) )
    """
    H, W, N_bombs= map(int, input().strip().split() )


    V_N = [0] * H
    W_N = [0] * W
    bombs = [ [] for _ in range(H) ]


    for i in range(N_bombs):
        y, x = map(int, input().strip().split() )
        """
        W_N_bomb[x-1][0] += 1
        V_N_bomb[y-1][0] += 1
        """
        V_N[y-1] += 1
        W_N[x-1] += 1
        bombs[y-1].append(x-1)




    print( solve(W_N, V_N, bombs, H, W) )
S = input()
max = 0
for i in range(len(S)):
    if S[i] in 'ACGT':
        for j in range(i+1, len(S)):
            if S[j] not in ['A', 'C', 'G', 'T']:
                break
        max = (j - i) if max < (j - i) else max 
print(max)

### FIXED CODE ###

s = input()
z = ''
ans = 0
for i in range(len(s)):
    if s[i] in 'ACGT':
        ans = max(ans, 1)
        for j in range(i+1, len(s)):
            if s[j] in 'ACGT':
                ans = max(ans, j-i+1)
            else:
                break
    else:
        continue
print(ans)
n, i = map(int, input().split())

print(n - i + 1)　

### FIXED CODE ###

n, i = map(int, input().split())

print(n - i + 1)
H,W = map(int,input().split())
s = [[] for i in range(H)]
for i in range(H): s[i] = list(input())
ans_y = [[0]*W for i in range(H)]
ans_t = [[0]*W for i in range(H)]

def yoko(h,w,n):
    if w == W-1 or s[h][w+1] == "#":
        ans_y[h][w] = n
        if n != 1: return n
    else:
        num = yoko(h,w+1,n+1)
        ans_y[h][w] = num
        if n != 1: return num

def tate(h,w,n):
    if h == H-1 or s[h+1][w] == "#":
        ans_t[h][w] = n
        if n != 1: return n
    else:
        num = tate(h+1,w,n+1)
        ans_t[h][w] = num
        if n != 1: return num

for h in range(H):
    for w in range(W):
        if s[h][w] == ".":
            if ans_y[h][w] == 0: yoko(h,w,1)
            if ans_t[h][w] == 0: tate(h,w,1)

ans = 0
for h in range(H):
    for w in range(W):
        ans = max(ans, ans_y[h][w] + ans_t[h][w] - 1)

print(ans)

### FIXED CODE ###

H,W = map(int,input().split())
s = [[] for i in range(H)]
for i in range(H): s[i] = list(input())
l = [[0]*W for i in range(H)]
r = [[0]*W for i in range(H)]
d = [[0]*W for i in range(H)]
u = [[0]*W for i in range(H)]

for h in range(H):
    if s[h][0] == ".": l[h][0] = 1
    for w in range(1,W):
        if s[h][w] == ".": l[h][w] = l[h][w-1] + 1
    if s[h][W-1] == ".": r[h][W-1] = 1
    for w in range(1,W):
        if s[h][W-1-w] == ".": r[h][W-1-w] = r[h][W-w] + 1

for w in range(W):
    if s[0][w] == ".": d[0][w] = 1
    for h in range(1,H):
        if s[h][w] == ".": d[h][w] = d[h-1][w] + 1
    if s[H-1][w] == ".": u[H-1][w] = 1
    for h in range(1,H):
        if s[H-1-h][w] == ".": u[H-1-h][w] = u[H-h][w] + 1
ans = 0
for h in range(H):
    for w in range(W):
        ans = max(ans, l[h][w]+r[h][w]+u[h][w]+d[h][w]-3)

print(ans)
import collections,math,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,M = LI()
ans = 1
def prime_factor(num):
    prime_factor = collections.defaultdict(int)
    for i in range(2,int(num**0.5)+1):
        while num%i==0:
            prime_factor[i] += 1
            num //= i
    if num>1:
        prime_factor[num]=1
    return prime_factor
for v in prime_factor(M).values():
    ans *= math.factorial(v+N-1)//math.factorial(v)//math.factorial(N-1)
    ans %= 10**9+7
print(ans)

### FIXED CODE ###

ABC = list(map(int,input().split()))
ABC.sort(reverse= True)
print(int(str(ABC[0])+str(ABC[1])) +ABC[2])
a=int(input())
b=[3,5,7,9,11,13,15,17,19]
c=d=0
if a<105:a=105
for i in range(104,a):
    for j in b:
        if a%j==0:c+=1
    if c==3:d+=1
    c=0
print(d)

### FIXED CODE ###

a,b=map(int,input().split())
print((a-1)*(b-1))
a,b,c,d=map(int,input()split())
A=abs(a-b)
B=abs(b-c)
C=abs(c-a)
if (C<=d) or (A<=d and B<=d):
  print("Yes")
else:
  print("No")

### FIXED CODE ###

a,b,c,d=map(int,input().split())
A=abs(a-b)
B=abs(b-c)
C=abs(c-a)
if (C<=d) or (A<=d and B<=d):
  print("Yes")
else:
  print("No")
#!/mnt/c/Users/moiki/bash/env/bin/python
# N,M = map(int, input().split())
L = int(input())
A = [int(input()) for _ in  range(L)]


# mode = A[0] % 2
# B = []
# for a in A:
#     if a == 0:
#         mode = -1
#     elif a % 2 == mode:
#     elif a % 2 != mode:


fromEnd = []

i = 0
while i < L:
    if A[i] != 0:
        start = i
        while i < L and A[i] != 0:
            i += 1
        end = i-1 if i != start else start
        fromEnd.append((start, end, sum(A[start:end+1])))
    i += 1

ans = float("inf")

# start forward
mode = 2 % 2
sum_forward = sum(A)
for i in range(start, L):
    sum_forward = min(sum_forward, ans)
    if   A[i] % 2 ==  1 and mode == A[i] % 2:
        sum_forward -= A[i]
    elif A[i] % 2 ==  1 and mode != A[i] % 2:
        mode = A[i] % 2
        sum_forward -= A[i]

    elif A[i] == 0:
        sum_forward += 1
        mode = -1

    elif A[i] % 2 == 0 and mode == A[i] % 2 :
        sum_forward -= A[i]

    elif A[i] % 2 == 0 and mode != A[i] % 2 :
        sum_forward -= A[i] - 1
        mode = A[i] % 2 
    
    if i == L-1 and A[i] %2 == 0 and mode != A[i] %2:
        sum_forward -= 1

# print("sum forward: ", sum_forward)
ans = sum_forward
mode = 2 % 2
sum_backward = sum(A)


for i in range(end, -1, -1):
    ans = min(sum_backward, ans)
    
    # ans = min(sum_backward, ans)
    if   A[i] % 2 ==  1 and mode == A[i] % 2:
        sum_backward -= A[i]
    elif A[i] % 2 ==  1 and mode != A[i] % 2:
        mode = A[i] % 2
        sum_backward -= A[i]

    elif A[i] == 0:
        sum_backward += 1
        mode = -1

    elif A[i] % 2 == 0 and mode == A[i] % 2 :
        sum_backward -= A[i]
    elif A[i] % 2 == 0 and mode != A[i] % 2 :
        sum_backward -= A[i] - 1
        mode = A[i] % 2 
    if i == 0 and A[i] %2 == 0 and mode != A[i] %2:
        sum_backward -= 1

ans = min(sum_backward, sum_forward)
print(ans)

    


### FIXED CODE ###

#!/mnt/c/Users/moiki/bash/env/bin/python
# N,M = map(int, input().split())
L = int(input())
A = [int(input()) for _ in  range(L)]


DP = [0] * 5
for i in range(L):
    r0 = A[i]
    r1 = (A[i] + 1) % 2

    if A[i] == 0:
        r2 = 2
    else:
        r2 = A[i] % 2

    for i,r in zip(range(4,-1,-1), [r0,r2,r1,r2,r0]):
        DP[i] = min(DP[:i+1]) + r
        # print(DP)

print(min(DP))
def modpow(a,n,p):
    if n==0:
        return 1
    x=modpow(a,n//2,p)
    x=(x*x)%p
    if (n%2)==1:
        x=(x*a)%p
    return x%p
def modinv(a,p):
    return modpow(a,p-2,p)
import math
import fractions
import collections
import itertools
import pprint
from collections import deque
N,K=map(int,input().split())
A=list(map(int,input().split()))
ans=1
p=10**9+7
ab=[]
for i in range(N):
    ab.append([abs(A[i]),i])
ab.sort(key=lambda x:x[0],reverse=True)
micount=0
ans=1
for i in range(K):
    if A[ab[i][1]]<0:
        micount=micount+1
    ans=(ans*ab[i][0])%p
if micount%2==0:
    print(ans)
else:
    for i in range(N-K,N):
        if A[ab[i][1]]<0:
            divind=i
            break
    mulind=0
    for i in range(N-K-1,-1,-1):
        if A[ab[i][1]]>=0:
            mulind=i
            break
    ans=(ans*modinv(A[divind],p)*A[mulind])%p
    print(ans)


### FIXED CODE ###

import math
import fractions
import collections
import itertools
import pprint
from collections import deque
N,K=map(int,input().split())
A=list(map(int,input().split()))
plist=[]
mlist=[]
ans=1
p=10**9+7
for i in range(N):
    if A[i]>=0:
        plist.append(A[i])
    else:
        mlist.append(A[i])
if len(plist)==0:
    if K%2==1:
        A.sort(reverse=True)
    else:
        A.sort()
    for i in range(K):
        ans=(ans*A[i])%p
    print(ans%p)
elif len(plist)==1:
    #print(plist,mlist)
    mlist.sort()
    if K%2==1:
        ans=plist[0]
    for i in range(K-1):
        ans=(ans*mlist[i])%p
    print(ans%p)
else:
    ans=1
    plist.sort(reverse=True)
    mlist.sort()
    pmap=deque()
    mmap=deque()
    if K%2==1:
        ans=plist[0]%p
        plist.pop(0)
        K=K-1
    #print(plist,mlist)
    for i in range(0,len(plist)-1,2):
        pmap.append(plist[i]*plist[i+1])
    if len(plist)>0:
        pres=plist[len(plist)-1]
    if len(mlist)>0:
        mres=mlist[len(mlist)-1]
    for i in range(0,len(mlist)-1,2):
        mmap.append(mlist[i]*mlist[i+1])
    #print(K)
    mapnum=K//2
    #print(mapnum)
    #print(pmap,mmap,ans)
    for i in range(mapnum):
        if (len(pmap)>0)and(len(mmap)>0):
            pl=pmap.popleft()
            mi=mmap.popleft()
            if pl>mi:
                ans=(ans*pl)%p
                mmap.appendleft(mi)
            else:
                ans=(ans*mi)%p
                pmap.appendleft(pl)
        elif (len(pmap)==0)and(len(mmap)>0):
            mi=mmap.popleft()
            ans = (ans *mi) % p
        elif (len(mmap)==0)and(len(pmap)>0):
            pl=pmap.popleft()
            ans = (ans *pl) % p
        else:
            ans=(ans*pres*mres)%p
    print(ans)
n, i = map(int, input().split())
    print(n - i + 1)

### FIXED CODE ###

n, i = [int(_) for _ in input().split()]
print(n - i + 1)
n,m=map(int,input().split())
x=list(map(int,input().split()))
count=0
a=max(x)
i=min(x)
if m<=2:
  print(count)
while True:
  x.remove(a)
  x.remove(b)
  a-=1
  b+=1
  count+=1
  if x==[]:
    print(count)
    break

### FIXED CODE ###

n,m=map(int,input().split())
x=list(map(int,input().split()))
x.sort()
y=[]
for i in range(len(x)-1):
  y+=[x[i+1]-x[i]]
y.sort()
if n>=m:
  print(0)
else:
  print(sum(y[:m-n]))
import math

N, X = map(int, input().split())
town = list(map(int, input().split()))

for i in range(N):
  if town[i] < X:
    town[i] = X - town[i]
  else:
    town[i] = town[i] - X

if N ==1:
  print(town[0])
  
else:
  gcd = math.gcd(town[0], town[1])
  for i in range(2, N):
    gcd = math.gcd(gcd, town[i])
  print(gcd)
  
  

### FIXED CODE ###

import fractions
  

N, X = map(int, input().split())
town = list(map(int, input().split()))
 
for i in range(N):
  if town[i] < X:
    town[i] = X - town[i]
  else:
    town[i] = town[i] - X
  
gcd = town[0]
for i in range(1, N):
  gcd = fractions.gcd(gcd, town[i])
print(gcd)
N = int(input())
words = []
for _ in range(N):
    words.append(input())
print('Yes' if all(w[i].startswith(w[i-1][-1]) for i in range(1, N)) and len(set(words)) == N else 'No')

### FIXED CODE ###

N = int(input())
words = []
for _ in range(N):
    words.append(input())
print('Yes' if all(words[i].startswith(words[i-1][-1]) for i in range(1, N)) and len(set(words)) == N else 'No')