Harryxun/stf_run huggingface dataset:
n=0
s=[]
ans=[]

def dfs(a,b,c,i,root):
    if i==n:
        global ans
        ans=root.copy()
        return True
    l=False
    r=False
    if s[i]=='AB':
        if a>0:
            root.append('B')
            l=dfs(a-1,b+1,c,i+1,root)
            root.pop()
        if b>0:
            root.append('A')
            r=dfs(a+1,b-1,c,i+1,root)
            root.pop()
    elif s[i]=='AC':
        if a>0:
            root.append('C')
            l=dfs(a-1,b,c+1,i+1,root)
            root.pop()
        if c>0:
            root.append('A')
            r=dfs(a+1,b,c-1,i+1,root)
            root.pop()
    else:
        if b>0:
            root.append('C')
            l=dfs(a,b-1,c+1,i+1,root)
            root.pop()
        if c>0:
            root.append('B')
            r=dfs(a,b+1,c-1,i+1,root)
            root.pop()
    return l or r

n,a,b,c=map(int,input().split())
s=['']*n
for i in range(n):
    s[i]=input()
flag=dfs(a,b,c,0,[])

if flag:
    print("Yes")
    for t in ans:
        print(t)
else:
    print("No")

### FIXED CODE ###

n,a,b,c=map(int,input().split())
s=[]
for i in range(n):
    s.append(input())
s.append('EOF')

ans=[]
 
flag=True
 
for i in range(n):
    if s[i]=='AB':
        if a==0 and b==0:
            flag=False
            break
        if a==0 or (b!=0 and a==1 and s[i+1]=='AC'):
            ans.append('A')
            a+=1
            b-=1
        else:
            ans.append('B')
            a-=1
            b+=1
    elif s[i]=='AC':
        if a==0 and c==0:
            flag=False
            break
        if a==0 or (c!=0 and a==1 and s[i+1]=='AB'):
            ans.append('A')
            a+=1
            c-=1
        else:
            ans.append('C')
            a-=1
            c+=1
    else:
        if c==0 and b==0:
            flag=False
            break
        if c==0 or (b!=0 and c==1 and s[i+1]=='AC'):
            ans.append('C')
            c+=1
            b-=1
        else:
            ans.append('B')
            c-=1
            b+=1

if flag:
    print("Yes")
    for i in ans:
        print(i)
else:
    print("No")
str = input('')
start = str[:1]
end = str[-1:]
print(start + (len(str) - 2) + end)

### FIXED CODE ###

input_str = input('')
start = input_str[:1]
end = input_str[-1:]
print(start + str((len(input_str) - 2)) + end)
h,w=map(int,input().split())
list2=[[0 for i in range(w)]for j in range(h)]
list1 =  [input().split() for _ in range(h)]
dx=[-1,-1,-1,0,0,1,1,1]
dy=[-1,0,1,-1,1,-1,0,1]
for j in range(h):
  for i in range(w):
   if list1[j][i]=="#":
    for k in range(8):
     xk=i+dx[k]
     yk=j+dy[k]
     if xk>=0 and xk<w and yk>=0 and yk<h:
      list2[yk][xk]+=1
for j in range(h):
  for i in range(w):
    if list1[j][i]=="#":
      list2[j][i]="#"
    else:
      list2[j][i]=str(list2[j][i])
for j in range(h):
 print("".join(list2[j]))

### FIXED CODE ###

h,w=map(int,input().split())
list1=[[0 for i in range(w)]for j in range(h)]
list2=[[0 for i in range(w)]for j in range(h)]
dx=[-1,-1,-1,0,0,1,1,1]
dy=[-1,0,1,-1,1,-1,0,1]
for j in range(h):
 s=input()
 for i in range(w):
  list1[j][i]=s[i]
for j in range(h):
  for i in range(w):
   if list1[j][i]=="#":
    for k in range(8):
     xk=i+dx[k]
     yk=j+dy[k]
     if xk>=0 and xk<w and yk>=0 and yk<h:
      list2[yk][xk]+=1
for j in range(h):
  for i in range(w):
    if list1[j][i]=="#":
      list2[j][i]="#"
    else:
      list2[j][i]=str(list2[j][i])
for j in range(h):
 print("".join(list2[j]))
n=int(input())
a=list(map(int,input().split()))
q=int(input())
sum=sum(a)
a2,a3=[],[]
import bisect as bs

for i in set(a):
    a2.append(i)
    a3.append(a.count(i))

#print(sum)
#print(a2,a3)

def idx(l,x):
    return bs.bisect_left(l,x)

for i in range(q):
    b,c=map(int,input().split())
    if b in a2:
        b_idx=idx(a2,b)
        if c in a2:
            c_idx=idx(a2,c)
        else:
            a2.append(c)
            a3.append(0)
            c_idx=-1
        sum+=(c-b)*a3[b_idx]
        a3[c_idx]+=a3[b_idx]
        a3[b_idx]=0
#    print(a2,a3)
    print(sum)

### FIXED CODE ###

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

count=[0]*(10**5+1)

for i in a:
    count[i]+=1

for i in range(q):
    b,c=map(int,input().split())
    if count[b]!=0:
        sum+=(c-b)*count[b]
        count[c]+=count[b]
        count[b]=0
    print(sum)
#!/usr/bin/env python3
    import sys
    import math

    def make_divisors(n):
        divisors = []
        for i in range(1, int(n**0.5)+1):
            if n % i == 0:
                divisors.append(i)
                if i != n // i:
                    divisors.append(n//i)
        # divisors.sort()
        return divisors

    def lef(a, b):
        return a*a*a*a + a*a*a*b + a*a*b*b + a*b*b*b + b*b*b*b

    def solve(X: int):
        divs = make_divisors(X)
        for d in divs:
            upper = X // d
            
            base = 0
            while(lef(base+d,base) < upper):
                base+=1
            if lef(base+d,base) == upper:
                print(base+d,base)
                return

            base = -(d//2)
            while(lef(base+d,base) < upper) and (base > d-1):
                base -= 1
            if lef(base+d, base) == upper:
                print(base+d, base)
                return

            base = -d
            while(lef(base+d,base) < upper) and (base < -(d//2)+1):
                base += 1
            if lef(base+d, base) == upper:
                print(base+d, base)
                return
    
            base = -d-1
            while(lef(base+d,base) < upper):
                base -= 1
            if lef(base+d, base) == upper:
                print(base+d, base)
                return
        # raise
        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()
        X = int(next(tokens))  # type: int
        solve(X)

    if __name__ == '__main__':
        main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

def solve(X: int):

    for i in range(-150, 150):
        for j in range(-150, 150):
            if j**5 - i**5 == X:
                print(j, i)
                return
    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()
    X = int(next(tokens))  # type: int
    solve(X)

if __name__ == '__main__':
    main()
const int limit = 50;

int n, m;
int a[limit], b[limit];

bool graph[limit][limit];
bool visited[limit];

void dfs(int v){
    visited[v] = true;
    for (int v2=0; v2<n;++v2){
        if (graph[v][v2]==false) continue;
        if (visited[v2]==true) continue;
        dfs(v2);
    }
}

int main(void){
    cin >> n >> m;
    for (int i=0; i<m; ++i){
        graph[a[i]][b[i]] = graph[b[i]][a[i]] = false;
        for (int j=0; j<n; ++j) visited[j] = false;
        dfs(0);
        bool bridge = false;
        for (j=0; j<n; ++j) if (visited[j] == false) bridge = true;
        if (bridge) ans += 1;
        graph[a[i]][b[i]] = graph[b[i]][a[i]] = true;
        }
    cout << ans << endl;
    return 0;
    }

### FIXED CODE ###

n, m = map(int, input().split())
edges = [list(map(int, input().split())) for i in range(m)]
ans = 0
for x in edges:
    l = list(range(n))
    for y in edges:
        if y != x:
            l = [l[y[0]-1] if l[i] == l[y[1]-1] else l[i] for i in range(n)]
    if len(set(l)) != 1:
        ans += 1
print(ans)
S = list(str.imput())

if S[2] == S[3]:
  if S[4] == S[5]:
    print("Yes")
  else:
    print("No")
else:
  print("No")


### FIXED CODE ###

S = list(input())

if S[2] == S[3]:
  if S[4] == S[5]:
    print("Yes")
  else:
    print("No")
else:
  print("No")
H, W = (int(i) for i in input().split())
t = []
t.append(['.']*(H+2))

for j in range(H):
	tmp = input()
	tmp = '.' + tmp + '.'
	t.append(list(tmp))

t.append(['.']*(H+2))

def CheckBlock(i,k):
	if t[i][k-1] == '#': #check up
		return 0
	elif t[i-1][k] == '#': #check left
		return 1
	elif t[i+1][k] == '#': #check right
		return 2
	elif t[i][k+1] == '#': #check down
		return 3
	else:
		return 4

for i in range(1,W+1):
	for k in range(1,H+1):
		if t[i][k] == '#':
			marker = CheckBlock(i,k)
			if marker == 4:
				print('No')
				quit()
print('Yes')

### FIXED CODE ###

H, W = (int(i) for i in input().split())
t = []
t.append(['.']*(H+2))

for j in range(H):
	tmp = input()
	tmp = '.' + tmp + '.'
	t.append(list(tmp))

t.append(['.']*(H+2))

def CheckBlock(i,k):
	if t[i][k-1] == '#': #check up
		return 0
	elif t[i-1][k] == '#': #check left
		return 1
	elif t[i+1][k] == '#': #check right
		return 2
	elif t[i][k+1] == '#': #check down
		return 3
	else:
		return 4

for k in range(1,W+1):
	for i in range(1,H+1):
		if t[i][k] == '#':
			marker = CheckBlock(i,k)
			if marker == 4:
				print('No')
				quit()
print('Yes')
n,m=map(int,input().split())
a=[]
for i in range(0,m):
    a[i] = input()
    n-=a[i]
if n<=0:
    print(-1)
else:
    print(n)

### FIXED CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in range(0,m):
    n-=a[i]
if n<0:
    print(-1)
else:
    print(n)
n,x=map(int,input().split())
a=list(input().split())
count=0
d=0
i=0
while d<=x:
    if i==0:
        d=0
        if d<=x:
            count=1
        i+=1
    elif count<=n+1:
        d=d+int(a[i-1])
        if d<=x:
            count+=1
            i+=1
        else:
            break;
    else:
        break;
print(count)

### FIXED CODE ###

n,x=map(int,input().split())
a=list(input().split())
count=0
d=0
i=0

while d<=x:
    if i==0:
        d=0
        count=1
        i+=1
    elif count<=n+1 and i<n+1:
        d=d+int(a[i-1])
        if d<=x:
            count+=1
            i+=1
        else:
            break;
    else:  
        break;
print(count)
n,q=map(int,input().split())
s=input()
retsu=[]
for i in range(len(s)):
  if s[i]=="A" and s[i+1]=="C":
    retsu.append(i+1)
#print(retsu)
#ここまではあってる

for i in range(q):
  temp=set(retsu)
  l,r=map(int,input().split())
  hani=set(range(l,r))
  #print(hani)
  hani&=temp

  print(len(hani))

### FIXED CODE ###

n,q=map(int,input().split())
s=input()
hantei=[0]
for i in range(1,len(s)):
  if s[i-1]=="A" and s[i]=="C":
    hantei.append(hantei[i-1]+1)
  else:
    hantei.append(hantei[i-1])
#print(hantei)
#ここまではあってる

for i in range(q):
  l,r=map(int,input().split())
  print(hantei[r-1]-hantei[l-1])
X = int(input())

item_value = [100, 101, 102, 103, 104, 105]
dp = [0] * (X + 1)
for value in item_value:
    dp[value] = 1

for i in range(200, X + 1):
    for value in item_value:
        if dp[i - value] == 1:
            dp[i] = 1

print(dp[X])

### FIXED CODE ###

X = int(input())

item_value = [100, 101, 102, 103, 104, 105]
dp = [0] * (100001)
for value in item_value:
    dp[value] = 1

for i in range(200, X + 1):
    for value in item_value:
        if dp[i - value] == 1:
            dp[i] = 1

print(dp[X])
import math
N,M = map(int,input().split())
S = input()
T = input()

flag = True
for n in range(N):
    if M*n%N==0:
        m = M*n//N
        flag = S[n]==T[m]
        if not flag:
            break
if flag:
    print(N*M//math.gcd(N,M))
else:
    print(-1)


### FIXED CODE ###

def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
    
N,M = map(int,input().split())
s = input()
t = input()
g = gcd(N,M)
l = N*M//g

n = N//g
m = M//g

ans = l

for i in range(g):
    if s[i*n]!=t[i*m]:
        ans = -1
        break
print(ans)
N,M=map(int, input().split())

sc = []
for i in range(m):
    sc.append(list(map(int, input().split())))
for i in range(10**N):
    anc = str(i)
    if len(ans) == N and all(ans[s-1] == str(c) for s,c in sc):
        print(ans)
        quit()
print(-1)

### FIXED CODE ###

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

sc = []
for i in range(M):
    sc.append(list(map(int, input().split())))
for i in range(10**N):
    ans = str(i)
    if len(ans) == N and all(ans[s-1] == str(c) for s,c in sc):
        print(ans)
        quit()
print(-1)
from math import ceil
N, K = map(int,input().split())
A = list(map(int,input().split()))
def chk(L):
    cnt = 0
    for i in range(N):
        cnt += ceil(A[i]/L)-1
    return cnt <= K
l, r = 1, max(A)
while l <= r:
    m = (l+r)//2
    if chk(m):
        r = m-1
    else:
        l = m+1
print(max([x for x in [l-1, l, l+1, r-1,r,r+1, m-1,m,m+1] if chk(x)]))

### FIXED CODE ###

from math import ceil
N, K = map(int,input().split())
A = list(map(int,input().split()))
def chk(L):
    cnt = 0
    for i in range(N):
        cnt += ceil(A[i]/L)-1
    return cnt <= K
l, r = 1, max(A)
while l <= r:
    m = (l+r)//2
    if chk(m):
        r = m-1
    else:
        l = m+1
print(min([x for x in [m-1,m,m+1] if x > 0 and chk(x)]))
import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline
#sys.setrecursionlimit(10**8)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


def main():
    a = gete(int)
    s = gete()

    if s < 3200:
        print(a)
    else:
        print('red')


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline
#sys.setrecursionlimit(10**8)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


def main():
    a = gete(int)
    s = gete()

    if a < 3200:
        print('red')
    else:
        print(s)


if __name__ == "__main__":
    main()
N = int(input())
v =  list(map(int,input().split()))

for i in N:

    titi = max(v)
    haha = min(v)

    v.remove(titi)
    v.remove(haha)

    son = (titi + haha)/2 

    v.add(son)

res = v[0] 
print(str(res))


### FIXED CODE ###

N = int(input())
v = list(map(int,input().split()))

v.sort()

son = v[0]

for i in range(1,len(v)):
	son = (v[i] + son)/2

print(son)
n = int(input())
count = 0
 
for i in range(1,n+1):
  if len(int(i))%2 == 1:
    count += 1
 
print(count)

### FIXED CODE ###

a,b,c = map(int, input().split())
 
if b+c > a :
  print(c-(a-b))
  
else:
  print(0)
a = 1
b = 2
c = 3
d = 4
e = 5
a,b,c,d,e = map(int,input().split())
if a != 1:
print(1)

if b != 2:
print(2)

if c != 3:
print(3)

if d != 4:
print(4)

if e != 5:
print(5)

### FIXED CODE ###

a = 1
b = 2
c = 3
d = 4
e = 5
a,b,c,d,e = map(int,input().split())

if a != 1:
    print("1")

if b != 2:
    print("2")

if c != 3:
    print("3")

if d != 4:
    print("4")

if e != 5:
    print("5")
n,l,T = map(int,input().split())
s = [0 for i in range(n)]
for i in range(n):
    s[i] = list(map(int, input().split()))

def f(w):
    if w == 1:
        return 1
    elif w == 2:
        return -1
    
t = 0
d = l

while t < T:
    for i in range(n):
        if i < n-1 :
            if s[i][0] < s[i+1][0] and s[i][1] == 1 and s[i+1][1] == 2:
                if s[i+1][0] - s[i][0] < d:
                    d = s[i+1][0] - s[i][0]
    
            elif s[i][0] > s[i+1][0] and s[i][1] == 1 and s[i+1][1] == 2:
                if s[i+1][0] + l - s[i][0] < d:
                    d = s[i+1][0] + l - s[i][0]
                    
        elif i == n-1:
            if s[i][0] < s[0][0] and s[i][1] == 1 and s[0][1] == 2:
                if s[0][0] - s[i][0] < d:
                    d = s[0][0] - s[i][0]
                    
            elif s[i][0] > s[0][0] and s[i][1] == 1 and s[0][1] == 2:
                if s[0][0] + l - s[i][0] < d:
                    d = s[0][0] + l - s[i][0]
                    
                    
    for j in range(n):
        if t + d/2 <= T:
            s[j][0] += f(s[j][1]) * (d/2)
            if s[j][0] >= l:
                s[j][0] -= l
            elif s[j][0] < 0:
                s[j][0] += l
            
        else:
            s[j][0] += f(s[j][1]) * (T-t)
            if s[j][0] >= l:
                s[j][0] -= l
            elif s[j][0] < 0:
                s[j][0] += l
        if j > 0 and s[j][0] == s[j-1][0]:
            s[j][1], s[j-1][1] = s[j-1][1], s[j][1]
        if j == n-1 and s[j][0] == s[0][0] :
            s[j][1], s[0][1] = s[0][1], s[j][1]
            
    t = t + d/2
    i_d.clear()
    d = l
    
import math

for i in range(n):
    print(math.floor(s[i][0]))

### FIXED CODE ###

from math import floor
n,l,t = map(int,input().split())
ants = []
touch = 0

for i in range(n):
    x, w = map(int,input().split())
    if w == 1:
        touch += (x + t) // l
        x1 = (x + t) % l
    else:
        touch += (x - t) // l
        x1 = (x - t) % l
    ants.append(x1)
touch = touch % n
ants.sort()
ants = ants[touch:]+ants[:touch]

for i in range(n):
    print(ants[i])
N=int(input())
S=input()
s=0
s+=S.count('R')*S.count('G')*S.count('B')
for i in range(N):
  for j in range(i+1,j):
    k=2*j-i
    if k<n and S[i]!=S[j] and S[j]!=S[k] and S[k]!=S[i]:
      s-=1
print(s)      

### FIXED CODE ###

N=int(input())
S=input()
s=0
s+=S.count('R')*S.count('G')*S.count('B')
for i in range(N):
  for j in range(i+1,N):
    k=2*j-i
    if k<N and S[i]!=S[j] and S[j]!=S[k] and S[k]!=S[i]:
      s-=1
print(s)
def reads(offset = 0):
	return [int(i) - offset for i in input().split(' ')]
def Judge(vector):
	length = len(vector)-1
	for i in range(length):
		if(vector[i] > vector[i+1]):		
			return 0
	return 1
(N, M) = reads()
Q = int(input())
A = reads(1)
pos = [-1] * M
pat = []
freq = [0] * (M+1)
freq[0] = N
found = set()
for i in A[::-1]:
	if (i not in found):
		pat.append(i)
		found.add(i)
		pos[i] = counter
for i in range(M):
	if (pos[i] == -1):
		pat.append(i)		
for i in A[::-1]:
	temp = pos[i]
	if (freq[temp] > 0):
		freq[temp] -= 1
		freq[temp+1] += 1
for i in range(M+1):
	if (freq[i] != 0):
		start = i
		break
print("Yes") if Judge(pat[start:]) else print("No")

### FIXED CODE ###

def reads(offset = 0):
	return [int(i) - offset for i in input().split(' ')]
def Judge(vector):
	length = len(vector)-1
	for i in range(length):
		if(vector[i] > vector[i+1]):		
			return 0
	return 1
(N, M) = reads()
Q = int(input())
A = reads(1)
pos = [-1] * M
pat = []
freq = [0] * (M+1)
freq[0] = N
found = set()
counter = 0
for i in A[::-1]:
	if (i not in found):
		pat.append(i)
		found.add(i)
		pos[i] = counter
		counter += 1
		if(counter == M):
			break
for i in range(M):
	if (pos[i] == -1):
		pat.append(i)	
for i in A[::-1]:
	temp = pos[i]
	if (freq[temp] > 0):
		freq[temp] -= 1
		freq[temp+1] += 1
start = M
for i in range(M):
	if (freq[i] != 0):
		start = i
		break
print("Yes") if Judge(pat[start:]) else print("No")
N,K=map(int,input().split())
A=list(map(int,input().split()))
X=[1]
for i in range(K):
    x=X[-1]
    if A[x-1] in X:
        q=X.index(A[x-1])
        p=i-q+1
        break
    else:
        X.append(A[x-1])
X=X[q:]
print(X[(K-q)%p])


    

        




    















    



    





    






        






    
















        


























            
    


    


    
    














    


    














### FIXED CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
l=[1]
X=[True]*N
X[0]=False
num=1
for i in range(K):
    num=A[num-1]
    if X[num-1]:
        l.append(num)
        X[num-1]=False
    else:
        q=l.index(num)
        l=l[q:]
        print(l[(K-q)%len(l)])
        exit()
print(l[-1])
a,b,t=map(input().split())
ans=0.0
ans=int(((t+0.5)//a)*b)
print(ans)

### FIXED CODE ###

a,b,t=map(int,input().split())
ans=int(((t+0.5)//a)*b)
print(ans)
from math import *

def main():
    m, n = [int(_) for _ in input().split()]
    print(pow(m, n, 1000000007))

main()



### FIXED CODE ###

def main():
    m, n = [int(_) for _ in input().split()]
    print(pow(m, n, 1000000007))

main()
a, b = map(int, input().split())
int s = a*b
if s%2==0:
  print('Even')
else:
  print('Odd')


### FIXED CODE ###

a, b = map(int, input().split())
s = a*b
if s%2==0:
  print('Even')
else:
  print('Odd')
n=int(input('N'))
if n<10 or n>0:
    combination=n*n*n
    print(combination)
else:
    break

### FIXED CODE ###

N=int(input())
n= N*N*N
print(n)
import heapq
 
mod=10**9+7
n,k=map(int,input().split())
arr=list(map(int,input().split()))
q=[]
cnt_plus=0
for i in range(n):
  if arr[i]>0:
    cnt_plus+=1
    heapq.heappush(q,(-arr[i],1))
  elif arr[i]<0:
    heapq.heappush(q,(arr[i],-1))
  else:
    heapq.heappush(q,(0,0))
pick=[]
prev_plus
prev_minus=0
cnt=0
for i in range(k):
  tmp,flag=heapq.heappop(q)
  tmp*=-1
  if flag==0:
    print(0)
    exit()
  if flag==1:
    pick.append(tmp)
    prev_plus=tmp
  if flag==-1:
    if cnt==0:
      prev_minus=tmp
      cnt+=1
    else:
      cnt=0
      pick.append(prev_minus)
      pick.append(tmp)
if cnt==0:
  ans=1
  for i in range(k):
    ans*=pick[i]
    ans%=mod
  print(ans%mod)
else:
  cand_plus=0
  cand_minus=0
  while len(q)!=0:
    tmp,flag=heapq.heappop(q)
    tmp*=-1
    if flag==1 and cand_plus==0:
      cand_plus=tmp
    if flag==-1 and cand_minus==0:
      cand_minus=tmp
  if (k%2==1 and cnt_plus==0) or (cand_plus==0 and cand_minus==0):
    if arr.count(0)!=0:
      print(0)
      exit()
    else:
      q=[]
      for i in range(n):
        heapq.heappush(q,abs(arr[i]))
      ans=1
      for _ in range(k):
        ans*=heapq.heappop(q)
        ans%=mod
      print((-ans)%mod)
  else:
    if prev_plus*cand_plus>=prev_minus*cand_minus:
      pick.append(cand_plus)
    else:
      pick=pick[:-1]
      pick.append(prev_minus)
      pick.append(cand_minus)
    ans=1
    for i in range(k):
      ans*=pick[i]
      ans%=mod
    print(ans%mod)

### FIXED CODE ###

import heapq
 
mod=10**9+7
n,k=map(int,input().split())
arr=list(map(int,input().split()))
q=[]
cnt_plus=0
for i in range(n):
  if arr[i]>0:
    cnt_plus+=1
    heapq.heappush(q,(-arr[i],1))
  elif arr[i]<0:
    heapq.heappush(q,(arr[i],-1))
  else:
    heapq.heappush(q,(0,0))
pick=[]
prev_plus=0
prev_minus=0
cnt=0
for i in range(k):
  tmp,flag=heapq.heappop(q)
  tmp*=-1
  if flag==0:
    print(0)
    exit()
  if flag==1:
    pick.append(tmp)
    prev_plus=tmp
  if flag==-1:
    if cnt==0:
      prev_minus=tmp
      cnt+=1
    else:
      cnt=0
      pick.append(prev_minus)
      pick.append(tmp)
if cnt==0:
  ans=1
  for i in range(k):
    ans*=pick[i]
    ans%=mod
  print(ans%mod)
else:
  cand_plus=0
  cand_minus=0
  while len(q)!=0:
    tmp,flag=heapq.heappop(q)
    tmp*=-1
    if flag==1 and cand_plus==0:
      cand_plus=tmp
    if flag==-1 and cand_minus==0:
      cand_minus=tmp
  if (k%2==1 and cnt_plus==0) or (cand_plus==0 and cand_minus==0):
    if arr.count(0)!=0:
      print(0)
      exit()
    else:
      q=[]
      for i in range(n):
        heapq.heappush(q,abs(arr[i]))
      ans=1
      for _ in range(k):
        ans*=heapq.heappop(q)
        ans%=mod
      print((-ans)%mod)
  else:
    if prev_plus*cand_plus>=prev_minus*cand_minus:
      pick.append(cand_plus)
    else:
      if prev_plus!=0:
        pick.remove(prev_plus)
        pick.append(prev_minus)
        pick.append(cand_minus)
      else:
        pick.append(cand_plus)
    ans=1
    for i in range(k):
      ans*=pick[i]
      ans%=mod
    print(ans%mod)