Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

S = input()

T = [s if s != "?" else "0" for s in S]
T = int(''.join(T))
SS = T % 13

c = {}
iii = 1
for i in range(len(S)):
    if S[len(S) - i - 1] != "?":
        iii *= 10
        iii %= 13
        continue
    tc = {}
    for j in range(0, 10):
        t = (j * iii) % 13
        tc[t] = 1
    c[i] = tc
    iii *= 10
    iii %= 13

dp = []
tdp = {i: 0 for i in range(13)}
tdp[SS] += 1
dp.append(tdp)
for k, v in c.items():
    tdp = {i: 0 for i in range(13)}
    for r, _ in v.items():
        for _r, _v in dp[-1].items():
            tdp[(_r + r) % 13] += _v
    dp.append(tdp)

ans = dp[-1][5]
print(ans % (10**9 + 7))

### FIXED CODE ###

S = input()
con = 10**9 + 7

T = [s if s != "?" else "0" for s in S]
T = int(''.join(T))
SS = T % 13

def get_mod(S):
    c = {}
    iii = 1
    for i in range(len(S)):
        if S[len(S) - i - 1] != "?":
            iii *= 10
            iii %= 13
            continue
        c[i] = {(j * iii) % 13: 1 for j in range(0, 10)}
        iii *= 10
        iii %= 13
    return c
c = get_mod(S)

def get_tdp(pdp):
    tdp = {i: 0 for i in range(13)}
    for r in v.keys():
        for _r, _v in pdp.items():
            tdp[(_r + r) % 13] += _v
    for i in range(13):
        tdp[i] %= con
    return tdp

pdp = {i: 0 for i in range(13)}
pdp[SS] += 1
for k, v in c.items():
    pdp = get_tdp(pdp)

ans = pdp[5]
print(ans)
### BUGGY CODE ###

import itertools
K, S = map(int, input().split())
list_ans = [(x,y,z) for x, y, z in itertools.product([w for w in range(K + 1)], repeat = 3) if ((x + y + z) == S)]
print(len(list_ans))



### FIXED CODE ###

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

c = 0
for x in range(S//3 + 1):
    for y in range(x, (S-x)//2 + 1):
        z = S - (x + y)
        if z <= K:
            l = len(set((x,y,z)))
            if l == 1: c += 1
            elif l == 2: c += 3
            else: c += 6
print(c)
### BUGGY CODE ###

n, k = map(int, input().split())
import numpy as np
import copy
A = np.array(list(map(int, input().split())))
for _ in range(k):
    C = np.zeros([n,], dtype=np.int32)
    for i in range(n):
        a = A[i]
        l = max(0, i - a)
        r = min(n, i + a + 1)
        C[l:r] += 1
    A = C + 0
print(" ".join(map(str, list(A))))

### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))
    _max = max
    _min = min
    for _ in range(k):
        C = [0] * n
        i = 0
        for a in A:
            l = _max(0, i - a)
            r = _min(n, i + a + 1)
            C[l] += 1
            if r < n:
                C[r] -= 1
            i += 1
        r = 0
        for i in range(n):
            r += C[i]
            A[i] = r
        if A == [n] * n:
            break
    print(" ".join(map(str, A)))
main()
### BUGGY CODE ###

while 1:
	n = input()
	if n == 0: break
	s = map(int,raw_input().split())
	sm = sum(s)
	dp = [0] * (sm+1)
	ref = {i:[i] for i in s}
	for i in s:
		dp[i] = i
	for i in s:
		for j in range(sm+1):
			if dp[j] > 0 and j not in ref[i]:
				try:
					dp[j+i] = dp[j] + i
					ref[i].append(j + i)
				except: break
	print min([abs(sm-2*dp[i]) for i in range(sm)])

### FIXED CODE ###

def S(i,x,y):
	if 2*x >= A: return 2*x-A
	if 2*y >= A: return 2*y-A
	return min(S(i+1,x+a[i],y),S(i+1,x,y+a[i]))
while 1:
	n = input()
	if n == 0: break
	a = sorted(map(int,raw_input().split()))[::-1]
	A = sum(a)
	print S(1,a[0],0)
### BUGGY CODE ###

n=int(input())
a=[int(input()) for _ in range(n)]
b=max(a)
for i in range(n):
    if a[i]!=b:
        print(b)
    else:
        
        print(sorted(a)[-2])

### FIXED CODE ###

n=int(input())
a=[int(input()) for _ in range(n)]
b=sorted(a)
ans=[b[-1]]*n
ans[a.index(b[-1])]=b[-2]
print(*ans,sep="\n")
### BUGGY CODE ###

n = int(input())
mx = int(10e6+1)
y=0
mn = int(10e13)
for v in range(1,mx):
    if v<=n and n%v==0:
        y=1
        left = n//v
        mn=min(v-1+left-1,mn)
    if v>n:
        break
if y:
    print(mn)
else:
    print(n-1)


### FIXED CODE ###

n = int(input())
mx = int(10e6+1)
y=0
mn = int(10e13)
for v in range(1,mx):
    if v<=n and n%v==0:
        y=1
        left = n//v
        mn=min(v-1+left-1,mn)
    if v>n:
        break
if y:
    print(mn)
else:
    print(n-1)
### BUGGY CODE ###

N, W = map(int, input().split())
w, v = [0] * N, [0] * N
for i in range(N):
	w[i], v[i] = map(int, input().split())

V = sum(v)
dp = [[float("inf")] * (V + 1) for _ in range(N + 1)]
dp[0][0] = 0
for i in range(N):
	for j in range(V + 1):
		if j - v[i] >= 0:
			dp[i + 1][j] = min(dp[i + 1][j], dp[i][j - v[i]] + w[i])
		dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])

ans = 0
for j in range(V + 1):
	if dp[N][j] <= W:
		ans = j

print(ans)


### FIXED CODE ###

N, W = map(int, input().split())
w, v = [0] * N, [0] * N
for i in range(N):
	w[i], v[i] = map(int, input().split())

V = sum(v)
dp = [[float("inf")] * (V + 1) for _ in range(N + 1)]
"""
for j in range(V + 1):
	dp[0][j] = 0
"""
dp[0][0] = 0
# dp[i][j]:i番目までの品物から価値がj以上になるよう選んだときの重さの総和の最小値
for i in range(N):
	for j in range(V + 1):
		# i+1番目を選ぶ場合
		if j - v[i] >= 0:
			dp[i + 1][j] = min(dp[i + 1][j], dp[i][j - v[i]] + w[i])
		# i+1番目を選ばない場合
		dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])

# print(dp)

# dp[N][j]がW以下であるようなjの最大値が答えになる
ans = 0
for j in range(V + 1):
	if dp[N][j] <= W:
		ans = j

print(ans)
### BUGGY CODE ###

n=int(input())
a=[]
ans=0
for i in range(n):
    x=int(input())
    if a.count(x)%2==0:
        ans+=1
        a.append(x)
    else:
        ans-=1
        a.append(x)
print(ans)


### FIXED CODE ###

n=int(input())
d={}
ans=0
for i in range(n):
    a=int(input())
    try:
        if d[a]%2==0:
            ans+=1
            d[a]+=1
        else:
            ans-=1
            d[a]+=1
    except:
        d[a]=1
        ans+=1
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

H, W = map(int, input().split())
maze = [input() for i in range(H)]
ans = 0

def search1(x, y, cnt):
    global ans
    if x < 0 or W <= x or y < 0 or H <= y or maze[y][x] == '#':
        ans += cnt - 1
        return

    search1(x + 1, y, cnt + 1)
    return
def search2(x, y, cnt):
    global ans
    if x < 0 or W <= x or y < 0 or H <= y or maze[y][x] == '#':
        ans += cnt - 1
        return

    search2(x - 1, y, cnt + 1)
    return
def search3(x, y, cnt):
    global ans
    if x < 0 or W <= x or y < 0 or H <= y or maze[y][x] == '#':
        ans += cnt - 1
        return

    search3(x, y + 1, cnt + 1)
    return
def search4(x, y, cnt):
    global ans
    if x < 0 or W <= x or y < 0 or H <= y or maze[y][x] == '#':
        ans += cnt - 1
        return

    search4(x, y - 1, cnt + 1)
    return

MAX = 0
for i in range(H):
    for j in range(W):
        if maze[i][j] == '#':
            continue
        search1(j, i, 0)
        search2(j, i, 0)
        search3(j, i, 0)
        search4(j, i, 0)
        MAX = max(ans + 1, MAX)
        ans = 0

print(MAX)


### FIXED CODE ###

H, W = map(int, input().split())
maze = [input() for _ in range(H)]
cnt = [[0] * W for _ in range(H)]

for i in range(H):
    done = [0] * W
    for j in range(W):
        if maze[i][j] == '#':
            continue
        if done[j]:
            continue
        l = 0
        while j + l < W:
            if maze[i][j+l] == '#':
                break
            l += 1
        for k in range(l):
            cnt[i][j+k] += l
            done[j+k] = 1

for j in range(W):
    done = [0] * H
    for i in range(H):
        if maze[i][j] == '#':
            continue
        if done[i]:
            continue
        l = 0
        while i + l < H:
            if maze[i+l][j] == '#':
                break
            l += 1
        for k in range(l):
            cnt[i+k][j] += l
            done[i+k] = 1
ans = 0
for i in range(H):
    ans = max(ans, max(cnt[i]) - 1)

print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
from bisect import bisect_right

def main():
	N, K = map(int, input().split(" "))
	osushi = []
	for _ in  range(N):
		t, d = map(int, input().split(" "))
		osushi.append((d, t))
		
	osushi.sort()
	osushi.reverse()
	
	osushi_list = []
	syu_total = 0
	syu_list = []
	for i, val in enumerate(osushi):
		d, t = val;
		if not t in syu_list:
			syu_total += 1
			syu_list.append(t)
			t = 1
		else:
			t = 0
		osushi_list.append((d, t))
	
	man = 0
	syu = 0
	for i, val in enumerate(osushi_list):
		if i >= K:
			break
		d, t = val
		if t == 1:
			syu += 1
		man += d
	
	ans = man + (syu ** 2)
	for syu_mokuhyou in range(syu+1, syu_total+1):
		man = 0
		syu_local = 0
		count = 0
		for i, val in enumerate(osushi_list):
			d, t = val
			if t == 1:
				syu_local += 1
				man += d
				count += 1
				if syu_local == syu_mokuhyou or count >= K:
					break
					
		for i, val in enumerate(osushi_list):
			if count >= K:
				break
			d, t = val
			if t == 0:
				man += d
				count += 1
		tmp = man + (syu_local ** 2)
		if tmp > ans:
			ans = tmp
		
	print(ans)
	
	
if __name__ == "__main__":
	main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import itertools
from decimal import *

input = sys.stdin.readline

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N,K = inputMap()
	sushi_mii = []
	sushi_kii = []
	syu = [[] for i in range(N)]
	for i in range(N):
		t,d = inputMap()
		t -= 1
		syu[t].append(d)

	for i in syu:
		if len(i) > 0:
			i.sort()
			i = i[::-1]
			for j,val in enumerate(i):
				if j == 0:
					sushi_mii.append(val)
				else:
					sushi_kii.append(val)

	sushi_mii.sort()
	sushi_mii = sushi_mii[::-1]
	sushi_kii.sort()
	sushi_kii = sushi_kii[::-1]

	sushi_mi = []
	sushi_ki = []
	for i,val in enumerate(sushi_mii):
		if i == 0:
			sushi_mi.append(val)
		else:
			tmp = sushi_mi[i-1]
			sushi_mi.append(tmp + val)

	for i,val in enumerate(sushi_kii):
		if i == 0:
			sushi_ki.append(val)
		else:
			tmp = sushi_ki[i-1]
			sushi_ki.append(tmp + val)

	ans = 0
	for i in range(1, min(len(sushi_mi), K)+1):
		x = 0
		tmp = 0
		if K - i > len(sushi_ki):
			continue

		tmp += sushi_mi[i-1]
		x = i

		if K - i > 0:
			tmp += sushi_ki[K - i-1]

		oishi = tmp + x * x
		if ans < oishi:
			ans = oishi
	print(ans)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()
### BUGGY CODE ###

import sys
e=sys.stdin.readlines()
N,M,Q=map(int,e[0].split())
dp=[[0]*-~N for _ in[0]*-~N]
for x in e[1:M+1]:
    L,R=map(int,x.split())
    for i in range(1,L+1):
        for j in range(R,N+1):
            dp[i][j] += 1
for x in e[M+1:]:
    p,q=map(int,x.split())
    print(dp[p][q])

### FIXED CODE ###

import sys
def main():
    s = sys.stdin.readlines()
    N, M, Q = map(int, s[0].split())
    x = [[0] * N for _ in [0] * N]
    for e in s[1:M + 1]:
        L, R = map(int, e.split())
        x[L - 1][R - 1] += 1
    for k in range(1, N):
        for i in range(N - k):
            j = i + k
            x[i][j] += x[i][j - 1] + x[i + 1][j] - x[i + 1][j - 1]
    res = []
    for e in s[M + 1:]:
        p, q = map(int, e.split())
        res.append(x[p - 1][q - 1])
    print('\n'.join(map(str, res)))
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n, m = map(int,input().split())
nei =[[i] for i in range(n)]

for i in range(m):
    a, b = map(int,input().split())
    a -= 1
    b -= 1
    nei[a].append(b)
    nei[b].append(a)

color = [0 for i in range(n)]
#print(nei)
def paint(v,d,c):
    if color[v] == 0:
        color[v] = c
    if d == 0:
        return
    for i in nei[v]:
        paint(i,d-1,c)

q = int(input())
vbc = [list(map(int,input().split())) for i in range(q)][::-1]

for i in range(q):
    paint(vbc[i][0]-1,vbc[i][1],vbc[i][2])
    #print(color)

for i in range(n):
    print(color[i])

### FIXED CODE ###

import sys
input = sys.stdin.readline

n, m = map(int,input().split())
nei =[[i] for i in range(n)]

for i in range(m):
    a, b = map(int,input().split())
    a -= 1
    b -= 1
    nei[a].append(b)
    nei[b].append(a)

color = [0 for i in range(n)]
depth = [-1 for i in range(n)]

def paint(v,d,c,pre):
    if d <= depth[v]:
        return
    depth[v] = d
    if color[v] == 0:
        color[v] = c
    if d == 0:
        return
    for next in nei[v]:
        if next == pre:
            continue
        paint(next,d-1,c,v)

q = int(input())
vbc = [list(map(int,input().split())) for i in range(q)][::-1]

for i in range(q):
    paint(vbc[i][0]-1,vbc[i][1],vbc[i][2],-1)
    #print(color)


for co in color:
    print(co)
### BUGGY CODE ###

R, G, B, N = map(int, input().split())

n = 1000
count = 0
for i in range(N // R + 1):
  if i*R > N:
    break
  for j in range(N // G + 1):
    if i*R + j*G > N:
      break
    if (N - i*R - j*G) % B == 0:
      count += 1
 
print(count)

### FIXED CODE ###

R, G, B, N = map(int, input().split())

org_list = [R, G, B]
org_list.sort()
first_num = org_list[2]
second_num = org_list[1]
third_num = org_list[0]

count = 0

for i in range(N // first_num + 1):
  for j in range((N-i*first_num) // second_num + 1):
    if (N - i*first_num - j*second_num) % third_num == 0:
      count += 1
 
print(count)
### BUGGY CODE ###

N = int(input())
V = list(map(int, input().split()))
C = list(map(int, input().split()))

# ビットで使う使わないパターン表を作る
# Nが桁数、2のN乗がパターン数
max = 0
for i in range(0, 2 ** N):
    ptn = '0' + str(N) + 'b'
    bin_i = list(format(i, ptn))
    work = 0
    for j in range(0, N):
        if bin_i[j] == '1':
            work += V[j] - C[j]
    if max < work:
        max = work

print(max)

### FIXED CODE ###

N = int(input())
V = list(map(int, input().split()))
C = list(map(int, input().split()))

Rec = []
Chk = []

# (V-C)＋(V-C)..の結果を１つずつ見て一番高いものを記録
# 宝石ループ
work = None
for i in range(0, N):
    for j in range(0, N):
        if not(j in Chk) and (work == None or work < V[j] - C[j]):
            work = V[j] - C[j]
            work2 = j
    Chk.append(work2)
    if len(Rec) > 0:
        Rec.append(Rec[i - 1] + work)
    else:
        Rec.append(work)
    work = None

if max(Rec) > 0:
    print(max(Rec))
else:
    print('0')
### BUGGY CODE ###

N = int(input())
ax = list(map(int,input().split()))

memo = {}
memo_size = min(100,N)
for i in range(1, memo_size+1):
    memo[i] = 0

boxin = []
for cnt in range(N, 0, -1):
    a = ax[cnt-1]
    if cnt < memo_size:
        memo_cnt = memo[cnt]
    else:
        i = 2
        memo_cnt = 0
        while 1:
            test_val = i * cnt
            if test_val > N:
                break
            if test_val in boxin:
                memo_cnt += 1
            i += 1
    if a != memo_cnt % 2:
        boxin.append(cnt)
        for i in range(1,memo_size+1):
            if cnt % i == 0:
                memo[i] += 1

box = len(boxin)
print(box)
if box != 0:
    boxin.reverse()
    print(' '.join(map(str, boxin)))

### FIXED CODE ###

import math
N = int(input())
ax = list(map(int,input().split()))

M = 0
boxin = []
bx = [0 for _ in range(N+1)]
for cnt in range(N, 0, -1):
    a = ax[cnt-1]
    tmp = 0
    for tmp_cnt in range(cnt*2, N+1, cnt):
        if bx[tmp_cnt] != 0:
            tmp += 1
    
    if tmp % 2 != a:
        bx[cnt] = 1
        boxin.append(cnt)

box = len(boxin)
print(box)
if box != 0:
    boxin.reverse()
    print(' '.join(map(str, boxin)))
### BUGGY CODE ###

a = int(input())
b = list(map(int,input().split()))
ans = 0
c = 0
list.sort(b, reverse=True)
ans += b.pop(0)
b.extend(b)
list.sort(b, reverse=True)

for i in range(2,a):
    ans += b.pop(0)
print(str(ans))

### FIXED CODE ###

a = int(input())
b = list(map(int,input().split()))
ans = 0
c = 0
list.sort(b, reverse=True)
ans += b.pop(0)
b.extend(b)
list.sort(b, reverse=True)

ans += sum(b[0:a-2])
print(str(ans))
### BUGGY CODE ###

S = input()
ans = 0
for i in range(len(S) - 4):
    for j in range(4, len(S) - i + 1):
        x = int(S[i:i + j])
        if x < 2019:
            continue

        if x % 2019 == 0:
            ans += 1
print(ans)


### FIXED CODE ###

from collections import Counter

S = input()
mods = [0]
num, ten = 0, 1
for n in S[::-1]:
    num += int(n) * ten
    num %= 2019
    mods.append(num)
    ten *= 10
    ten %= 2019

c = Counter(mods)
ans = 0
for v in c.values():
    ans += v * (v - 1) // 2
print(ans)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
a=sorted(a)
b=list(set(a))
ans=0
for i in range(len(b)):
  if a.count(b[i])>=b[i]:
    ans+=a.count(b[i])-b[i]
  else:
    ans+=a.count(b[i])
print(ans)

### FIXED CODE ###

N=int(input())
a=list(map(int,input().split()))

a=sorted(a)
l=a[0]
cnt=0

b=[]
for i in range(N):
    if a[i]==l:
        cnt+=1
    else:
        b.append([l,cnt])
        l=a[i]
        cnt=1
if cnt>0:
    b.append([l,cnt])

ans=0
for i in range(len(b)):
    if b[i][0]>b[i][1]:
        ans+=b[i][1]
    else:
        ans+=b[i][1]-b[i][0]

print(ans)
### BUGGY CODE ###

import copy

N,Q = map(int,input().split())
ki = [list(map(int,input().split())) for i in range(N-1)]
co = [list(map(int,input().split())) for i in range(Q)]
 
ki.sort()
#print(ki)
 
ver = [0 for i in range(N)]
 
for i in range(Q):
    ver[co[i][0]-1] += co[i][1]
 
ver2 = copy.deepcopy(ver)

#print(ver)
#print(ver2)
 
for i in range(N-1):
    if ver[ki[i][0]-1] == ver2[ki[i][0]-1] and ver[ki[i][1]-1] != ver2[ki[i][1]-1]:
        ver[ki[i][0]-1] += ver[ki[i][1]-1]
    else:
        ver[ki[i][1]-1] += ver[ki[i][0]-1]

 
print(' '.join(map(str,ver)))


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque

N,Q = map(int,readline().split())
ki = []
for i in range(N-1):
    ki.append(list(map(int,readline().split())))
co = []
for i in range(Q):
    co.append(list(map(int,readline().split())))
 
ki.sort(key=lambda x: x[1])

kid = deque(ki)
ver = []
check = []
for i in range(N):
    ver.append(0)
    check.append(False)
 
for c in co:
    ver[c[0]-1] += c[1]

check[0] = True

kid2 = deque()

while len(kid) != 0:
    k = kid.popleft()
    if check[k[0]-1] == True:
        ver[k[1]-1] += ver[k[0]-1]
        check[k[1]-1] = True
    elif check[k[1]-1] == True:
        ver[k[0]-1] += ver[k[1]-1]
        check[k[0]-1] = True
    else:
        kid2.append(k)

while len(kid2) != 0:
    k = kid2.pop()
    if check[k[0]-1] == True:
        ver[k[1]-1] += ver[k[0]-1]
        check[k[1]-1] = True
    elif check[k[1]-1] == True:
        ver[k[0]-1] += ver[k[1]-1]
        check[k[0]-1] = True
    else:
        kid2.appendleft(k)


print(' '.join(map(str,ver)))
### BUGGY CODE ###

N = int(input())
L = [int(i) for i in input().split()]


from itertools import combinations

ans = 0
for a, b, c in combinations(L,3):
    # print(a, b, c)
    if a<b+c and b<a+c and c<a+b:
        ans += 1
        # print(a, b, c)

print(ans)

### FIXED CODE ###

N = int(input())
L = [int(i) for i in input().split()]

import bisect
L.sort()
ans = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        idx = bisect.bisect_left(L, L[i]+L[j])
        ans += (idx-(j+1))

print(ans)
### BUGGY CODE ###

from collections import defaultdict
from itertools import combinations
import sys
input = sys.stdin.readline

n = int(input())
s = [input().split()[0] for _ in range(n)]
cnt = defaultdict(int)
for i in range(n):
    cnt["".join(sorted(s[i]))] += 1
result = 0
for c in cnt:
    result += len(list(combinations([""] * cnt[c], 2)))
print(result)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
s = ["".join(sorted(input().split()[0])) for _ in range(n)]
cnt = {}
result = 0
for si in s:
    if si in cnt:
        result += cnt[si]
        cnt[si] += 1
    else:
        cnt[si] = 1
print(result)
### BUGGY CODE ###

n = int(input())
s = input()

seen = [False] * 10

ans = 0
for i in range(n - 2):
    if seen[int(s[i])]:
        continue

    tmp = set()
    for j in range(i + 1, n - 1):
        for k in range(j + 1, n):
            tmp.add(s[j] + s[k])
    ans += len(tmp)
    seen[int(s[i])] = True

print(ans)


### FIXED CODE ###

from collections import defaultdict
n = int(input())
S = input()

d = defaultdict(list)
for i, s in enumerate(S):
    d[s].append(i)

ans = 0
for p in range(1000):
    p1, p2, p3 = str(p).zfill(3)

    i0 = -1
    for i in d[p1]:
        if i > i0:
            i1 = i
            break
    else:
        continue

    for i in d[p2]:
        if i > i1:
            i2 = i
            break
    else:
        continue

    for i in d[p3]:
        if i > i2:
            ans += 1
            break


print(ans)
### BUGGY CODE ###

import copy

mod = 1000000007

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

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

plus_1 = []

minus_1 = []

for i in a:
    if i > 0:
        plus_1.append(i)
    else:
        minus_1.append(i)

plus_2 = plus_1.copy()
minus_2 = minus_1.copy()

plus_1.sort(reverse=True)
minus_1.sort()
maxa = 1

plus_2.sort()
minus_2.sort(reverse=True)
mini = 1

i = 0

while i < k:
    if len(plus_1) > 1 and len(minus_1) > 1:
        if plus_1[0]*plus_1[1] < minus_1[0]*minus_1[1] and i+2<=k:
            maxa *= minus_1[0]*minus_1[1]
            minus_1.pop(0)
            minus_1.pop(0)
            i += 2
        else:
            maxa *= plus_1[0]
            plus_1.pop(0)
            i += 1
    elif len(plus_1):
        maxa *= plus_1[0]
        plus_1.pop(0)
        i += 1
    else:
        maxa *= minus_1[0]
        minus_1.pop(0)
        i += 1

i = 0

while i < k:
    if len(plus_2) and len(minus_2):
        if plus_2[0] < abs(minus_2[0]):
            mini *= plus_2[0]
            plus_2.pop(0)
        else:
            mini *= minus_2[0]
            minus_2.pop(0)
    elif len(plus_2):
        mini *= plus_2[0]
        plus_2.pop(0)
    else:
        mini *= minus_2[0]
        minus_2.pop(0)
    i += 1

if maxa > 0:
    print(maxa%mod)
else:
    print(mini%mod)

### FIXED CODE ###

MOD = 10 ** 9 + 7
 
N, K = map(int, input().split())
l = list(map(int, input().split()))
pos = []
neg = []
z = 0
 
for v in l:
    if v > 0:
        pos.append(v)
    elif v < 0:
        neg.append(v)
    else:
        z += 1
pos.sort()
neg.sort()
 
if N - z < K:
    print(0)
elif N - z == K:
    if len(neg) % 2 and z:
        print(0)
    else:
        out = 1
        for v in neg + pos:
            out *= v
            out %= 10 ** 9 + 7
        print(out)
elif len(pos) == 0:
    if K % 2:
        if z:
            print(0)
        else:
            neg.reverse()
            out = 1
            for i in range(K):
                out *= neg[i]
                out %= 10 ** 9 + 7
            print(out)
    else:
        out = 1
        for i in range(K):
            out *= neg[i]
            out %= 10 ** 9 + 7
        print(out)
else:
    out = 1
    neg.reverse()
    if K % 2:
        out = pos.pop()
        K -= 1
    while K:
        if len(pos) >= 2:
            nP = pos[-1] * pos[-2]
        else:
            nP = 0
 
        if len(neg) >= 2:
            nN = neg[-1] * neg[-2]
        else:
            nN = 0
 
        if nP > nN:
            pos.pop()
            pos.pop()
            out *= nP
        else:
            neg.pop()
            neg.pop()
            out *= nN
        out %= MOD
        K -= 2
    print(out)