Harryxun/stf_run huggingface dataset:
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(M)]
visited = {i:False for i in range(M)}
visited[0] = True
ans = 0

def DFS(x):
  global ans
  nextx = []
  if False not in visited.values():
    ans += 1
    return
  for i in range(M):
    if x in ab[i]:
      xcol = ab[i].index(x)
      if visited[ab[i][1-xcol]-1]:
        continue
      else:
        nextx.append(ab[i][1-xcol])
  for i in nextx:
    visited[i-1] = True
    DFS(i)
    visited[i-1] = False
  return

DFS(1)
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(M)]
visited = {i:False for i in range(N)}
visited[0] = True
ans = 0

def DFS(x):
#  print(visited)
  global ans
  nextx = []
  if False not in visited.values():
    ans += 1
    return
  for i in range(M):
    if x in ab[i]:
      xcol = ab[i].index(x)
      if visited[ab[i][1-xcol]-1]:
        continue
      else:
        nextx.append(ab[i][1-xcol])
#  print(nextx)
  for i in nextx:
    visited[i-1] = True
    DFS(i)
    visited[i-1] = False
  return

DFS(1)
print(ans)
while True:
	dict = {}
	n = input()
	if n == 0:break
	for x in xrange(n):
		a, b = raw_input().split()
		dict[a] = b
	res = ""
	for x in xrange(input()):
		a = raw_input()
		if a in dict:
			res += dict[a]
		else
			res += a
	print a

### FIXED CODE ###

while True:
	dict = {}
	n = input()
	if n == 0:break
	for x in xrange(n):
		a, b = raw_input().split()
		dict[a] = b
	res = ""
	for x in xrange(input()):
		a = raw_input()[0]
		if a in dict:
			res += dict[a]
		else:
			res += a
	print res
N,M = (int(i) for i in input().split())
K = []
for i in range(M):
    J = [int(i) for i in input().split()]
    J.sort()
    K.append(J)

#1以外の頂点リストを作成
vertex = []
for i in range(N-1):
    vertex.append(i+2)
#順列作成
X = list(itertools.permutations(vertex))

#各値ごとに有無をチェック
ans = 0
for i in X:
    start = 1
    localcount = 0
    for j in i:
        tmp = [start,j]
        tmp.sort()
        if tmp in K == False:
            break            
        else:
            localcount += 1
            start = j
            
    if localcount == N-1:
        ans += 1

print(ans)

### FIXED CODE ###

import itertools
N,M = (int(i) for i in input().split())
K = []
for i in range(M):
    J = [int(i) for i in input().split()]
    J.sort()
    K.append(J)

#1以外の頂点リストを作成
vertex = []
for i in range(N-1):
    vertex.append(i+2)
#順列作成
X = list(itertools.permutations(vertex))

#各値ごとに有無をチェック
ans = 0
for i in X:
    start = 1
    localcount = 0
    for j in i:
        tmp = [start,j]
        tmp.sort()
        if tmp in K:            
            localcount += 1   
        start = j
            
    if localcount == N-1:
        ans += 1

print(ans)
A, op, B = input()
A = int(A)
B = int(B)
op = str("+", "-")
if op =="+":
    print(A+B)
elif op == "-":
    print(A-B)


### FIXED CODE ###

A, op, B = input().split()

if op =="+":
    print(int(A) + int(B))
elif op == "-":
    print(int(A) - int(B))
import sys

sys.setrecursionlimit(10000)

def dfs(x):
  if x == N:
    return 1
  if x > N or x in a:
    return 0
  if memo.get(x):
    return memo[x]
  memo[x] = dfs(x+1) + dfs(x+2)
  return memo[x]

N, M = map(lambda x: int(x), input().split())
a = [int(input()) for i in range(M)]
#print(N)
#print(M)
#print(a)
memo = {}
count = dfs(0)
print(count%1000000007) 



### FIXED CODE ###

import sys
sys.setrecursionlimit(100000000)

def dfs(x):
  if x == N:
    return 1
  if x > N:
    return 0
  if memo[x] >= 0:
    return memo[x]
  memo[x] = dfs(x+1) + dfs(x+2)
  return memo[x]

N, M = map(lambda x: int(x), input().split())
a = [int(input()) for i in range(M)]
#print(N)
#print(M)
#print(a)
memo = [-1]*(N+1)
for ai in a:
  memo[ai] = 0
count = dfs(0)
print(count%1000000007)
n = int(input())
a = [int(i) for i in input().split()]

ans = 0
for i in range(n-1):
    if a[i] > i[i+1]:
        x += a[i] - a[i+1]
        a[i+1] = a[i]

print(ans)

### FIXED CODE ###

N = int(input())
A = [int(x) for x in input().split()]
ans = 0
for i in range(N-1):
    if A[i]>A[i+1]:
        ans += A[i]-A[i+1]
        A[i+1] = A[i]
print(ans)
N = int(input())
K = 0
for i in range(N):
    s = i % 3
    t = i % 5
        if s !=0 and t != 0:
            K += i

print(K)

### FIXED CODE ###

N = int(input())
K = 0
for i in range(N):
    s = (i+1) % 3
    t = (i +1) % 5
    if s !=0 and t != 0:
        K +=( i+1)
print(K)
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    n, lim = MI()
    ww = []
    vv = []
    for _ in range(n):
        w, v = MI()
        ww.append(w)
        vv.append(v)
    w0=ww[0]
    # dp[i][j]…荷物の個数がiで、端数の合計がjのときの価値の最大値
    dp=[[0]*(3*n+1) for _ in range(n+1)]
    for w,v in zip(ww,vv):
        for i in range(n,0,-1):
            for j in range(lim-i*w0,-1,-1):
                nj=j-(w-w0)
                if nj<0:continue
                dp[i][j]=max(dp[i][j],dp[i-1][nj]+v)
    #p2D(dp)
    print(max(max(row) for row in dp))

main()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    n, lim = MI()
    ww = []
    vv = []
    for _ in range(n):
        w, v = MI()
        ww.append(w)
        vv.append(v)
    w0=ww[0]
    # dp[i][j]…荷物の個数がiで、端数の合計がjのときの価値の最大値
    dp=[[0]*(3*n+1) for _ in range(n+1)]
    for w,v in zip(ww,vv):
        for i in range(n,0,-1):
            sj=min(lim-i*w0,3*n)
            for j in range(sj,-1,-1):
                nj=j-(w-w0)
                if nj<0:break
                dp[i][j]=max(dp[i][j],dp[i-1][nj]+v)
    #p2D(dp)
    print(max(max(row) for row in dp))

main()
import math:

r = int( raw_input() ) 

S = math.pi * r ** 2 
l = 2 * r * math.pi

print"%f %f" %(S,l)

### FIXED CODE ###

import math

r = float( raw_input() ) 

S = math.pi * r * r
l = 2 * r * math.pi

print"%f %f" %(S,l)
# a(1)〜z(26)を使った26進数に変換する

import string

N = int(input())
alpha = list(string.ascii_lowercase)
alpha.append('')

# valueに答えとなるalphabetの羅列を入れる
value = []
value.append(alpha[N // (26**10) - 1])

for i in range(10,1,-1):
  value.append(alpha[(N % (26**i)) // (26**(i-1)) - 1])

value.append(alpha[N % (26**1) - 1])

value = ''.join(value)
print(value)

### FIXED CODE ###

alpha = input()

if alpha.islower():
  print('a')
else:
  print('A')
N,D = map(int, input().split())
print(N//(2D+1)+1)


### FIXED CODE ###

N,D = map(int, input().split())
count = 0
i = 0
while i < N:
  i += 2*D+1
  count +=1
print(count)
N,K=map(int,input().split())
S=input()
po=[0]
X=[]
i=0
for i in range(N-1):
	if not S[i] == S[i+1]:
		po.append(i+1)
po.append(len(S))
for i in range(len(po)):
	if 2*K+i+1>=len(po):
		X.append(po[2*K+i]-po[i])
		break
	elif S[po[i]]=='0':
		X.append(po[2*K+i]-po[i])
	else:
		X.append(po[2*K+1+i]-po[i])
print(max(X))

### FIXED CODE ###

N,K=map(int,input().split())
S=input()
po=[0]
X=[]
i=0
for i in range(N-1):
	if not S[i] == S[i+1]:
		po.append(i+1)
po.append(len(S))
for i in range(len(po)):
	if 2*K+1>=len(po):
		X.append(po[-1])
		break
	elif 2*K+i+1>=len(po):
		X.append(po[2*K+i]-po[i])
		break
	elif S[po[i]]=='0':
		X.append(po[2*K+i]-po[i])
	else:
		X.append(po[2*K+1+i]-po[i])
print(max(X))
N = input()
 R = input()
 if N >= 10:
     print(R)
 else :
     K = 100 * (10 - int(N))
     print(K)


### FIXED CODE ###

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

#print(a ,type(a))
if x<10:
    print(y+(100*(10-x)))
else:
    print(y)
import math
n,m=map(int,input().split())
print(int(n*m/math.gcd(n,m)))


### FIXED CODE ###

def gcd(a,b):
    if a<b:
        t=a
        a=b
        b=t
    while b!=0:
            a,b=b,a%b
    return a

n,m=map(int,input().split())
print(int(n*m/gcd(n,m)))
import math

n=int(input())
m=int(math.sqrt(n))
for i in reverse(range(1,m+1)):
	if n%i==0:
		print(int(i+n/i-2))
		break

### FIXED CODE ###

import math

n=int(input())
m=int(math.sqrt(n))
for i in reversed(range(1,m+1)):
	if n%i==0:
		print(int(i+n/i-2))
		break
n,x=map(int,input().split())
l=list(map(int,input().split()))
l=sorted([abs(i-x) for i in l],reverse=True)

def gcd(a,b):
    while b!=0:
        a,b=b,a%b
    return a

p=gcd(l[0],l[1])
for i in l[2:]:
    q=gcd(i,p)
    p=q
print(p)

### FIXED CODE ###

n,x=map(int,input().split())
l=list(map(int,input().split()))
l=sorted([abs(i-x) for i in l],reverse=True)

def gcd(a,b):
    while b!=0:
        a,b=b,a%b
    return a

if n!=1:
    p=gcd(l[0],l[1])
    for i in l[2:]:
        q=gcd(i,p)
        p=q
else:
    p=l[0]
print(p)
a, b, k = (int(i) for i in input().split())
ok_list = []
for i in range(1,max(a, b)):
    if a % i == b % i == 0:
       ok_list.append(i)
print(ok_list[k-1])

### FIXED CODE ###

A,B,K = map(int,input().split())
 
cnt = 0
ans = []
 
for i in range(1,101):
    if A%i == 0 and B%i == 0:
        ans.append(i)
 
print(ans[-K])
n = int(input())
m = list(map(int,input().split()))
f = True
for i in m:
  if i % 2 == 0:
    if (i % 3 == 0 ) or (i % 5 == 0 ):
      f = True
    else:
      print('DENIED')
      exit()

print('APPROVED')



### FIXED CODE ###

n,m,l = map(int,input().split())
if (n != m) and (n != l ) and (m != l):
  print('No')
elif n == m:
  if n == l:
    print('No')
  else:
    print('Yes')
elif n == l:
  print('Yes')
elif m == l:
  print('Yes')
import sys

S = input()

Q = int(input())
flag=0

for i in range(Q):
    r = sys.stdin.readline().strip('\n')
    if r == '1':
        S = S[::-1]
    else:
        ni, f, c = r.split()
        if f=='1':
            S = c + S
        else:
            S+=c

print(S)

### FIXED CODE ###

N = input()

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

if N[0]==N[1]==N[2]:
    print('No')
    exit()
print('Yes')
from sys import stdin
from collections import defaultdict
from collections import deque

N,M = list(map(int,stdin.readline().split()))
Cs = [tuple(map(int,stdin.readline().split())) for _ in range(M)]
S,T = list(map(int,stdin.readline().split()))

INF = 10 ** 15
# visit = [False] * ( (N + 1) * 3 )
dist  = [-1] * ( (N) * 3 + 1 )
graph_connection = defaultdict(lambda :[])
graph_cost = defaultdict(lambda :defaultdict(lambda :INF))
#
# def dfs(v,dist_before):
#
#     dist[v] = dist_before + 1
#     next_vertexs = graph_connection[v]
#     for next_v  in next_vertexs :
#         if dist[next_v] == -1:
#             dfs(next_v,dist[v])
#     return 0
#

for cost in  Cs:
    a,b= cost
    for i in range(0,3):
        from_v = a + (i) * N
        to_v = b + (i + 1) % 3 * N
        graph_connection[from_v].append(to_v )

        # from_v = b + (i) * N
        # to_v = a + (i + 1) % 3 * N
        # graph_connection[from_v].append(to_v )

# dist[S] = 0


que = deque()
#(from_v,to_v)
que.append((S,S))

while not que.empty():
    from_v, to_v = que.popleft()
    dist[to_v] = dist[from_v] + 1
    for next_v in graph_connection[to_v]:
        if dist[next_v] == -1:
            que.appendleft((to_v,next_v))
if dist[T] < 0:
    print(dist[T] )
else:
    print(dist[T]//3)


### FIXED CODE ###

from sys import stdin
from collections import defaultdict
from collections import deque

N,M = list(map(int,stdin.readline().split()))
Cs = [tuple(map(int,stdin.readline().split())) for _ in range(M)]
S,T = list(map(int,stdin.readline().split()))

INF = 10 ** 15
# visit = [False] * ( (N + 1) * 3 )
dist  = [-1] * ( (N) * 3 + 1 )
graph_connection = defaultdict(lambda :[])
graph_cost = defaultdict(lambda :defaultdict(lambda :INF))
#
# def dfs(v,dist_before):
#
#     dist[v] = dist_before + 1
#     next_vertexs = graph_connection[v]
#     for next_v  in next_vertexs :
#         if dist[next_v] == -1:
#             dfs(next_v,dist[v])
#     return 0
#

for cost in  Cs:
    a,b= cost
    for i in range(0,3):
        from_v = a + (i) * N
        to_v = b + (i + 1) % 3 * N
        graph_connection[from_v].append(to_v )

        # from_v = b + (i) * N
        # to_v = a + (i + 1) % 3 * N
        # graph_connection[from_v].append(to_v )

# dist[S] = 0


que = deque()
#(from_v,to_v)
dist[S] = 0
que.append(S)
while len(que) != 0:
    from_v = que.popleft()
    nexts = graph_connection[from_v]
    for next_v in nexts:
        if dist[next_v] == -1:
            dist[next_v] = dist[from_v] + 1
            que.append(next_v)

if dist[T] < 0:
    print(dist[T] )
else:
    print(dist[T]//3)
A, B, C = map(int,input().split())

n = 100 * B

for i in range(1, n, B):
  if A * i % B = C:
    print("YES")
    flag == True:
    break
  else:
    continue

if flag != True:
  print("No")
  

### FIXED CODE ###

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

for i in range(B):
  if A * i % B == C:
    print("YES")
    exit()
  else:
    continue
print("NO")
N, Y = map(int, input().split())
c = [-1,-1,-1]
for i in range(N+1):
    for j in range(N-i+1):
            if 10000*i + 5000*j + 1000*(N-i-k) == Y:
                c = [i,j,N-i-k]
print(c[0],c[1],c[2])

### FIXED CODE ###

N,Y = map(int, input().split())
c = [-1,-1,-1]
for i in range(N+1):
    for j in range(N+1):
        a = N - i - j
        if a >= 0 and (10000*i + 5000*j + 1000*a) == Y:
            c = [i,j,a]
            break
print(c[0],c[1],c[2])
S = input()

d = set(['A', 'T', 'C', 'G'])
ans = 0
nums = list()
for s in S:
    if s in d:
        ans += 1
    else:
        nums.append(ans)
        ans = 0
print(max(nums))


### FIXED CODE ###

S = input()

d = set(['A', 'T', 'C', 'G'])
len_ = 0
ans = 0
for s in S:
    if s in d:
        len_ += 1
    else:
        if len_ > ans:
            ans = len_
        len_ = 0
if len_ > ans:
    ans = len_
print(ans)
a=list(map(int,input().split()))

print((3*a_1+a_2)%2)

### FIXED CODE ###

a=list(map(int,input().split()))
b=(3*a[0]+a[1])//2
print(b)
x,y,z = int(input().split())
D=x
T=y
S=z

if T-D/S>= 0:
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

D,T,S = map(int, input().split())

if T-D/S >= 0:
    print("Yes")
else:
    print("No")
def rightMinNumber(L):
    min = L[len(L)-1]
    min_index = len(L) - 1
    for i in range(len(L)-2,-1,-1):
        if L[i] < min:
            min = L[i]
            min_index = i
    lL = L[:min_index]
    rL = L[min_index+1:]
    a.append(min)
    rightMinNumber(rL)
    rightMinNumber(lL)


N = int(input())
B = (int(i) for i in input().split())
#出力
a = []
#Bのエンコーダを作る
x = 0

#Bの正当性を調べる。
for i in range(N):
    if B[i] > i:
        x = -1
        break
if x == -1:
    print(x)
else :
    rightMinNumber(B)
    for i in range(N):
        print(a[i])


### FIXED CODE ###

def main():
    N = int(input())
    B = [int(_) for _ in input().split()]

    #出力用
    outs = []

    for i in range(N):
        for k in range(N-1-i,-1,-1):
            if B[k] == k+1:
                del B[k]
                outs.insert(0,k+1)
                break
        else:
            print(-1)
            return

    for out in outs:
        print(out)

if __name__ == '__main__':
    main()
from scipy.sparse import*
(n,m),*t=[map(int,t.split())for t in open(0)]
*b,a=zip(*[(i,j+n,1)for i,(_,*t)in enumerate(t)for j in t])
print('YNEOS'[1in csgraph.connected_components(csr_matrix((a,b),[n*9]*2))[1][:n]::2])

### FIXED CODE ###

from scipy.sparse import*
(n,m),*p=[map(int,t.split())for t in open(0)]
a,b,c=zip(*[(i,j+n-1,1)for i,q in enumerate(p)for j in list(q)[1:]])
print('YNEOS'[1in csgraph.connected_components(csr_matrix(((c,(a,b))),[n+m]*2))[1][:n]::2])
n=input()
mochi=[]
for i in range(n):
  k=int(input())
  mochi.append(k)
print(len(list(set(mochi))))

### FIXED CODE ###

n=int(input())
mochi=[]
for i in range(n):
  k=int(input())
  mochi.append(k)
print(len(set(mochi)))
n = int(input())
ans = 1
flg = True

if '0' in list(input().split()):
    print(0)
else:
    for a in input().split():
        _a = int(a)
        ans *= _a
        if ans > 10 ** 18:
            print(-1)
            flg = False
            break

    if flg:
        print(ans)


### FIXED CODE ###

n = int(input())
ans = 1
flg = True
input_a = list(input().split())

if '0' in input_a:
    print(0)
else:
    for a in input_a:
        _a = int(a)
        ans *= _a
        if ans > 10 ** 18:
            print(-1)
            flg = False
            break

    if flg:
        print(ans)
nmq=list(map(int, input().split()))
N=nmq[0]
M=nmq[1]
Q=nmq[2]
ablist=[list(map(int, input().split())) for i in range(Q)]
sumlist=[]
alist=[]
for i in range(1,M+1):
    alist.append(i)
import itertools as ite
case=list(ite.combinations_with_replacement(alist,N))
for nowcase in case:
    sumd=0
    for i in range(Q):
        a=ablist[i][0]
        b=ablist[i][1]
        c=ablist[i][2]
        d=ablist[i][3]
        aa=nowcase[a-1]
        ab=nowcase[b-1]
        if ab-aa==c:
            sumd+=d
    sumlist.append(sumd)
sumlist.sort(reverse=True)
print(sumlist[0])


### FIXED CODE ###

K=int(input())
ab=list(map(int, input().split()))
A=ab[0]
B=ab[1]
flg=False
for i in range(A,B+1):
    if i%K==0:
        flg=True
if flg:
    print('OK')
else:
    print('NG')
N, K = map(int, input().split())
H = sorted([int(x) for x in input().split()], inverse=True)
if K >= len(H):
    print('0')
else:
    print(sum(H[K:]))

### FIXED CODE ###

N, K = map(int, input().split())
H = sorted([int(x) for x in input().split()])[::-1]
if K >= len(H):
    print('0')
else:
    print(sum(H[K:]))
#!/usr/bin/env python
# coding: utf-8

# In[23]:


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


# In[24]:


def nCk(n, k, mod):
    a = 1
    for i in range(n, n-k, -1):
        a *= i
        a %= mod
    b = 1
    for i in range(1, k+1):
        b *= i
        b %= mod
    a *= pow(b, mod-2, mod)
    return a


# In[25]:


ans = pow(2, n, mod)-1
ans -= nCk(n, a, mod) + nCk(n, b, mod)
print(ans%mod)


# In[ ]:






### FIXED CODE ###

#!/usr/bin/env python
# coding: utf-8

# In[1]:


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


# In[2]:


def nCk(n, k, mod):
    a = 1
    for i in range(n, n-k, -1):
        a *= i
        a %= mod
    b = 1
    for i in range(1, k+1):
        b *= i
        b %= mod
    a *= pow(b, mod-2, mod)
    return a


# In[3]:


mod = 10**9+7
ans = pow(2, n, mod)-1
ans -= nCk(n, a, mod) + nCk(n, b, mod)
print(ans%mod)


# In[ ]:
N = int(input())
K = int(input())
cnt = 0
for i in range(N):
  tmp = int(input())
  cnt += min(abs(K-tmp), (tmp))*2
print(cnt)

### FIXED CODE ###

N = int(input())
K = int(input())
A = list(map(int, input().split()))
cnt = 0
for i in A:
  cnt += min(abs(K-i), (i))*2
print(cnt)
a,b = map(int,input().split())
s = list(input())
ans = Yes
if len(s) != a+b+1:
    ans = 'No'
else:
    for i in range(a+b+1):
        if i == a and s[i] != '-':
            ans = 'No'
            break
        if (not s[i].isdigit()) and i != a:
            ans ='No'
            break
print (ans)


### FIXED CODE ###

a,b = map(int,input().split())
s = list(input())
ans = 'Yes'
if len(s) != a+b+1:
    ans = 'No'
else:
    for i in range(a+b+1):
        if i == a and s[i] != '-':
            ans = 'No'
            break
        if (not s[i].isdigit()) and i != a:
            ans ='No'
            break
print (ans)
n,x = map(int,input().split())
b = list(map(int,input().split()))
cnt  = 0
ans = 0
while cnt<=x:
  cnt += b[ans]
  ans += 1

print(ans)
  

### FIXED CODE ###


n,x = map(int,input().split())
b = list(map(int,input().split()))
cnt = 0
ans = 1
for i in b:
    cnt += i
    if cnt <= x:
        ans += 1

print(ans)
s = input()
f = 0
a = 0; b = 0; c = 0
for i in range(len(s)//2):
    if s[i]==s[-1-i]:
        a += 1
    if a == len(s)//2:
        f += 1
for i in range(len(s)//4):
    if s[i]==s[(len(s)-1)//2-1-i]:
        b += 1
    if b == len(s)//4:
        f += 1
    if s[(len(s)+3)//2-1+i]==s[len(s)-1+i]:
        c += 1
    if c == len(s)//4:
        f += 1
print('Yes' if f == 3 else 'No')

### FIXED CODE ###

s = input()
f = 0
a = 0; b = 0; c = 0
if len(s)==3 and s[0]==s[2]:
    print('Yes')
else :
    
    for i in range(len(s)//2):
        if s[i]==s[-1-i]:
            a += 1
        if a == len(s)//2:
            f += 1
    for i in range(len(s)//4):
        if s[i]==s[(len(s)-1)//2-1-i]:
            b += 1
        if b == len(s)//4:
            f += 1
        if s[(len(s)+3)//2-1+i]==s[len(s)-1-i]:
            c += 1
        if c == len(s)//4:
            f += 1
    print('Yes' if f == 3 else 'No')
n,k,*a=map(int,open(0).read().split())
a.sort(reverse=True,key=lambda x:abs(x))
MOD=10**9+7
ans=1
if n==k:
  for i in a:
    ans*=i
    ans%=MOD
  print(ans)
  exit()
if k%2==1 and sum([i>=0 for i in a])==0:
  ans=1
  for i in range(k):
    ans*=a[-1-i]
    ans%=MOD
  print(ans)
  exit()

sp=[]
sn=[]
negidx=False
posidx=False
flg=1
for i in range(k):
  if a[i]>=0:
    posidx=i
  else:
    negidx=i
    flg*=-1
  sp.append(a[i])
  sn.append(a[i])
  
if flg==1:
  ans=1
  for si in sp:
    ans*=si
    ans%=MOD
  print(ans)
  exit()
else:
  for i in range(k,n):
    if a[i]>0:
      sn[negidx]=a[i]
      ans1=1
      for si in sn:
        ans1*=si
        ans1%=MOD
      break
  for i in range(k,n):
    if a[i]<0:
      sp[posidx]=a[i]
      ans2=1
      for si in sp:
        ans2*=si
        ans2%=MOD        
      break
  print(max(ans1,ans2))

### FIXED CODE ###

import sys

# after これ通る？コピペs


def solve(n, k, aaa):
    MOD = 10 ** 9 + 7

    if n == k:
        ans = 1
        for a in aaa:
            ans = ans * a % MOD
        return ans

    pos = []  # Strictly, Non-neg
    neg = []
    for a in aaa:
        if a >= 0:
            pos.append(a)
        elif a < 0:
            neg.append(a)

    if len(pos) == 0:
        if k % 2 == 1:
            neg.sort(reverse=True)
        else:
            neg.sort()
        ans = 1
        for a in neg[:k]:
            ans = ans * a % MOD
        return ans

    pos.sort()
    neg.sort(reverse=True)
    ans = 1
    r = k

    if r % 2 == 1:
        ans = ans * pos.pop() % MOD
        r -= 1

    while r > 0:
        if len(pos) <= 1:
            ans = ans * neg.pop() * neg.pop() % MOD
        elif len(neg) <= 1:
            ans = ans * pos.pop() * pos.pop() % MOD
        else:
            pm = pos[-1] * pos[-2]
            nm = neg[-1] * neg[-2]
            if pm > nm:
                ans = ans * pos.pop() * pos.pop() % MOD
            else:
                ans = ans * neg.pop() * neg.pop() % MOD
        r -= 2

    return ans


n, k, *aaa = map(int, sys.stdin.buffer.read().split())
print(solve(n, k, aaa))
def main():
    a, b = map(int, input().split())
    print('Odd') if a*B % 2 != 0 else print('Even')


if __name__ == "__main__":
    main()


### FIXED CODE ###

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


if __name__ == "__main__":
    main()