Harryxun/stf_run huggingface dataset:
from collections import deque

def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    warp[sy][sx]=0 #ワープ回数
    while queue:
        y, x = queue.popleft()
        if [y, x] == [gy, gx]:
            return warp[y][x]
        
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]): #進める方向
            ny, nx = y+j, x+k
            
            # 迷路の範囲外なら戻る
            if ny < 0 or ny >= h or nx < 0 or nx >= w:
                continue
            
            # 移動先候補が壁のとき
            if maze[ny][nx] == "#":
                for ii in range(-2,3):
                    for jj in range(-2,3):
                        # 範囲外なら戻る
                        if y+ii<0 or y+ii>=h or x+jj<0 or x+jj>=w:
                            continue
                        # 移動先が通路かつ現状必要ワープ回数が多い
                        if warp[y+ii][x+jj] > warp[y][x]+1 and maze[y+ii][x+jj]==".":
                            warp[y+ii][x+jj]=warp[y][x]+1
                            queue.append([y+ii,x+jj])
                
            if maze[ny][nx] == "." and warp[ny][nx]>warp[x][y]:
                warp[ny][nx]=warp[x][y]
                queue.appendleft([ny,nx])
            
    return -1 #ゴールできない

h,w=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())

maze=[input() for _ in range(h)]

visited = [[-1]*w for _ in range(h)]
warp = [[10000]*w for _ in range(h)]
ans=bfs(maze, visited, sy-1, sx-1, gy-1, gx-1)
if ans==10000:
    ans=-1
print(ans)


### FIXED CODE ###

from collections import deque

def make_wall(maze,h,w):
    maze=deque(maze)
    for i in range(h):
        maze[i]="##"+maze[i]+"##"
    maze.appendleft("#"*(w+4))
    maze.appendleft("#"*(w+4))
    maze.append("#"*(w+4))
    maze.append("#"*(w+4))
    return list(maze)

def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    cost[sy][sx]=0
    walk = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    warp = [(i,j) for i in range(-2,3) for j in range(-2,3) if (i,j) not in [(0,0)]+walk]
    
    while queue:
        y, x = queue.popleft()
        if [y, x] == [gy, gx]:
            return cost[y][x]
        
        # 移動A
        for i,j in walk:
            ny, nx = y+i, x+j
            if maze[ny][nx] == "." and cost[ny][nx]>cost[y][x]:
                cost[ny][nx]=cost[y][x]
                queue.appendleft([ny,nx])
            
        # 移動B
        for i, j in warp:
            ny, nx = y+i, x+j
            if cost[ny][nx] > cost[y][x]+1 and maze[ny][nx]==".":
                cost[ny][nx]=cost[y][x]+1
                queue.append([ny,nx])
            
    return -1 #ゴールできない

h,w=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())

maze=[input() for _ in range(h)]

maze=make_wall(maze,h,w)
h+=4
w+=4
sy+=2
sx+=2
gy+=2
gx+=2

INF = 10**12
cost = [[INF]*w for _ in range(h)]

ans=bfs(maze, cost, sy-1, sx-1, gy-1, gx-1)
if ans==INF:
    ans=-1
print(ans)
print(n-m)

### FIXED CODE ###

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

n = b // x
m = (a-1) // x

print(n-m)
def visit(u):
    global color, d, f, t
    color[u] = GRAY
    d[u] += t
    t += 1
    for v in range(n):
        if (M[u][v] == 0):
            continue
        else:
            if (color[v] == WHITE):
                visit(v)
    color[u] = BLACK
    f[u] = t
    t += 1

n = int(input())
M = [[0 for i in range(n)] for i in range(n)]
for i in range(n):
    tmp = list(map(int, input().split()))
    for j in range(tmp[1]):
        M[tmp[0]-1][tmp[j+2]-1] = 1

WHITE = 0
GRAY = 1
BLACK = 2
color = [WHITE for i in range(n)]
d, f = [0 for i in range(n)]
t = 1

for u in range(n):
    if (color[u] == WHITE):
        visit(u)
for u in range(n):
    print(str(u+1), str(d[u]), str(f[u]), sep = " ")

### FIXED CODE ###

def dfs(u):
    global dfs_color, d, f, t
    color[u] = GRAY
    d[u] += t
    t += 1
    for v in range(n):
        if (M[u][v] == 0):
            continue
        else:
            if (color[v] == WHITE):
               dfs(v)
    color[u] = BLACK
    f[u] = t
    t += 1

n = int(input())
M = [[False for i in range(n)] for j in range(n)]
for i in range(n):
    tmp = list(map(int, input().split()))
    for j in range(tmp[1]):
        M[tmp[0]-1][tmp[j+2]-1] = True

WHITE = 0
GRAY = 1
BLACK = 2
color = [WHITE for i in range(n)]
d = [0 for i in range(n)]
f = [0 for i in range(n)]
t = 1

for u in range(n):
    if (color[u] == WHITE):
        dfs(u)
for u in range(n):
    print(str(u+1), str(d[u]), str(f[u]), sep = " ")
n = input()
cur = 0

for x in n:
  cur += int(x)

  if cur % 9 == 0:
    print("Yes")
    else:
      print("No")

### FIXED CODE ###

import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n = input()
    cur = 0

    for x in n:
        cur += int(x)

    if cur % 9 == 0:
        print("Yes")
    else:
        print("No")


if __name__ == '__main__':
    main()
from sys import stdin
from itertools import combinations
from math import factorial

n = int(stdin.readline().rstrip())
li = [stdin.readline().rstrip() for _ in range(n)]

lin = [0]*n

for i in range(len(lin)):
    if li[i][0] == "M":
        lin[0] += 1
    elif li[i][0] == "A":
        lin[1] += 1
    elif li[i][0] == "R":
        lin[2] += 1
    elif li[i][0] == "C":
        lin[3] += 1
    elif li[i][0] == "H":
        lin[4] += 1

from itertools import combinations
lis = list(combinations(lin, 3))


point = 0
for i in lis:
    point += i[0]*i[1]*i[2]

print(point)

### FIXED CODE ###

from sys import stdin
from itertools import combinations
from math import factorial

n = int(stdin.readline().rstrip())
li = [stdin.readline().rstrip() for _ in range(n)]

lin = [0]*5

for i in range(len(li)):
    if li[i][0] == "M":
        lin[0] += 1
    elif li[i][0] == "A":
        lin[1] += 1
    elif li[i][0] == "R":
        lin[2] += 1
    elif li[i][0] == "C":
        lin[3] += 1
    elif li[i][0] == "H":
        lin[4] += 1
        
lis = list(combinations(lin, 3))

point = 0
for i in lis:
    point += i[0]*i[1]*i[2]

print(point)
import sympy
n=int(input())
cnt=0
a=sympy.divisors(n)


for i in range(1,len(a)):
    if n%a[i]==0:
        cnt+=1
        n=n/a[i]
print(cnt)

### FIXED CODE ###

n=int(input())

import math

def factorization(n): #nを素因数分解する
    arr = []
    temp = n
    for i in range(2, int(math.sqrt(n))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append(cnt)

    if temp!=1:
        arr.append(1)

#    if arr==[]:
#        arr.append([n, 1])  #n=1でarr=[1,1]としたいとき

    return arr

z=factorization(n)

ans=0
for i in range(len(z)):
    for j in range(1,z[i]+1):
        if (z[i]-j)>=0:
            z[i]-=j
            ans+=1
        else:
            break
print(ans)
n = input()
l=[]
count=0
for i in range(len(n)):
    if n[i]=="A" or n[i]=="C" or n[i]=="G" or n[i]=="T":
        count+=1
    else:
        l.append(count)
        count=0
print(max(l))   

### FIXED CODE ###

n=list(input())
count=0
ans=[]
for i in range(len(n)):
    if n[i]=="A" or n[i]=="C" or n[i]=="G" or n[i]=="T":
        count+=1
    else:
        ans.append(count)
        count=0
ans.append(count)
print(max(ans))
a,b,c=map(int(input().split())
A=[a,b,c]
A.sort()
print(abs(A[0]-A[1])+abs(A[1]-A[2]))

          


### FIXED CODE ###

a,b,c=map(int,input().split())
A=[a,b,c]
A=sorted(A)
print(abs(A[0]-A[1])+abs(A[1]-A[2]))
h, w = map(int, input().split())
s = ["a"*(w+2)] + ["a" + input() + "a" for i in range(h)] + ["a"*(w+2)]

for i in range(1, h+1):
  for j in range(1, w+1):
    if s[i][j] != "#":
      c = [s[i-1][j-1], s[i-1][j], s[i-1][j+1], s[i][j-1], s[i][j+1], s[i+1][j-1], s[i+1][j], s[i+1][j+1]]
      s[i][j] = str(c.count("#"))
      
for i in s:
  print(i)

### FIXED CODE ###

h, w = map(int, input().split())
s = ["a"*(w+2)] + ["a" + input() + "a" for i in range(h)] + ["a"*(w+2)]

ans = []
for i in range(1, h+1):
  for j in range(1, w+1):
    if s[i][j] == "#":
      ans.append("#")
    else:
      c = [s[i-1][j-1], s[i-1][j], s[i-1][j+1], s[i][j-1], s[i][j+1], s[i+1][j-1], s[i+1][j], s[i+1][j+1]]
      ans.append(c.count("#"))
      
for i in range(h):
  print("".join(list(map(str, ans[i*w:(i+1)*w]))))
a = input()
if a.isupper():
    print(A)
else:
    print(a)


### FIXED CODE ###

a = input()
if a.isupper():
    print('A')
else:
    print('a')
n,k=map(int,input().split(()))
ls=list(map(int,input().split()))
l=len('{:b}'.format(k))
r=0
for i in range(l-1,-1,0):
    c=0
    for j in ls:
        if j>>i & 1:
            c+=1
    if c<n//2:
    p=1<<i
    if r+p<=k:
        r=r+p
sum=0
for i in ls:
    sum+=i^r
print(sum)

### FIXED CODE ###

n, k = [int(x) for x in input().split()]
a_list = [int(x) for x in input().split()]
s=0
l = len(bin(k)) - 2
b = n / 2
x = 0
for i in range(l, -1, -1):
    count = sum([(a >> i) & 1 for a in a_list])
    if count < b:
        temp = 1 << i
        if x + temp <= k:
            x += temp
print(sum([x ^ a for a in a_list]))
def main():
    _ = int(input())
    # nums = [int(input()) for _ in range(N)]
    nums = map(int, input().split())
    counter = 0
    loop = True
    while loop:
        for i, n in enumerate(nums):
            if n % 2 == 0:
                nums[i] = n / 2
            else:
                loop = False
                break
        if loop:
            counter += 1
    print(counter)


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    _ = int(input())
    nums = [int(i) for i in input().split()]
    # nums = map(int, input().split())
    counter = 0
    loop = True
    while loop:
        for i, n in enumerate(nums):
            if n % 2 == 0:
                nums[i] = n / 2
            else:
                loop = False
                break
        if loop:
            counter += 1
    print(counter)


if __name__ == '__main__':
    main()
import numpy as np
 
N = int(input())
A = list(map(int, input().split()))  
a = 1
if 0 in A:
	print(0)
for i in range(N):
  a = a*A[i] 
	if (a > 10**18):
  	a = -1
    return
print(a)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
wa = 1
ka = 0
if(a.count(0)>=1):
  print(0)
  ka +=1
else:
  for i in range(n):
    wa = wa*a[i]
    if(wa>10**18):
      print("-1")
      ka +=1
      break
if(ka==0):
  print(wa)
import sys
from io import StringIO
import unittest
import numpy as np


def resolve():
    N = int(input())
    L = [list(map(int, input().split())) for i in range(N)]
    L.sort(key=lambda v: v[1])
    A_sum = 0
    for a, b in L:
        A_sum += a
        if (b < A_sum):
            print("No")
            return
    print("Yes")
resolve()

### FIXED CODE ###

import sys
from io import StringIO
import unittest
import numpy as np


def resolve():
    N = int(input())
    L = [list(map(int, input().split())) for i in range(N)]
    L.sort(key=lambda v: v[1])
    A_sum = 0
    for a, b in L:
        A_sum += a
        if (b < A_sum):
            print("No")
            return
    print("Yes")
resolve()
n = int(input())
a = map(int, input().split())
ans = 1

while True:
  if a%2 == 1:
    print(0)
  print(ans)
  ans += 1

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
ans = 0

while True:
  if [i for i in a if i%2 == 1]:
    break
  a = [ i//2 for i in a]
  ans += 1
print(ans)
N , A, B = int(input().split())
S = str(N)
count = 0
s for a in S:
  s = [a for a in S]
i for i in range(S):
  Ns = sum(s[i])
if A <= Ns <= B:
  count += N
print(count)

### FIXED CODE ###

N, A, B = list(map(int, input().split()))
print(sum(i for i in range(1,N+1) if A<=sum(map(int,str(i)))<=B))
n=int(input())
p=list(map(int,input().split(())))
count=0
for i in range(n);
    if p[i] != i+1:
        count+=1
if count==0 or count==2:
    print("Yes")
else:
    print("Noß")



### FIXED CODE ###

N = int(input())
p = list(map(int,input().split()))
count = 0

for i in range(N):
  if p[i] != i + 1:
    count += 1
    
if count <= 2:
  print('YES')
else:
  print('NO')
a, b, c, d, e = int(input()),int(input()),int(input()),int(input()),int(input())
k = int(input())
print("Yay!" if e-a<=k else":("))


### FIXED CODE ###

a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
k = int(input())

ab = b-a
ac = c-a
ad = d-a
ae = e-a
bc = c-b
bd = d-b
be = e-b
cd = d-c
ce = e-c
de = e-d

if ab <= k and ac <= k and ad <= k and ae <= k and bc <= k and bd <= k and be <= k and cd <= k and ce <= k and de <= k:
    print("Yay!")
else:
    print(":(")
n, k = map(int, input().split())
x = list(map(int, input().split()))

# if 0 in x:
#     x.remove(0)
#     k -= 1

if k==0:
    print(0)

else:
    flag01 = 0
    flag02 = 0
    
    i=0
    if x[0]>=0:
        print(x[k-1])
    else:
        while(x[i]<0 and i+k-1<n):
            xtmp = x[i:i+k]
            if flag01==1:
                MIN = min(MIN, abs(xtmp[-1]))
                break

            if xtmp[0]<0 and xtmp[1]>0:
                flag01 = 1
            if i<n-k:
                if x[i+k]>0 and x[i+k-1]<0:
                    flag02=1

            if flag02==1:
                MIN = min(MIN, abs(xtmp[0]))             

            if i==0:
                MIN = abs(xtmp[0])+2*abs(xtmp[-1])

            MIN = min(MIN, abs(xtmp[0])+2*abs(xtmp[-1]))
            MIN = min(MIN, 2*abs(xtmp[0])+abs(xtmp[-1]))

            i+=1

        print(MIN)

### FIXED CODE ###

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

n, k = map(int, input().split())
X = list(map(int, input().split()))
ans = 10**10
for i in range(n-k+1):
    left = X[i]
    right = X[i+k-1]
    ans = min(ans, abs(left)+abs(left-right), abs(right)+abs(right-left))
print(ans)
import sys
import copy
import math
import bisect
import pprint
import bisect
from functools import reduce
from copy import deepcopy
from collections import deque

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

if __name__ == '__main__':
    a = [str(i) for i in input().split()]
    count = 0

    for i in range(4):
        if a[i] == "+":
            count +=1
        else:
            count -=1
    print(count)

### FIXED CODE ###

import sys
import copy
import math
import bisect
import pprint
import bisect
from functools import reduce
from copy import deepcopy
from collections import deque

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

if __name__ == '__main__':
    a = [str(i) for i in input().split()]
    count = 0

    for i in range(4):
        if a[0][i] == "+":
            count +=1
        else:
            count -=1
    print(count)
s = input()
a = s[::-1]
b = (s[0:((len(s)-1)//2])
c = (s[((len(s)*3)//2:-1])
if s == a and b == c:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

s = input()
n = len(s)
a = s[0:(n-1)//2]
b = s[(n+3)//2-1:n]
if s ==s[::-1] and a == a[::-1] and b == b[::-1] :
    print("Yes")
else:
    print("No")
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()


N=int(input())
X=input()
C=X.count("1")

lst=[]
for x in [C-1,C+1]:

    if C<0:
        lst.append(-1)
    else:
        Z=0
        p=1
        for i in range(N):
            if X[-i-1]=="1":
                Z+=p
            p*=2
            Z%=x
        lst.append(Z)

#print(lst)
for i in range(N):

    _C=C+(1 if X[i]=="0"  else -1 )
    if  X[i]=="0":
        lstidx=1
    else:
        lstidx=0

    idx=(N-1-i)

    value=lst[lstidx]+(pow(2,idx,_C) if  X[i]=="0" else -pow(2,idx,_C))
    #print(lst[lstidx],value)
    count=0
    while value:
        count+=1
        value%=_C
        _C=0
        bit=value
        while bit:
            _C+=bit&1
            bit>>=1
    print(max(count,1))


### FIXED CODE ###

from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()


N=int(input())
X=input()
C=X.count("1")

lst=[]
lstcount=[]
for x in [C-1,C+1]:
    flg=0
    if x<=0:
        lst.append(0)
        lstcount.append(0)
    else:
        Z=0
        p=1
        for i in range(N):
            if X[-i-1]=="1":
                Z+=p
            p*=2
            if Z>=x:
                Z%=x
                flg=1
            if flg:
                p%=x
        lst.append(Z)
        lstcount.append(flg)
#print(lst)
fac1=[1]
fac2=[1]
C1=max(C-1,1)
C2=max(C+1,1)
for i in range(N):
    fac1.append(fac1[-1]*2%C1)
    fac2.append(fac2[-1]*2%C2)

for i in range(N):

    _C=C+(1 if X[i]=="0"  else -1 )
    if _C==0:
        print(0)
        continue
    if  X[i]=="0":
        lstidx=1
    else:
        lstidx=0

    idx=(N-1-i)

    value=lst[lstidx]+(fac2[idx] if  X[i]=="0" else -fac1[idx])
    #print(value,X[i]=="0",lst,C-1,C+1)
    bit=value
    count=0
    while value and _C:
        count+=1
        value%=_C
        _C=0
        bit=value
        while bit:
            _C+=bit&1
            bit>>=1
    print(max(count,1))
import sys
def main():
    input = sys.stdin.readline
    N = int(input())
    E = [[] for _ in range(N)]
    for i in range(N-1):
        a, b = map(int, input().split())
        a, b = a-1, b-1
        E[a].append((b,i))
        E[b].append((a,i))
    
    def dfs(s, g):
        par = [(-1,-1)] * N
        par[s] = (s,-1)
        stack = [s]
        while stack:
            v = stack.pop()
            for to, i in E[v]:
                if par[to][0] >= 0: continue
                par[to] = (v, i)
                if to == g: break
                stack.append(to)
        r = 0
        v = g
        while v != s:
            v, i = par[v]
            r |= 1 << i
        return r
    
    M = int(input())
    path = [0] * M
    for i in range(M):
        u, v = map(int, input().split())
        u, v = u-1, v-1
        path[i] = dfs(u, v)

    def calc(s): return 1<<(N-1-popcount(s))

    i_ans = 0
    for p in range(1, 1<<M):
        is_odd = 0
        s = 0
        for i in range(M):
            if p&1:
                s |= path[i]
                is_odd ^= 1
            p >>= 1
        if is_odd: i_ans += calc(s)
        else: i_ans -= calc(s)

    print((1<<(N-1)) - i_ans)

def popcount(x):
    x = (x & 0x5555555555555555) + (x >> 1 & 0x5555555555555555)
    x = (x & 0x3333333333333333) + (x >> 2 & 0x3333333333333333)
    x += (x >> 4) & 0x0f0f0f0f0f0f0f0f
    x += x >> 8
    x += x >> 16
    x += x >> 32
    return x & 0x7f

if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import deque
from collections import Counter
N=int(input())
E=[set() for _ in range(N)]
for i in range(N-1):
    a,b=map(lambda x:int(x)-1,input().split())
    E[a].add((b,i))
    E[b].add((a,i))
M=int(input())
P=[tuple(map(lambda x:int(x)-1,input().split())) for _ in range(M)]

pc=[set() for _ in range(M)] #各制約で使用する辺の集合

def bfs(S,G,p):
    q=deque([S])
    parent=[(-1,-1)]*N
    while q:
        n=q.popleft()
        for to,i in E[n]:
            if parent[to][0]!=-1:
                continue
            parent[to]=(n,i)
            if to==G:
                break
            q.append(to)
    n=G
    while n!=S:
        n,i=parent[n]
        pc[p].add(i)

for i,p in enumerate(P):
    bfs(p[0],p[1],i)

ans=0
for i in range(1<<M):
    whiteset=set()
    sign=1
    for j in range(M):
        if i>>j&1:
            whiteset|=pc[j]
            sign*=-1
    ans+=sign*(1<<(N-1-len(whiteset)))

print(ans)
def main(n: int, a: list):
    prev = [0, 0]
    ans = 0

    for _a in a:
        if _a == prev[0]:
            if prev[1] % 2 == 0:
                ans += 1

            prev[1] += 1
        else:
            prev = [_a, 0]

    print(ans)


if __name__ == '__main__':
    n = int(input())
    a = map(int(input().split()))

    main(n, a)


### FIXED CODE ###

def main(n: int, a: list):
    prev = [0, 0]
    ans = 0

    for _a in a:
        if _a == prev[0]:
            if prev[1] % 2 == 0:
                ans += 1

            prev[1] += 1
        else:
            prev = [_a, 0]

    print(ans)


if __name__ == '__main__':
    n = int(input())
    a = map(int, input().split())

    main(n, a)
import math
from functools import reduce

n = int(input())
a = [int(_) for _ in input().split()]
ans = 0

for i in range(n):
    r = reduce(math.gcd, a[:i] + a[i+1:])
    if ans < r:
        ans = r

print(ans)


### FIXED CODE ###

import fractions
from functools import reduce

n = int(input())
a = [int(_) for _ in input().split()]
left, right, ans = ([0], [0], 0)

for i in range(n):
    left.append(fractions.gcd(left[i], a[i]))
    right.append(fractions.gcd(right[i], a[n-i-1]))

for i in range(n):
    g = fractions.gcd(left[i], right[n-i-1])
    if ans < g:
        ans = g

print(ans)
2*5=10
100*100=10000

### FIXED CODE ###

a,b = map(int,input(). split ())
print(a*b)
N,K = map(int,input().split())
A = list(map(int,input().split()))
MOD = 10**9+7

if all(a<0 for a in A):
    A.sort()
    ans = 1
    for _ in range(K):
        ans *= A.pop()
        ans %= MOD
    print(ans)
    exit()

arr = []
for a in A:
    if a < 0:
        arr.append((-a,1))
    else:
        arr.append((a,0))

arr.sort()
pz = []
ng = []
ans = 1
for _ in range(K):
    v,s = arr.pop()
    if s:
        ng.append(v)
    else:
        pz.append(v)

for v in ng:
    ans *= v
    ans %= MOD
for v in pz:
    ans *= v
    ans %= MOD
if len(ng)%2 == 0:
    print(ans)
    exit()

b = pz[-1] if pz else None
c = ng[-1] if ng else None
a = d = None
while arr and (a is None or d is None):
    v,s = arr.pop()
    if s:
        if a is None:
            a = v
    else:
        if d is None:
            d = v

if (a is not None and b is not None) or (c is not None and d is not None):
    print(ans)
    exit()

if a is None or b is None:
    ans *= c * pow(d,-1,MOD)
elif c is None or d is None:
    ans *= a * pow(b,-1,MOD)
else:
    if a*d > b*c:
        ans *= a * pow(b,-1,MOD)
    else:
        ans *= c * pow(d,-1,MOD)
ans %= MOD
print(ans)

### FIXED CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
MOD = 10**9+7

if all(a>=0 for a in A):
    A.sort()
    ans = 1
    for _ in range(K):
        ans *= A.pop()
        ans %= MOD
    print(ans)
    exit()
if all(a<0 for a in A):
    A.sort(reverse=K%2==0)
    ans = 1
    for _ in range(K):
        ans *= A.pop()
        ans %= MOD
    print(ans)
    exit()
if N==K:
    ans = 1
    for a in A:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

arr = []
for a in A:
    if a < 0:
        arr.append((-a,1))
    else:
        arr.append((a,0))

arr.sort()
pz = []
ng = []
for _ in range(K):
    v,s = arr.pop()
    if s:
        ng.append(v)
    else:
        pz.append(v)

if len(ng)%2 == 0:
    ans = 1
    for v in ng:
        ans *= v
        ans %= MOD
    for v in pz:
        ans *= v
        ans %= MOD
    print(ans)
    exit()

b = pz[-1] if pz else None
c = ng[-1] if ng else None
a = d = None
while arr and (a is None or d is None):
    v,s = arr.pop()
    if s:
        if a is None:
            a = v
    else:
        if d is None:
            d = v

if (a is None or b is None) and (c is None or d is None):
    assert False

ans = 1
if a is None or b is None:
    ans = d
    for v in ng[:-1]:
        ans *= v
        ans %= MOD
    for v in pz:
        ans *= v
        ans %= MOD
elif c is None or d is None:
    ans = a
    for v in ng:
        ans *= v
        ans %= MOD
    for v in pz[:-1]:
        ans *= v
        ans %= MOD
else:
    if a*c > b*d:
        ans = a
        for v in ng:
            ans *= v
            ans %= MOD
        for v in pz[:-1]:
            ans *= v
            ans %= MOD
    else:
        ans = d
        for v in ng[:-1]:
            ans *= v
            ans %= MOD
        for v in pz:
            ans *= v
            ans %= MOD
ans %= MOD
print(ans)