Harryxun/stf_run huggingface dataset:
from math import gcd
n =int(input())
a =list(map(int ,input().split()))

b =[a[0]]
for i in range(1,n-1):
    b.append(gcd(b[-1],a[i]))

c =[a[-1]]
for i in range(n-2,0,-1):
    c.append(gcd(c[-1], a[i]))

MAX =0
for i in range(n):
    if i == 0:
        MAX =max(MAX, c[-1])
    elif i ==n-1:
        MAX =max(MAX, b[-1])
    else:
        MAX =max(MAX, gcd(b[i-1], c[n-i-2]))
print(MAX)

### FIXED CODE ###

from fractions import gcd
n =int(input())
a =list(map(int ,input().split()))

b =[a[0]]
for i in range(1,n-1):
    b.append(gcd(b[-1],a[i]))

c =[a[-1]]
for i in range(n-2,0,-1):
    c.append(gcd(c[-1], a[i]))

MAX =0
for i in range(n):
    if i == 0:
        MAX =max(MAX, c[-1])
    elif i ==n-1:
        MAX =max(MAX, b[-1])
    else:
        MAX =max(MAX, gcd(b[i-1], c[n-i-2]))
print(MAX)
n = input()
N = input().split()
sum = 0
for i in range (n):
  sum += N[i]

print "%d %d %d" %(min(N), max(N), sum)
    

### FIXED CODE ###

n = input()
N = map(int,raw_input().split())
sum = 0
for i in range (n):
  sum += N[i]

print "%d %d %d" %(min(N), max(N), sum)
a=int(input())
b=2*3.14.a
print(b)

### FIXED CODE ###

a=int(input())
print(2*3.14*a)
from collections import Counter
N = int(input())
A = list(map(int,input().split()))
ac = Counter(A)
comblist = [0 for i in range(max(ac.values())+1)]
comblist[2] = 1
for i in range(3,max(4,max(ac.values())+1)):
    comblist[i] = comblist[i-1]*i//(i-2)
ans = {}
anssum = 0
for k,v in ac.items():
    if v > 1:
        anssum += comblist[v]
    if k not in ans:
        if v == 2:
            ans[k] = -1
        elif v == 1:
            ans[k] = 0
        else:
            ans[k] = comblist[v-1] - comblist[v]
for i in A:
    print(anssum+ans[i])

### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int,input().split()))
ac = Counter(A)
comblist = [0 for i in range(max(ac.values())+1)]
if max(ac.values()) == 1:
    for i in range(N):
        print(0)
else:
    comblist[2] = 1
    for i in range(3,max(4,max(ac.values())+1)):
        comblist[i] = comblist[i-1]*i//(i-2)
    ans = {}
    anssum = 0
    for k,v in ac.items():
        if v > 1:
            anssum += comblist[v]
        if k not in ans:
            if v == 2:
                ans[k] = -1
            elif v == 1:
                ans[k] = 0
            else:
                ans[k] = comblist[v-1] - comblist[v]
    for i in A:
        print(anssum+ans[i])
N,Q = map(int,input().split())
S = input()


def fnc(l,r):
    cnt = 0
    for i in range(l-1,r):
        if S[i] == "A" and S[i+1] == "C" and i != r-1:
            cnt += 1
    print(cnt)
    
for i in range(Q):
    L,R = map(int,input().split())
    fnc(L,R)
            

### FIXED CODE ###

N,Q = map(int,input().split())
S = input()
t = [0]*(N+1)

for i in range(N):
    t[i+1] = t[i] + (1 if S[i:i+2]=="AC" else 0)

for i in range(Q):
    r,l = map(int,input().split())
    print(t[l-1]-t[r-1])
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
div = 10**9 + 7
if N % 2 == 0:
    if A.count(0) != 0:
        print(0)
    else:
        A = dict(Counter(A))
        val = A.values()
        val = list(filter(lambda x: x == 2, val))
        if len(val) * 2 == N:
            print(int(2**(N/2) % div))
        else:
            print(0)

else:
    if A.count(0) != 1:
        print(0)
    else:
        A.remove(0)
        A = dict(Counter(A))
        val = A.values()
        val = list(filter(lambda x: x == 2, val))
        if len(val) * 2 == (N-1):
            print(int(2 ** ((N-1) / 2) % div))
        else:
            print(0)



### FIXED CODE ###

from collections import Counter
N = int(input())
A = sorted(list(map(int, input().split())))
div = 10 ** 9 + 7
if N % 2 == 0:
    B = [i for i in range(1, N, 2)]
    B.extend(B)
    B.sort()
    if A == B:
        print(2**(int(N/2)) % div)
    else:
        print(0)

else:
    B = [i for i in range(2, N, 2)]
    B.extend(B)
    B.append(0)
    B.sort()
    if A == B:
        print(2**(int(N/2)) % div)
    else:
        print(0)
a=[]
while True:
    try:
	h = float(row_input())
	a.append(h)
    except:
	break
a.sort()
print a[len(a)-1] - a[0]

### FIXED CODE ###

a=[]
while True:
    try:
        a.append(float(raw_input()))
    except:
        break

a.sort()
print a[len(a)-1] - a[0]
n = int(input())
a = list(map(int,input().split()))
res = 0

for i in range(n):
  sel = a[i]
  if a[sel] == i:
    res += 1
else:
  print(res/2)

### FIXED CODE ###

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

for i in range(n):
  sel = a[i] -1
  if a[sel] == i+1:
    res += 1
else:
  print(int(res/2))
#!/usr/bin/env python3
import sys


def solve(N: int, K: int, S: int):
    if K==0:
        if S>N:
            ans=[0]*N
        else:
            ans=[N+1]*N
    elif K==N:
        ans=[S]*N

    else:
        for i in range(N):
            yok=0
            if i<K:
                ans[i]=S
            else:
                ans[i]=1
                yok+=1
    
        ans[K-1]-=yok
    
    for i in range(N):
        print(ans[i],end=" ")

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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
    K = int(next(tokens))  # type: int
    S = int(next(tokens))  # type: int
    solve(N, K, S)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, K: int, S: int):
    ans=[-1]*N
    yok=0
    for i in range(N):
        if i<K:
            ans[i]=S
        else:
            if S>N:
                ans[i]=1
                yok+=1
            else:
                ans[i]=10**9
    
    for i in range(N):
        print(ans[i],end=" ")

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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
    K = int(next(tokens))  # type: int
    S = int(next(tokens))  # type: int
    solve(N, K, S)

if __name__ == '__main__':
    main()
def modinv(a,m):
    b, u, v = m, 1, 0
    while b:
        t = a//b
        a -= t*b
        a,b = b,a
        u -= t * v
        u,v = v,u
    u %= m
    return u

s=input()
all_hatena = s.count('?')

a_cnt = 0
ab_cnt = 0
hatena_cnt = 0
ans = 0

MOD = 10**9+7
for si in s:
    if si == 'A':
        a_cnt += 1
    elif si == 'B':
        ab_cnt += a_cnt*pow(3,all_hatena,MOD)
        ab_cnt += hatena_cnt*pow(3,all_hatena-1,MOD)
    elif si == 'C':
        ans += ab_cnt
    else:
        ans += ab_cnt*modinv(3,MOD)
        ab_cnt += a_cnt*pow(3,all_hatena-1,MOD)
        ab_cnt += hatena_cnt*pow(3,all_hatena-2,MOD)
        hatena_cnt += 1
    ab_cnt%=MOD
    ans%=MOD
    # print(a_cnt,ab_cnt,ans)
print(ans)

### FIXED CODE ###

def modinv(a,m):
    b, u, v = m, 1, 0
    while b:
        t = a//b
        a -= t*b
        a,b = b,a
        u -= t * v
        u,v = v,u
    u %= m
    return u

s=input()
all_hatena = s.count('?')

a_cnt = 0
ab_cnt = 0
hatena_cnt = 0
ans = 0

MOD = 10**9+7
for si in s:
    if si == 'A':
        a_cnt += 1
    elif si == 'B':
        ab_cnt += a_cnt*pow(3,all_hatena,MOD)
        if all_hatena >= 1:
            ab_cnt += hatena_cnt*pow(3,all_hatena-1,MOD)
    elif si == 'C':
        ans += ab_cnt
    else:
        ans += ab_cnt*modinv(3,MOD)
        ab_cnt += a_cnt*pow(3,all_hatena-1,MOD)
        if all_hatena >= 2:
            ab_cnt += hatena_cnt*pow(3,all_hatena-2,MOD)
        hatena_cnt += 1
    ab_cnt%=MOD
    ans%=MOD
    # print(a_cnt,ab_cnt,ans)
print(ans)
s = list(input())
t = list(input())
s.sort()
t.sort()

r = len(s) if len(s) < len(t) else len(t)
for i in range(0, r-1):
    if s.pop(i) == t.pop(i):
        continue
    elif s.pop(i) < t.pop(i):
        print("Yes")
        exit()
    else:
        print("No")
        exit()
print("Yes") if len(s) < len(t) else print("No")


### FIXED CODE ###

s = list(input())
t = list(input())
s.sort()
t.sort()
t.reverse()
print("Yes") if s < t else print("No")
# -*- coding: utf-8 -*-
# 天気の入力
s = int(input())
# 出力
lis = ['Sunny', 'Cloudy', 'Rainy']
index = lis.index(s)
index = (index+1)%len(lis)
print(lis[index])

### FIXED CODE ###

# -*- coding: utf-8 -*-
# 天気の入力
s = (input())
# 出力
lis = ['Sunny', 'Cloudy', 'Rainy']
index = lis.index(s)
index = (index+1)%len(lis)
print(lis[index])
t = input().split()
  if t[0]＊t[1] % 2 == 0:
    print("No")
  else:
    print("Yes")

### FIXED CODE ###

s, t = map(int, input().split())
if s * t % 2 == 0:
  print("No")
else:
  print("Yes")
from itertools import takewhile
(lambda *_: None)(*map(print,
                       map(eval,
                           map(lambda s: s.replace('/', '//'),
                               takewhile(lambda s: '?' not in s,
                                         iter(input))))))

### FIXED CODE ###

from __future__ import division, print_function
from sys import stdin, exit
from operator import add, sub, mul, floordiv
d = {'+': add, '-': sub, '*': mul, '/': floordiv, '?': lambda a,b: exit(0)}
while True:
    a, op, b = stdin.readline().split()
    print(d[op](int(a), int(b)))
n=int(input())
H=list(map(int,input().split()))
dp=[10**9]*(n)
dp[0]=0
for i in range(n):
    if i==1:
        dp[i]=min(dp[i],dp[i-1]+abs(H[i]-H[i-1]))
    elif i>1:
        dp[i]=min(dp[i],dp[i-1]+abs(H[i]-H[i-1]),dp[i-2]+abs(H[i]-H[i-2]))

print(dp[n]) 

### FIXED CODE ###

n=int(input())
H=list(map(int,input().split()))
dp=[10**9]*(n)
dp[0]=0
for i in range(n):
    if i==1:
        dp[i]=min(dp[i],dp[i-1]+abs(H[i]-H[i-1]))
    elif i>1:
        dp[i]=min(dp[i],dp[i-1]+abs(H[i]-H[i-1]),dp[i-2]+abs(H[i]-H[i-2]))

print(dp[-1])
S = input()
if(S="ABC"):
    print("ARC")
else:
    print("ABC")

### FIXED CODE ###

S = input()
if(S=="ABC"):
    print("ARC")
else:
    print("ABC")
import sys
input = sys.stdin.readline

N,M = map(int,input().split())
mod = 998244353

FACT=[1]
for i in range(1,2*10**6+1):
    FACT.append(FACT[-1]*i%mod)

FACT_INV=[pow(FACT[-1],mod-2,mod)]
for i in range(2*10**6,0,-1):
    FACT_INV.append(FACT_INV[-1]*i%mod)

FACT_INV.reverse()

def Combi(a,b):
    if 0<=b<=a:
        return FACT[a]*FACT_INV[b]*FACT_INV[a-b]%mod
    else:
        return 0


ANS=Combi(M*3+N-1,N-1)

for i in range(M*2+1,M*3+1):
    k=M*3-i
    ANS=(ANS-N*Combi(k+(N-1)-1,N-2))%mod


for i in range(M+1,N+1):
    if (M*3-i)%2==1:
        continue
    k=(M*3-i)//2
    ANS=(ANS-Combi(N,i)*Combi(k+N-1,N-1))%mod

print(ANS)



### FIXED CODE ###

import sys
input = sys.stdin.readline

N,M = map(int,input().split())
mod = 998244353

FACT=[1]
for i in range(1,4*10**6+1):
    FACT.append(FACT[-1]*i%mod)

FACT_INV=[pow(FACT[-1],mod-2,mod)]
for i in range(4*10**6,0,-1):
    FACT_INV.append(FACT_INV[-1]*i%mod)

FACT_INV.reverse()

def Combi(a,b):
    if 0<=b<=a:
        return FACT[a]*FACT_INV[b]*FACT_INV[a-b]%mod
    else:
        return 0


ANS=Combi(M*3+N-1,N-1)

for i in range(M*2+1,M*3+1):
    k=M*3-i
    ANS=(ANS-N*Combi(k+(N-1)-1,N-2))%mod


for i in range(M+1,N+1):
    if (M*3-i)%2==1:
        continue
    k=(M*3-i)//2
    ANS=(ANS-Combi(N,i)*Combi(k+N-1,N-1))%mod

print(ANS)
#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int


def solve(N: int, A: "List[int]"):
    from functools import reduce
    xyz_list = [[0]*3]
    for a in A:
        xyz_list.append(xyz_list[-1][:])
        xyz_list[-1][xyz_list[-1].index(a)] += 1
    T = [xyz.count(a) for xyz, a in zip(xyz_list, A)]
    return reduce(lambda a,b: a*b%MOD, T)

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
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
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    print(solve(N, A))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int


def solve(N: int, A: "List[int]"):
    from functools import reduce
    xyz_list = [[0]*3]
    for a in A:
        xyz_list.append(xyz_list[-1][:])
        for i, v in enumerate(xyz_list[-1]):
            if v == a:
                xyz_list[-1][i] += 1
                break
    T = [xyz.count(a) for xyz, a in zip(xyz_list, A)]
    return reduce(lambda a,b: a*b%MOD, T)

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
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
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    print(solve(N, A))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()
from collections import Counter
N = int(input())
A = list(map(int,input().split()))
count = Counter(A)
sides = [k for k, v in count.items() if v >= 2]
sides.sort(reverse = True)
print(sides[0] * sides[1])

### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int,input().split()))
count = Counter(A)
keys = list(count.keys())
keys.sort(reverse = True)
a = 0
b = 0
for k in keys:
    if a == 0:
        if count[k] >= 4:
            a = b = k
            break
        elif count[k] >= 2:
            a = k
    else:
        if count[k] >= 2:
            b = k
            break
print(a * b)
x, y = map(int, input().split())

d = {1:300000, 2:200000, 3:100000}

if x == 1 and y == 1:
	print(10**6)
	exit()

su = 0
if x in d:
	su += d[x]
if y in d:
	su += d[x]
print(su)




### FIXED CODE ###

x, y = map(int, input().split())

d = {1:300000, 2:200000, 3:100000}

if x == 1 and y == 1:
	print(10**6)
	exit()

su = 0
if x in d:
	su += d[x]
if y in d:
	su += d[y]
print(su)
from collections import deque

def cndP(w):
    if len(w)>1:
        x = w.pop()
        cndP(w.copy())
        w.append(x)
        s = 0
        while(len(w)>0):
            s += w.pop()
            st.add(s)
    else:
        st.add(w[0])
        
def pIsAccptbl(w,k,p):
    tr = 0
    c = 0
    d = w.copy()
    while(d):
        tmp = d.popleft()
        if(tmp > p):
            return False
        
        if( tr + tmp > p):
            tr = tmp
            c += 1
        else:
            tr += tmp
        if c+1>k:
            return False
    return True

n,k = [int(x) for x in input().split()]
w = deque()

for i in range(n):
    w.append(int(input()))
    
st = set()
from collections import deque

def cndP(w):
    if len(w)>1:
        x = w.pop()
        cndP(w.copy())
        w.append(x)
        s = 0
        while(len(w)>0):
            s += w.pop()
            st.add(s)
    else:
        st.add(w[0])
        
def pIsAccptbl(w,k,p):
    tr = 0
    c = 0
    d = w.copy()
    while(d):
        tmp = d.popleft()
        if(tmp > p):
            return False
        
        if( tr + tmp > p):
            tr = tmp
            c += 1
        else:
            tr += tmp
        if c+1>k:
            return False
    return True

n,k = [int(x) for x in input().split()]
w = deque()

for i in range(n):
    w.append(int(input()))
    
st = set()
cndP(w.copy())

### FIXED CODE ###

from collections import deque

def isPa(w,k,p):
    tr = 0
    c = 0
    d = deque(w)
    while(d):
        tmp = d.popleft()
        if(tmp > p):
            return False
        
        if( tr + tmp > p):
            tr = tmp
            c += 1
        else:
            tr += tmp
        if c+1>k:
            return False
    return True

def MaxInP(w,k,p):
    maxinp = 0
    tmp = 0
    d = deque(w)
    while(d):
        tmp += d.popleft();
        if(tmp > p):
            if(tmp > maxinp):
                maxinp = tmp
            tmp = 0
    return maxinp

n,k = [int(x) for x in input().split()]
w = deque()
for i in range(n):
    w.append(int(input()))
    
mean = int(sum(w)/k)
maxinp = MaxInP(w,k,mean)

if k == 1:
    print(mean)
else:
    minP = mean
    maxP = maxinp
    while(True):
        m = int ((minP + maxP)/2)
        if ( isPa(w,k,m) ):
            maxP = m
        else:
            minP = m
        if (minP+1 == maxP or minP == maxP):
            print(maxP)
            break
N=input()
if N%2==0:
  print("N/2")
else:
  print("N/2+1")

### FIXED CODE ###

n = int(input())
if n % 2:
    print(n // 2 + 1)
else:
    print(n // 2)
n, r  = map(int, input().split())
if n >=10:
	print(r)
else:
	print(r-1000+100n)

### FIXED CODE ###

n, r  = map(int, input().split())
if n >=10:
	print(r)
else:
	print(r+1000-100*n)
A, B, C = int(input().split())


ans = max(A*10 + B + C, B*10 + A + C, C*10 + A + B)
print(ans)

### FIXED CODE ###

A, B, C = map(int, input().split())


ans = max(A*10 + B + C, B*10 + A + C, C*10 + A + B)
print(ans)
n, w = map(int, input().split())

dp = [0]*(w+1)

for _ in range(n):
  wei, v = map(int, input().split())
  dp_1 = dp[:]
  for j in range(w + 1):
    if j - wei >= 0:
      dp[j] = dp_1[j-wei] + v if (dp_1[j-wei] + v) > dp_1[j] else dp[j]
  
print(dp[w])

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    n, w_max = map(int, input().split())
    items = [tuple(map(int, input().split())) for _ in range(n)]
    inf = float('inf')
    dp = [[inf] * 100001 for _ in range(n + 1)]
    dp[0][0] = 0
    for i1 in range(1, n + 1):
        w, v = items[i1 - 1][0], items[i1 - 1][1]
        for col in range(1, 100001):
            if v >= col:
                tmp1 = w
            else:
                tmp1 = dp[i1 - 1][col - v] + w
            dp[i1][col] = min(dp[i1 - 1][col], tmp1)
    for i2 in range(100000, 0, -1):
        if dp[-1][i2] <= w_max:
            print(i2)
            sys.exit()

if __name__ == '__main__':
    main()
import typing 
import sys

def dp(costs: typing.List[int]) -> int:
    table = [0]
    for i in range(1, len(costs)):
        if i == 1:
            table.append(table[0] + abs(costs[0] - costs[1]))
            continue
        one_step = table[i-1] + abs(costs[i-1] - costs[i])
        two_step = table[i-2] + abs(costs[i-2] - costs[i])
        table.append(min([one_step, two_step]))
    return table[-1]
        
def main():
    for index, line in enumerate(sys.stdin):
        if index == 0:
            continue
        costs = [int(s) for s in line.split(" ")]
        print(dp(costs))

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys

def dp(costs):
    table = [0]
    for i in range(1, len(costs)):
        if i == 1:
            table.append(table[0] + abs(costs[0] - costs[1]))
            continue
        one_step = table[i-1] + abs(costs[i-1] - costs[i])
        two_step = table[i-2] + abs(costs[i-2] - costs[i])
        table.append(min([one_step, two_step]))
    return table[-1]
        
def main():
    for index, line in enumerate(sys.stdin):
        if index == 0:
            continue
        costs = [int(s) for s in line.split(" ")]
        print(dp(costs))

if __name__ == "__main__":
    main()
n = int(input())
d = {}
for i in range(n - 1):
  u, v, w = map(int, input().split())
  u -= 1
  v -= 1
  if u in d:
    d[u].append([v, w])
  else:
    d[u] = [[v, w]]
  if v in d:
    d[v].append([u, w])
  else:
    d[v] = [[u, w]]

rem = {}

for i in range(n):
  rem[i] = 1
  
ans = [0 for _ in range(n)]

def check(p, tmp):
  rem.pop(p)
  for n, w in d[p]:
    if n in rem:
      ntmp = (tmp + w) % 2
      ans[n] = ntmp
      check(n, ntmp)
      
check(0, 0)

for res in ans:
  print(res)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

n = int(input())
d = {}
for i in range(n - 1):
  u, v, w = map(int, input().split())
  u -= 1
  v -= 1
  if u in d:
    d[u].append([v, w])
  else:
    d[u] = [[v, w]]
  if v in d:
    d[v].append([u, w])
  else:
    d[v] = [[u, w]]

rem = {}

for i in range(n):
  rem[i] = 1
  
ans = [0 for _ in range(n)]

def check(p, tmp):
  rem.pop(p)
  for n, w in d[p]:
    if n in rem:
      ntmp = (tmp + w) % 2
      ans[n] = ntmp
      check(n, ntmp)
      
check(0, 0)

for res in ans:
  print(res)
while True:
    e = int(input())
    if e == 0:
        break
    
    m = e + 1
    for y in range(e + 1):
        y2 = y ** 2
        if y2 > e:
            break
        for z in range(e + 1):
            z3 = z ** 3
            if z3 + y2 > e:
                break
            x = e - y2 - z3
            m = min(m, x + y + z)

    print(m)


### FIXED CODE ###

import math

while True:
    e = int(input())
    if e == 0:
        break
    
    m = e + 1
    z = 0
    while z <= e:
        z3 = z ** 3
        if z3 > e:
            break
        y = int(math.sqrt(e - z3))
        x = e - y ** 2 - z3
        m = min(m, x + y + z)
        z += 1
    print(m)
n,k=map(int,input().split())
a=list(map(int,input().split()))
p=[]
m=[]
z=0
a.sort(reverse=True)
for i in range(n):
    if a[i]>0:
        p.append(a[i])
    elif a[i]==0:
        z+=1
    else:
        m.append(a[i])
nump=len(p)
numm=len(m)
ans=1
if nump+numm<k and z!=0:
    print(0)
elif numm<2 and nump>=k:
    for i in range(k):
        ans*=p[i]
        ans%=10**9+7
    print(ans)
elif 2*(numm//2)+nump<k:
    if z!=0:
        print(0)
    else:
        a.sort()
        for i in range(k):
            ans*=a[i]
            ans%=10**9+7
        print(ans)
elif  nump==0:
    if z!=0:
        print(0)
    else:
        for i in range(k):
            ans*=m[i]
            ans%=10**9+7
        print(ans)
else:
    if k%2==1:
        ans*=p[0]
    m.sort()
    nump=(nump-1)//2
    numm=numm//2
    nump1=0
    nump2=0
    numm1=0
    numm2=0
    for i in range(k//2):
        if nump2==nump:
            nump1=0
        else:
            nump1=p[nump2*2]*p[nump*2+1]
        if numm2==numm:
            numm1=0
        else:
            numm1=m[numm2*2]*m[numm2*2+1]
        if numm1>nump1:
            num=numm1
            numm2+=1
        else:
            num=nump1
            nump2+=1
        ans*=num
        ans%=10**9+7
    print(ans)


### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
p=[]
m=[]
z=0
a.sort(reverse=True)
for i in range(n):
    if a[i]>0:
        p.append(a[i])
    elif a[i]==0:
        z+=1
    else:
        m.append(a[i])
nump=len(p)
numm=len(m)
ans=1
if nump+numm<k:
    print(0)
elif numm<2 and nump>=k:
    for i in range(k):
        ans*=p[i]
        ans%=10**9+7
    print(ans)
elif 2*(numm//2)+nump<k: #2
    if z!=0:
        print(0)
    else:
        for i in range(n):
            a[i]=abs(a[i])
        a.sort()
        ans=-1
        for i in range(k):
            ans*=a[i]
            ans%=10**9+7
        print(ans)
elif  nump==0: #8?
    if z!=0 and k%2==1:
        print(0)
    elif z!=0 and numm<k:
        print(0)
    else:
        if k%2==0:
            m.sort()
            for i in range(k):
                ans*=m[i]
                ans%=10**9+7
        else:
            m.sort(reverse=True)
            for i in range(k):
                ans*=m[i]
                ans%=10**9+7
        print(ans)
else:
    if k%2==1:
        ans*=p[0]
        p=p[1:]
    m.sort()
    p.sort(reverse=True)
    nump=len(p)//2
    numm=numm//2
    nump1=0
    nump2=0
    numm1=0
    numm2=0
    for i in range(k//2):
        if nump2==nump:
            nump1=-1
        else:
            nump1=p[nump2*2]*p[nump2*2+1]
        if numm2==numm:
            numm1=-1
        else:
            numm1=m[numm2*2]*m[numm2*2+1]
        if numm1>=nump1:
            num=numm1
            numm2+=1
        else:
            num=nump1
            nump2+=1
        ans*=num
        ans%=10**9+7
    print(ans)