Harryxun/stf_run huggingface dataset:
# -*- cod:utf-8 -*-
import sys

sys.setrecursionlimit(1000000)

def dfs(x, y, sym):
    field[x][y] = '.'
    for dx in range(-1,2):
        if dx==-1 or dx==1:
            nx = x + dx
            ny = y
            if(nx>=0 and nx<N and 0<=ny and ny<M and field[nx][ny]==sym):
                dfs(nx, ny, sym)
        else:
            nx = x
            for dy in [-1,1]:
                ny = y + dy
                if(nx>=0 and nx<N and 0<=ny and ny<M and field[nx][ny]==sym):
                    dfs(nx, ny, sym)
def solve():
    res = 0
    flg=0
    for i in range(N):
        for j in range(M):
            if not field[i][j] == '.':
                if field[i][j] == '@':
                    dfs(i, j, '@')
                    res += 1
                elif field[i][j] == '#':
                    dfs(i, j, '#')
                    res += 1
                else:
                    dfs(i, j, '*')
                    res += 1
    print(res)


while True:
    datas = sys.stdin.readlines()
    data = datas[0].split(' ')
    N = int(data[0])
    M = int(data[1])
    if ' ' in data[-1]:
        data2 = datas[-1].split(' ')
        L = int(data2[0])
        K = int(data2[1])
        if L==0 and K==0:
            break
    field = [[0 for i in range(N) ]for j in range(M)]

    for i in range(M):
        field[i] = list(datas[i+1])[0:-1]
    solve()

### FIXED CODE ###

# -*- coding:utf-8 -*-
import sys
def dfs(x, y, sym):
	tile[x][y] = "."
	for i in range(len(DX)):
		nx = x + DX[i]
		ny = y + DY[i]
		if (0<=nx and nx<N and 0<=ny and ny<M and tile[nx][ny] is sym):
			dfs(nx, ny, sym)

def solve():
	res = 0
	for i in range(N):
		for j in range(M):
			sym = tile[i][j]
			if tile[i][j] != ".":
				if tile[i][j] is sym:
					dfs(i, j, sym)
					res += 1
	print(res)

counter=0
DX = [-1,0,1,0]
DY = [0,-1,0,1]
sys.setrecursionlimit(10**7)
while True:
	line = input()
	if " " in line:
		nums = line.split(" ")
		N = int(nums[0])
		M = int(nums[1])
		tile = [[0 for i in range(M)] for j in range(N)]
	else:
		tile[counter-1] = list(line)
	if N is 0 and M is 0:
		break
	counter += 1
	if counter-1 is N:
		solve()
		counter = 0
X=int(input())
B=0
C=0
for i in range(0,360):
    B=B+X
    C=B%360
    K=K+1
    if C==0:
        print(K)
        break
        
    
    

### FIXED CODE ###

X=int(input())
K=0
B=0
C=0
for i in range(0,360):
    B=B+X
    C=B%360
    K=K+1
    if C==0:
        print(K)
        break
MOD = 10**9 + 7
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
dp = [0] * (1 << N)
dp[0] = 1
prev = [0]
for i, a in enumerate(A):
    temp = []
    for j in [k for k, v in a if v == 1]:
        bit = 1 << j
        for s in prev:
            if s & bit == 0:
                new_s = s | bit
                dp[new_s] += dp[s]
                dp[new_s] %= MOD
                temp.append(new_s)
    prev = list(set(temp))
print(dp[(1 << N) - 1])

### FIXED CODE ###

MOD = 10**9 + 7
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
dp = [0] * (1 << N)
dp[0] = 1
bits = [1 << i for i in range(N)]
cands = [[] for _ in range(N+1)]
for s in range(1 << N):
    temp = 0
    for n in range(N):
        if s & (1 << n): temp += 1
    cands[temp].append(s)
for i, a in enumerate(A):
    for j in [k for k, v in enumerate(a) if v == 1]:
        bit = bits[j]
        for s in cands[i]:
            if s & bit == 0:
                new_s = s | bit
                dp[new_s] += dp[s]
                dp[new_s] %= MOD
print(dp[-1])
n, k = map(int, input().split())
A = list(map(int, input().split()))
S = [0] * (n + 1)
for i in range(n):
    S[i+1] = S[i] + A[i]

C = [0] * k
ans = 0
for i in range(n+1):
    j = i - k
    mi = (S[i] - i) % k
    mj = (S[j] - j) % k
    if j >= 0:
        C[mj] -= 1
    ans += C[mi]
    C[mi] += 1
print(ans)

### FIXED CODE ###

from collections import defaultdict

n, k = map(int, input().split())
A = list(map(int, input().split()))
S = [0] * (n + 1)
for i in range(n):
    S[i+1] = S[i] + A[i]

f = lambda n: (S[n] - n) % k
C = defaultdict(int)
ans = 0
for i in range(n):
    C[f(i)] += 1
    j = i - k + 1
    if 0 <= j:
        C[f(j)] -= 1
    ans += C[f(i+1)]
print(ans)
a,b,x = map(int,input().split())

    print((b - a) // x)

### FIXED CODE ###

a,b,x = map(int,input().split())
if a != 0:
    print(b // x - (a - 1) // x)
else:
    print(b // x + 1)
a, b, m = map(int, input().split())
a_price = list(map(int, input().split()))
b_price = list(map(int, input().split()))
coupon = []
for _ in range(m):
  coupon.append(list(map(int, input().split())))
  
a_min = a_price.sort()[0]
b_min = b_price.sort()[0]
min = a_min + b_min
totals = [min]
for list in coupon:
  tmp = a_list[list[0]-1] + b_list[list[1]-1] - list[2]
  totals.append(tmp)

totals.sort()
ans = totals[0]

print(ans)

### FIXED CODE ###

a, b, m = map(int, input().split())
a_price = list(map(int, input().split()))
b_price = list(map(int, input().split()))
coupon = []
for _ in range(m):
    coupon.append(list(map(int, input().split())))

a_copy = a_price.copy()
a_copy.sort()
b_copy = b_price.copy()
b_copy.sort()
a_min = a_copy[0]
b_min = b_copy[0]
min = a_min + b_min
totals = [min]
for list in coupon:
    tmp = a_price[list[0] - 1] + b_price[list[1] - 1] - list[2]
    totals.append(tmp)

totals.sort()
ans = totals[0]

print(ans)
x1, y1, x2, y2 = map(int, input().split())

a, b = abs(x2 - x1), abs(y1 - y2)

print(a, b)

if (x1 <= x2)and(y1 <= y2):
    x3, y3 = x2 - b, y2 + a
    x4, y4 = x3 - a, y3 - b
elif (x1 > x2)and(y1 < y2):
    x3, y3 = x2 - b, y2 - a
    x4, y4 = x3 + a, y3 - b
elif (x1 > x2)and(y1 > y2):
    x3, y3 = x2 + b, y2 - a
    x4, y4 = x3 + a, y3 + b
elif (x1 < x2)and(y1 > y2):
    x3, y3 = x2 + b, y2 + a
    x4, y4 = x3 - a, y3 + b


print("{} {} {} {}".format(x3, y3, x4, y4))

### FIXED CODE ###

x1, y1, x2, y2 = map(int, input().split())

a, b = abs(x2 - x1), abs(y1 - y2)

if (x1 <= x2)and(y1 <= y2):
    x3, y3 = x2 - b, y2 + a
    x4, y4 = x3 - a, y3 - b
elif (x1 >= x2)and(y1 <= y2):
    x3, y3 = x2 - b, y2 - a
    x4, y4 = x3 + a, y3 - b
elif (x1 >= x2)and(y1 >= y2):
    x3, y3 = x2 + b, y2 - a
    x4, y4 = x3 + a, y3 + b
elif (x1 <= x2)and(y1 >= y2):
    x3, y3 = x2 + b, y2 + a
    x4, y4 = x3 - a, y3 + b

print(x3, y3, x4, y4)
import sys

input = sys.stdin.readline
S =  input()
S = S.replace("\n","")
s_list = list(S)
alpha_list = [chr(i) for i in range(97, 97+26)]
flag_list = [False for _ in range(23)]


if len(s_list) == 26:
    for i in range(25, 0, -1):
        if s_list[i - 1] < s_list[i]:
            c = 'ω'
            for j in range(i, 26):
                if s_list[i - 1] < s_list[j]:
                    c = min(c, s_list[j])
            print(S[:i-1] + c)
            exit(0)
    print(-1)

else:
    for i,alpha in enumerate(alpha_list):
        if alpha in s_list:
            flag_list[i] = True
    for i,flag in enumerate(flag_list):
        if not flag:
            print(S + alpha_list[i])
            break

### FIXED CODE ###

import sys

input = sys.stdin.readline
S =  input()
S = S.replace("\n","")
s_list = list(S)
alpha_list = [chr(i) for i in range(97, 97+26)]
flag_list = [False for _ in range(26)]


if len(s_list) == 26:
    for i in range(25, 0, -1):
        if s_list[i - 1] < s_list[i]:
            c = 'ω'
            for j in range(i, 26):
                if s_list[i - 1] < s_list[j]:
                    c = min(c, s_list[j])
            print(S[:i-1] + c)
            exit(0)
    print(-1)

else:
    for i,alpha in enumerate(alpha_list):
        if alpha in s_list:
            flag_list[i] = True
    for i,flag in enumerate(flag_list):
        if not flag:
            print(S + alpha_list[i])
            break
a,b,c = map(int,input().split())
print(max(0,b+c-a)

### FIXED CODE ###

a,b,c = map(int,input().split())
if b+c<=a:
  ans=0
else:
  ans = (b+c)-a
print(ans)
x = input().split(" ")
a = int(x[0])
b = int(x[1])

print((a * b), (a + b) * 2))

### FIXED CODE ###

x = input().split()
 
a = int(x[0])
b = int(x[1])
 
print((a * b),((a + b) * 2))
S = input()

words = []
words.append(S)
words.append(S[:(N-1)//2])
words.append(S[(N+3)//2 - 1:])

ans = all([word == word[::-1] for word in words])

print("Yes" if ans else "No")

### FIXED CODE ###

import sys
S = input()
N = len(S)

if S == S[::-1]:
    if S[0:(N-1)//2] == S[0:(N-1)//2][::-1]:
        if S[((N+3)//2)-1:N] == S[((N+3)//2)-1:N][::-1]:
            print("Yes")
            sys.exit()


print("No")
from collections import Counter
N,K = (int(i) for i in input().split())
A = [int(i) for i in input().split()]
d = [a for a in Counter(A).values()]
tmp = 0
for i in range(min(K,len(set(d))+1)):
    tmp += max(d)
    d.remove(max(d))
print(len(A)-tmp)


### FIXED CODE ###

from collections import Counter
N,K = (int(i) for i in input().split())
d = Counter([int(i) for i in input().split()])
if len(d) <= K:
    print(0)
    exit()

tmp = 0
for _,p in d.most_common(K):
    tmp += p
print(N-tmp)
N, X, Y = map(int, input().split(' '))

dct = {X : Y}
short = Y - X - 1

dist_list = [0] * N

for i in range(1,N):
    for j in range(i+1,N+1):
        d1 = abs(X - i) + 1 + abs(Y - j)
        d2 = j - i
        dist = min(d1,d2)
        dist_list[dist] += 1

for k in range(1,N):
    print(dist[k])

### FIXED CODE ###

N, X, Y = map(int, input().split(' '))

dist_list = [0] * N

for i in range(1,N):
    for j in range(i+1,N+1):
        d1 = abs(X - i) + 1 + abs(Y - j)
        d2 = j - i
        dist = min(d1,d2)
        dist_list[dist] += 1

for k in range(1,N):
    print(dist_list[k])
a,b,k = map(int,input().split())

yakusuu_array = []

for ab in [a,b]:
    yakusuu_array_ab = []
    for i in range(1,ab):
        if ab % i == 0:
            yakusuu_array_ab.append(i)
    yakusuu_array.append(yakusuu_array_ab)

kouyakusuu = list(set(yakusuu_array[0]) & set(yakusuu_array[1]))

if len(kouyakusuu) == 0:
    print(1)
else:
    print(kouyakusuu[k-1])


### FIXED CODE ###

a,b,c = map(int,input().split())
oto = b//a
if oto >= c:
    oto = c
print(oto)
N = int(input())
A = list(input().split())

edge_list =  []
selection = list(set(A)).sort()[::-1]

for i in selection:
    edge_list += i * (A.count(i) // 2)
    if len(edge_list) >= 2:
        break
edge_list.sort()

if len(edge_list) < 2:
    print(0)
else:
    print(int(edge_list[-1]) * int(edge_list[-2]))

### FIXED CODE ###

import collections
N = int(input())
A = list(map(int, input().split()))

x = 0
y = 0
selection = sorted(list(set(A)))[::-1]
c = collections.Counter(A)
for i in selection:
    if c[i] >= 4:
        if x == 0:
            x = i
        if y == 0:
            y = i
    elif c[i] >= 2:
        if x == 0:
            x = i
        elif y == 0:
            y = i
    if x != 0 and y != 0:
        print(x * y)
        exit()

print(x * y)
def mostFrequent(L):
  return max(set(A), key = A.count)

N = input()
L = []
for i in range(0,N):
  L.append(input())
print(mostFrequent(L))

### FIXED CODE ###

from collections import defaultdict
from collections import OrderedDict
N = int(input())
ans = dict()
for _ in range(N):
    k = str(input())
    if k in ans:
        ans[k]+=1
    else:
        ans.update({k:1})
groupedByValue = defaultdict(list)
for key, value in sorted(ans.items()):
    groupedByValue[value].append(key)
l = groupedByValue[max(groupedByValue)]
for i in l:
    print(i)
def f(vs,i):
	# print(vs)
	for j in range(len(vs)):
		if vs[j]+i in vs:
			a = vs[j]
			b = vs[j]+i
			print(a,b)
			vs.remove(a)
			vs.remove(b)
			return

n,m = map(int,input().split())
vs = list(range(1,n+1))

for i in range(1,m+1):
	f(vs,i)

### FIXED CODE ###

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

ans = 'NG'
for i in range(a,b+1):
	if i%k == 0:
		ans = 'OK'

print(ans)
r = map(int,input())
s = 3 * r ** 2
print(s)

### FIXED CODE ###

r = int(input())
s = 3 * r * r
print(s)
N, C, D = map(int, input().split())
check = [i*i for i in range(N)]
time = 0
stop = N * N

if C * D % 2 ==1:
 for i in range(2*N):
  for j in range(2*N):
   if (i + j) % 2 == 0:
    print(i, j)
    time += 1
    if stop == time:
     break
  if stop == time:
   break
elif (C+D) % 2 == 0:
 for i in range(2*N):
  for j in range(2*N):
   if (i + j) % 2 == 1:
    print(i, j)
    time += 1
    if stop == time:
     break
  if stop == time:
   break



 

### FIXED CODE ###

N = int(input())
while(N%10 == 0):
 N /= 10
if N == 1:
 print(10)
else:
 s = str(N)
 array = list(map(int, list(s)))
 print(sum(array))
n=int(input())
s=len(n)
N=''
for i in range(s[:s+1:-1]):
    a = n % (10**i)
    N.append(a)
al = sum(N)
if n%al == 0:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

n=input()
f=0
for i in range(len(n)):
    f += int(n[i])
if int(n) % f == 0:
    print('Yes')
else:
    print('No')
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
def main():
    s = input()
    t = input()
    if t in s:
        print(0)
        sys.exit()
    if len(s) == 1 and len(t) == 1:
        if s in t:
            print(0)
            sys.exit()
        else:
            print(1)
            sys.exit()

    lent = len(t)
    lens = len(s)
    res = []
    for i1 in range(lent):
        tmp1 = t[i1:]
        for i2 in range(lent, i1, -1):
            end = lens - (lent - i2)
            if t[i1:i2] in s[i1:end]:
                res.append(i1 + (lent - i2))

    r = min(res)
    print(r)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
def main():
    s = input()
    t = input()
    if t in s:
        print(0)
        sys.exit()
    if len(s) == 1 and len(t) == 1:
        if t != s:
            print(1)
            sys.exit()
    lens = len(s)
    lent = len(t)
    res = set()
    for i1 in range(lens - lent + 1):
        tmp1 = sum([c1 == c2 for c1, c2 in zip(t, s[i1:i1+lent])])
        res.add(lent - tmp1)
        #print(s[i1:i1+lent], res)
    if res:
        r = min(res)
        print(r)
    else:
        print(lent)

if __name__ == '__main__':
    main()
A,B = map(int,input().aplir())
print((A-1)*(B-1))

### FIXED CODE ###

# -*-  coding: utf-8 -*-
n,m=map(int,input().split())
print("{}".format((n-1)*(m-1)))
n, k = list(map(int, input().split()))
x = [int(inout()) for i in range(n)]
ans = [min(abs(x[i]), abs(x[i+k-1]))+x[i+k-1]-x[i] for i in range(n-k+1)]
print(min(ans))

### FIXED CODE ###

n, k = list(map(int, input().split()))
x = list(map(int, input().split()))
ans = [min(abs(x[i]), abs(x[i+k-1]))+x[i+k-1]-x[i] for i in range(n-k+1)]
print(min(ans))
import math
N,K = map(int, input().split())
a = list(map(int,input().split()))
l = 0
r = K - 1
Min = float("inf")
for i in range(N - K + 1):
    if(a[l]*a[r]<=0):#原点を跨ぐとき
        Min = min(Min,abs(a[l])+abs(a[l]-a[r]),abs(a[r])+abs(a[r]-a[l]))
    elif(l==0):#左端の時
        if(a[r]*a[r+1]<0 or a[0]>0):
            Min = min(Min,abs(a[l])+abs(a[l]-a[r]),abs(a[r])+abs(a[r]-a[l]))
    elif(r==N-1):#右端の時
        if(a[l-1]*a[l]<0 or a[l]>0):
            Min = min(Min,abs(a[l])+abs(a[l]-a[r]),abs(a[r])+abs(a[r]-a[l]))
    else:
        if(a[r]*a[r+1]<0 or a[l-1]*a[l]<0):
            Min = min(Min,abs(a[l])+abs(a[l]-a[r]),abs(a[r])+abs(a[r]-a[l]))
    l = l + 1
    r = r + 1
print(Min)


### FIXED CODE ###

import math
N,K = map(int, input().split())
a = list(map(int,input().split()))
l = 0
r = K - 1
Min = float("inf")
for i in range(N - K + 1):
    if(a[l]*a[r]<=0):#原点を跨ぐとき
        Min = min(Min,abs(a[l])+abs(a[l]-a[r]),abs(a[r])+abs(a[r]-a[l]))
    elif(l == 0 and r == N-1):
        Min = min(Min,abs(a[l])+abs(a[l]-a[r]),abs(a[r])+abs(a[r]-a[l]))        
    elif(l==0):#左端の時
        if(a[r]*a[r+1]<0 or a[0]>0 or (a[N-1]<0 and r == N-1)):
            Min = min(Min,abs(a[l])+abs(a[l]-a[r]),abs(a[r])+abs(a[r]-a[l]))
    elif(r==N-1):#右端の時
        if(a[l-1]*a[l]<0 or (a[l]>0 and l == 0) or a[r] <= 0):
            Min = min(Min,abs(a[l])+abs(a[l]-a[r]),abs(a[r])+abs(a[r]-a[l]))
    else:
        if(a[r]*a[r+1]<0 or a[l-1]*a[l]<0):
            Min = min(Min,abs(a[l])+abs(a[l]-a[r]),abs(a[r])+abs(a[r]-a[l]))
    l = l + 1
    r = r + 1
print(Min)
def make_divisors(n):
    cnt = 0
    i = 1
    while i*i <= n:
        if n % i == 0:
            cnt += 1
            if i != n // i:
                cnt += 1
        i += 1
    return cnt
numbers = [1,10, 100, 1000, 10000, 100000, 200000, 250000,300000,350000, 400000,450000, 500000,750000,1000000]
datas = [0,23,473,7053,93643,1166714, 2472071, 3145923, 3829761, 4522005,5221424,5927120,6638407,10261678,13969985]

N = int(input())
ttl = 0
numPin = 0

for i in range(len(numbers)):
    if numbers[i] <= N < numbers[i+1]:
        numPin = i
        break

if numPin != len(numbers)-1:
    if N - numbers[numPin] < numbers[numPin + 1] - N:
        for i in range(numbers[numPin], N):
            ttl += make_divisors(i)
        print(ttl + datas[numPin])
    else:
        for i in range(N,numbers[numPin+1]):
            ttl -= make_divisors(i)
        print(ttl + datas[numPin + 1])
else:
    print(datas[numPin])


### FIXED CODE ###

def make_divisors(n):
    cnt = 0
    i = 1
    while i*i <= n:
        if n % i == 0:
            cnt += 1
            if i != n // i:
                cnt += 1
        i += 1
    return cnt
numbers = [1,10, 100, 1000, 10000, 100000, 150000,200000, 250000,300000,350000, 400000,450000, 500000,550000,600000,630000,675000,700000,720000,750000,800000,825000,850000,875000,900000,912500,925000,950000,975000,987500,1000000]
datas = [0,23,473,7053,93643,1166714, 1810893, 2472071, 3145923, 3829761, 4522005,5221424,5927120,6638407,7354651,8075420,8509899,9164377,9529244,9821778,10261678,10997400,11366472,11736253,12106789,12478098,12664043,12850013,13222660,13595947,13782871,13969985]

N = int(input())
ttl = 0
numPin = 0

for i in range(len(numbers)):
    if N == 1000000:
        numPin = len(numbers) - 1
        break
    if numbers[i] <= N < numbers[i+1]:
        numPin = i
        break

if numPin != len(numbers)-1:
    if N - numbers[numPin] < numbers[numPin + 1] - N:
        for i in range(numbers[numPin], N):
            ttl += make_divisors(i)
        print(ttl + datas[numPin])
    else:
        for i in range(N,numbers[numPin+1]):
            ttl -= make_divisors(i)
        print(ttl + datas[numPin + 1])
else:
    print(datas[numPin])
N, Ma, Mb = map(int, input().split())
items = []
for i in range(N):
    a, b, c = map(int, input().split())
    items.append((a, b, c))

inf = float("inf")
dp = [[[inf for _ in range(401)] for _ in range(401)] for i in range(N+1)]
dp[0][0][0] = 0

for i in range(N):
    for a in range(401):
        for b in range(401):
            dp[i + 1][a][b] = min(dp[i + 1][a][b], dp[i][a][b])
            dp[i + 1][a + items[i][0]][b + items[i][1]] = min(dp[i + 1][a + items[i][0]][b + items[i][1]],
                                                              dp[i][a][b] + items[i][2])
ans = inf
for a in range(1, 401):
    for b in range(1, 401):
        if a * Mb == b * Ma:
            ans = min(ans, dp[N][a][b])
if ans != inf:
    print(ans)
else:
    print(-1)

### FIXED CODE ###

N, Ma, Mb = map(int, input().split())
items = []
for i in range(N):
    a, b, c = map(int, input().split())
    items.append((a, b, c))

a_sum = sum([item[0] for item in items])
b_sum = sum([item[1] for item in items])
inf = float("inf")
dp = [[[inf for _ in range(a_sum + 100)] for _ in range(b_sum + 100)] for i in range(N+1)]
dp[0][0][0] = 0

for i in range(N):
    for a in range(a_sum + 1):
        for b in range(b_sum + 1):
            dp[i + 1][a][b] = min(dp[i + 1][a][b], dp[i][a][b])
            dp[i + 1][a + items[i][0]][b + items[i][1]] = min(dp[i + 1][a + items[i][0]][b + items[i][1]],
                                                              dp[i][a][b] + items[i][2])
ans = inf
for a in range(1, a_sum + 1):
    for b in range(1, b_sum + 1):
        if a * Mb == b * Ma:
            ans = min(ans, dp[N][a][b])
if ans != inf:
    print(ans)
else:
    print(-1)
N, K = map(int, input().split())
X = list(map(int, input().split()))

MOD = 10 ** 9 + 7

if K % 2 == 1 and all(v < 0 for v in X):
    # Minimize abs
    X.sort(key=lambda x: -x)
    ans = 1
    for i in range(K):
        ans = ans * X[i] % MOD
    print(ans)
else:
    pos = sorted(v for v in X if v >= 0)
    neg = sorted(-v for v in X if v < 0)

    ans = 1
    if K % 2 == 1:
        ans *= pos.pop()

    cand = []
    while len(pos) >= 2:
        tmp = pos.pop() * pos.pop()
        cand.append(tmp)

    while len(neg) >= 2:
        tmp = neg.pop() * neg.pop()
        cand.append(tmp)

    cand.sort(reverse=True)
    for i in range(K // 2):
        ans = ans * cand[i] % MOD

    print(ans)


### FIXED CODE ###

N, K, *A = map(int, open(0).read().split())

MOD = 10 ** 9 + 7
s = []  # v >= 0
t = []  # v < 0
for i in range(N):
    if A[i] < 0:
        t.append(A[i])
    else:
        s.append(A[i])
        
ok = False  # ans > 0
if len(s) > 0:
    if N == K:
        ok = len(t) % 2 == 0
    else:
        ok = True
else:
    ok = K % 2 == 0

ans = 1
if not ok:
    x = sorted(A, key=lambda x: abs(x))
    for i in range(K):
        ans = ans * x[i] % MOD
else:
    s.sort()
    t.sort(key=lambda x: abs(x))
    if K % 2 == 1:
        ans = ans * s.pop() % MOD
        
    p = []
    while len(s) >= 2:
        x = s.pop() * s.pop()
        p.append(x)
    
    while len(t) >= 2:
        x = t.pop() * t.pop()
        p.append(x)

    p.sort(reverse=True)
    for i in range(K // 2):
        ans = ans * p[i] % MOD
    
print(ans)
def Stepenica(L,i,p1,p2):
    if i<len(L):
        p3=min( p1+abs(L[i]-L[i-2]), p2+abs(L[i]-L[i-1]) )
        Stepenica(L,i+1,p2,p3)
    else:
        print(p2)
        return
    
n=int(input())
L=list(map(int,input().split()))
Stepenica(L,2,0,abs(L[0]-L[1]))
               


### FIXED CODE ###

n=int(input())
L=list(map(int,input().split()))
dp=[]
dp.append(0)
dp.append(abs(L[0]-L[1]))
for i in range(2, n):
    dp.append( min( dp[i-2]+abs(L[i]-L[i-2]), dp[i-1]+abs(L[i]-L[i-1]) ) )
print(dp[n-1])
from collections import deque

def solve():
    N, M, K = map(int, input().split())
    A = list(map(int,input().split()))
    B = list(map(int,input().split()))

    sumA = 0
    sumB = 0

    tmp = 0

    dA = deque(A)
    dB = deque(B)

    dsA = deque()
    dsB = deque()

    while dA:
        tmp = dA.popleft()
        if sumA + tmp <= K:
            dsA.append(tmp)
            sumA += tmp
        else:
            break
    
    while dB:
        tmp = dB.popleft()
        if sumB + tmp <= K:
            dsB.append(tmp)
            sumB += tmp
        else:
            break

    sumall = sumA + sumB
    lenall = len(dsA) + len(dsB)
    Atmp = 0
    Btmp = 0

    while sumall > K:
        if Atmp == 0:
            Atmp = dsA.pop()
        if Btmp == 0:
            Btmp = dsB.pop()
        if Atmp >= Btmp:
            sumall -= Atmp
            lenall -= 1
            Atmp = 0
        else:
            sumall -= Btmp
            lenall -= 1
            Btmp = 0

    print(lenall)
                 
solve()

### FIXED CODE ###


a = int(input())

print(a+a**2+a**3)
x,a,b = map(int, input().split())
if abs(x-a) < abs(x-b):
    print('A')
else :
    print('B')

### FIXED CODE ###

x,a,b = map(int, input().split())
if abs(x-a) < abs(x-b):
    print('A')
else :
    print('B')
S=int(input())
W=10

if S>W:
	print("safe")
if S<W:
	print("unsafe")

### FIXED CODE ###

S,W=map(int, input().split())
 
if S>W:
	print("safe")
if S<W:
	print("unsafe")
if S==W:
	print("unsafe")
n = int(input())
ans = 0
for i in range(pow(n,1/2)+1):
  if i**2 <= n:
    ans = i**2
print(ans)

### FIXED CODE ###

n = int(input())
ans = 0
for i in range(int(pow(n,1/2))+1):
  if i**2 <= n:
    ans = i**2
print(ans)
N,K=map(int,input().split())

con = 0
ans = list(int() for _ in range(100))
pre = 0


for _ in range(K):

    D = int(input())
    arr = list(map(int,input().split()))

    for j in range(D):

        ans[pre+j]=arr[j]

    pre += D

        
fin = (N+1) - len(set(ans))

print(fin)

### FIXED CODE ###

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

con = 0
ans = list(int() for _ in range(100000))
pre = 0


for _ in range(K):

    D = int(input())
    arr = list(map(int,input().split()))

    for j in range(D):

        ans[pre+j]=arr[j]

    pre += D

        
fin = (N+1) - len(set(ans))

print(fin)
n,m=int(input().split())
if n<=1:
    n=0
if m<=1:
    m=0
print((n*(n-1)//2)+(m*(m-1)//2))

### FIXED CODE ###

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

print((n*(n-1)//2)+(m*(m-1)//2))