Harryxun/stf_run huggingface dataset:
import sys
sys.setrecursionlimit(10**5)
m = 100005
visited = [False]*(m*2)
cnt = [0,0]
def dfs(i):
    visited[i] = True
    cnt[i//m] +＝ 1
    for j in to[i]:
        if not visited[j]:
            dfs(j)
 
input = sys.stdin.readline
n = int(input())
to = [[] for _ in range(m*2)]
for _ in range(n):
    x,y = map(int,input().split())
    y = y+m
    to[x].append(y)
    to[y].append(x)
 
ans = 0
for i in range(m):
    if not visited[i]:
        cnt = [0,0]
        dfs(i)
        ans = ans + cnt[0]*cnt[1]
 
print(ans-n)

### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)

    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    def Unite(self, x, y):
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    def Count(self, x):
        return -self.root[self.Find_Root(x)]

m = 100010
uf = UnionFind(m*2)
n = int(input())
for i in range(n):
    x,y = map(int,input().split())
    y = y+m
    uf.Unite(x,y)

lx = {}
ly = {}
ans = 0
for i in range(m):
    rx = uf.Find_Root(i)
    lx[rx] = lx.get(rx,0)+1
    ry = uf.Find_Root(i+m)
    ly[ry] = ly.get(ry,0)+1
for i in range(m*2):
    ans += lx.get(i,0)*ly.get(i,0)

print(ans-n)
import sys
import numpy as np
sys.setrecursionlimit(1000000)
 
N,K = map(int,input().split())
VN =  [int(i) for i in input().split()]

ans = 0
temp = 0

for i in range(K):
    for j in range(K-i):
        now = 0
        if i + j > K:
            break
       
        tmp_list = []
        
        for l in range(i):
            now += VN[l]
            tmp_list.append(VN[l])
    
        for m in range(j):
            now += VN[N-1-m]
            tmp_list.append(VN[N-1-m])
        
        tmp_list.sort()
        
        for n in range(N-i-j-2):
            if n >= len(tmp_list)-1:
                break
            if tmp_list[n] >= 0:
                break
            now -= tmp_list[n]
        ans = max(ans,now)

print(ans)

### FIXED CODE ###

import sys
import numpy as np
sys.setrecursionlimit(1000000)
 
N,K = map(int,input().split())
VN =  [int(i) for i in input().split()]

ans = 0
temp = 0

for i in range(min(N,K)+1):
    for j in range(min(K-i,N-i)+1):
        now = 0
        if i + j > min(N,K):
            break
       
        tmp_list = []
        
        for l in range(i):
            now += VN[l]
            tmp_list.append(VN[l])
    
        for m in range(j):
            now += VN[N-1-m]
            tmp_list.append(VN[N-1-m])
        
        tmp_list.sort()
        
        for n in range(K-i-j):
            if n >= len(tmp_list):
                break
            if tmp_list[n] >= 0:
                break
            now -= tmp_list[n]
        ans = max(ans,now)

print(ans)
import math
import sys
import itertools
import queue
from fractions import gcd
import numpy as np


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

mod = 2019

if __name__ == "__main__":
    L,R= map(int, sys.stdin.readline().split())
    if R-L>=2018:
        print(0)
    else:
        ans=2019
        for i in range(L,R):
            for j in range(i+1,R+1):
                ans=min(ans,(j*i)%mod)
    print(ans)

### FIXED CODE ###

L, R = map(int, input().split())
if R - L >= 2018:
	print(0)
else:
	ans = 2019
	for i in range(L, R):
		for j in range(i + 1, R + 1):
			ans = min(ans, i * j % 2019)
	print(ans)
# AGC039B - Graph Partition (153ms)
from collections import deque


def is_bipartite() -> bool:
    stack, color = [(1, 1)], [0] * (N + 1)
    color[1] = 1
    while stack:
        v, cur_color = stack.pop()
        next_color = -cur_color
        for u in E[v]:
            if color[u] == cur_color:
                return False
            if not color[u]:
                color[u] = next_color
                stack.append((u, next_color))
    return True


def bfs(source: int) -> int:
    queue = deque([source])
    dist = [0] * (N + 1)  # dist[i] := distance from V_source to V_i
    dist[start] = 1
    while queue:
        v = queue.popleft()
        cur = dist[v]
        for u in E[v]:
            if not dist[u]:
                dist[u] = cur + 1
                queue.append(u)
    return max(dist)


def main():
    # if bipartite graph -> diameter of the graph + 1
    global N, E
    N, *S = open(0).read().split()
    N = int(N)
    E = [0] + [[i for i, flg in enumerate(s, 1) if flg == "1"] for s in S]
    if is_bipartite():
        ans = max(bfs(i) for i in range(1, N + 1))
        print(ans)
    else:
        print(-1)


if __name__ == "__main__":
    main()

### FIXED CODE ###

# AGC039B - Graph Partition
from collections import deque


def is_bipartite() -> bool:
    stack = [(1, 1)]
    color = [-1] * (N + 1)
    color[1] = 1
    while stack:
        v, cur_color = stack.pop()
        next_color = cur_color ^ 1
        for u in E[v]:
            if color[u] == cur_color:
                return False
            if color[u] == -1:
                color[u] = next_color
                stack.append((u, next_color))
    return True


def bfs(start) -> int:
    que = deque([start])
    dist = [-1] * (N + 1)  # dist[i] := distance from V_start to V_i
    dist[start] = 0
    while que:
        v = que.popleft()
        cur = dist[v]
        for u in E[v]:
            if dist[u] == -1:
                dist[u] = cur + 1
                que.append(u)
    return max(dist)


def main():
    # if bipartite graph -> diameter of the graph + 1
    global N, E
    N, *S = open(0).read().split()
    N = int(N)
    E = [0] + [[i for i, flg in enumerate(s, 1) if flg == "1"] for s in S]
    if is_bipartite():
        ans = max(bfs(i) for i in range(1, N + 1)) + 1
        print(ans)
    else:
        print(-1)


if __name__ == "__main__":
    main()
n = int(input())
A = list(map(int,input().split()))
A.sort()

m = 0
cnt = 0
for i in A:
  if(m != A[i]):
    m = A[i]
    cnt += 1

if(cnt % 2 == 0):
  cnt -= 1
print(cnt)
    

### FIXED CODE ###

n = int(input())
A = list(map(int,input().split()))
A.sort()

m = 0
cnt = 0
for i in A:
  if(m != i):
    m = i
    cnt += 1

if(cnt % 2 == 0):
  cnt -= 1
print(cnt)
N,A,B = list(map(int,input().split()))
a = 0

for i in range(N+1):
  S = sum(list(map(int,list(str(i)))))
  if A<=S<=B:
    a+=i

print(z)

### FIXED CODE ###

a = list(map(int,input().split()))
z = 0

for i in range(a[0]+1):
  b = list(str(i))
  c = list(map(int,b))
  d = sum(c)
  if a[1]<=d<=a[2]:
    z+=i
else:
  print(z)
n = int(input())
pyr = []
for i in range(n):
    x, y, h = map(int, input().split())
    if h != 0:
        pyr.append((x, y, h))

if len(pyr) == 1:
    print(*pyr[0])
    exit()

for i in range(101):
    for j in range(101):
        cx, cy = (i, j)
        h_list = []
        for k in range(n):
            x, y, h = pyr[k]
            h_list.append(h + abs(x - cx) + abs(y - cy))
        if len(set(h_list)) != 1:
            continue
        else:
            print(cx, cy, h_list[0])
            exit()



### FIXED CODE ###

n = int(input())
pyr = []
for i in range(n):
    x, y, h = map(int, input().split())
    if h != 0:
        pyr.append((x, y, h))

if len(pyr) == 1:
    print(*pyr[0])
    exit()

for i in range(101):
    for j in range(101):
        cx, cy = (i, j)
        h_list = []
        for k in range(len(pyr)):
            x, y, h = pyr[k]
            h_list.append(h + abs(x - cx) + abs(y - cy))
        if len(set(h_list)) != 1:
            continue
        else:
            print(cx, cy, h_list[0])
            exit()
N,M=map(int,input().split(' '))

x=[]
y=[]
z=[]
for _ in range(N):
  _x,_y,_z=map(int,input().split(' '))
  x.append(_x)
  y.append(_y)
  z.append(_z)

def argmin(l):
  m=min(l)
  for i in range(len(l)):
    if l[i]==m:
      return i

def f(sign_x, sign_y, sign_z):
  l=[]
  for i in range(N):
    s=x[i]*sign_x + y[i]*sign_y + z[i]*sign_z
    if len(l)<M:
      l.append(s)
    elif min(l)<s:
      del l[argmin(l)]
      l.append(s)
  return sum(l)



res=0
for x_s in [1,-1]:
  for y_s in [1,-1]:
    for z_s in [1,-1]:
      score = f(x_s, y_s, z_s)
      if score>res:
        res=score

print(res)




### FIXED CODE ###

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

x=[]
y=[]
z=[]
for _ in range(N):
  _x,_y,_z=map(int,input().split(' '))
  x.append(_x)
  y.append(_y)
  z.append(_z)

def argmin(l):
  m=min(l)
  for i in range(len(l)):
    if l[i]==m:
      return i

def f(sign_x, sign_y, sign_z):
  l=[]
  for i in range(N):
    s=x[i]*sign_x + y[i]*sign_y + z[i]*sign_z
    l.append(s)
    if len(l)>M:
      del l[argmin(l)]
  return sum(l)


res=0
for x_s in [1,-1]:
  for y_s in [1,-1]:
    for z_s in [1,-1]:
      score = f(x_s, y_s, z_s)
      if score>res:
        res=score

print(res)
C:\Users\ia\Documents\Python Scripts\test.pydef getmax(x,y):
    if x>y:
        return x
    else:
        return y
N,M,K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

a,b = [0],[0]
for i in range(N):   #a[i]にはAの本をi冊読んだ時の時間がそれぞれ保存されている．
    a.append(a[i]+A[i])  #計算量を減らすため，a[i]（1冊前までにかかる時間）を用いる
for i in range(M):
    b.append(b[i]+B[i])

ans,j = 0,M
for i in range(N+1):
    if a[i]>K:
        break
    while b[j] > K-a[i]:    #Bの本を読んだ場合の処理はここで実行される．
        j -=1
    ans = max(ans, i+j)
print(ans)


### FIXED CODE ###

def getmax(x,y):
    if x>y:
        return x
    else:
        return y
N,M,K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

a,b = [0],[0]
for i in range(N):   #a[i]にはAの本をi冊読んだ時の時間がそれぞれ保存されている．
    a.append(a[i]+A[i])  #計算量を減らすため，a[i]（1冊前までにかかる時間）を用いる
for i in range(M):
    b.append(b[i]+B[i])

ans,j = 0,M
for i in range(N+1):
    if a[i]>K:
        break
    while b[j] > K-a[i]:    #Bの本を読んだ場合の処理はここで実行される．
        j -=1
    ans = max(ans, i+j)
print(ans)
N = int(input())
a = list(map(int,input().split()))
one = 0
four = 0
two = 0

for j in range(N):

  if a[j]%2 == 1:
    one += 1
  elif a[j]%4 == 0:
    four += 1
  else :
    two +=1

  
if one =< four:
  print('Yes')
else :
  if two == 0:
    if four == one-1:
      print('Yes')
    else:
      print("No")
  else:
    print('No')

### FIXED CODE ###

N = int(input())
a = list(map(int,input().split()))
one = 0
four = 0
two = 0

for j in range(N):

  if a[j]%2 == 1:
    one += 1
  elif a[j]%4 == 0:
    four += 1
  else :
    two +=1

print("Yes" if four >= one or (four == one - 1 and two == 0) else "No")
abc125b

n=int(raw_input())
v=map(int,raw_input().split())
c=map(int,raw_input().split())
res=0
for i in xrange(n):
 if v[i]-c[i]>0:
  res+=v[i]-c[i]
print res


### FIXED CODE ###

#abc125b

n=int(raw_input())
v=map(int,raw_input().split())
c=map(int,raw_input().split())
res=0
for i in xrange(n):
 if v[i]-c[i]>0:
  res+=v[i]-c[i]
print res
A, B, C, D = list(input())
A = int(A)
B = int(B)
C = int(C)
D = int(D)

for i in range(2):
    s = A
    op1 = '+' if i == 0 else '-'
    s += B if op1 == '+' else -1 * B
    for j in range(2):
        op2 = '+' if j == 0 else '-'
        s += C if op2 == '+' else -1 * C
        for k in range(2):
            op3 = '+' if k == 0 else '-'
            s += D if op3 == '+' else -1 * D
            if s == 7:
                ans = str(A)+op1+str(B)+op2+str(C)+op3+str(D)+'=7'

print(ans)


### FIXED CODE ###

S = input()
A = S[0]
B = S[1]
C = S[2]
D = S[3]

op = ['+', '-']

def check(A, B, C, D):
    for i in range(2):
        for j in range(2):
            for k in range(2):
                x = A+op[i]+B+op[j]+C+op[k]+D
                if eval(x) == 7:
                    return x

print(check(A, B, C, D)+'=7')
N = int(input())
flag = False
for i in range(N//4 +1):
  for j in range(N//7 +1):
	if 4*i + 7*j == N:
	  print('Yes')
      flag = True
	  break

if flag:
  break
else:
  print('No')


### FIXED CODE ###

N = int(input())
fmax = int(N/4)+1
smax = int(N/7)+1
for i in range(fmax+1):
  for j in range(smax+1):
    if (4*i+7*j) == N:
      print('Yes')
      exit()
print('No')
n,a,b,c,d=map(int,input().split())
res=list(input())
if c<d:
    for i in range(1,n):
        if res[i-1]=="#" and res[i]=="#":
            print("No")
            exit()
    print("Yes")
    exit()

for i in range(b,d+1):
    if i==1:
        continue
    if res[i-2]=="." and res[i-1]=="." and res[i]==".":
        print("Yes")
        exit()
    if res[i-1]=="#" and res[i]=="#":
        print("No")
        exit()
        
if res[i-1]=="." and res[i]=="." and res[i+1]==".":
    print("Yes")
    exit()
print("No")
exit()


### FIXED CODE ###

n,a,b,c,d=map(int,input().split())
res=list(input())
if c<d:
    for i in range(a,d+1):
        if res[i-1]=="#" and res[i]=="#":
            print("No")
            exit()
    print("Yes")
    exit()

for i in range(b,d+1):
    if i==1:
        continue
    if res[i-2]=="." and res[i-1]=="." and res[i]==".":
        print("Yes")
        exit()
    if res[i-1]=="#" and res[i]=="#":
        print("No")
        exit()
        
print("No")
exit()
#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(N: int, p: "List[int]"):
    counter = 0
    i = 0
    while i < N:
        if i+1 == p[i]:
            if i+2 == p[i+1]:
                counter += 1
                i += 2
                continue
            else:
                counter += 1
                i += 1
                continue
        else:
            i += 1
            continue
    print(counter)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    p = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, p)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(N: int, p: "List[int]"):
    counter = 0
    i = 0
    while i < N:
        if i+1 == p[i]:
            if i+1 < N and i+2 == p[i+1]:
                counter += 1
                i += 2
                continue
            else:
                counter += 1
                i += 1
                continue
        else:
            i += 1
            continue
    print(counter)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    p = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, p)


if __name__ == '__main__':
    main()
a = int(input())
b = int(input())
h = int(input())
m = int(input())
ans = math.sqrt(float(a)^2+float(b)^2+2*a*b*math.cos((h/12 + m/720 - m/60)*math.pi))
print(ans)

### FIXED CODE ###

import math
a,b,h,m = map(int, input().split())
ans = math.sqrt(float(a)**2+float(b)**2-2*a*b*math.cos((h/12 + m/720 - m/60)*math.pi*2))
print(ans)
a,b=map(int,input().split())
height=list(input())
count=0
for i in range (a):
  	 if height[i]>=b:
      	count+=count
print(str(count))

### FIXED CODE ###

a,b=map(int,input().split())
height=list(map(int,input().split()))
count=0
for i in range (a):
    if int(height[i])>=b:
       count+=1
print(count)
s = input()
t = 0
u = 0
n = len(s)
for i in range(n):
  if s[i] == "A":
    t = i
    break
for j in range(n):
  if s[n-j] == "Z":
    u = n-j
print(u-t)

### FIXED CODE ###

s = input()
t = 0
u = 0
n = len(s)
for i in range(n):
  if s[i] == "A":
    t = i
    break
for j in range(n):
  if s[n-j-1] == "Z":
    u = n-j-1
    break
print(u-t+1)
N = int(input())
T = [[0,0,0]]+[map(int, input().split()) for _ in range(N)]
for i in range(len(T)-1):
    t1,x1,y1 = T[i] 
    t2,x2,y2 = T[i+1]
    dis = abs(x2-x1)+abs(y2-y1)
    _t = t2-t1
    if dis > _t or _t%2 != dis%2:
        flag = 'No'
    else:
        flag = 'Yes'
    if not flag:
        break
print(flag)
    

### FIXED CODE ###

N = int(input())
T = [[0,0,0]]+[ [int(x) for x in input().split()] for _ in range(N)]

flag = 'Yes'
i = 0
while flag=='Yes' and i<len(T)-1:
    t1,x1,y1 = T[i] 
    t2,x2,y2 = T[i+1]
    dis = abs(x2-x1)+abs(y2-y1)
    _t = t2-t1
    if dis > _t or _t%2 != dis%2:
        flag = 'No'
    i += 1        
print(flag)
# coding:utf-8
class Tree(object):
    def __init__(self, N):
        self.tree   = [[] for _ in range(N)]
        self.colors = [0  for _ in range(N)]

    def add_node(self, a, b):
        self.tree[a].append(b)
    # 二部グラフか判定する関数
    def is_bipartite_graph(self, v, color):
        self.colors[v] = color
        for to in self.tree[v]:
            if self.colors[to] == color:
                return False
            if self.colors[to] == 0 and not self.is_bipartite_graph(to, -color):
                return False
        return True
    
    def count_node(self, color):
        return self.colors.count(color)
    
if __name__ == "__main__":

    # input data
    N, M = map(int, input().split())
    tree = Tree(N)
    for _ in range(M):
        a, b = map(int, input().split())
        tree.add_node(a-1, b-1)
        tree.add_node(b-1, a-1)
    
    # tree dp
    is_bpr = tree.is_bipartite_graph(0, 1)
    if is_bpr:
        bla = tree.count_node(1)
        whi = N - bla
        print(bla*whi-M)
    else:
        print(N*(N-1)/2-M)



### FIXED CODE ###

# coding:utf-8
class Tree(object):
    def __init__(self, N):
        self.tree   = [[] for _ in range(N)]
        self.colors = [0  for _ in range(N)]

    def add_node(self, a, b):
        self.tree[a].append(b)
    # 二部グラフか判定する関数
    def is_bipartite_graph(self, v, color):
        self.colors[v] = color
        for to in self.tree[v]:
            if self.colors[to] == color:
                return False
            if self.colors[to] == 0 and not self.is_bipartite_graph(to, -color):
                return False
        return True
    
    def count_node(self, color):
        return self.colors.count(color)
    
if __name__ == "__main__":

    import sys
    sys.setrecursionlimit(200000)
    # input data
    N, M = map(int, input().split())
    tree = Tree(N)
    for _ in range(M):
        a, b = map(int, input().split())
        tree.add_node(a-1, b-1)
        tree.add_node(b-1, a-1)
    
    # tree dp
    is_bpr = tree.is_bipartite_graph(0, 1)
    if is_bpr:
        bla = tree.count_node(1)
        whi = N - bla
        print(bla*whi-M)
    else:
        print(int(N*(N-1)/2-M))
n = input()
inf = 1000000000
M = [[inf for i in range(n)] for i in range(n)]
for i in range(n):
  str = map(int, raw_input().split())
  u = str[0]
  k = str[1]
  for j in range(k):
    v = str[2+j]
    c = str[3+j]
    M[u][v] = c
d = [inf for i in range(n)]
color = [0 for i in range(n)]

d[0] = 0
color[0] = 1

while 1:
  minv = inf
  u = -1
  for i in range(n):
    if minv>d[i] and color[i]!=2:
      u = i
      minv = d[i]
    print minv
  if u == -1:
    break
  color[u] = 2
  for v in range(n):
    if color[v]!=2 and M[u][v]!=inf:
      if d[v]>d[u]+M[u][v]:
        d[v] = d[u] + M[u][v]
        color[v] = 1
for i in range(n):
  if d[i]==inf:
    print '%d -1' % i
  else:
    print '%d %d' % (i, d[i])

### FIXED CODE ###

n = input()
inf = 1000000000
M = [[inf for i in range(n)] for i in range(n)]
for i in range(n):
  str = map(int, raw_input().split())
  u = str[0]
  k = str[1]
  for j in range(k):
    v = str[2+2*j]
    c = str[3+2*j]
    M[u][v] = c
d = [inf for i in range(n)]
color = [0 for i in range(n)]
 
d[0] = 0
color[0] = 1
 
while 1:
  minv = inf
  u = -1
  for i in range(n):
    if minv>d[i] and color[i]!=2:
      u = i
      minv = d[i]
  if u == -1:
    break
  color[u] = 2
  for v in range(n):
    if color[v]!=2 and M[u][v]!=inf:
      if d[v]>d[u]+M[u][v]:
        d[v] = d[u] + M[u][v]
        color[v] = 1
for i in range(n):
  if d[i]==inf:
    print '%d -1' % i
  else:
    print '%d %d' % (i, d[i])
s="abcdefghijklmnopqrstuvwxyz"
	m=""
	while n:		
		# print(r)
		if(n%26==0):
			m+='z'
		else:
			m+=s[(n%26)-1]
		n=(n//26)
	# reverse
	m=m[::-1]
	print(m)


### FIXED CODE ###

n=int(input())
s = ""
cons = 96

if n%26:
    s+=chr(cons + n%26)
else:
    n-=1
    s+="z"
n = n//26

while n:
    if n%26:
        s+=chr(cons + n%26)
    else:
        n-=1
        s+="z"
    n = n//26
    
print(s[::-1])
s=list(input())


c=[]
for i in range(3):
  
  if s[i]=='R':
    cnt=0
    
    while i<3:
      if s[i]=='R':
        cnt+=1
        i+=1
        
      else:
        break
        
    c.append(cnt)
    
print(max(c))
        
        

### FIXED CODE ###

s=list(input())


c=[]
for i in range(3):
  cnt=0
  if s[i]=='R':
    
    
    while i<3:
      if s[i]=='R':
        cnt+=1
        i+=1
        
      else:
        break
        
  c.append(cnt)
    
print(max(c))
import numpy as np
n,s=map(int,input().split())
t=np.zeros(s+1)
m=10**9+7
a=list(map(int,input().split()))
ans=0
for i in range(n):
    t[a[i]:]+=t[:-a[i]]
    if a[i]<=s:
        t[a[i]]+=i+1
    ans+=t[-1]
    ans%=m
print(int(ans))

### FIXED CODE ###

n,s=map(int,input().split())
t=[0]*(s+1)
m=998244353
a=list(map(int,input().split()))
ans=0
for i in range(n):
    d=t.copy()
    if a[i]<=s:
        for j in range(a[i],s+1):
            t[j]+=d[j-a[i]]
        t[a[i]]+=i+1
    ans+=t[-1]
    ans%=m
print(int(ans))
N = int(input())
a = list(map(int, input().split()))
res = 0
a.sort()
k = 0
for i in range(N-1):
    if a[i] != a[i+1]:
        count = i + 1 - k
        k = count 
        
        if count < a[i]:
            res += count
        else:
            res += count - a[i]
        
for i in range(a[-1]):
    if a[-1] != a[-i]:
        res += 1
        break
        
        
print(res)
  

### FIXED CODE ###

from collections import Counter
N = int(input())
a = list(map(int, input().split()))
L = list(set(a))
res = 0
d = Counter()
d.update(a)
for i in L:
    X = d[i]
    if X < i:
        res += X
    
    else:
        res += X - i

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

l, r = map(int, input().split())


def check(i, l, r):
    if i == m:
        return max(r - l + 1, 0)
    l_, r_ = map(int, input().split())
    nl = max(l, l_)
    nr = min(r, r_)
    i += 1
    return check(i, nl, nr)


print(check(1, l, r))

### FIXED CODE ###

n, m = map(int, input().split())
l, r = map(int, input().split())
li = []


for _ in range(m - 1):
    l_, r_ = map(int, input().split())
    l = max(l, l_)
    r = min(r, r_)


print(max(r - l + 1, 0))
from functools import reduce
from operator import mul

mod = 10**9 + 7

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

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

if N == K:
    print(reduce(mul, A)%mod)

else:

    AP = []
    AM = []
    for i in A:
        if i < 0:
            AM.append(i)
        else:
            AP.append(i)
            
    if len(AP) == 0 and K%2 != 0:
        AM.sort(reverse=True)
        AM = AM[:K]
        print(reduce(mul, AM)%mod)
    
    else:
        
        AP.sort(reverse=True)
        AM.sort()

        AP = AP[:K]
        AM = AM[:K]

        P = reduce(mul, AP)
        M = 1
        ans = P
        for i in range(0, len(AM)):
            if i < len(AP): 
                M *= AM[i]
                ans = max(ans, P*M/AP[-(i+1)])

        print(int(ans%mod))

### FIXED CODE ###

from bisect import bisect_left,bisect_right
p=10**9+7
n,k=map(int,input().split())
a=sorted(list(map(int,input().split())))
pi=1
ni=0
ans=1
i=0
while i<k-1:
  if a[ni]*a[ni+1]>a[-pi]*a[-pi-1]:
    ans=ans*a[ni]*a[ni+1]%p
    ni+=2
    i+=2
  else:
    ans=ans*a[-pi]%p
    pi+=1
    i+=1
if i==k-1:
  ans=ans*a[-pi]%p
if a[-1]<0 and k%2==1:
  ans=1
  for i in a[n-k:]:
    ans=ans*i%p
print(ans)