Harryxun/stf_run huggingface dataset:
import sys
import math
import collections
import bisect
import copy

# import numpy as np

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))


# ===CODE===


def main():
    n = ni()
    yes = dict()
    for i in range(3, 1000):
        if (i * (i - 1)) % 2 == 0:
            yes[(i * (i - 1)) // 2] = [i, i - 1]

    if n not in yes.keys():
        print("No")
        exit(0)

    xl, xs = yes[n]

    ans = [[] for _ in range(xl)]
    cnt = 1
    idx = 0
    prev = -1
    while cnt <= n and prev != cnt:
        prev = cnt
        for i in range(idx, idx + 3):
            for j in range(xs):
                if i == idx and j == 0:
                    ans[idx + 2].append(cnt)
                if i == idx + 2 and j == xs - 1:
                    continue
                ans[i].append(cnt)
                if j != 0 and j != xs - 1:
                    ans[idx + 2 + j].append(cnt)
                if j != xs - 1:
                    cnt += 1
        idx += 3
        xs -= 3
    print("Yes")
    print(len(ans))
    for ansi in ans:
        print(len(ansi), *ansi, sep=" ")


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import math
import collections
import bisect
import copy

# import numpy as np

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))


# ===CODE===


def main():
    n = ni()
    yes = dict()
    for i in range(3, 1000):
        if (i * (i - 1)) % 2 == 0:
            yes[(i * (i - 1)) // 2] = [i, i - 1]
    tmp = max(yes)

    if n == 1:
        print("Yes")
        print(2)
        print(1, 1)
        print(1, 1)
        exit(0)


    if n not in yes.keys():
        print("No")
        exit(0)

    xl, xs = yes[n]

    ans = [[] for _ in range(xl)]
    cnt = 1
    idx = 0
    while xs >= 0:
        tmp = cnt
        for i in range(idx, min(xl, idx + 3)):
            for j in range(xs):
                if cnt == tmp + 3 * (xs - 1):
                    ans[i].append(tmp)
                    break
                else:
                    ans[i].append(cnt)

                if j != 0 and j != xs - 1:
                    ans[idx + 2 + j].append(cnt)
                if j != xs - 1:
                    cnt += 1
        idx += 3
        xs -= 3

    print("Yes")
    print(len(ans))
    for ansi in ans:
        print(len(ansi), *ansi, sep=" ")


if __name__ == '__main__':
    main()
y,m,d=input().split()

heisei = False:
heisei = heisei or y < 2019:
heisei = heisei or y == 2019 and m < 4
heisei = heisei or y == 2019 and m == 4 and d <= 30:

print("Heisei" if heisei else "TBD")


### FIXED CODE ###


y,m,d=map(int, input().split('/'))


heisei = False
heisei = heisei or y < 2019
heisei = heisei or y == 2019 and m < 4
heisei = heisei or y == 2019 and m == 4 and d <= 30

print("Heisei" if heisei else "TBD")
while True
    x,y = (int,input().split)
    if x!=0 and y!=0:
        print(min([x,y]), max([x,y]))
    



### FIXED CODE ###

while True:
    x,y = map(int,input().split())
    if (x,y) == (0,0):
        break
    else:
        if x < y:
            print(x,y)
        else:
            print(y,x)
N = input()
ans = 0
for i in range(len(N)):
  ans += N[i]
print("Yes") if ans%9 == 0 else print("No")

### FIXED CODE ###

print("Yes") if int(input())%9 == 0 else print("No")
x = int(input())

for a in range(1, 1001001001):
    b = (x - a**5)
    if b != 0:
        if b > 0 and b ** 0.2 == int(b ** 0.2):
            print(a, int(b ** 0.2))
            break
        else:
            b = -1*b
            if b ** 0.2 == int(b ** 0.2):
                print(a, -1*int(b ** 0.2))
                break

### FIXED CODE ###

x = int(input())
for i in range(-120, 120):
    for j in range(-120, 120):
        if i ** 5 - j ** 5 == x:
            print(i, j)
            exit()
import numpy as np

h,w,k = map(int,input().split())
S = [list(input()) for _ in range(h)]

res = float('inf')
# bit全探索
for div in range(2**(h-1)):
    cut = []
    for i in range(h-1):
        if ((div >> i) & 1):
            cut.append(i+1)
    fr = 0
    part = []
    for i in range(len(cut)):
        to = cut[i]
        part.append(S[fr:to])
        fr = to
    else:
        part.append(S[fr:])
    comp_arr = []
    for p in part:
        p_ = np.array(p).astype(np.int)
        comp_arr.append(p_.sum(axis=0))
    comp_arr_T = np.array(comp_arr).T
    
    cnt = len(cut)

    tank = [0]*len(comp_arr)
    
    for m in range(w):
        for n in range(len(comp_arr)):
            tank[n] += comp_arr[n][m]

        if any([c>k for c in tank]):
            cnt += 1
            for n in range(len(comp_arr)):
                tank[n] = comp_arr[n][m]

    res = min(res, cnt)
print(res)

### FIXED CODE ###

h,w,k = map(int,input().split())
S = [list(map(int,list(input()))) for _ in range(h)]
ans = 10**9+7
for i in range(1 << (h-1)):
    group = [[0]*w]
    g_id = 0
    group[g_id] = [s+b for s, b in zip(S[0], group[0])]
    for j in range(1, h):
        if (i>>(j-1))&1:
            group.append([0]*w)
            g_id += 1
        group[g_id] = [s+b for s, b in zip(S[j], group[g_id])]
    if not all([all([i <= k for i in b]) for b in group]):
        continue
    cnt = len(group) - 1
    g_cnt = [0] * len(group)
    
    for jj in range(w):
        for g_id in range(len(group)):
            g_cnt[g_id] += group[g_id][jj]
        if any([c > k for c in g_cnt]):
            cnt  += 1
            for g_id in range(len(group)):
                g_cnt[g_id] = group[g_id][jj]
    ans = min(ans, cnt)
print(ans)
inputs = [int(input()) for i in range(2)]

print(max([sum(inputs), inputs[0]*2-1, inputs[1]*2-1]))

### FIXED CODE ###

inputs = list(map(int, input().split(" ")))
print(max([sum(inputs), inputs[0]*2-1, inputs[1]*2-1]))
n,d=map(int,input().split())
for i in range(n):
	a,b=map(int,input().split())
	if a*a+b*b<=d*d:ans+=1
print(ans)

### FIXED CODE ###

n,d=map(int,input().split())
ans=0
for i in range(n):
	a,b=map(int,input().split())
	if a*a+b*b<=d*d:ans+=1
print(ans)
n = int(input())

print(int((n/500))*1000 + int((n%500)/5))*5

### FIXED CODE ###

n = int(input())

print(int((n/500))*1000 + int((n%500)/5)*5)
next_weather = {'Sunny': 'Cloudy', 'Cloudy': 'Rainy', 'Rainy': 'Sunny'}
print(next_weahter[input()])

### FIXED CODE ###

next_weather = {'Sunny': 'Cloudy', 'Cloudy': 'Rainy', 'Rainy': 'Sunny'}
print(next_weather[input()])
N = int(input())
W = []
for i in range(N):
    tmp = input()
    if tmp in W and i != 0:
        print("No")
        exit()
    W.append(tmp)

last_word = W[0][-1]
for i in range(1, len(N)):
    if last_word != W[i][0]:
        print("No")
        exit()
print("Yes")


### FIXED CODE ###

N = int(input())
W = []
ans = True
for i in range(N):
    tmp = input()
    if tmp in W and i != 0:
        ans = False
    W.append(tmp)

if ans:
    last_word = W[0][-1]
    for i in range(1, N):
        if last_word != W[i][0]:
            ans = False
        last_word = W[i][-1]

print("Yes" if ans else "No")
import collections

n = int(input())
s = [input() for i in range(n)]
s = map(list,s)
lst = []
for i in s:
  i.sort()
  lst.append(''.join(i))
ans = collections.Counter(lst)
ctr = 0
for v in ans.items():
  if v != 1:
    ctr += v
print(ctr)

### FIXED CODE ###

import collections

n = int(input())
s = [input() for i in range(n)]
s = map(list,s)
lst = []
for i in s:
  i.sort()
  lst.append(''.join(i))
ans = collections.Counter(lst)
ctr = 0
for v in ans.values():
  if v != 1:
    for n in range(1,v):
      ctr+=n
      
print(ctr)
from math import factorial
MOD = 1_000_000_007

def calc_nCr(n, r):
    return (int(factorial(n) / (factorial(r) * factorial(n - r)))) % MOD
def count_patterns(stairs):
    if stairs == 0 or stairs == 1:
        return 1
    max_double_num = int(stairs/2)
    combs = [None]*(max_double_num+1)
    for i in range(max_double_num+1):
        double = i
        single = stairs - double*2
        n = double + single
        r = double
        nCr = calc_nCr(n, r)
        combs[i] = nCr
    return sum(combs) % MOD
  
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]

now = 0
total = 1

for broken in a:
    if broken <= now:
        print(0)
        break
    total = (total * count_patterns(broken-now-1)) % MOD
    now = broken + 1
else:
    total = (total * count_patterns(N-now)) % MOD
    print(total)


### FIXED CODE ###

def main():
    MOD = 1000000007
    N, M = map(int, input().split())
    a = [int(input()) for _ in range(M)]
    table = [1]*(N+1)
    for broken in a:
        table[broken] = 0
    table[1] = table[0] * table[1]
    if N > 1:
        for n in range(2, N+1):
            table[n] = ((table[n-2] + table[n-1]) * table[n]) % MOD
    print(table[-1])
main()
N, M = map(int, input().split())
S = [0]*M
C = [0]*M
SC = {}
for i in range(N):
    SC[i+1] = set()
for m in range(M):
    S[m], C[m] = map(int, input().split())
    SC[S[m]].add(C[m])

ANS = [0]*N
out = 0
for i in range(1, 4):
    if len(SC[i]) >= 2:
        out = 1
if out == 1:
    print(-1)

else:
    if N == 1:
        if len(SC[1]) == 0:
            ANS[0] = 0
        else:
            ANS[0] = list(SC[1])[0]

    else:
        for i in range(N):
            if i == 0:
                if list(SC[i+1])[0] == 0:
                    out = 1
                elif len(SC[i+1]) == 0:
                    ANS[0] = 1
                else:
                    ANS[0] = list(SC[i+1])[0]
            else:
                if len(SC[i+1]) == 0:
                    ANS[i] = 0
                else:
                    ANS[i] = list(SC[i+1])[0]
    if out == 1:
        print(-1)
    else:
        ans = 0
        for i in range(N):
            ans += ANS[i]*10**(N-i-1)
        print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
S = [0]*M
C = [0]*M
SC = {}
SC = {1: set([]), 2: set([]), 3: set([])}
for m in range(M):
    S[m], C[m] = map(int, input().split())
    SC[S[m]].add(C[m])

ANS = [0]*N
out = 0
for i in range(1, 4):
    if len(SC[i]) >= 2:
        out = 1
if out == 1:
    print(-1)

else:
    out = 0
    if N == 1:
        if len(SC[1]) == 0:
            ANS[0] = 0
        else:
            ANS[0] = list(SC[1])[0]

    else:
        for i in range(N):
            if i == 0:
                if len(SC[i+1]) == 0:
                    ANS[0] = 1
                elif list(SC[i+1])[0] == 0:
                    out = 1
                else:
                    ANS[0] = list(SC[i+1])[0]
            else:
                if len(SC[i+1]) == 0:
                    ANS[i] = 0
                else:
                    ANS[i] = list(SC[i+1])[0]
    if out == 1:
        print(-1)
    else:
        ans = 0
        for i in range(N):
            ans += ANS[i]*10**(N-i-1)
        print(ans)
import sys, ast

def dfs(str_input,count = 1):
    if count == 7:
        if ast.literal_eval(str_input) == 7:
            sys.exit(str_input + "=7")
        else:
            return 0
    for i in ["+","-"]:
        dfs(str_input[:count] + i + str_input[count:], count = count + 2)

x = input()

dfs(x)

### FIXED CODE ###

import sys, ast

def dfs(str_input,count = 1):
    if count == 7:
        if ast.literal_eval(str_input) == 7:
            print(str_input + "=7")
            sys.exit(0)
        else:
            return 0
    for i in ["+","-"]:
        dfs(str_input[:count] + i + str_input[count:], count = count + 2)

x = input()

dfs(x)
def gcd(a, b):
	"""Compute the greatest common divisor of a and b"""
	while b > 0:
		a, b = b, a % b
	return a

def lcm(a, b):
	"""Compute the lowest common multiple of a and b"""
	return a * b / gcd(a, b)

def resolve():
	n = int(input())
	T = []
	for _ in range(n):
		T.append(int(input()))
	ans = 1
	for i in range(n):
		ans = lcm(ans, T[i])
	print(int(ans))
resolve()

### FIXED CODE ###

def gcd(a, b):
	"""Compute the greatest common divisor of a and b"""
	while b > 0:
		a, b = b, a % b
	return a

def lcm(a, b):
	"""Compute the lowest common multiple of a and b"""
	return a * b // gcd(a, b)

def resolve():
	n = int(input())
	T = []
	for _ in range(n):
		T.append(int(input()))
	ans = 1
	for i in range(n):
		ans = lcm(ans, T[i])
	print(int(ans))
resolve()
S = int(input())

flag = False
ans = 0
for i in range(len(S)):
    if S[i] == 'R':
        ans += 1
        flag = True
    elif S[i] == 'S' and flag:
        break

print(ans)


### FIXED CODE ###

S = input()

flag = False
ans = 0
for i in range(len(S)):
    if S[i] == 'R':
        ans += 1
        flag = True
    elif S[i] == 'S' and flag:
        break

print(ans)
N, K = map(int, input().split())
def calc_ans(ans):
    x = 0
    tmp = 0
    for i in range(K):
      tmp += ans[i][0]
      x += ans[i][1]
    return tmp + (x * x)
 
L = [list(map(int, input().split())) for i in range(N)]
L.sort(key=lambda x:x[1], reverse=True)
ans = []
etc = []
dic = {}
ind = {}
for l in L:
    if dic.get(l[0]):
        dic[l[0]].append(l[1])
    else:
        dic[l[0]] = [l[1]]
    if len(dic.keys()) > K:
        break
for t in dic.keys():
    dic[t].sort(reverse=True)
    for i,n in enumerate(dic[t]):
      if i == 0:
          ans.append((n, 1))
      else:
          etc.append((n, 0))
ans_all = calc_ans(ans)
ans.sort(reverse=True)
etc.sort(reverse=True)
for n in etc:
    if ans[-1][1] == 0 and ans[-1][0] >= n[0]:
        break
    ans[-1] = n
    tmp = calc_ans(ans)
    if ans_all < tmp:
        ans_all = tmp
    ans.sort(reverse=True)
print(ans_all)

### FIXED CODE ###

N,K = map(int,input().split())
td = [[int(i) for i in input().split()] for _ in range(N)]
td.sort(key=lambda x:x[1],reverse=True)
ans = 0
ls = set()
dl = []
for i in range(K):
    ans += td[i][1]
    if not td[i][0] in ls:
        ls.add(td[i][0])
    else:
        dl.append(td[i][1])
ans = ans + len(ls)**2
res = ans
for i in range(K,N):
    if not dl:
        break
    if td[i][0] in ls:
        continue
    ans += len(ls)*2+1
    ans += td[i][1]
    ans -= dl[-1]
    del dl[-1]
    res = max(res,ans)
    ls.add(td[i][0])
print(res)
a,b = map(str,input().split())
b.replace(".")
print(a*b//100)

### FIXED CODE ###

a,b=map(str,input().split())
a = int(a)
b = list(b)
del b[1]
b = int(''.join(b))
print(a*b//100)
def factor(x):
  factor=[]
  if x==1:
    return
  else:
    i=2
    while x>1:
      if x%i==0:
        factor.append([i,1])
        x/=i
        while x%i==0:
          factor[-1][1]+=1
          x/=i
      i+=1
    return factor

m,n=(int(i) for i in input().split(' '))
factor=factor(m)
ans=1
for data in factor:
  data[1]=data[1]//n
  ans=ans*(data[0]**data[1])
print(ans)

### FIXED CODE ###

N = int(input())
if N == 1:
    print('Hello World')
elif N == 2:
    A = int(input(''))
    B = int(input(''))
    print(A + B)
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

# def conb(n,r): 
#     return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
from scipy.special import comb
x,y = inpl()
x,y = max(x,y),min(x,y)
if (x+y)%3 or y*2 < x:
    print(0)
    quit()
n = (x+y)//3 + 1
k = x-n+2


def cmd(n,r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

a = cmd(n-1,k-1)%mod
print(a)


### FIXED CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

# def conb(n,r): 
#     return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

x,y = inpl()
x,y = max(x,y),min(x,y)
if (x+y)%3 or y*2 < x:
    print(0)
    quit()
n = (x+y)//3 + 1
k = x-n+2


def cmd(n,r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

a = cmd(n-1,k-1)%mod
print(a)
x, y, z = input().split(" ")
print( f"{z} {x} {y}")

### FIXED CODE ###

x, y, z = input().split(" ")
print("{} {} {}".format(z,x,y))
def resolve():
    a = list(int(input()) for _ in range(5))
    mint = 1000
    ans = 0
    for i in range(5):
        ans += math.ceil(a[i]/10)*10
        if a[i]%10 == 0: continue
        mint = min(mint,a[i]%10)
    print(ans+mint-10)

resolve()

### FIXED CODE ###

import math
def resolve():
    a = list(int(input()) for _ in range(5))
    mint = 1000
    ans = 0
    for i in range(5):
        ans += math.ceil(a[i]/10)*10
        if a[i]%10 == 0: continue
        mint = min(mint,a[i]%10)
    if mint == 1000:
        print(ans)
    else:
        print(ans+mint-10)
resolve()
def gho1(x):
  g=1
  for i in range(1,x+1):
    g*=i
  return g
def gho2(x):
  g=1
  for i in range(1,x+1):
    g*=i;g=g%(10**9+7)
  return g

q,w=map(int,input().split())
e,d=divmod((2*w-q),3)
r,f=divmod((2*q-w),3)

if d!=0 or f!=0:print(0)
else:
  print((gho(e+r)//(gho(e)*gho(r)))%(10*9+7))


### FIXED CODE ###

x,y=map(int,input().split());n=0;mod=10**9+7;ans=0
if not (x+y)%3:
  n=(x+y)//3;x-=n;y-=n
  if x>=0 and y>=0:
    ans=1
    for i in range(x):ans=ans*(n-i)*pow(i+1,mod-2,mod)%mod
print(ans)
A.sort()
n = N//2
if N%2 != 0:
    ans1,ans2,ans = 0,0,0
    ar1,ar2 = A[:n],A[n+1:]
    ar = []
    for i in range(n):
        ar.append(ar2[i])
        ar.append(ar1[i])
    ar.append(A[n])
    for i in range(N-1):
        ans1 += abs(ar[i]-ar[i+1])
    ar = [A[n]]+ar[:-1]
    for i in range(N-1):
        ans2 += abs(ar[i]-ar[i+1])
    ans = max(ans1,ans2)
else:
    ans = 0
    ar1,ar2 = A[:n],A[n:]
    ar = []
    for i in range(n):
        ar.append(ar2[i])
        ar.append(ar1[i])
    for i in range(N-1):
        ans += abs(ar[i]-ar[i+1])
 
print(ans)

### FIXED CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]

A.sort()
n = N//2
if N%2 != 0:
    ans1,ans2,ans = 0,0,0
    ar1,ar2 = A[:n],A[n+1:]
    ar = []
    for i in range(n):
        ar.append(ar2[i])
        ar.append(ar1[i])
    ar.append(A[n])
    for i in range(N-1):
        ans1 += abs(ar[i]-ar[i+1])
    ar = [A[n]]+ar[:-1]
    for i in range(N-1):
        ans2 += abs(ar[i]-ar[i+1])
    ans = max(ans1,ans2)
else:
    ans = 0
    ar1,ar2 = A[:n],A[n:]
    ar = []
    for i in range(n):
        ar.append(ar2[i])
        ar.append(ar1[i])
    for i in range(N-1):
        ans += abs(ar[i]-ar[i+1])
 
print(ans)
N = int(raw_input())
a = raw_input()
aa = a.split(" ")
aaa = []
for i in range(len(aa)):
	aaa.append((i+1,int(aa[i])))

ctr = 0

for (x,y) in aaa:
	if (y,x) in aaa:
		ctr = ctr + 1
		aaa.remove( (y,x) )
print(str(ctr))

### FIXED CODE ###

s = raw_input()
s2 = s[:4] + " " + s[4:]
print(s2)
a, b = map(int, input().split())
    c = a * b
    if (c % 2 == 0):
        print("Even")
    else:
        print("Odd")

### FIXED CODE ###

a, b = map(int, input().split())
c = a * b
if (c % 2 == 0):
    print("Even")
else:
    print("Odd")
MOD = 10**9+7

n, k = [int(_) for _ in input().split()]

a = [int(_) for _ in input().split()]

m = list(filter(lambda x: x < 0, a))
p = list(filter(lambda x: x > 0, a))

m.sort()
p.sort(reverse=True)


if len(p)+len(m) < k:
    print(0)
    exit()
if len(p) == 0:
    ans = 1
    for i in range(k):
        ans = (ans*m[-i-1]) % MOD
    print(ans)
    exit()


i, j = 0, 0

m.append(0)
m.append(0)
p.append(0)
p.append(0)
ans = 1
for c in range(k//2):
    # print(i, j)
    if m[i]*m[i+1] >= p[j]*p[j+1]:
        ans = (ans*m[i]*m[i+1]) % MOD
        i += 2
    else:
        ans = (ans*p[j]*p[j+1]) % MOD

        j += 2
if k % 2 == 1:
    ans = (ans*p[i]) % MOD
print(ans)


### FIXED CODE ###

MOD = 10**9+7

n, k = [int(_) for _ in input().split()]

a = [int(_) for _ in input().split()]

m = list(filter(lambda x: x < 0, a))
p = list(filter(lambda x: x > 0, a))

m.sort()
p.sort(reverse=True)


if len(p)+len(m) < k:
    print(0)
    exit()
if len(p)+len(m) == k:
    ans = 1
    for p_ in p:
        ans = (ans*p_) % MOD
    for q_ in m:
        ans = (ans*q_) % MOD
    print(ans)
    exit()

if len(p) == 0 and k % 2 == 1:
    ans = 1
    for i in range(k):
        ans = (ans*m[-i-1]) % MOD
    if 0 in a:
        ans *= 0
    print(ans)
    exit()

i, j = 0, 0
if k % 2 == 1:
    d = p.pop(-1)
m.append(0)
m.append(0)
p.append(0)
p.append(0)
# print(p, m)
ans = 1
for c in range(k//2):
    # print(i, j)
    if m[i]*m[i+1] >= p[j]*p[j+1]:
        ans = (ans*m[i]*m[i+1]) % MOD
        i += 2
    else:
        ans = (ans*p[j]*p[j+1]) % MOD
        j += 2

if k % 2 == 1:
    ans = (ans*max(p[j], d)) % MOD


if ans > MOD:
    ans -= MOD
print(ans)
while True:
    try:
        s=raw_input().rstrip().split()
    except EOFError:
        break
    L=[]
    for d in s:
        if d.isdigit():
            L.append(float(d))
        else:
            op1=L.pop()
            op2=L.pop()
            if d=="-":
                L.append(op2-op1)
            elif d=="+":
                L.append(op2+op1)
            elif d=="*":
                L.append(op2*op1)
            else:
                L.append(op2/op1)
    print L[0]

### FIXED CODE ###

import sys
for s in sys.stdin.readlines():
    L=[]
    for d in s.strip().split():
        if d=="-":
            d=(-(L.pop()-L.pop()))
        elif d=="+":
            d=(L.pop()+L.pop())
        elif d=="*":
            d=(L.pop()*L.pop())
        elif d=="/":
            d=(1/L.pop()*L.pop())
        L.append(float(d))
    print "%.6f"%L[0]
import string

count = {x: 0 for x in string.ascii_lowercase}
lines = ""

while True:
    try:
        lines += input().lower()
    except EOFError:
        break

for c in lines:
    if 'a' <= c <= 'z':
        count[c] += 1

for key,in string.asciilowercase:
    print("{0} : {1}".format(key, count[key]))

### FIXED CODE ###

import string
   
count = {x: 0 for x in string.ascii_lowercase}
lines = ""
   
while True:
    try:
        lines += input().lower()
    except EOFError:
        break
           
for c in lines:
    if 'a' <= c <= 'z':
        count[c] += 1
           
for key in string.ascii_lowercase:
    print("{0} : {1}".format(key, count[key]))
import math
def lcm(x, y):
    return (x * y) // math.gcd(x, y)
a, b, c, d = map(int, input().split())
print(b-(a-1) - b//c + (a-1)//c - b//d + (a-1)//d + b//lcm(c,d) + (a-1)//lcm(c, d))

### FIXED CODE ###

from fractions import gcd
def lcm(x, y):
    return (x * y) // gcd(x, y)
a, b, c, d = map(int, input().split())
print(b-(a-1) - b//c + (a-1)//c - b//d + (a-1)//d + b//lcm(c, d) - (a-1)//lcm(c, d))
S = input()
 print('Heisei' if S <= '2019/04/30' else 'TBD')

### FIXED CODE ###

S = input()
print('Heisei' if S <= '2019/04/30' else 'TBD')