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

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

ans = 0
for i in range(n-k+1):
  tmp = 0
  for j in range(k):
     tmp = tmp + p[i+j]
  ans = max(ans,tmp)

print((k+ans)/2)


### FIXED CODE ###

n,k = map(int,input().split())
p = list(map(int, input().split()))

ans = sum(p[0:k])
tmp = ans
for i in range(n-k):
  tmp = tmp - p[i] + p[i+k]
  ans = max(ans,tmp)

print((k+ans)/2)
### BUGGY CODE ###

N = int(input())
A = [int(input()) for i in range(N)]
Ad = [0] *N

for i in range(N):
    tmp = A[i]
    A[i] = 0
    print(max(A))
    A[i] = tmp

### FIXED CODE ###

N = int(input())
A = [int(input()) for i in range(N)]
A_reverse = sorted(A)

for i in range(N):
    if A[i] == A_reverse[-1]:
        print(A_reverse[-2])
    else:
        print(A_reverse[-1])
### BUGGY CODE ###

import numpy
N,K=map(int,input().split())
A=list(map(int,input().split()))
S=[0]+list(numpy.cumsum(A)) #累積和
S2=[(S[i]-i)%K for i in range(N+1)]

d = {}
ans = 0
for j in range(1,N+1):
    if j>K-1 and str(S2[j-K]) in d:
        d[str(S2[j-K])] -= 1
        
    if str(S2[j-1]) in d:
        d[str(S2[j-1])] += 1
    else:
        d[str(S2[j-1])] = 1
        
    if str(S2[j]) in d:
        ans += d[str(S2[j])]
print(ans)

### FIXED CODE ###

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

if K==1:
    print(0)
    exit(0)

A=list(map(int,input().split()))
S=[0]+list(numpy.cumsum(A)) #累積和
S2=[(S[i]-i)%K for i in range(N+1)]

d = {}
ans = 0
for j in range(1,N+1):
    if j>K-1:
        if S2[j-K] in d:
            d[S2[j-K]] -= 1
        
    if S2[j-1] in d:
        d[S2[j-1]] += 1
    else:
        d[S2[j-1]] = 1
        
    if S2[j] in d:
        ans += d[S2[j]]
print(ans)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
result=1
for i in (a):
    result = result * i
 # Multiply elements one by one 
if result> (10**18):
     print("-1")
else:
     print(result)


### FIXED CODE ###

# we collect the input A1 upto An.
# limit cannot exceed 10**18
# if N = 0 then ans = 0
# in N is in range then compute ans * A[n]
# else if  ans is greater than limit then display 1
# finally if length equal 1 then display -1
N = int(input())
ans = 1
limit = 10 ** 18
length = 0

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

A0 = set(A)
if 0 in A0:
    ans = 0
else:
    pass

for n in range(N):
    ans = ans * A[n]
    if ans == 0:
        break
    elif ans > limit:
        length = 1
        break
    else:
        pass

if length == 1:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

from collections import deque
n = int(input())
deq = deque()
sub_deq = {}
for i in range(n):
    cmd = input()
    if cmd == 'deleteFirst':
        while deq:
            data = deq.popleft()
            if data[1]:
                data[1] = 0
                break
    elif cmd == 'deleteLast':
        while deq:
            data = deq.pop()
            if data[1]:
                data[1] = 0
                break
    else:
        cmd, val = cmd.split()
        if cmd == 'insert':
            data = [val, 1]
            deq.appendleft(data)
            if val not in sub_deq:
                sub_deq[val] = deque()
            sub_deq[val].appendleft(data)
        elif cmd == 'delete':
            if val in sub_deq:
                deq_v = sub_deq[val]
                while deq_v:
                    data = deq_v.popleft()
                    if data[1]:
                        data[1] = 0
                        break
print(*(data[0] for data in deq if data[1]))

### FIXED CODE ###

from collections import deque
import sys
n = int(input())
deq = deque()
sub_deq = {}
for cmd in sys.stdin.readlines():
    if cmd == 'deleteFirst\n':
        while deq:
            data = deq.pop()
            if data[1]:
                data[1] = 0
                break
    elif cmd == 'deleteLast\n':
        while deq:
            data = deq.popleft()
            if data[1]:
                data[1] = 0
                break
    else:
        cmd, val = cmd.split()
        if cmd == 'insert':
            data = [val, 1]
            deq.append(data)
            if val not in sub_deq:
                sub_deq[val] = [data]
            else:
                sub_deq[val].append(data)
        elif cmd == 'delete':
            if val in sub_deq:
                deq_v = sub_deq[val]
                while deq_v:
                    data = deq_v.pop()
                    if data[1]:
                        data[1] = 0
                        break
sys.stdout.write(" ".join(data[0] for data in reversed(deq) if data[1]))
sys.stdout.write('\n')
### BUGGY CODE ###

n = int(input())
a = [int(input()) for x in range(n)]
for i in range(len(a)):
    b = []
    b.append(a[:i])
    b.append(a[i+1:])
    b = [flatten for inner in b for flatten in inner]
    print(max(b))

### FIXED CODE ###

n = int(input())
a = [int(input()) for x in range(n)]
b = sorted(a,reverse=True)
for i in range(n):
    if b[0] == a[i]:
        print(b[1])
    else:
        print(b[0])
### BUGGY CODE ###

from fractions import gcd
import sys
input = sys.stdin.readline
MOD = 10 ** 9 + 7


def main():
    N = int(input())
    A = list(map(int, input().split()))

    l = A[0]
    for i in range(1, N):
        l = l * A[i] // gcd(l, A[i])

    ans = 0
    for a in A:
        ans += l // a
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from fractions import gcd
import sys
input = sys.stdin.readline
MOD = 10 ** 9 + 7


def main():
    N = int(input())
    A = list(map(int, input().split()))

    l = A[0]
    for i in range(1, N):
        l = l * A[i] // gcd(l, A[i])

    print(sum([l // a for a in A]) % MOD)


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

N = int(input())
s = [i+1 for i in range(N)]
print(sum(s[:-1]))


### FIXED CODE ###

N = int(input())
ans = ((N-1)*N)//2
print(ans)
### BUGGY CODE ###

h,n=map(int,input().split())
M=[list(map(int,input().split())) for _ in range(n)]
res=[0]
f=0
for j in range(1,h+1):
    
    i=0
    if 0>=j-M[i][0]:
        ind=0
    else:
        ind=j-M[i][0]
    ff=res[ind]+M[i][1]
    
    for i in range(1,n):
        if 0>=j-M[i][0]:
            ind=0
        else:
            ind=j-M[i][0]
        kari=res[ind]+M[i][1]
        
        ff=min(ff,kari)
    res.append(ff)
print(res[-1])


### FIXED CODE ###

h,n=map(int,input().split())
M=[list(map(int,input().split())) for _ in range(n)]
res=[0]
f=0
for j in range(1,h+1):
    
    i=0
    if 0>=j-M[i][0]:
        ind=0
    else:
        ind=j-M[i][0]
    ff=res[ind]+M[i][1]
    
    for i in range(1,n):
        if 0>=j-M[i][0]:
            ind=0
        else:
            ind=j-M[i][0]
        kari=res[ind]+M[i][1]
        
        ff=min(ff,kari)
    res.append(ff)
print(res[-1])
### BUGGY CODE ###

n = int(input())
li = list(map(int,input().split()))	
for i in range(n):
    print(li.count(i + 1))

### FIXED CODE ###

import collections

N = int(input())
A = list(map(int,input().split()))
c = collections.Counter(A)

for i in range(1, N + 1):
  print(c[i])
### BUGGY CODE ###

n,c,k=map(int,input().split())
t=[int(input()) for _ in range(n)]
t.sort()
res=0
while(t):
    i=0
    j=t[0]+k
    if len(t)==1:
        res+=1
        break
    while(i<len(t) and t[i]<=j and i<c):
        i+=1
    res+=1
    t=t[i:]
print(res)

### FIXED CODE ###

n,c,k=map(int,input().split())
t=[int(input()) for _ in range(n)]
t.sort()
res=0
i1=0
while(i1<n):
    i2=0
    j=t[i1]+k
    if i1==n-1:
        res+=1
        break
    while(i1+i2<len(t) and t[i1+i2]<=j and i2<c):
        i2+=1
    res+=1
    i1+=i2
print(res)
### BUGGY CODE ###

import collections
import queue
import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N, M = map(int, input().split())
        edges = [tuple(map(int, input().split())) for _ in range(M)]
        S, T = map(int, input().split())

        edge_map = collections.defaultdict(list)
        for u, v in edges:
            edge_map[u].append(v)

        q = queue.Queue()
        q.put((S, 0))

        dist = collections.defaultdict(lambda: [10 ** 5] * 3)
        dist[S][0] = 0
        while not q.empty():
            node, total_path_length = q.get()

            for next_node in edge_map[node]:
                nl = (total_path_length + 1) % 3
                if dist[next_node][nl] == 10 ** 5:
                    dist[next_node][nl] = total_path_length + 1
                    q.put((next_node, total_path_length + 1))

        if dist[T][0] == 10 ** 5:
            print(-1)
        else:
            print(dist[T][0]//3)


# Run main
if __name__ == '__main__':
    AtCoder().main()


### FIXED CODE ###

import collections
import queue
import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N, M = map(int, input().split())
        edges = [tuple(map(int, input().split())) for _ in range(M)]
        S, T = map(int, input().split())

        edge_map = collections.defaultdict(list)
        for u, v in edges:
            edge_map[u - 1].append(v - 1)

        q = queue.Queue()
        q.put((S - 1, 0))

        INF = 10 ** 5
        dist = [[INF] * 3 for _ in range(N)]
        dist[S - 1][0] = 0
        while not q.empty():
            node, kkp = q.get()

            for next_node in edge_map[node]:
                next_kkp = (kkp + 1) % 3
                if dist[next_node][next_kkp] == INF:
                    dist[next_node][next_kkp] = dist[node][kkp] + 1
                    q.put((next_node, next_kkp))

        if dist[T - 1][0] == INF:
            print(-1)
        else:
            print(dist[T - 1][0] // 3)


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

n=int(input())
s=[input() for _ in range(n)]
s.sort()
s.append("")
#print(s)
a=[]
count=[]
buf=1
for i in range(n):
    if s[i]==s[i+1]:
        buf+=1
    else:
        a.append(s[i])
        count.append(buf)
        buf=1
#print(a)
#print(count)
for i in range(len(a)):
    if count[i]==max(count):
        print(a[i])

### FIXED CODE ###

n=int(input())
s=[input() for _ in range(n)]
s.sort()
s.append("")
a=[]
count=[]
buf=1
count_max=1
for i in range(n):
    s_i=s[i]
    if s_i==s[i+1]:
        buf+=1
    else:
        if buf>=count_max:
            a.append(s_i)
            count.append(buf)
            if buf>count_max:
                count_max=buf
        buf=1
count_max=max(count)
for i in range(len(a)):
    if count[i]==count_max:
        print(a[i])
### BUGGY CODE ###

N=int(input())
s=[input() for i in range(N)]
kison=[]
ans=0
for youso in s:
    if youso not in kison:
        kison.append(youso)
        ans+=1
    else:
        pass
print(ans)

### FIXED CODE ###

N=int(input())
s_li=[input() for i in range(N)]
print(len(set(s_li)))
### BUGGY CODE ###

N = int(input())
Ai = [0] * N
Ai = list(map(int,input().split()))
Ans = 1

for i in range(N):
  if Ai[0] == 0:
    Ans = 0
    break
    
  Ans = Ans * Ai[i]
  
if Ans <= 10**18:
  print(Ans)
else:
  print('-1')

### FIXED CODE ###

N = int(input())
Ai = [0] * N
Ai = list(map(int,input().split()))
Ai.sort()
Ans = 1

for i in range(N):
  if Ai[i] == 0:
    Ans = 0
    break
    
  Ans = Ans * Ai[i]

  if Ans > 10 ** 18:
    Ans = -1
    break
  
if Ans <= 10**18:
  print(Ans)
else:
  print('-1')
### BUGGY CODE ###

def chmin(a,b):
    if a > b:
        return b
    else:
        return a


N, K = map(int, input().split())
h = list(map(int, input().split()))
INF = float('inf')
dp = [INF] * (10**5 + 10000)
dp[0] = 0


for i in range(N):
    for j in range(1,K+1):
        if i+j < N:
            dp[i+j] = chmin(dp[i+j], dp[i] + abs(h[i] - h[i+j]))

print(dp[N-1])

### FIXED CODE ###

def chmin(a,b):
    if a > b:
        return b
    else:
        return a


N, K = map(int, input().split())
h = list(map(int, input().split()))
INF = float('inf')
dp = [INF] * N
dp[0] = 0


for i in range(N):
    for j in range(1,K+1):
        if i+j < N:
            dp[i+j] = chmin(dp[i+j], dp[i] + abs(h[i] - h[i+j]))

print(dp[N-1])
### BUGGY CODE ###

N = int(input())

dp = [0 for _ in range(N+1)]
for x in range(1,N):
    for y in range(1,N):
        for z in range(1,N):
            t = x * x + y * y + z * z + x * y + y * z + z * x
            if t <= N:
                dp[t] += 1

for i in range(1,N+1):
    print(dp[i])

### FIXED CODE ###

N = int(input())

dp = [0 for _ in range(N+1)]
for x in range(1,int(N**0.5)+1):
    for y in range(1,int(N**0.5)+1):
        for z in range(1,int(N**0.5)+1):
            t = x * x + y * y + z * z + x * y + y * z + z * x
            if t <= N:
                dp[t] += 1

for i in range(1,N+1):
    print(dp[i])
### BUGGY CODE ###

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

ans = 0
c19 = 0
for i in range(1,100001):
    ca = a.count(i)
    if ca >= i:
        ans += ca - i
    else:
        ans += ca
    c19 += ca
print(ans + n-c19)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
d = {}
count = 0
for i in range(n):
    if not a[i] in d.keys() and (n-count)>=a[i]:
        ac = a.count(a[i])
        d.update({a[i]:ac})
        count += ac
ans = 0
for i in sorted(d.keys()):
    if i <= d[i]:
        ans += d[i]-i
    else:
        ans += d[i]

print(ans + n-count)
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
s = [0] * (n - k + 1)
for i in range(n - k + 1):
    p = 1
    for j in range(i, i + k):
        p *= a[j]
    s[i] = p
for i in range(n - k):
    print('Yes' if s[i] < s[i + 1] else 'No')

### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
for i in range(1, n - k + 1):
    print('Yes' if 1 < a[k + i - 1] / a[i - 1] else 'No')
### BUGGY CODE ###

N, Q = map(int,input().split())
S = input()
index = []
for i in range(N-1):
  if S[i] =='A' and S[i+1] == 'C':
    index.append(i)
for _ in range(Q):
  l,r = map(int,input().split())
  counter = 0
  for item in index:
    if l-1 <= item and item+1 <= r-1:
      counter += 1
  print(counter)

### FIXED CODE ###

N,Q = map(int,input().split())
S = input()
index = [0] *(N+1)
for i in range(N):
  index[i+1] = index[i] + (1 if S[i:i+2] =='AC' else 0)
for _ in range(Q):
  r, l = map(int,input().split())
  print(index[l-1] - index[ r -1])
### BUGGY CODE ###

#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #ここにコード
    #input
    from collections import Counter
    import itertools
    N = int(input())

    dp = [[0, 0] for _ in range(N)]
    for i in range(N):
        S = str(input())
        T = []
        for s in S:
            if s == "(":
                T.append(1)
            else:
                T.append(-1)
        x = list(itertools.accumulate(T))[-1]
        y = min(itertools.accumulate(T))
        dp[i] = [x, y]


    #output
    dp1 = [[x, y] for x, y in dp if x >= 0]
    dp2 = [[x, y] for x, y in dp if x < 0]
    dp1 = sorted(dp1, key = lambda x:x[1], reverse = True)
    dp2 = sorted(dp2, key = lambda x:x[0]-x[1], reverse = True)
    dp = dp1 + dp2

    checker = 0
    for p in dp:
        if checker + p[1] < 0:
            print("No")
            exit()
        checker += p[0]

    if checker == 0:
        print("Yes")
    else:
        print("No")

if __name__ == "__main__":
    main()

### FIXED CODE ###

#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #ここにコード
    #input
    from collections import Counter
    import itertools
    N = int(input())

    dp = [[0, 0] for _ in range(N)]
    for i in range(N):
        S = str(input())
        T = []
        for s in S:
            if s == "(":
                T.append(1)
            else:
                T.append(-1)
        x = list(itertools.accumulate(T))[-1]
        y = min(itertools.accumulate(T))
        dp[i] = [x, y]


    #output
    dp1 = [[x, y] for x, y in dp if x >= 0]
    dp2 = [[x, y] for x, y in dp if x < 0]
    dp1 = sorted(dp1, key = lambda x:x[1], reverse = True)
    dp2 = sorted(dp2, key = lambda x:x[0]-x[1], reverse = True)
    dp = dp1 + dp2

    checker = 0
    for p in dp:
        if checker + p[1] < 0:
            print("No")
            exit()
        checker += p[0]

    if checker == 0:
        print("Yes")
    else:
        print("No")

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

from collections import deque
N = int(input())

Q = deque()
Q.append(0)
i = 1
f = False
while Q:
  Q2 = Q
  Q = []
  for t in Q2:
    if t+i == N or t-i == N:
      print (i)
      f = True
      break
    Q.append(t-i)
    Q.append(t)
    Q.append(t+i)
  if f: break
  i += 1


### FIXED CODE ###

import math
X = int(input())
t = math.ceil((-1 + (1 + 8 * X) ** 0.5)/2)
print (t)
### BUGGY CODE ###

inf = 1001001001
n = int(input())
lis = list(map(int, input().split()))
lis.sort()
lis.append(inf)
ans = 0
for i in range(n-2):
    a = lis[i]
    for j in range(i + 1, n-1):
        b = lis[j]
        l = j
        r = n
        while r > l+1:
            mid = (l+r) // 2
            if lis[mid] < a + b:
                l = mid
            else:
                r = mid
        ans += l - j
print(ans)

### FIXED CODE ###

inf = 1001001001
n = int(input())
lis = list(map(int, input().split()))
lis.sort()
lis.append(inf)
ans = 0
for i in range(n-2):
    a = lis[i]
    for j in range(i + 1, n-1):
        b = lis[j]
        l = j
        r = n
        while r > l+1:
            mid = (l+r) // 2
            if lis[mid] < a + b:
                l = mid
            else:
                r = mid
        ans += l - j
print(ans)
### BUGGY CODE ###

from itertools import product
from collections import deque

def state_brute_force(state, count):
    state_list = [state for _ in range(count)]
    for s in product(*state_list):
        yield s


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

ans = 0

pop_l = deque.popleft
pop_r = deque.pop
add_l = deque.appendleft
add_r = deque.append

stop_condition = sum([item for item in D if item > 0])

for cmb in state_brute_force([pop_l, pop_r, add_l, add_r], K):
    q = deque(D)
    now = []
    value = 0
    for operation in cmb:
        if operation == add_l or operation == add_r:
            if len(now) == 0:
                break
            item = min(now)
            now.remove(item)
            operation(q, item)
        if operation == pop_l or operation == pop_r:
            if len(q) == 0:
                break
            now.append(operation(q))
    value = max(value, sum(now))
    ans = max(ans, value)
    if ans == stop_condition:
        break

print(ans)




### FIXED CODE ###

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

ans = 0

for left in range(K + 1):
    for right in range(K - left + 1):
        if left + right > N:
            break
        items = list(D[0:left])
        items.extend(D[::-1][0:right])
        dis = K - (left + right)
        i = 0
        items = sorted(items, reverse=True)
        while True:
            ans = max(ans, sum(items))
            if i < dis and len(items) > 0:
                i += 1
                items.pop()
                continue
            else:
                break

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

n, k = map(int, input().split())
ans = 10**18 + 1
if k == 1:
    print(0)
    exit()
while ans > k:
    ans = min(ans, n)
    n = abs(n-k)

print(min(ans, k-ans))

### FIXED CODE ###

n, k = map(int, input().split())
z = n%k
if z == 0:
    print(0)
else:
    print(min(k-z, k-(k-z)))
### BUGGY CODE ###

h, n = map(int, input().split())
m = [list(map(int, input().split())) for _ in range(n)]
INF = 10 ** 12
dp = [INF for _ in range(h + 1)]
dp[0] = 0
for a, b in m:
    for i in range(h + 1):
        if i + a > h:
            dp[h] = min(dp[h], dp[i] + b)
        else:
            dp[i + a] = min(dp[i + a], dp[i] + b)
print(dp[h])


### FIXED CODE ###

h, n = map(int, input().split())
m = [list(map(int, input().split())) for _ in range(n)]
INF = 10 ** 12
dp = [INF for _ in range(h + 1)]
dp[0] = 0
for a, b in m:
    for i in range(h + 1):
        if i + a > h:
            dp[h] = min(dp[h], dp[i] + b)
        else:
            dp[i + a] = min(dp[i + a], dp[i] + b)
print(dp[h])
### BUGGY CODE ###

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

N, M = map(int, input().split())
A = list(map(int, input().split()))
B = set(A)
power = 1
for b in B:
    power = lcm(power, b//2)

mn = min(B)

mn2 = mn // 2
p2 = power // mn2

if p2 % 2 == 0:
    print(0)
    exit()
ans1 = M // mn2 // p2
ans2 = M // mn2 // (p2*2)
print(ans1-ans2)


### FIXED CODE ###

from fractions import gcd
def lcm(a, b):
    return a * b // gcd(a, b)
N, M = map(int, input().split())
B = set(map(lambda x: int(x)//2, input().split()))
power = 1
for b in B:
    power = lcm(power, b)

mn = min(B)
p2 = power // mn

if p2 % 2 == 0:
    print(0)
    exit()
ans1 = M // mn // p2
ans2 = M // mn // (p2 * 2)
print(ans1-ans2)
### BUGGY CODE ###

n, m = map(int, input().split())
info = [list(map(int, input().split())) for _ in range(m)]
info = sorted(info, key=lambda x: x[0])

queue = []
for regular in info:
	if regular[0] == 1:
		queue.append(regular[1])

	elif (regular[0] in queue) and regular[1] == n:
		print("POSSIBLE")
		break
else:
	print("IMPOSSIBLE")

### FIXED CODE ###

n, m = map(int, input().split())
side1 = set()
side2 = set()

for i in range(m):
	a, b = map(int, input().split())

	if a == 1:
		side1.add(b)
	
	elif b == n:
		side2.add(a)

print(("" if side1 & side2 else "IM") + "POSSIBLE")
### BUGGY CODE ###

from collections import deque

N, K = map(int, input().split())
a_list = list(map(int, input().split()))
a_list = deque(sorted(a_list))
MOD = 10**9 + 7
 
 
def choose1():
    l = 1
    if a_list[-1]*a_list[-2] >= a_list[0]*a_list[1]:
        l *= a_list.popleft()
        l *= a_list.popleft()
    else:
        l *= a_list.pop()
        l *= a_list.pop()
    return l

def choose2():
    l = 1
    if a_list[-1]*a_list[-2] >= a_list[0]*a_list[1]:
        l *= a_list.pop()
        l *= a_list.pop()
    else:
        l *= a_list.popleft()
        l *= a_list.popleft()
    return l
 
 
ans = 1
if K == 1:
    print(a_list[-1]%MOD)
    exit()
else:
    if K % 2 == 0:
        for _ in range(K//2):
            ans *= choose2() % MOD
    else:
        ans *= a_list.pop()
        if ans < 0:
            for _ in range((K-1)//2):
                ans *= choose1() % MOD
        else:
            for _ in range((K-1)//2):
                ans *= choose2() % MOD
 
print(ans%MOD)

### FIXED CODE ###

"""
E.
"""
from functools import reduce
from collections import deque


def prod(x, y):
    return x * y % MOD

    
N, K = map(int, input().split())
a_list = list(map(int, input().split()))
a_list.sort(reverse=True)
# abs_a_list = sorted(a_list, key=abs, reverse=True)
MOD = 10**9 + 7

if K%2 == 1:
    flg = True
    for a in a_list:
        if a >= 0:
            flg = False
            break
    if flg:
        print(reduce(prod, a_list[:K]))
        exit()

S = []
a_list = deque(a_list)
i = 0
while i < K:
    if len(a_list)>=2:
        if a_list[0]*a_list[1] > a_list[-1]*a_list[-2]:
            S.append(a_list.popleft())
            i += 1
        elif a_list[0]*a_list[1] <= a_list[-1]*a_list[-2] and i <= K-2:
            S.append(a_list.pop())
            S.append(a_list.pop())
            i += 2
        else:
            S.append(a_list.popleft())
            i += 1
    else:
        S.append(a_list.popleft())
        i += 1
        
ans = reduce(prod, S)
print(ans)