Harryxun/stf_run huggingface dataset:
range = xrange
input = raw_input
MOD = 10**9+7
 
n = int(input())
 
dp = [0] * (1 << n)
for i in [i for i, x in enumerate(input().split()) if x == '1']:
    dp[1 << i] = 1
 
npow = 1 << n
 
for i in range(n - 1):
    _dp = [0] * npow
    for j in [i for i, x in enumerate(input().split()) if x == '1']:
        jpow = 1 << j
        mask = (npow - 1) ^ jpow
        x = npow
        while x:
          	x -= 1
            x &= mask
            _dp[x + jpow] += dp[x]
    for mask in range(npow):
        _dp[mask] %= MOD
    dp = _dp
 
print(sum(dp) % MOD)

### FIXED CODE ###

range = xrange
input = raw_input
MOD = 10**9+7
 
n = int(input())

dp = [0] * (1 << n)
for i in [i for i, x in enumerate(input().split()) if x == '1']:
    dp[1 << i] = 1

npow = 1 << n

for i in range(n - 1):
    _dp = [0] * npow
    for j in [i for i, x in enumerate(input().split()) if x == '1']:
        jpow = 1 << j
        mask = 0
        while mask < npow:
            _dp[mask + jpow] += dp[mask]
            mask += 1 + ((mask+1) & jpow)
    for mask in range(npow):
        _dp[mask] %= MOD
    dp = _dp
 
print(sum(dp) % MOD)
import math

x1,y1 = 0, 0

def fact(n):
    b = 2
    fct = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct.append(b)
        b = b + 1
    if n > 1:
        fct.append(n)
    return fct

S = int(input())

list1 = sorted(fact(S))#おおきいのが最後

if int(list1[-1]) <= 10**9:
  f = list1[::-1]
  st = 1
  i = 0
  while (st <= 10**9)&(i<len(list1)):
    st *= list1[i]
    i += 1
  x2,y2 = st,0
  x3,y3 = 0,S//st

else:
  list2 = []
  list2.append(int(S//list1[-1]))
  while list1[-1] > 10**9:
    dash = list1[-1]
    list1 = fact(dash + 1)
    list2.append(int((dash+1)//list1[-1]))

  sum2 = 0
  sum4 = 1
  for i in range(len(list2)-1):
    sum4 *= list2[i] 
    sum2 += sum4

  y2 = fact(sum2)[-1]
    
  b = list1[-1]
  x2 = b
  x3 = sum2//y2
  y3 = (S + x3*y2)//b
  s = x2*y3 - x3*y2
  
print(int(x1),int(y1),int(x2),int(y2),int(x3),int(y3))

### FIXED CODE ###

S = int(input())

if S == 10**18:
  x1,y1 = 0,0
  x2 = 10**9
  y3 = 10**9
  x3 = 0
  y2 = 0

else:
  x1, y1 = 0,0

#|x2y3-x3y2|=S

  x2 = 10**9
  y2 = 1

#|10**9y3-x3|= s

  y3 = (S//(10**9)) + 1
  x3 = (10**9)*y3 - S

print(int(x1),int(y1),int(x2),int(y2),int(x3),int(y3))
n=int(input())
import collections
c=collections.Counter()
from math import gcd
mod=10**9+7
for _ in range(n):
    a,b=map(int,input().split())
    g=abs(gcd(a,b))
    a//=g
    b//=g
    c[(a,b)]+=1
ans=1
s=set()
for i,j in c:
    if (i,j) not in s:
        s.add((i,j))
        s.add((-i,-j))
        s.add((-j,i))
        s.add((j,-i))
        ans*=(pow(2,c[(i,j)]+c[(-i,-j)],mod)+pow(2,c[(j,-i)]+c[(-j,i)],mod)-1)%mod
print((ans-1)%mod)

### FIXED CODE ###

import collections
from math import gcd
import sys
input=sys.stdin.readline
def main():
    n=int(input())
    c=collections.Counter()
    mod=10**9+7
    for _ in range(n):
        a,b=map(int,input().split())
        g=abs(gcd(a,b))
        if g==0:
            g=1
        a//=g
        b//=g
        c[(a,b)]+=1
    ans=1
    s=set()
    for i,j in c:
        if (i,j)==(0,0):
            continue
        if (i,j) not in s:
            s.add((i,j))
            s.add((-i,-j))
            s.add((-j,i))
            s.add((j,-i))
            ans*=(pow(2,c[(i,j)]+c[(-i,-j)],mod)+pow(2,c[(j,-i)]+c[(-j,i)],mod)-1)%mod
    print((ans-1+c[(0,0)])%mod)

if __name__ == "__main__":
    main()
a = int(input())
b = int(input())
c = int(input())

print( (a + b + c) - max(a, b, c)) 

### FIXED CODE ###

a = [i for i in input().split()]
print(int(sorted(a)[0]) + int(sorted(a)[1]))
n=int(input())
swi = "No"
for a in range(100)
  if (n - 4＊a) % 7 == 0 and n - 4＊a >= 0:
    swi="Yes"
    break
print(swi)
    
    

### FIXED CODE ###

n = int(input())
swi = "No"
for a in range(100):
    if (n - 4*a) % 7 == 0 and n - 4*a >= 0:
        swi = "Yes"
        break
print(swi)
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
s = sum(a)
cnt = Counter(a)
q = int(input())
for i in range(q):
    b, c = map(int, input().split())
    cnt_b = cnt.pop(b)
    cnt[c] += cnt_b
    s += (c - b)*cnt_b
    print(s)

### FIXED CODE ###

from collections import defaultdict
n = int(input())
a = [int(i) for i in input().split()]
dict_a = defaultdict(int)
for i in range(n):
    dict_a[a[i]] += 1
q = int(input())
s = [sum(a)] + [0] * q
for i in range(q):
    b, c = map(int, input().split())
    try:
        cnt_b = dict_a.pop(b)
        dict_a[c] += cnt_b
        s[i + 1] = s[i] + (c - b)*cnt_b
    except KeyError:
        s[i + 1] = s[i]
print(*s[1:], sep='\n')
import array

N, M = list(map(int, input().split()))
R = [[] for _ in range(N+1)]

def grp(R, i, S):
    S[i] = True
    ret = 1
    for j in range(len(R[i])):
        if S[ R[i][j] ]: continue
        ret += grp(R, R[i][j], S)
    return ret

for i in range(M):
    a, b = list(map(int, input().split()))
    R[a].append(b)
    R[b].append(a)

S = [False] * (N+1)
maxgrp = 1
for i in range(N):
    if S[i]: continue
    grpsize = grp(R, i, S)
#    print (grpsize)
    maxgrp = max(grpsize, maxgrp)

print(maxgrp)

### FIXED CODE ###

#import array
#import random
#import sys

#N, M = 200000, 200000
N, M = list(map(int, input().split()))
R = [[] for _ in range(N+1)]
G = [0] * (N+1)
Z = [0] * (N+1)

def grp(R, grpid, i, G, Z):
    stack = [i]
    while len(stack) > 0:
        k = stack.pop()
        if G[k] > 0: continue
        G[k] = grpid
        Z[grpid] += 1
        for l in range(len(R[k])):
            stack.append(R[k][l])
        
for i in range(M):
    a, b = list(map(int, input().split()))
#    a, b = random.choice(range(N)), random.choice(range(N))
    R[a].append(b)
    R[b].append(a)

grpid = 0
for i in range(1, N+1):
    if G[i] > 0: continue
    grpid += 1
    grp(R, grpid, i, G, Z)
    
Z.sort(reverse=True)
print(Z[0])
N = int(input())
S = 0

for i in range(N):
   S = S+i+1 if N//(i+1)==N%(i+1) else S

print(S)


### FIXED CODE ###

N,K = map(int, input().split())
print(N-K+1)
= list(map(int,input().split()))
m = []
for i in range(2):
    m.append(n[i])
    n.pop(i)
    n.append(m[i])
  
for i in range(3):
  print(str(n[i]) + ' ',end='')

### FIXED CODE ###

n = list(map(int,input().split()))
m = []
for i in range(2):
    m.append(n[0])
    n.pop(0)
    
n.append(m[0])
n.append(m[1])
  
print(*n)
[N,K] = list(map(int,input().split()))
A = list(map(int,input().split()))

#ループする場合
flag=[0]*N
patt=[]
i=0
while True:
    patt.append(i)
    if flag[i]==1:
        #del patt[-1]
        break
    flag[i]=1
    i=A[i]-1

srt = patt.index(patt[-1])
#print(srt)
end = len(patt)-2
ptrn = patt[srt:end+1]

B = (K-srt) % len(ptrn)
if B==0:
    print(ptrn[0]+1)
else:
    print(ptrn[B+1])
    #print('0000000')

### FIXED CODE ###

[N,K] = list(map(int,input().split()))
A = list(map(int,input().split()))
 
#ループする場合
flag=[0]*N
patt=[]
aaaa=0
i=0
while True:
    patt.append(i)
    if flag[i]==1:
        #del patt[-1]
        break
    flag[i]=1
    i=A[i]-1
 
 
srt = patt.index(patt[-1])
#print('srt',srt)
end = len(patt)-2
ptrn = patt[srt:end+1]
 
if K<srt:
    print(patt[K]+1)
else:
    B = (K-srt) % len(ptrn)
    #print('B',B)
 
    print(ptrn[B]+1)
    #print('0000000')
 
    #print('ptrm',ptrn)
    #print(patt)
test_cases = input()

for test_case in range(test_cases):
	A, B, C, D = map(int, raw_input().split(' '))

	last_take = max(1, (A - C + B - 1) // B)
	A -= last_take * B

	if A < 0 or B > D:
		print "No"
	elif B == D or B <= C: 
		print "Yes"
	else:
		printed = False

		for i in range(10000):
			x = (C - A) // (D - B) + 1
			A += (D - B) * x
			last_take = max(1, (A - C + B - 1) // B)
			A -= last_take * B

			if A < 0:
				print "No"
				printed = True
				break
			
		if printed is False:
			print "Yes"


### FIXED CODE ###

N = input()

v = map(int, raw_input().split(' '))

found = 0

i = 0
while i < N:
	j = i
	while j < N - 1 and v[i] == v[j + 1]:
		j += 1

	found += (j - i + 1) / 2

	i = j + 1

print found
import math

class Point():
    def __init__(self, x=None, y=None):
        self.x = x
        self.y = y

class Vector():
    def __init__(self, x, y):
        self.x = x
        self.y = y
        self.abs = math.sqrt(x*x + y*y)

    def constant_multipled(self, c):
        return Vector(self.x*c, self.y*c)

    def inner_product(self, vec):
        return self.x*vec.x + self.y*vec.y

x1, y1, x2, y2 = list(map(int, input().split(' ')))
start = Point(x1, y1)
base_vec = Vector(x2-x1, y2-y1)
q = int(input())
vectors = []
for i in range(q):
    x, y = list(map(int, input().split(' ')))
    vectors.append(Vector(x-start.x, y-start.y))

for vec in vectors:
    cos = base_vec.inner_product(vec)/(base_vec.abs*vec.abs)
    b_cos = vec.abs*cos
    vec_x = base_vec.constant_multipled(b_cos/base_vec.abs)
    ans_x, ans_y = vec_x.x + start.x, vec_x.y + start.y
    print('%.8f'%ans_x, '%.8f'%ans_y)


### FIXED CODE ###

import math

class Point():
    def __init__(self, x=None, y=None):
        self.x = x
        self.y = y

class Vector():
    def __init__(self, x, y):
        self.x = x
        self.y = y
        self.abs = math.sqrt(x*x + y*y)

    def constant_multipled(self, c):
        return Vector(self.x*c, self.y*c)

    def inner_product(self, vec):
        return self.x*vec.x + self.y*vec.y

x1, y1, x2, y2 = list(map(int, input().split(' ')))
start = Point(x1, y1)
base_vec = Vector(x2-x1, y2-y1)
q = int(input())
vectors = []
for i in range(q):
    x, y = list(map(int, input().split(' ')))
    vectors.append(Vector(x-start.x, y-start.y))

for vec in vectors:
    if vec.abs == 0:
        ans_x, ans_y = 0, 0
        print('%.8f'%ans_x, '%.8f'%ans_y)
        continue
    cos = base_vec.inner_product(vec)/(base_vec.abs*vec.abs)
    b_cos = vec.abs*cos
    vec_x = base_vec.constant_multipled(b_cos/base_vec.abs)
    ans_x, ans_y = vec_x.x + start.x, vec_x.y + start.y
    print('%.8f'%ans_x, '%.8f'%ans_y)
import math
from decimal import Decimal

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

a = Decimal(str(a))
b = Decimal(str(b))
c = Decimal(str(c))
ab = Decimal(str(math.sqrt(a * b)))

if a + b + 2ab < c:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

a, b, c = map(int, input().split())
d = c - a - b
if d < 0:
    print('No')
elif 4*a*b < d**2:
    print('Yes')
else:
    print('No')
a,b=input().split()
l=["1","2","3"]
l.remove(a)
l.remove(b)
print(l[0])


### FIXED CODE ###

a=input()
b=input()
l=["1","2","3"]
l.remove(a)
l.remove(b)
print(l[0])
H,W=map(int,input().split())
S=[[i=="." for i in input()+"#"] for _ in range(H)]+[[False]*(W+1)]

map_=[[0]*W for _ in range(H)]
for i in range(H):
    cnt=0
    q=[]
    for j in range(W+1):
        if S[i][j]==False and cnt!=0:
            for Q in q:
                map_[Q[0]][Q[1]]=cnt
            cnt=0
            q=[]
        elif S[i][j]:
            cnt+=1
            q.append([i,j])
for j in range(W):
    cnt=0
    q=[]
    for i in range(H+1):
        if S[i][j]==False and cnt!=0:
            for Q in q:
                map_[Q[0]][Q[1]]+=cnt
            cnt=0
            q=[]
        elif S[i][j]:
            cnt+=1
            q.append([i,j])
print(max([max(i) for i in map_])-1)

### FIXED CODE ###

P,Q,R=map(int,input().split())
print(min(P+Q,Q+R,R+P))
usrInput = input()
splitedInput = usrInput.split()
clearFlag = True

for i in range(2):
    if splitedInput[i] > 9:
        clearFlag[i] = False

if clearFlag[0] == True & clearFlag[1] == True:
    print(splitedInput[0] + splitedInput[1])
else:
    print(-1)

### FIXED CODE ###

usrInput = input()
splitedInput = usrInput.split()
clearFlag = []

for i in range(2):
    if int(splitedInput[i]) < 10:
        clearFlag.append(True)
    else:
        clearFlag.append(False)

if bool(clearFlag[0]) == True and bool(clearFlag[1]) == True:
    print(int(splitedInput[0]) * int(splitedInput[1]))
else:
    print(-1)
a, b, c, d = map(int,list(input().strip()))

b_case = [b, -b]
c_case = [c, -c]
d_case = [d, -d]

for i in b_case:
    for j in c_case:
        for k in d_case:
            if a + i + j + k == 7:
                print('{}{:+}{:+}{:+}{}'.format(a, i, j, k, '=7'))
                flag = 1
                break
        
        if flag == 1:
            break
    if flag == 1:
        break

### FIXED CODE ###

a, b, c, d = list(map(int, list(input())))
if a + b + c + d == 7:
    print("{0}+{1}+{2}+{3}=7".format(a, b, c, d))
elif a + b + c - d == 7:
    print("{0}+{1}+{2}-{3}=7".format(a, b, c, d))
elif a + b - c + d == 7:
    print("{0}+{1}-{2}+{3}=7".format(a, b, c, d))
elif a - b + c + d == 7:
    print("{0}-{1}+{2}+{3}=7".format(a, b, c, d))
elif a - b - c + d == 7:
    print("{0}-{1}-{2}+{3}=7".format(a, b, c, d))
elif a - b + c - d == 7:
    print("{0}-{1}+{2}-{3}=7".format(a, b, c, d))
elif a + b - c - d == 7:
    print("{0}+{1}-{2}-{3}=7".format(a, b, c, d))
elif a - b - c - d == 7:
    print("{0}-{1}-{2}-{3}=7".format(a, b, c, d))
n,k=map(int,input().split())
s=list(map(int,str(input())))
if s[0]==1:
  one_st=[0]+[i+1 for i in range(n-1) if s[i]==0 and s[i+1]==1]
  zero_st=[i+1 for i in range(n-1) if s[i]==1 and s[i+1]==0]
else:
  one_st=[i+1 for i in range(n-1) if s[i]==0 and s[i+1]==1]
  zero_st=[0]+[i+1 for i in range(n-1) if s[i]==1 and s[i+1]==0]
if s[n-1]==1:
  one_en=[i for i in range(n-1) if s[i]==1 and s[i+1]==0]+[n-1]
  zero_en=[i for i in range(n-1) if s[i]==0 and s[i+1]==1]
else:
  one_en=[i for i in range(n-1) if s[i]==1 and s[i+1]==0]
  zero_en=[i for i in range(n-1) if s[i]==0 and s[i+1]==1]+[n-1]
if len(one_st) <= k:
  x=n
else:
  y=[one_en[i+k]-one_st[i]+1 for i in range(len(zero_st)-k+1)]
  y=y+[one_en[k-1],one_st[len(one_st)-k-1]]
  x=max(y)
print(x)

### FIXED CODE ###

n,k=map(int,input().split())
s=list(map(int,str(input())))
if s[0]==1:
  one_st=[0]+[i+1 for i in range(n-1) if s[i]==0 and s[i+1]==1]
  zero_st=[i+1 for i in range(n-1) if s[i]==1 and s[i+1]==0]
else:
  one_st=[i+1 for i in range(n-1) if s[i]==0 and s[i+1]==1]
  zero_st=[0]+[i+1 for i in range(n-1) if s[i]==1 and s[i+1]==0]
if s[n-1]==1:
  one_en=[i for i in range(n-1) if s[i]==1 and s[i+1]==0]+[n-1]
  zero_en=[i for i in range(n-1) if s[i]==0 and s[i+1]==1]
else:
  one_en=[i for i in range(n-1) if s[i]==1 and s[i+1]==0]
  zero_en=[i for i in range(n-1) if s[i]==0 and s[i+1]==1]+[n-1]
if len(zero_st) <= k:
  x=n
else:
  y=[one_en[i+k]-one_st[i]+1 for i in range(len(zero_st)-k+1) if i+k+1<=len(one_en)]
  y=y+[one_en[k-1]+1,n-one_st[len(one_st)-k]]
  x=max(y)
print(x)
import sys, fractions
sys.setrecursionlimit(5 * 10**5)
input = sys.stdin.readline

N = int(input())

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

gcds = []

for i in range(N - 2):
    for j in range(i + 1, N - 1):
        gcds.append(fractions.gcd(A[i], A[j]))

print(min(gcds))


### FIXED CODE ###

import sys
import fractions

sys.setrecursionlimit(10**9)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def LIST(): return [int(x) for x in input().split()]
MOD = 10**9 + 7

N = INT()

A = LIST()

def gcd_all(n):
    if len(n) == 1:
        return n[0]

    tail = n.pop(-1)
    return fractions.gcd(tail, gcd_all(n))

print(gcd_all(A))
def solve(S,crs=0):
    if crs >= len(S) or crs <0:
        return 0
    while crs + 1 < len(S):
        if S[crs] != S[crs+1]:
            #print(S,crs)
            return max(solve(S,crs+1),solve(S[:crs]+S[crs+2:],crs-1)+2)
        crs += 1
        
    return 0
  
S = input()
print(solve(S,0))

### FIXED CODE ###

def solve(S):
    return min(S.count("0"),S.count("1"))*2
  
S = input()
print(solve(S))
from collections import deque
def f(x,q):
    for i in route[x]:
        if not visit[i]:
            visit[i] = True
            f(i,q+[i])
            visit[i] = False
            if i == n-1:
                p = q + [i-1]
                flag = True
                return p
n = int(input())
route = [[] for i in range(n)]
for i in range(n-1):
    a , b = map(lambda x:int(x)-1,input().split())
    route[a].append(b)
    route[b].append(a)
visit = [False for i in range(n)]
p = f(0,[0])
t = p[-(-len(p)//2)-1]

d = deque()
d.append(n-1)
visit = [False for i in range(n)]
siro = 1
while d:
    now = d.popleft()
    for i in route[now]:
        if not visit[i] and i != t:
            visit[i] = True
            d.append(i)
            siro += 1
kuro = n - siro
if kuro <= siro:
    print("Snuke")
elif kuro > siro:
    print("Fennec")

### FIXED CODE ###

from heapq import heappop, heappush
from collections import deque
n = int(input())
mp2 = []
route = [[] for i in range(n)]
for i in range(n-1):
    a , b = map(lambda x:int(x)-1,input().split())
    mp2.append((a,b,1))
    mp2.append((b,a,1))
    route[a].append(b)
    route[b].append(a)
inf=float('inf')
d=[inf for i in range(n)]
d[0]=0
prev=[None]*n
p=dict()
for i,j,k in mp2: p[i]=p.get(i,[])+[(j,k)]

q=[]
heappush(q,(d[0],0))
while q:
    du, u = heappop(q)
    if d[u]<du: continue
    for v,weight in p.get(u,[]):
        alt=du+weight
        if d[v]>alt:
            d[v]=alt
            prev[v]=u
            heappush(q, (alt,v))

p=[n-1]
while prev[p[-1]]!=None: p.append(prev[p[-1]])

p = p[::-1]
t = p[-(-len(p)//2)-1]

d = deque()
d.append(n-1)
visit = [False for i in range(n)]
siro = 1
visit[n-1] = True
visit[t] = True
while d:
    now = d.popleft()
    for i in route[now]:
        if not visit[i] and i != t:
            visit[i] = True
            d.append(i)
            siro += 1
kuro = n - siro
if kuro <= siro:
    print("Snuke")
elif kuro > siro:
    print("Fennec")
import math
x,y = map(int,input().split())
print(int(math.log2(y/x))+1)

### FIXED CODE ###

import math
x,y = map(int,input().split())
tmp = 1
while x*(2**tmp) <= y:
    tmp += 1
print(tmp)
N,A,B=map(int,input().split())
lst=list(map(int,input().split()))
lst.sort()
a=lst[-A:]
print(sum(a)/A)
b=lst.count(a[0])
c=lst.count(a[0])
print(b!/(c!*(b-c)!))

### FIXED CODE ###

import math
N,A,B=map(int,input().split())
lst=list(map(int,input().split()))
lst.sort()
a=lst[-A:]
print(sum(a)/A)
b=lst.count(a[0])
c=a.count(a[0])
if c!=A:
    print(int(math.factorial(b)/(math.factorial(c)*math.factorial(b-c))))
else:
    l=[]
    i=min([b-c,B-A])
    for k in range(0,i+1):
        l.append(math.factorial(b)/(math.factorial(c+k)*math.factorial(b-c-k)))
    print(int(sum(l)))
a,b=(x for x in input().split()) 
t=len(a)
aa=[]
bb=[]
for i in range(t):
    aa.append(a[i])
    bb.append(b[i])
 
if(aa==bb):
  print("Yes")
else:
	print("No")
    

### FIXED CODE ###


#a,b=(int(x) for x in input().split()) #数値の時




#a,b=(x for x in input().split()) 
a=input()
print("\n")
b=input()
t=len(a)
aa=[]
bb=[]
for i in range(t):
    aa.append(a[i])
    bb.append(b[i])
 
if(aa==bb):
  print("Yes")
else:
	print("No")
N, P = map(int, input().split())
p_dict = {}
for num in range(int(P*0.5)+1):
  while P%num == 0:
    if num in p_dict:
      p_dict[num] += 1
    else:
      p_dict[num] = 1

ans = 1
for k, v in p_dict.items():
  ans *= k**(N//v)
print(ans)

### FIXED CODE ###

N, P = map(int, input().split())
p_dict = {}
if N == 1:
  print(P)
  exit()
for num in range(2, int(P**0.5)+1):
  while P%num == 0:
    if num in p_dict:
      p_dict[num] += 1
    else:
      p_dict[num] = 1
    P //= num
ans = 1
for k, v in p_dict.items():
  ans *= k**(v//N)
print(ans)
N = int(input())

num = [[0] * 10 for _ in range(10)]

for i in range(1, N+1):
    top = int(str(i)[0])
    end = int(str(i)[-1])
    num[top][end] += 1

ans = 0
for i in range(10):
    for j in range(10):
        count += num[i][j] * num[j][i]

print(count)

### FIXED CODE ###

N = int(input())

num = [[0] * 10 for i in range(10)]

for i in range(1, N+1):
    top = int(str(i)[0])
    end = int(str(i)[-1])
    num[top][end] += 1

count = 0
for i in range(10):
    for j in range(10):
        count += num[i][j] * num[j][i]

print(count)
n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7

plus = []
minus = []
for i in a:
    if i > 0: plus.append(i)
    if i < 0: minus.append(-i)
plus.sort(reverse=True)
minus.sort(reverse=True)

ans = 1
if k == n:
    for x in a:
        ans = (ans * x) % mod
elif k > len(plus) + len(minus):
    ans = 0
elif n == len(plus):
    for x in plus[:k]:
        ans = (ans * x) % mod
elif n == len(minus):
    if k % 2 == 1:
        ans = -1
        minus.sort()
    for x in minus[:k]:
        ans = (ans * x) % mod
else:
    i, j = 0, 0
    if k % 2 == 1:
        ans = plus[0]
        i += 1
    while i + j < k:
        x_p = (plus[i] * plus[i + 1]) % mod if i < len(plus) - 1 else 0
        x_m = (minus[j] * minus[j + 1]) % mod if j < len(minus) - 1 else 0
        if x_p > x_m:
            ans = (ans * x_p) % mod
            i += 2
        else:
            ans = (ans * x_m) % mod
            j += 2
print(ans)


### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7

plus = []
minus = []
for i in a:
    if i > 0: plus.append(i)
    if i < 0: minus.append(i)

ans = 1
if k > len(plus) + len(minus):
    ans = 0
elif len(minus) == 0:
    plus.sort(reverse=True)
    for i in range(k):
        ans = (ans * plus[i]) % mod
elif len(plus) == 0:
    if k % 2 == 0:
        minus.sort()
        for i in range(k):
            ans = (ans * minus[i]) % mod
    else:
        if n != len(minus):
            ans = 0
        else:
            minus.sort(reverse=True)
            for i in range(k):
                ans = (ans * minus[i]) % mod
elif k == len(plus) + len(minus) and (len(minus) % 2) == 1:
    if n != k:
        ans = 0
    else:
        for x in plus:
            ans = (ans * x) % mod
        for y in minus:
            ans = (ans * y) % mod
else:
    plus.sort(reverse=True)
    minus.sort()
    i, j = 0, 0
    if k % 2 == 1:
        ans = plus[0]
        i = 1
    while i + j < k:
        tmp_p = plus[i] * plus[i + 1] if i <= len(plus) - 2 else 1
        tmp_m = minus[j] * minus[j + 1] if j <= len(minus) - 2 else 1
        if tmp_p >= tmp_m:
            ans = (ans * (tmp_p % mod)) % mod
            i += 2
        else:
            ans = (ans * (tmp_m % mod)) % mod
            j += 2
print(ans)
n = int(input())
a = map(int,input().split())
s = 0
for i in range(n-2):
  s+=min(a[n-2-i],a[n-i-3])
print(s+a[n-2])


### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
s = 0
for i in range(n-2):
  s+=min(a[n-2-i],a[n-i-3])
print(s+a[n-2]+a[0])
x=input()
a=[1]
for i in range(1,len(x)):
    if x[i]==x[i-1]:
        a[-1]+=1
    else:a+=[1]
ans=0    
if x[0]=="T":
    ans+=a.pop(0)
if x[-1]=="S":
    ans+=a.pop(-1)
    
while len(a)>1:
    a=[a[i]-a[i+1] for i in range(0,len(a),2)]
    if a:
        if a[0]<0:
            ans-=a.pop(0)
    if a:
        if a[-1]>0:
            ans+=a.pop(-1)
    a=[abs(i) for i in a if i!=0]
print(ans+abs(a[0]) if a else ans)

### FIXED CODE ###

a=[]
for i in input():
    if i=="S":
        a+=i
    
    if a:
        if i=="T" and a[-1]=="T":
            a+=i
        if i=="T" and a[-1]=="S":
            a.pop(-1)
    elif i=="T" and len(a)==0:
        a+=i    
print(len(a))
N = int(input())
A = sorted(map(int,input().split()),reverse = True)
answer = 0
i = 1
s = 0
answer = A[0]
while True:
    s = i+i%2
    answer += A[s]
    #print(i,s)
    i += 1
    if i == N-1:
        break
    
print(answer)

### FIXED CODE ###

N = int(input())
A = sorted(map(int,input().split()),reverse = True)
answer = 0
i = 1
s = 0
answer = A[0]
if N == 2:
    anwer=A[0]
else:
    while True:
        s = (i+1)//2
        answer += A[s]
        i += 1
        if i == N-1:
            break
    
print(answer)
from collections import defaultdict, deque
import sys
#input = sys.stdin.readline
def inpl(): return list(map(int, input().split()))
N = int(input())
A = sorted(inpl())

print(a[-1] - sum(map(abs, A[1:-1])) - A[0])
for i in range(N-2, 0, -1):
	a = A[i]
	if a > 0:
    	print(A[0], a)
    	A[0] -= a
    else:
    	print(A[-1], a)
    	A[-1] -= a
    	print(A[-1], A[0])

### FIXED CODE ###

#!/usr/bin/env python3
import bisect
n = int(input())
a = sorted(map(int, input().split()))
if n == 2:
    print(a[1] - a[0])
    print(a[1], a[0])
    exit()

p = bisect.bisect_left(a, 0)
p = min(max(1, p), n - 1)
print(sum(a[p:]) - sum(a[:p]))
b = a[p - 1]
for i in range(p, n - 1):
    print(b, a[i])
    b -= a[i]
c = a[n - 1]
for i in range(p - 1):
    print(c, a[i])
    c -= a[i]
print(c, b)