Harryxun/stf_run huggingface dataset:
if input() == "A" : print("T")
elif input() == "T" : print("A")
elif input() == "C" : print("G")
else : print("C")

### FIXED CODE ###

b = str(input())
if b == "A" : print("T")
elif b == "T" : print("A")
elif b == "C" : print("G")
else : print("C")
N = int(input())
A = list(map(int, input().split()))
d = {}
for a in A:
  for i in range(a - 1, a + 2)
  d[i] = d.get(i, 0) + 1
x = sorted(d.values())
print(max(x))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
d = {}
for a in A:
  for i in range(a - 1, a + 2):
    d[i] = d.get(i, 0) + 1
x = sorted(d.values())
print(max(x))
count, outrate = input().split()
if count >= 10:
  result = outrate
  print(result)
else:
  result = outrate + 100 * (10 - count)
  print(result)


### FIXED CODE ###

count, outrate = map(int, input().split())

if count >= 10:
  result = outrate
  print(result)
else:
  result = outrate + 100 * (10 - count)
  print(result)
a = int(input())
b = int(input())

if a * b % 2 == 0:
	print('even')
else:
	print('odd')


### FIXED CODE ###

a, b = map(int, input().split())

if a * b % 2 == 0:
    print('Even')
else:
    print('Odd')
S = int(input())
print('{0}:{1}:{2}'format(S//3600, S // 60, S % 60))

### FIXED CODE ###

S = int(input())
print('{0}:{1}:{2}'.format(S//3600,  (S % 3600) // 60,  (S % 3600)  % 60))
n,k = map(int, input().split())
dp = [float("inf")] * n*10
h = list(map(int, input().split()))
dp[0] = 0
for i in range(n):
    for j in range(1,k+1):
        dp[i+j] = min(dp[i+j], dp[i] + abs(h[i]-h[i+j]))
print(dp[n-1])

### FIXED CODE ###

n,k = map(int, input().split())
dp = [float("inf")] * 100000
h = list(map(int, input().split()))
dp[0] = 0
for i in range(n):
    for j in range(1,k+1):
        if i+j < n:
            dp[i+j] = min(dp[i+j], dp[i] + abs(h[i]-h[i+j]))
print(dp[n-1])
# coding: utf-8
# Your code here!
from collections import Counter

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

a,b = [],[]

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

p,x = [],[]

for i in range(q):
    _p,_x = map(int,input().split())
    p.append(_p)
    x.append(_x)

class ki:
    def __init__ (self,n):
        self.name = n
        self.num = 0
        self.node = []
    
    def add(self,n,ne):
        if self.name == n:
            self.node.append(ki(ne))
            return 0
        else:
            for i in self.node:
                i.add(n,ne)
            return 0
            
    def add_num(self,n,num,f):
        if self.name == n or f:
            self.num += num
            f = True
        else:
            f = False
            
        for i in self.node:
            i.add_num(n,num,f)
    
    def out(self):
        d = {self.name:self.num}
        for i in self.node:
            d = dict(Counter(d) + Counter(i.out()))
        return(d)

Ki = ki(1)

for i,j in zip(a,b):
    Ki.add(i,j)
for i,j in zip(p,x):
    Ki.add_num(i,j,False)

d = Ki.out()
print(" ".join([str(d[i+1]) for i in range(n)]))
    
    

### FIXED CODE ###

# coding: utf-8
# Your code here!
from collections import Counter

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

d = {}

for i in range(n-1):
    _a,_b = map(int,input().split())
    d[_b] = _a

ans = [0]*n

for i in range(q):
    _p,_x = map(int,input().split())
    ans[_p-1]+=_x


for i in range(1,n):
    ans[i] += ans[d.get(i+1)-1]

#print(ans)
print(" ".join(map(str,ans)))
def intinput(): return map(int,input().split())

def ab(i):
    global c,l,x
    while len(l[i])>0:
        x[l[i][0]]=c.pop(0)
        l[l[i][0]].remove(i)
        ab(l[i][0])
        try:
            l[i].pop(0)
        except:
            pass
    return

n=int(input())
l = [[] for _ in range(n+1)]
for i in range(n-1):
    a,b=intinput()
    l[a].append(b)
    l[b].append(a)
c = list(intinput())
c.sort(reverse=1)
x = [0 for _ in range(n+1)]
x[1]=c.pop(0)
for i in range(1,n+1):
    ab(i)
print(sum(x[2:]))
f = ""
q= len(x[1:])
for i in range(q):
    if i != q-1:
        f += str(x[i+1])+" "
    else:
        f += str(x[i+1])
print(f)

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000) 

def intinput(): return map(int,input().split())

def ab(i):
    global c,l,x
    while len(l[i])>0:
        x[l[i][0]] = c.pop(0)
        l[l[i][0]].remove(i)
        ab(l[i][0])
        l[i].pop(0)
    return

n=int(input())
l = [[] for _ in range(n+1)]
for i in range(n-1):
    a,b=intinput()
    l[a].append(b)
    l[b].append(a)
c = list(intinput())
c.sort(reverse=1)
x = [0 for _ in range(n+1)]
x[1]=c.pop(0)
for i in range(1,n+1):
    ab(i)
print(sum(x[2:]))
f = ""
q= len(x[1:])
for i in range(q):
    if i != q-1:
        f += str(x[i+1])+" "
    else:
        f += str(x[i+1])
print(f)
n,k = map(int, input().split())
li = []
i = 0
for i<k:
  li.append(int(input()))
  i += 1
else:
  Li = list(n)
  while not set(li)&set(Li) == set():
    n += 1
    Li = list(n)
  else: print("".join(Li))

### FIXED CODE ###

n,k = map(str, input().split())
li = list(map(str, input().split()))
Li = list(n)
while len(set(Li)&set(li)):
  n = int(n)+1
  Li = list(str(n))
else: print("".join(Li))
N, K = map(int, input().split())
A = [int(input()) for i in range(N)]


ans = []

i = 0
while(i<=N-2):
  a = A[i]
  T = 1
  while (i<=N-2):
    if ( abs(a-A[i]) <= K ):
      T += 1
      a = A[i]
    i += 1
  ans.append(T)
  i += 1
  
print(max(ans))


### FIXED CODE ###

K = int(input())
A = ""
for i in range(K):
  A += "ACL"
  
print(A)
class uft():
    def __init__(self,n):
        self.p=[ -1 for i in range(n)]
        self.r=[ 1 for i in range(n)]
        
    def find(self,x):
        if(self.p[x]==-1):
            return x
        else:
            self.p[x]=self.find(self.p[x])
            return self.find(self.p[x])
        
    def unite(self,x,y):
        x=self.find(x)
        y=self.find(y)
        if(self.r[x]>self.r[y]):
            tmp=x
            x=y
            y=tmp
            
        if(self.r[x]==self.r[y]):
            self.r[y]+=1
            
        if(x!=y):
            self.p[x]=y
        return
    
n,m=map(int,input().split())
p=list(map(int,input().split()))
uf=uft(n)
for i in range(m):
    x,y=map(int,input().split())
    x-=1
    y-=1
    uf.unite(x,y)
ans=0
for i in range(n):
    if(uf.find(i)==uf.find(p[i])):
        ans+=1
        
print(ans)

### FIXED CODE ###

class uft():
    def __init__(self,n):
        self.p=[ -1 for i in range(n)]
        self.r=[ 1 for i in range(n)]
        
    def find(self,x):
        if(self.p[x]==-1):
            return x
        else:
            self.p[x]=self.find(self.p[x])
            return self.find(self.p[x])
        
    def unite(self,x,y):
        x=self.find(x)
        y=self.find(y)
        if(self.r[x]>self.r[y]):
            tmp=x
            x=y
            y=tmp
            
        if(self.r[x]==self.r[y]):
            self.r[y]+=1
            
        if(x!=y):
            self.p[x]=y
        return
    
n,m=map(int,input().split())
p=list(map(int,input().split()))
for i in range(n):
  p[i]-=1
uf=uft(n)
for i in range(m):
    x,y=map(int,input().split())
    x-=1
    y-=1
    uf.unite(x,y)
ans=0
for i in range(n):
    if(uf.find(i)==uf.find(p[i])):
        ans+=1
        
print(ans)
mod=1000000007
n,m=map(int,input().split())
a=[]
for i in range(m):
    a.append(int(input()))
a.sort()
f=0
for i in range(len(a)):
    if a[i]+1 in a:
        f=1
        break
if f==1:
    print(0)
else:
    dp=[0]*(n+1)
    dp[0]=1
    if 1 in a:
        dp[1]=0
    else:
        dp[1]=1
    
    for i in range(2,n+1):
        if i==a[0]:
            dp[i]=0
            a.pop(0)
        else:
            dp[i]=(dp[i-1]+dp[i-2])%mod
    print(dp[n]%mod)
  

### FIXED CODE ###

import sys
input = sys.stdin.readline

mod=1000000007
n,m=map(int,input().split())
a=[]
for i in range(m):
    a.append(int(input()))
al=len(a)


f=0
for i in range(al-1):
    if a[i+1]==a[i]+1:
        f=1
        break
if f==1:
    print(0)
else:
    dp=[0]*(n+1)
    dp[0]=1
    if 1 in a:
        dp[1]=0
        a.pop(0)
        al-=1
    else:
        dp[1]=1
    
    for i in range(2,n+1):
        if al>0 and i==a[0]:
            dp[i]=0
            a.pop(0)
            al-=1
        else:
            dp[i]=(dp[i-1]+dp[i-2])%mod
    print(dp[n]%mod)
import math

N = int(input())
print (factorial(N) % (10 ** 9 + 7))

### FIXED CODE ###

import math

N = int(input())
print (math.factorial(N) % (10 ** 9 + 7))
import sys
for line in sys.stdin:
    a,b = line.split()
    a,b = int(a),int(b)
    print '%d %d %f15' %(a/b, a%b, 1.0*a/b)

### FIXED CODE ###

a, b = map(int, raw_input().split())
print '%d %d %.12f' %(a/b, a%b, 1.0*a/b)
a = input()
a. split(,)
a[31]

### FIXED CODE ###

k = int(input())
alist = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
print(alist[k-1])
class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

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

p = 998244353

comb = Combination(N-1,p)

# 何個を同じ色の組にするか0~K
cnt = 0
for k in range(K+1):
    buf = 0
    # N-1個の組のうちどれを同じ色にするかN-1Ck
    buf = comb(N-1,k)

    # それぞれで、N-k個を別の色の順列にする
    # M*(M-1)**(N-k-1)
    buf *= M
    buf *= pow((M-1),(N-k-1),p)
    buf %= p
    cnt += buf
    cnt %= p

print(cnt)


### FIXED CODE ###

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

p = 998244353
# 何個を同じ色の組にするか0~K
cnt = 0
com = 1
for k in range(K+1):
    l = N-k
    # N-1個の組のうちどれを同じ色にするかN-1Ck
    # それぞれで、N-k個を別の色の順列にする
    # M*(M-1)**(N-k-1)
    x = pow((M-1),(l-1),p)
    cnt += M * x * com
    cnt %= p

    # 次のkのnCk
    com *= N-(k+1)
    com *= pow(k+1,p-2,p)
    com %= p


print(cnt)
N,M=map(int,inputt().split())
x = M * (M - 1) // 2
x += N * (N - 1) // 2
print(x)

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
N, M = map(int, readline().split())
x = M * (M - 1) // 2
x += N * (N - 1) // 2
print(x)
n = input()
for i in range(len(n)//2){
  if n[i] != n[-(i+1)]:
  	print('No')
  	exit(0)
print('Yes')

### FIXED CODE ###

import sys
n = input()
for i in range(len(n)//2):
  if n[i] != n[-(i+1)]:
  	print('No')
  	sys.exit(0)
print('Yes')
Enter a title here
Main.py 
Success  
  
        
出力
入力
コメント 0
(0.03 sec)
 
4


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split( )))
###連続区間に分ける

tmp = a[0]
tmp2 = 1
ans = 0
for i in range(1,n):
    if a[i]==tmp:
        tmp2 += 1
    else:
        tmp = a[i]
        ans += tmp2//2
        tmp2 = 1
ans += tmp2//2
print(ans)
ss = input()

for i in range(3):
  if ss[i] = ss[i+1]:
    print("Good")
    break
else:
  print("Bad")


### FIXED CODE ###

ss = input()

for i in range(3):
  if ss[i] == ss[i+1]:
    print("Bad")
    break
else:
  print("Good")
a,b=list(map(int,input().split()))
if a<0:
  print(100*(10-a)+b)
esle:
  print(b)

### FIXED CODE ###

a,b=list(map(int,input().split()))
if a<10:
  print(100*(10-a)+b)
else:
  print(b)
import math
import heapq

N, M = list(map(int, input().split()))
A = list(map(lambda a: -int(a), input().split()))
A.sort()
heapq.heapify(A)

for i in range(M):
  a = heapq.heappop(A)
  a =/ 2.0
  heapq.heappush(A, a)

amount = 0
for a in A:
  amount += math.floor(-a)
print(amount)


### FIXED CODE ###

import math
import heapq

N, M = list(map(int, input().split()))
A = list(map(lambda a: -int(a), input().split()))
A.sort()
heapq.heapify(A)

for i in range(M):
  a = heapq.heappop(A)
  a = -(-a / 2.0)
  heapq.heappush(A, a)

amount = 0
for a in A:
  amount += math.floor(-a)
print(amount)
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
n, q = list(map(int, input().split()))
count = (n - 2) ** 2
c = [n] * n
r = [n] * n
for _ in range(q):
  m,q = list(map(int, input().split()))
  if m == 1:
    pos = r[q-1]
    c[:pos] = [min(q, v) for v in c[:pos]] 
    r[q-1] = 1
    if q not in [1,n]:
      count -= max(0, pos - 2)
  else:
    pos = c[q-1]
    r[:pos] = [min(q, v) for v in r[:pos]]
    c[q-1] = 1
    if q not in [1,n]:
      count -= max(0, pos-2)
print(count)


### FIXED CODE ###

import os
import io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline


n, q = list(map(int, input().split()))
count = (n - 2) ** 2
c = [n] * (n + 1)
r = [n] * (n + 1)
mc = n
mr = n
for _ in range(q):
    m,q = list(map(int, input().split()))
    if m == 1:
        if q <= mc:
            count -= mr -2
            for p in range(q+1, mc):
                c[p] = mr
            c[q] = 0
            mc = q
        else:
            count -= c[q] - 2
    else:
        if q <= mr:
            count -= mc -2
            for p in range(q+1, mr):
                r[p] = mc
            r[q] = 0
            mr = q
        else:
            count -= r[q] - 2
print(count)
n = int(raw_input)

print n**3

### FIXED CODE ###

n = int(raw_input())
print n**3
import bisect


n,m = map(int,input().split())
a = list(map(int,input().split()))
a = sorted(a)
k = 0
for _ in range(m):
    k -= 1
    if(k > 0):continue
    a_tmp = a.pop()
    if(len(a)==0):a.append(a_tmp//2)
    else:
        a2 = a[-1]
        k = a_tmp // a2
        a_tmp //= 2 ** k
        if(a_tmp >= a[-1]):a.append(a_tmp)
        elif(a_tmp <= a[0]):a.insert(0,a_tmp)
        else:
            index = bisect.bisect_left(a,a_tmp)
            a.insert(index,a_tmp)


print(sum(a))


### FIXED CODE ###

import heapq

n,m = map(int,input().split())
a = list(map(lambda x:int(x)*(-1),input().split()))

heapq.heapify(a)

for _ in range(m):
    x = heapq.heappop(a) * -1
    x //= 2
    heapq.heappush(a,-1*x)
print(-sum(a))
x,y=(int(x) for x in input().split())
a=[int(x) for x in input().split()]
1<=x<=100
0<=y<=100
while y>0:
    if y in a:
        z=y+1
    elif not y in a:
        print('y')
        break
    elif z in a:
        z+=1
    else:
        break
while y<100:
    if y in a:
        b=y-1
    elif b in a:
        b+=1
    else:
        break
c=z-y
d=b-y
if not y in a:
    pass
elif abs(c)<abs(d):
    print(c)
else:
    print(d)


### FIXED CODE ###

a,b,c,d,e=(int(x) for x in input().split())
if a==0:
    print('1')
elif b==0:
    print('2')
elif c==0:
    print('3')
elif d==0:
    print('4')
elif e==0:
    print('5')
n, m, x, y = map(int, input().split())
xx = [int(i) for i in input().split()]
yy = [int(i) for i in input().split()]

ans = 'No War' if max(xx, x) < min(yy, y) else 'War'
print(ans)

### FIXED CODE ###

n, m, x, y = map(int, input().split())
xx = [int(i) for i in input().split()]
yy = [int(i) for i in input().split()]

ans = 'No War' if max(max(xx), x) < min(min(yy), y) else 'War'
print(ans)
# coding: utf-8
 
As = list(input().rstrip().split(" "))
N = As[0]
A = As[1]
B = As[2]
 
S  = input()
 
for i in range(N):
    if S[i] == "c":
        print("No")
    elif S[i] == "a":
        if i < A+B:
            print("Yes")
        else:
            print("No")
    elif S[i] == "b":
        if i < B:
            print("Yes")
        else:
            print("No") 

### FIXED CODE ###

N, A, B = map(int, input().split())
S = input()
count = 0
count2 = 0


for i in range(N):
    if S[i] == "c":
        print("No")
    elif S[i] == "a":
        
        if count < A+B:
            print("Yes")
            count += 1
        else:
            print("No")
    elif S[i] == "b":
        
        if count < A+B and count2 < B:
            print("Yes")
            count += 1
            count2 += 1
        else:
            print("No")
n = int(input())
alist = list(map(int,input().split()))
from collections import Counter
adic = Counter(alist)
count = 0
for k,v in adic:
  if int(k) <= v:
    count+=(v-int(k))
  else:
    count+=v
print(count)

### FIXED CODE ###

n = int(input())
alist = list(map(int,input().split()))
from collections import Counter
adic = Counter(alist)
count = 0
for k,v in adic.items():
  if int(k) <= v:
    count+=(v-int(k))
  else:
    count+=v
print(count)
'''
    Auther: ghoshashis545 Ashis Ghosh
    College: jalpaiguri Govt Enggineerin College
    Date:24/03/2020
'''

def main():
    
    # for _ in range(ii()):
    n=int(input())
    a=list(map(int,input().split()))
    f=0
    for i in a:
        if(i%2==0);
            if(i%3!=0 or i%5!=0):
                f=1
                break
    if(f):
        print('DENIED')
    else:
        print('APPROVED')
        
















    
    
if __name__ =="__main__":
    main()

### FIXED CODE ###

'''
    Auther: ghoshashis545 Ashis Ghosh
    College: jalpaiguri Govt Enggineerin College
    Date:24/03/2020
'''

def main():
    
    # for _ in range(ii()):
    n=int(input())
    a=list(map(int,input().split()))
    f=0
    for i in a:
        if(i%2==0):
            if(i%3!=0 and i%5!=0):
                f=1
                break
    if(f):
        print('DENIED')
    else:
        print('APPROVED')
        
















    
    
if __name__ =="__main__":
    main()
A,B,C,D = map(int,input().split())

import math
def lcm(x, y):
    return (x * y) // math.gcd(x, y)
s = lcm(C,D)
X =  A - (A//C + A //D - A//s)
Y =  B - (B//C + B //D - B//s)
print(Y-X)

### FIXED CODE ###

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

import fractions

def f(N):
    red = N//C
    red += N//D
    X = (C * D // fractions.gcd(C, D))
    red -= N//X
    return N - red

ans = f(B) - f(A-1)
print(ans)
A, B = map(int, input().split())

if (A*B) % 2 == 0:
  print(Even)
else:
  print(Odd)

### FIXED CODE ###

A, B = map(int, input().split())
 
if (A*B) % 2 == 0:
  print('Even')
else:
  print('Odd')
# -*- coding: utf-8 -*-

n = input(n)
a = input(a)

print(n*n-a)


### FIXED CODE ###

# -*- coding: utf-8 -*-

n = int(input())
a = int(input())

print(n*n-a)
import fractions
 
n, m = map(int, input().split())
a = list(map(int, input().split()))
def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)
 
def lcm(x, y):
	return (x * y) // gcd(x, y)
 
now = a[0]
for i in range(1, n):
	now = lcm(now, a[i])
    if now > m:
		print(0)
		exit(0)
 
for i in range(n):
	if (now//a[i])%2 == 0:
		print(0)
		exit(0)
 
print(((m//(now//2))+1)//2)

### FIXED CODE ###

import fractions

n, m = map(int, input().split())
a = list(map(int, input().split()))
def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)

def lcm(x, y):
	return (x * y) // gcd(x, y)

now = a[0]
for i in range(1, n):
	now = lcm(now, a[i])
	if now > 2 * m:
		print(0)
		exit(0)

for i in range(n):
	if (now//a[i])%2 == 0:
		print(0)
		exit(0)

print(((m//(now//2))+1)//2)
from bisect import bisect_left
N,K=map(int, input().split())
A=list(map(int, input().split()))
p=10**9+7
A=sorted(A)
thresh=bisect_left(A,0)
minus=A[:thresh]
plus=A[thresh:][::-1]

#print(plus, minus)
if len(plus)==0:
    ans=1
    if K%2!=0:
        minus=minus[::-1]
        for i in range(K):
            ans*=minus[i]
            ans%=p
    else:
        for i in range(K):
            ans*=minus[i]
            ans%=p
    print(ans)
    exit()

if len(minus)==0:
    ans=1
    for i in range(K):
        ans*=plus[i]
        ans%=p
    print(ans)
    exit()

midx=0
pidx=0
ans=1

while K>0 and (0<=midx<len(minus) or 0<=pidx<len(plus)):
    if midx==len(minus)-1:
        nexmin=minus[midx]
    elif midx>=len(minus):
        nexmin=-1
    else:
        nexmin=minus[midx]*minus[midx+1]

    if pidx==len(plus)-1:
        nexplus=plus[pidx]
        fact=newplus
    elif pidx>=len(plus):
        nexplus=-float("INF")
        fact=nexplus
    else:
        #if plus[pidx+1]!=0:
        #    nexplus=plus[pidx]*plus[pidx+1]
        #else:
        #    nexplus=plus[pidx]
        nexplus=plus[pidx]*plus[pidx+1]
        fact=plus[pidx]

    if nexmin>=nexplus and K>=2:
        ans*=nexmin
        ans%=p
        midx+=2
        K-=2
    else:
        ans*=fact
        ans%=p
        pidx+=1
        K-=1


print(ans)



### FIXED CODE ###

from bisect import bisect_left
N,K=map(int, input().split())
A=list(map(int, input().split()))
p=10**9+7
A=sorted(A)
thresh=bisect_left(A,0)
minus=A[:thresh]
plus=A[thresh:][::-1]

#print(plus, minus)
if len(plus)==0:
    ans=1
    if K%2!=0:
        minus=minus[::-1]
        for i in range(K):
            ans*=minus[i]
            ans%=p
    else:
        for i in range(K):
            ans*=minus[i]
            ans%=p
    print(ans)
    exit()

if len(minus)==0:
    ans=1
    for i in range(K):
        ans*=plus[i]
        ans%=p
    print(ans)
    exit()

midx=0
pidx=0
ans=1

while K>0 and (0<=midx<len(minus) or 0<=pidx<len(plus)):
    if midx==len(minus)-1:
        nexmin=minus[midx]
    elif midx>=len(minus):
        nexmin=-1
    else:
        if K>=2:
            nexmin=minus[midx]*minus[midx+1]
        else:
            nexmin=minus[midx]

    if pidx==len(plus)-1:
        nexplus=plus[pidx]
        fact=nexplus
    elif pidx>=len(plus):
        nexplus=-float("INF")
        fact=nexplus
    else:
        #if plus[pidx+1]!=0:
        #    nexplus=plus[pidx]*plus[pidx+1]
        #else:
        #    nexplus=plus[pidx]
        if K>=2:
            nexplus=plus[pidx]*plus[pidx+1]
        else:
            nexplus=plus[pidx]
        fact=plus[pidx]

    if nexmin>=nexplus:
        ans*=nexmin
        ans%=p
        midx+=2
        K-=2
    else:
        ans*=fact
        ans%=p
        pidx+=1
        K-=1


print(ans)