Harryxun/stf_run huggingface dataset:
N = int(input())
alist = list(map(int, input().split()))
left = 0
for i in range(1, N + 1):
    try:
        old_left = left
        left = alist[left:].index(i)
        p = left + old_left
    except ValueError:
        print(i, p)
        if i == 1:
            print(-1)
        else:
            print(N - i + (N - p))
        break
else:
    print(0)


### FIXED CODE ###

N = int(input())
alist = list(map(int, input().split()))
now = 1
for a in alist:
    if a == now:
        now += 1
if now == 1:
    print(-1)
else:
    print(N - now + 1)
s = input()
for i in list(s):
  print(x,end="")

### FIXED CODE ###

s = input()
print("x" * len(s))
n,k = map(int,input().split())
a = list(map(int,input().split()))

len_a=len(str(bin(max(a))))-2
len_k=len(str(bin(k)))-2

if len_a >= len_k:
  length =len_a
  for i in range(n):
    a[i] = ("0"*1000+str(bin(a[i]))[2:])[-len_a:] 
elif len_a < len_k:
  length =len_k
  for i in range(n):
    a[i] = ("0"*1000+str(bin(a[i]))[2:])[-len_k:]
    
k = ("0"*1000+str(bin(k))[2:])[-length:]

flag = False
for i in range(length):
  count_0 =0
  count_1 =0
  for j in range(n):
    if a[j][i]=="0":
      count_0 += 1
    else:
      count_1 += 1
  #print(count_0,count_1)
  if count_0 <= count_1 and k[i]=="1":
    if i==0:   
      k="0"+k[1:i]
    elif i == length - 1:
      k= k[0:i]+"0"
    else:
      k= k[0:i]+"0"+k[i+1:]
    flag = True
  elif count_0 > count_1 and k[i]=="0" and flag:
    if i==0:   
      k="1"+k[1:i]
    elif i == length - 1:
      k= k[0:i]+"1"
    else:
      k=k[0:i]+"1"+k[i+1:]
ans = 0
for i in range(n):
  for j in range(length):
    if a[i][j]!=k[j]:
      ans +=2**(length-1-j)
print(ans)
    

### FIXED CODE ###

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

len_a=len(str(bin(max(a))))-2
len_k=len(str(bin(k)))-2

if len_a >= len_k:
  length =len_a
  for i in range(n):
    a[i] = ("0"*length+str(bin(a[i]))[2:])[-len_a:] 
elif len_a < len_k:
  length =len_k
  for i in range(n):
    a[i] = ("0"*length+str(bin(a[i]))[2:])[-len_k:]
    
k = ("0"*length+str(bin(k))[2:])[-length:]

flag = False
for i in range(length):
  count_0 =0
  count_1 =0
  for j in range(n):
    if a[j][i]=="0":
      count_0 += 1
    else:
      count_1 += 1
  #print(count_0,count_1)
  if count_0 <= count_1 and k[i]=="1":
    if i==0:   
      k="0"+k[1:length]
    elif i == length - 1:
      k= k[0:i]+"0"
    else:
      k= k[0:i]+"0"+k[i+1:]
    flag = True
  elif count_0 > count_1 and k[i]=="0" and flag:
    if i==0:   
      k="1"+k[1:length]
    elif i == length - 1:
      k= k[0:i]+"1"
    else:
      k=k[0:i]+"1"+k[i+1:]
      
ans = 0
for i in range(n):
  for j in range(length):
    if a[i][j]!=k[j]:
      ans +=2**(length-1-j)
print(ans)
import math

# define
a = [0] * int(1e5 + 100)
# functions
# main

n, m = (int(s) for s in input().split())

inp = input().split()
for i in range(1, n + 1) :
    a[i] = int(inp[i - 1])

flag = False
lcm = a[1]

for i in range(1, n + 1) :
    gcd = math.gcd(lcm, a[i])
    lcm = int(lcm * a[i] / gcd)
    if(lcm > m):
        flag = True
        break
exit()
for i in range (1, n + 1):
    if lcm / a[i] % 2 == 0 : flag = True

if flag or lcm > m : print(0)
else : print(int( (m - int(lcm / 2)) / lcm ) + 1)


### FIXED CODE ###

# define
a = [0] * int(1e5 + 100)
# functions
def _gcd(a, b):
    if a % b == 0 : return b
    if b % a == 0 : return a
    while a != 1 and b != 1:
        if a > b: a %= b
        else : b %= a
        if a % b == 0: return b
        if b % a == 0: return a
# main

n, m = (int(s) for s in input().split())

inp = input().split()
for i in range(1, n + 1) :
    a[i] = int(inp[i - 1])

flag = False
lcm = a[1]

for i in range(2, n + 1) :
    gcd = _gcd(lcm, a[i])
    lcm = int(lcm * a[i] / gcd)
    if(lcm > 2 * m):
        flag = True
        break

for i in range (1, n + 1):
    if int(lcm / a[i]) % 2 == 0 : flag = True

if flag : print(0)
else : print(int( (m - int(lcm / 2)) / lcm ) + 1)
n = int(input())
k = int(input())
x = list(map(int,input().split()))
ans = 0

for i in x:
  ans += min(abs(x-k),x)
  
print(ans)

### FIXED CODE ###

n = int(input())
k = int(input())
x = list(map(int,input().split()))
ans = 0

for i in x:
  ans += min(abs(i-k),i)*2
  
print(ans)
from collections import deque
import heapq

def dijkstra(s,g):
    color=[0]*n
    dis={}
    for i in xrange(n):
        dis[i]=float('inf')
    dis[s]=0
    heapq.heappush(pq,[0,s])
    while len(pq)!=0:
        t,u=heapq.heappop(pq)
        color[u]=2
        if dis[u]<t:
            continue
        for v,c in g[u]:
            if color[v]!=2:
                if dis[u]+c<dis[v]:
                    dis[v]=dis[u]+c
                    color[v]=1
                    heapq.heappush(pq,[dis[v],v])
    return dis

n,m,c=map(int,raw_input().split())
g=[[] for _ in xrange(n)]
totalcost=0
for i in xrange(m):
    a,b,d=map(int,raw_input().split())
    g[a-1].append([b-1,d])
    g[b-1].append([a-1,d])
    totalcost+=d

pq=[]
dis=dijkstra(0,g,cost)
dis=sorted(dis.items(), key=lambda x:x[1])

ans=float('inf')
visited=[0]*n
for u,x in dis:
    visited[u]=1
    for v,c in g[u]:
        if visited[v]==1:
            totalcost-=c
    ans=min(ans,totalcost+c*x)
print ans

### FIXED CODE ###

import heapq

def dijkstra(s,g):
    color=[0]*n
    dis={}
    for i in xrange(n):
        dis[i]=float('inf')
    dis[s]=0
    heapq.heappush(pq,[0,s])
    while len(pq)!=0:
        t,u=heapq.heappop(pq)
        color[u]=2
        if dis[u]<t:
            continue
        for v,cost in g[u]:
            if color[v]!=2:
                if dis[u]+cost<dis[v]:
                    dis[v]=dis[u]+cost
                    color[v]=1
                    heapq.heappush(pq,[dis[v],v])
    return dis

n,m,c=map(int,raw_input().split())
g=[[] for _ in xrange(n)]
totalcost=0
for i in xrange(m):
    a,b,d=map(int,raw_input().split())
    g[a-1].append([b-1,d])
    g[b-1].append([a-1,d])
    totalcost+=d

pq=[]
dis=dijkstra(0,g)
dis=sorted(dis.items(), key=lambda x:x[1])

ans=float('inf')
visited=[0]*n
for u,x in dis:
    visited[u]=1
    for v,cost in g[u]:
        if visited[v]==1:
            totalcost-=cost
    ans=min(ans,totalcost+c*x)
print ans
s = sorted(list(input()))
t = sorted(list(input()),reverse=True)
if str(s) < str(t):
  print("Yes")
else:
  print("No")


### FIXED CODE ###

a,b = map(int,input().split())
print((a+b+1)//2)
S = input()
T = input()

ans = "Yes"
s2t = {}
for s, t in zip([S, T]):
  if s == t:
    pass
  else:
    if s in s2t:
      if s2t[s] != t:
        ans = "No"
    else:
      s2t[s] = t

print(ans)


### FIXED CODE ###

import sys

input = sys.stdin.readline


def main():
    S = input().rstrip()
    T = input().rstrip()

    S_table = {}
    T_table = {}
    ans = "Yes"
    for s, t in zip(S, T):
        # S
        if s in S_table:
            if S_table[s] != t:
                ans = "No"
        else:
            S_table[s] = t
        # T
        if t in T_table:
            if T_table[t] != s:
                ans = "No"
        else:
            T_table[t] = s

    print(ans)


if __name__ == "__main__":
    main()
s = input() 
t = input()

print(t + s)

### FIXED CODE ###

s, t = input().split()
print(t+s)
S_dash = list(input())
M = len(S_dash)

T = list(input())
N = len(T)

match = [False for _ in range(M)]

last_match = -100
for i in range(M - N + 1):
    for j in range(N):
        if S_dash[i+j] == "?":
            continue
        elif S_dash[i+j] == T[j]:
            continue
        elif S_dash[i+j] != T[j]:
            break
    else:
        match[i] = True
        last_match = i
S = S_dash.copy()

if last_match == -100:
    print("UNRESTORABLE")
else:
    for i in range(N):
        S[last_match+i] = T[i]
    for i in range(M):
        if S[i] == "?":
            S[i] = "a"
    print("".join(str(x) for x in (S)))

### FIXED CODE ###


S_dash = list(input())
M = len(S_dash)

T = list(input())
N = len(T)

match = [False for _ in range(M)]

last_match = -100
for i in range(M - N + 1):
    for j in range(N):
        if S_dash[i+j] == "?":
            continue
        elif S_dash[i+j] == T[j]:
            continue
        elif S_dash[i+j] != T[j]:
            break
    else:
        match[i] = True
        last_match = i
S = S_dash.copy()

if last_match == -100:
    print("UNRESTORABLE")
else:
    for i in range(N):
        S[last_match+i] = T[i]
    for i in range(M):
        if S[i] == "?":
            S[i] = "a"
    print("".join(str(x) for x in (S)))
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,W=map(int,input().split())
    w,v=[0]*N,[0]*N
    for i in range(N):
        w[i],v[i]=map(int,input().split())
    if w[0]>3*N:
        w0=w[0]
        W=max(W//w0*3*N+W%w0,(3*N+3)*N)
        for i in range(N):
            w[i]-=w0
            w[i]+=3*N
    dp=[[0]*(W+1) for _ in range(N+1)]
    for i in range(N):
        for j in range(W+1):
            dp[i+1][j]=max(dp[i+1][j],dp[i][j])
            if j-w[i]>=0:
                dp[i+1][j]=max(dp[i+1][j],dp[i][j-w[i]]+v[i])
    print(dp[-1][-1])

if __name__ == '__main__':
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,W=map(int,input().split())
    w,v=[0]*N,[0]*N
    for i in range(N):
        w[i],v[i]=map(int,input().split())
    if w[0]>3*N:
        w0=w[0]
        W=min(W//w0*(3*N+1)+min(W%w0,3*N),(3*N+4)*N)
        for i in range(N):
            w[i]-=w0
            w[i]+=3*N+1
    dp=[[0]*(W+1) for _ in range(N+1)]
    for i in range(N):
        for j in range(W+1):
            dp[i+1][j]=max(dp[i+1][j],dp[i][j])
            if j-w[i]>=0:
                dp[i+1][j]=max(dp[i+1][j],dp[i][j-w[i]]+v[i])
    print(dp[-1][-1])

if __name__ == '__main__':
    main()
N, M = map(int, input().split())
G = [[] for _ in range(N+1)]

# weighted graph
for _ in range(M):
    l, r, d = map(int, input().split())
    G[l].append((r, d))
    G[r].append((l, -d))

cache = set(range(1, N+1))

# depth first search
def dfs(graph, start, visited=None):
    global cache  # for checking disconnected
    visited = visited or {}
    visited[start[0]] = start[1]
    cache.remove(start[0])
    for nxt, v in graph[start[0]]:
        nxt_value = start[1] + v
        if nxt in visited:
            if nxt_value != visited[nxt]:
                return False
            continue
        return dfs(graph, (nxt, nxt_value), visited)
    return True

# while len(cache)>0:
#     if not dfs(G, (list(cache)[0], 0)):
#         print('No')
#         break
# else:
#     print('Yes')

if dfs(G, (0, 0)):
    print('Yes')
else:
    print('No')

### FIXED CODE ###

x = int(input())
a = int(input())
b = int(input())
print((x-a)%b)
n,m=map(int,input().split())
while m>0:

### FIXED CODE ###

N,M = map(int, input().split())
A=[0]*N
for i in range(M):
    a,b=map(int,input().split())
    A[a-1] += 1
    A[b-1] += 1
for h in range(N):
    print(A[h])
def main():
    S = list(map(str,input().rstrip()))
    l = len(S)
    result=0   
    
    for i in range(l):
        for j in range(1,l-i+1):
            print(S[i,i+j+1])
            n = int("".join(map(str, St)))
            print(S)
            if n %2019==0:
                result+=1
    print(result)
    
if __name__ == "__main__":
    main()  
    

### FIXED CODE ###

# coding: utf-8
# Your code here!
def main():
    from functools import reduce
    import collections
     
    S = list(map(int,input().rstrip()))
    N=len(S)
    mod_list = [0]
    for i in range(1,N+1):
        new1 =pow(10,i-1,2019)
        new = (new1*S[-i]+mod_list[-1])%2019
        #print(new)
        mod_list.append(new)
        
    count = collections.Counter(mod_list)
    ans =0
    for j in range(2019):
        n = count[j]
        ans+= n*(n-1)/2
    print(int(ans))
if __name__ == "__main__":
    main()
def getval():
    s = input()
    return s
    
def main(s):
    #dp for "a","ab","abc"
    mod = 10**9 + 7
    dp = [0,0,0,0]
    p3 = [1]
    for i in range(n):
        p3.append((3*p3[i])%mod)
    for i in s:
        if i=="A":
            dp[0] += p3[dp[3]]
            dp[0] %= mod
        elif i=="B":
            dp[1] += dp[0]
            dp[1] %= mod
        elif i=="C":
            dp[2] += dp[1]
            dp[2] %= mod
        else:
            temp1 = dp[0]*2
            temp2 = dp[1]*2
            temp3 = dp[2]*2
            dp[2] += dp[1]
            dp[1] += dp[0]
            dp[0] += p3[dp[3]]
            dp[2] += temp3
            dp[1] += temp2
            dp[0] += temp1
            dp[3] += 1
            for j in range(3):
                dp[j] %= mod
            #print(dp)
    print(dp[2])

if __name__=="__main__":
    s = getval()
    main(s)

### FIXED CODE ###

def getval():
    s = input()
    return s
    
def main(s):
    #dp for "a","ab","abc"
    mod = 10**9 + 7
    dp = [0,0,0,0]
    p3 = [1]
    for i in range(len(s)):
        p3.append((3*p3[i])%mod)
    for i in s:
        if i=="A":
            dp[0] += p3[dp[3]]
            dp[0] %= mod
        elif i=="B":
            dp[1] += dp[0]
            dp[1] %= mod
        elif i=="C":
            dp[2] += dp[1]
            dp[2] %= mod
        else:
            temp1 = dp[0]*2
            temp2 = dp[1]*2
            temp3 = dp[2]*2
            dp[2] += dp[1]
            dp[1] += dp[0]
            dp[0] += p3[dp[3]]
            dp[2] += temp3
            dp[1] += temp2
            dp[0] += temp1
            dp[3] += 1
            for j in range(3):
                dp[j] %= mod
            #print(dp)
    print(dp[2])

if __name__=="__main__":
    s = getval()
    main(s)
import math

x = parseInt(input())

print(math.pow(x,3))

### FIXED CODE ###

n = int(input())
print(n ** 3)
l = []
ans = []
a, b, k = list(map(int, input().split()))
l.append(a)
l.append(b)
i = 1

for i in range(1, min(l) + 1):
    if (a % i) == 0 and (b % i) == 0:
       ans.append(i) 

    print(ans[-k])

### FIXED CODE ###

l = []
ans = []
a, b, k = list(map(int, input().split()))
l.append(a)
l.append(b)
i = 1

for i in range(1, min(l) + 1):
    if (a % i) == 0 and (b % i) == 0:
       ans.append(i) 

if len(ans) == 0:
    print(1)
else:
    print(ans[-k])
H W = map(int, input().split())
h w = map(int, input().split())
print((H-h)*(W-w))

### FIXED CODE ###

H, W = map(int, input().split())
h, w = map(int, input().split())
print((H-h)*(W-w))
N,M,K=map(int,input().split())
A=list(map(int,input().split()))
A.insert(0,0)
B=list(map(int,input().split()))
B.insert(0,0)
best=0
for a in range(len(A)):
    atime=0
    btime=0
    for i in range(a+1):
        atime=atime+A[i]
        if atime>K:
          break
    else:
        for b in range(len(B)):
            btime=btime+B[b]
            if atime+btime>K:
                book=a+b-1
                if book>best:
                    best=book
                break
        else:
            book=a+b
            if book>best:
                best=book
print(best)

### FIXED CODE ###

a=int(input())
ans=a+a**2+a**3
print(ans)
S=list(map(int.input().split()))
T=list(map(int.input().split()))
x = 0
for i in range(3):
  if S[i] == T[i]:
    x += 1
print(x)


### FIXED CODE ###

S=input()
T=input()
x = 0
for i in range(3):
  if S[i] == T[i]:
    x += 1
print(x)
N = int(input())
S = str(input())

cnt=0
if N%2==1:
    print('No')
else:
    for i in range(int(N/2)):
        if S[i]==S[int(N/2)+i]:
            cnt+=1
        else:
            print('No')
            break
    if cnt==int(N/2):
    print('Yes')

### FIXED CODE ###

N = int(input())
S = str(input())

cnt=0
if N%2==1:
    print('No')
else:
    for i in range(int(N/2)):
        if S[i]==S[int(N/2)+i]:
            cnt+=1
        else:
            print('No')
            break
    if cnt==int(N/2):
        print('Yes')
def dfs(i,Str):
    if i==n:
        return sum(map(int,Str.split()))
    return dfs(i+1,Str+S[i+1])+dfs(i+1,Str+"+"+S[i+1])
S=input()
n=len(S)
print(dfs(0,S[0]))

### FIXED CODE ###

def dfs(i,s):
    if i==n-1:
        return sum(map(int,s.split('+')))
    return dfs(i+1,s+S[i+1])+dfs(i+1,s+'+'+S[i+1])

S=input()
n=len(S)
ans=dfs(0,S[0])
print(ans)
N,M=map(int,input().split())
A=list(map(int,input().split()))
S=sum(A)
l=S//(4*M)
h=0
for i in range(N):
  if A[i]>=l:
    h+=1
  else:
    h+=0
if h=M:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

N,M=map(int,input().split())
A=list(map(int,input().split()))
S=sum(A)
l=S/(4*M)
h=0
for i in range(N):
  if A[i]>=l:
    h+=1
if h>=M:
  print("Yes")
else:
  print("No")
text = list(input())

list = {}

for t in text:
  if text.count(t) != 2:
    continue
  if t in list:
    list[t] += 1
  else:
    list[t] == 1
    
if len(list) == 2:
  return Yes
else:
  return No

### FIXED CODE ###

text = input()

text1 = text.replace(text[0], "")
try:
	text2 = text1.replace(text1[0], "")
except:
	text2 = "e"

if len(text) == 4 and len(text1) == 2 and len(text2) == 0:
  print("Yes")
else:
  print("No")
def resolve():
    import sys
    import numpy as np
 
    readline = sys.stdin.readline
 
    N, W = map(int, readline().split())
    lst = [list(map(int, readline().split())) for _ in [0] * N]
    
    dp = np.zeros((N, W + 1), np.int64)
 
    for i in range(N):
        w, v = lst[i][0], lst[i][1]
        for sum_w in range(W + 1):
            if sum_w >= w:
                dp[i][sum_w] = max(dp[i][sum_w],
                                   dp[i - 1][sum_w - w] + v)
            dp[i][sum_w] = max(dp[i][sum_w], dp[i - 1][sum_w])
    print(max(dp[-1]))
 
 
resolve()


### FIXED CODE ###

def resolve():
    import sys
    
    readline = sys.stdin.readline

    N, W = map(int, readline().split())
    lst = [list(map(int, readline().split())) for _ in [0] * N]
    
    dp = [[0] * (W + 1) for _ in [0] * N]

    for i in range(N):
        w, v = lst[i][0], lst[i][1]
        for sum_w in range(W + 1):
            if sum_w >= w:
                dp[i][sum_w] = max(dp[i][sum_w],
                                   dp[i - 1][sum_w - w] + v)
            dp[i][sum_w] = max(dp[i][sum_w], dp[i - 1][sum_w])
    print(max(dp[-1]))


resolve()
P=int(input())
X=list(map(int,input().split()))
l=[]
for j in range(min(X),max(X)):
    ans = [(i-j)**2 for i in X ]
    l.append(sum(ans))
print(min(l))


### FIXED CODE ###

P=int(input())
X=list(map(int,input().split()))
l=[]
for j in range(min(X),max(X)+1):
    ans = [(i-j)**2 for i in X ]
    l.append(sum(ans))
print(min(l))
# -*- coding: utf-8 -*-
"""
Created on Sun Aug  5 19:16:59 2018
ABC104C
@author: maezawa
"""
import math

d, g = list(map(int, input().split()))
p = []
c = []
for i in range(d):
    pi, ci = list(map(int, input().split()))
    p.append(pi)
    c.append(ci)
 
min_cnt = 10**11 
    
for i in range(2**d):
    istr = '0'*d + format(i,'b')
    used = []
    cnt = 0
    maney = 0   
    for j in range(d):
        if istr[-1-j] == '1':
            maney += c[j]+p[j]*(j+1)*100
            cnt += p[j]
            used.append(j)
    if maney > g:
        if min_cnt > cnt:
            min_cnt = cnt
            #print(istr)
            continue
    else:
        k = d-1
        while k>=0:
            if k not in used:
                break 
            k -= 1
        rem = math.ceil((g-maney)/(100*(k+1)))
        if rem >= p[k]:
            continue
        else:
            cntp = cnt + rem
            if min_cnt > cntp:
                min_cnt = cntp
                #print(istr, rem)
                continue
    #print(min_cnt, istr)
print(min_cnt)
                        
        
            

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun Aug  5 19:16:59 2018
ABC104C
@author: maezawa
"""
import math

d, g = list(map(int, input().split()))
p = []
c = []
for i in range(d):
    pi, ci = list(map(int, input().split()))
    p.append(pi)
    c.append(ci)
 
min_cnt = 10**11 
    
for i in range(2**d):
    istr = '0'*d + format(i,'b')
    used = []
    cnt = 0
    maney = 0   
    for j in range(d):
        if istr[-1-j] == '1':
            maney += c[j]+p[j]*(j+1)*100
            cnt += p[j]
            used.append(j)
    if maney >= g:
        if min_cnt > cnt:
            min_cnt = cnt
            #print(istr)
            continue
    else:
        k = d-1
        while k>=0:
            if k not in used:
                break 
            k -= 1
        rem = math.ceil((g-maney)/(100*(k+1)))
        if rem >= p[k]:
            continue
        else:
            cntp = cnt + rem
            if min_cnt > cntp:
                min_cnt = cntp
                #print(istr, rem)
                continue
    #print(min_cnt, istr)
print(min_cnt)
MOD=1000000007
n,k=map(int,input().split())
a=[int(i) for i in input().split()]
pos=[]
neg=[]
nzero=0
for i in a:
    if i>0:
        pos.append(i)
    elif i<0:
        neg.append(-i)
    else:
        nzero+=1
if nzero+k>n:
    print(0)
elif len(pos)==0:
    res=1
    if k%2:
        neg.sort()
        for i in range(k):
            res*=MOD-neg[i]
            res%=MOD
    else:
        neg.sort(reverse=True)
        for i in range(k):
            res*=MOD-neg[i]
            res%=MOD
    print(res)
elif len(neg)==0:
    res=1
    pos.sort(reverse=True)
    for i in range(k):
        res*=pos[i]
        res%=MOD
    print(res)
else:
    pos.sort(reverse=True)
    neg.sort(reverse=True)
    ruip=[1 for i in range(len(pos)+1)]
    ruin=[1 for i in range(len(neg)+1)]
    for i in range(len(pos)):
        ruip[i+1]=ruip[i]*pos[i]
        ruip[i+1]%=MOD
    for i in range(len(neg)):
        ruin[i+1]=ruin[i]*neg[i]
        ruin[i+1]%=MOD
    np=0
    if len(pos)>=k:
        np=k
    elif (k-len(pos))%2:
        np=len(pos)-1
    else:
        np=len(pos)
    while np>=2 and (pos[np-1]*pos[np-2]<neg[k-np-1]*neg[k-np-2]):
        np-=2
    print((ruip[np]*ruin[k-np])%MOD)


### FIXED CODE ###

MOD=1000000007
n,k=map(int,input().split())
a=[int(i) for i in input().split()]
pos=[]
neg=[]
nzero=0
for i in a:
    if i>0:
        pos.append(i)
    elif i<0:
        neg.append(-i)
    else:
        nzero+=1
if nzero+k>n:
    print(0)
elif nzero+k==n and len(pos)>0 and len(neg)>0:
    if nzero==0:
        res=1
        for i in pos+neg:
            res*=i
            res%=MOD
        if len(neg)%2:
            res*=-1
            res+=MOD
        print(res)
    elif len(neg)%2:
        print(0)
    else:
        res=1
        for i in pos+neg:
            res*=i
            res%=MOD
        print(res)
elif len(pos)==0:
    res=1
    if k%2 and nzero>0:
        print(0)
    elif k%2:
        neg.sort()
        for i in range(k):
            res*=MOD-neg[i]
            res%=MOD
        print(res)
    else:
        neg.sort(reverse=True)
        for i in range(k):
            res*=MOD-neg[i]
            res%=MOD
        print(res)
elif len(neg)==0:
    res=1
    pos.sort(reverse=True)
    for i in range(k):
        res*=pos[i]
        res%=MOD
    print(res)
else:
    pos.sort(reverse=True)
    neg.sort(reverse=True)
    ruip=[1 for i in range(len(pos)+1)]
    ruin=[1 for i in range(len(neg)+1)]
    for i in range(len(pos)):
        ruip[i+1]=ruip[i]*pos[i]
        ruip[i+1]%=MOD
    for i in range(len(neg)):
        ruin[i+1]=ruin[i]*neg[i]
        ruin[i+1]%=MOD
    np=0
    if len(pos)>=k:
        np=k
    elif (k-len(pos))%2:
        np=len(pos)-1
    else:
        np=len(pos)
    while np>=2 and (pos[np-1]*pos[np-2]<neg[k-np+1]*neg[k-np]):
        np-=2
        if len(neg)-1<k-np+1:
            break
    print((ruip[np]*ruin[k-np])%MOD)