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

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

s = 1
if n == k:
	for i in l:
		s *= i
	print(s % 1000000007)
else:
	pos = []
	neg = []

	for i in l:
		if i >= 0:
			pos.append(i)
		else:
			neg.append(i)

	pos.sort()
	neg.sort(reverse=True)
	answer = []

	if k % 2 == 1 and not pos:
		for i in range(k):
			s *= neg[i]
		print(s % 1000000007)

	else:
		if k % 2 == 1:
			s = pos.pop()
		for i in range(k//2):
			if len(pos) >= 2:
				answer.append(pos.pop()*pos.pop())
			else:
				break
		for i in range(k//2):
			if len(neg) >= 2:
				answer.append(neg.pop()*neg.pop())
			else:
				break
		answer.sort(reverse=True)
		for i in range(k//2):
			s *= answer[i]
		print(s % 1000000007)

### FIXED CODE ###

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

s = 1
if n == k:
	for i in l:
		s *= i
		s %= 1000000007
	print(s)
else:
	pos = []
	neg = []

	for i in l:
		if i >= 0:
			pos.append(i)
		else:
			neg.append(i)

	pos.sort()
	neg.sort(reverse=True)
	answer = []

	if k % 2 == 1 and not pos:
		for i in range(k):
			s *= neg[i]
			s %= 1000000007
		print(s)

	else:
		if k % 2 == 1:
			s = pos.pop()
		for i in range(k//2):
			if len(pos) >= 2:
				answer.append(pos.pop()*pos.pop())
			else:
				break
		for i in range(k//2):
			if len(neg) >= 2:
				answer.append(neg.pop()*neg.pop())
			else:
				break
		answer.sort(reverse=True)
		for i in range(k//2):
			s *= answer[i]
			s %= 1000000007
		print(s)
### BUGGY CODE ###

#
# agc012 a
#

import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """2
5 2 8 5 1 5"""
        output = """10"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """10
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000"""
        output = """10000000000"""
        self.assertIO(input, output)


def resolve():
    N = int(input())
    a = list(map(int, input().split()))
    a.sort()
    ans = 0
    for i in range(N):
        a.pop()
        a.pop(0)
        ans += a.pop()
    print(ans)


if __name__ == "__main__":
    # unittest.main()
    resolve()


### FIXED CODE ###

#
# agc012 a
#

import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """2
5 2 8 5 1 5"""
        output = """10"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """10
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000"""
        output = """10000000000"""
        self.assertIO(input, output)


def resolve():
    N = int(input())
    a = list(map(int, input().split()))
    a.sort()
    ans = 0
    for i in range(N):
        a.pop()
        ans += a.pop()
    print(ans)


if __name__ == "__main__":
    # unittest.main()
    resolve()
### BUGGY CODE ###

if __name__ == '__main__':
    N = int(input())
    P = list(map(int,input().split()))
    P.insert(0, 0)
    Dis = [[abs(P[i]-P[(i+j)%(N+1)]) for i in range(N+1)] for j in range(1,N+1)]
    
    for i in range(N): print(sum(Dis[0])-sum(Dis[0][i:i+2])+Dis[1][i])

### FIXED CODE ###

if __name__ == '__main__':
    N = int(input())
    P = list(map(int,input().split()))
    P.insert(0, 0)
    Dis = [[abs(P[i]-P[(i+j+1)%(N+1)]) for i in range(N+1)] for j in range(2)]
    temp = sum(Dis[0])
    temp2 = [sum(Dis[0][i:i+2]) for i in range(N)]
    for i in range(N): print(temp-temp2[i]+Dis[1][i])
### BUGGY CODE ###

n = int(input())
t = list(map(int, input().split()))
to = t[0]
if 0 in t:
  print(0)
  exit()
for a in t[1:]:
	to *= a
if to > 10**18:
	print("-1")
else:
  print(to)

### FIXED CODE ###

n = int(input())
t = list(map(int, input().split()))
to = t[0]
if 0 in t:
  print(0)
  exit()
for a in t[1:]:
    to *= a
    if to > (10**18):
        print("-1")
        exit()
print(to)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n, q = map(int,input().split())
A = [list(map(int,input().split())) for i in range(n)]
D = [int(input()) for i in range(q)]

E = []
F = {}
for i in range(n):
    s = A[i][0]
    t = A[i][1]
    x = A[i][2]
    F[x] = 0
    E.append([s-x, x, 1])
    E.append([t-x, x, -1])
E.append([10**10, 10**10, 1])

E.sort()

# print(E)

from heapq import heappush, heappop
Q = []

for i in range(q):
    j = 0
    while E[j][0] <= D[i]:
        if E[j][2] == 1:
            F[E[j][1]] = 1
            heappush(Q, E[j][1])
        else:
            F[E[j][1]] = 0
        j += 1
    
    while len(Q) > 0:
        ans = heappop(Q)
        if F[ans] == 1:
            heappush(Q, ans)
            break
    if len(Q) == 0:
        print(-1)
    else:
        print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline
n,q = map(int,input().split())
A = [list(map(int,input().split())) for i in range(n)]
D = [int(input()) for i in range(q)]

E = []
F = {}
for i in range(n):
    s = A[i][0]
    t = A[i][1]
    x = A[i][2]
    F[x] = 0
    E.append((s-x, x, 1))
    E.append((t-x, x, -1))
E.append((10**10, 10**10, 1))

E.sort()

# print(E)

from heapq import heappush, heappop
Q = []

j = 0
for i in range(q):
    # print(F,j)
    while E[j][0] <= D[i]:
        if E[j][2] == 1:
            F[E[j][1]] += 1
            heappush(Q, E[j][1])
        else:
            F[E[j][1]] -= 1
        j += 1
    
    while len(Q) > 0 and F[Q[0]] == 0:
        _ = heappop(Q)
    if len(Q) == 0:
        print(-1)
    else:
        print(Q[0])
### BUGGY CODE ###

from itertools import combinations

N, P = map(int, input().split())
lst_A = list(map(int, input().split()))

ans = 0
for i in range(N+1):
    combi = list(combinations(lst_A, i))
    # print(combi)
    for tpl in combi:
        mod = sum(tpl)%2
        if mod == P:
            ans += 1

print(ans)


### FIXED CODE ###

N, P = map(int, input().split())
lst_A = list(map(int, input().split()))
lst_odd_even = [x%2 for x in lst_A]

if 1 in lst_odd_even:
    ans = 2 ** (N-1)
else:
    if P == 0:
        ans = 2 ** N
    else:
        ans = 0

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

#13:19
n = int(input())
s = input()
t = []
for i in range(n):
  t.append(ord(s[i])-97)
q = int(input())
scale = 19
seg = [[0 for _ in range(2**(scale+1))] for _ in range(26)]
for i in range(n):
  tmp = int(i) + 2 ** scale
  x = t[i]
  while tmp != 0:
    seg[x][tmp] += 1
    tmp //= 2
#print(seg)
raw = []
for _ in range(q):
  d,a,b = input().split()
  d = int(d)
  if d == 1:
    a = int(a) - 1
    b = ord(b) - 97
  else:
    a = int(a) - 2
    b = int(b) - 1
  raw.append([d,a,b])
for p in range(q):
  d,a,b = raw[p]
  if d == 1:
    tmp = int(a)
    c = t[tmp]
    tmp += 2**scale
    while tmp != 0:
      seg[c][tmp] -= 1
      tmp //= 2
    tmp = int(a)
    t[tmp] = b
    tmp += 2**scale
    while tmp != 0:
      seg[b][tmp] += 1
      tmp //= 2
  else:
    ans = 0
    for d in range(26):
      l = 0
      r = 0
      if a == -1:
        l = 0
      else:
        tmp = a + 2**scale
        l += seg[d][tmp]
        while tmp != 1:
          if tmp & 1:
            l += seg[d][tmp-1]
          tmp //= 2
      tmp = b + 2**scale
      r += seg[d][tmp]
      while tmp != 1:
        if tmp & 1:
          r += seg[d][tmp-1]
        tmp //= 2
      if r > l:
        ans += 1
      #print(d,r,l)
    print(ans)
#print(t)

### FIXED CODE ###

#13:19
n = int(input())
s = input()
t = []
for i in range(n):
  t.append(ord(s[i])-97)
q = int(input())
scale = 19
seg = [[0 for _ in range(2**(scale+1))] for _ in range(26)]
for i in range(n):
  tmp = int(i) + 2 ** scale
  x = t[i]
  while tmp != 0:
    seg[x][tmp] += 1
    tmp //= 2
#print(seg)
raw = []
for _ in range(q):
  d,a,b = input().split()
  d = int(d)
  if d == 1:
    a = int(a) - 1
    b = ord(b) - 97
  else:
    a = int(a) - 2
    b = int(b) - 1
  raw.append([d,a,b])
for p in range(q):
  d,a,b = raw[p]
  if d == 1:
    tmp = int(a)
    c = t[tmp]
    tmp += 2**scale
    while tmp != 0:
      seg[c][tmp] -= 1
      tmp >>= 1
    tmp = int(a)
    t[tmp] = b
    tmp += 2**scale
    while tmp != 0:
      seg[b][tmp] += 1
      tmp >>= 1
  else:
    ans = 0
    for d in range(26):
      l = 0
      r = 0
      if a == -1:
        l = 0
      else:
        tmp = a + 2**scale
        l += seg[d][tmp]
        while tmp != 1:
          if tmp & 1:
            l += seg[d][tmp-1]
          tmp >>= 1
      tmp = b + 2**scale
      r += seg[d][tmp]
      while tmp != 1:
        if tmp & 1:
          r += seg[d][tmp-1]
        tmp >>= 1
      if r > l:
        ans += 1
      #print(d,r,l)
    print(ans)
#print(t)
### BUGGY CODE ###

a, b, c, k = [int(tmp) for tmp in input().split()]
ans = 0
for i in range(1,k+1) :
	if a>0 :
		ans +=1
		a-=1
	elif b>0 :
		b-=1
	elif c>0 :
		c-=1
		ans -= 1
print(ans)


### FIXED CODE ###

a, b, c, k = [int(tmp) for tmp in input().split()]
if k <= a :
  print(k)
elif k <= a+b :
  print(a)
else :
  print(a-(k-a-b))
### BUGGY CODE ###

k = int(input())
if k%2==0 or k%5==0:
    print('-1')
else:
    from itertools import accumulate
    ac = list(accumulate([7*pow(10, i, k)%k for i in range(999983)]))
    for idx, a in enumerate(ac):
        if a%k == 0:
            print(idx+1)
            break
    else:
        print('-1')

### FIXED CODE ###

k = int(input())

if k%2==0 or k%5==0:
    print('-1')
else:
    from itertools import accumulate
    ac = list(accumulate([7*pow(10, i, k)%k for i in range(999983)]))
    for idx, a in enumerate(ac):
        if a%k == 0:
            print(idx+1)
            break
    else:
        print('-1')
### BUGGY CODE ###

N,W = map(int,input().split())
table = [ list(map(int,input().split(" "))) for i in range(N)]
N += 1
W += 1
dp = [[0 for i in range(W)] for j in range(N)]

for i in range(1,N):
    for j in range(W):
        if(j- table[i-1][0] >= 0):
            dp[i][j] = max(dp[i-1][j],dp[i-1][j-table[i-1][0]]+table[i-1][1])
        else:
            dp[i][j] = dp[i-1][j]


print(dp[N-1][W-1])


### FIXED CODE ###

N,W = map(int,input().split())
table = [ list(map(int,input().split(" "))) for i in range(N)]
N += 1
W += 1
dp = [[0 for i in range(W)] for j in range(N)]

for i in range(1,N):
    for j in range(W):
        if(j- table[i-1][0] >= 0):
            dp[i][j] = max(dp[i-1][j],dp[i-1][j-table[i-1][0]]+table[i-1][1])
        else:
            dp[i][j] = dp[i-1][j]


print(dp[N-1][W-1])
### BUGGY CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    count = 0

    s = [0 for _ in range(N)]
    for i in range(N):
        if i == 0:
            s[i] = A[i]
        else:
            s[i] = s[i-1] + A[i]
    count += s.count(0)

    for i in range(N-1):
        del s[0]
        for j in range(len(s)):
            s[j] -= A[i]
        count += s.count(0)

    return count

if __name__ == '__main__':
    print(main())


### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    count = 0

    s = [0 for _ in range(N+1)]
    for i in range(N):
        s[i+1] = s[i] + A[i]
    s.sort()
    n = 1
    for i in range(N):
        if s[i+1] == s[i]:
            n+=1
        else:
            count += n*(n-1)//2
            n = 1
    count += n*(n-1)//2
    return count

if __name__ == '__main__':
    print(main())
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))

l.sort(reverse=True)
ans=0

for i in range(0,n-1):
  for j in range(i+1,n-1):
    for k in range(j+1,n):
      if l[i]+l[j]>l[k] and l[i]+l[k]>l[j] and l[k]+l[j]>l[i]:
        ans+=1
        #print(l[i],l[j],l[k])
print(ans)
    
    

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))

l.sort(reverse=True)
ans=0

for i in range(0,n-2):
  for j in range(i+1,n-1):
    left = j
    right = n
    while right-left>1:
      mid = (left + right)//2
      
      if l[i]+l[j]>l[mid] and l[i]+l[mid]>l[j] and l[mid]+l[j]>l[i]:
        left = mid
      else:
        right = mid
    #print(i,j,left)
    ans+=(left-j)
      
print(ans)
### BUGGY CODE ###

import sys
from bisect import *

input=sys.stdin.readline

def main():
    n = int(input()[:-1])
    aa = list(map(int, input().split()))
    ans = 0
    pos = [0] * n
    for i, a in enumerate(aa):
        pos[a - 1] = i
    # print(pos)
    fin = [-1, -1, n, n]
    for a in range(n - 1, -1, -1):
        i = pos[a]
        j = bisect_left(fin, i)
        fin.insert(j, i)
        ans += (a + 1) * ((fin[j - 1] - fin[j - 2]) * (fin[j + 1] - fin[j])
                          + (fin[j] - fin[j - 1]) * (fin[j + 2] - fin[j + 1]))
        # print(a, ans, fin)
    print(ans)

main()


### FIXED CODE ###

# 参考 https://atcoder.jp/contests/abc140/submissions/7411285
import sys
input = sys.stdin.readline

def main():
    n = int(input()[:-1])
    aa = list(map(int, input().split()))
    ans = 0
    pos = [0] * (n + 1)
    for i, a in enumerate(aa):
        pos[a] = i + 2
    Lnext = [1, 1] + list(range(1, n + 1)) + [n, n]
    Rnext = [3, 3] + list(range(3, n + 3)) + [n + 2, n + 2]
    for a in range(1,n + 1):
        i = pos[a]
        l0 = Lnext[i]
        l1 = Lnext[l0]
        r0 = Rnext[i]
        r1 = Rnext[r0]
        ans += a * ((l0 - l1) * (r0 - i) + (i - l0) * (r1 - r0))
        Lnext[r0] = l0
        Rnext[l0] = r0
    print(ans)

main()
### BUGGY CODE ###

n,m,q = list(map(int,input().split()));

data = [0]*q;
for i in range(q):
    data[i] = list(map(int,input().split()));

A = [1]*n;
ans = 0;
As = [A];

for i in As :
    A_now = As.pop(-1);
    for j in range(n) :
        if A_now[j] < m :
            A_next = [A_now[j]+1]*n;
            for k in range(j) :
                A_next[k] = A_now[k];
            As.append(A_next);
    ans_now = 0;
    for j in range(q) :
        if A_now[data[j][1]-1] - A_now[data[j][0]-1] == data[j][2] :
            ans_now += data[j][3];
    if ans_now>ans :
        ans = ans_now;


print(ans);

### FIXED CODE ###

n,m,q = list(map(int,input().split()));
 
data = [0]*q;
for i in range(q):
    data[i] = list(map(int,input().split()));
 
A = [1]*n;
ans = 0;
As = [A];
 
for i in As :
    A_now = As.pop(-1);
    for j in range(n) :
        if A_now[j] < m :
            A_next = [A_now[j]+1]*n;
            for k in range(j) :
                A_next[k] = A_now[k];
            As.append(A_next);
    ans_now = 0;
    for j in range(q) :
        if A_now[data[j][1]-1] - A_now[data[j][0]-1] == data[j][2] :
            ans_now += data[j][3];
    if ans_now>ans :
        ans = ans_now;
 
 
print(ans);
### BUGGY CODE ###

n = int(input(''))
stra = input('')

alist = stra.split(' ')
dic = {}
for i in range(0,len(alist)):
  if alist[i] in dic.keys():
    dic[alist[i]]+=1
  else:
    dic[alist[i]] = 1

for k in range(0,n):
  cnt = 0
  key = alist[k]
  for k,v in dic.items():
    if k== key:
      cnt += ((v-1)*(v-2))/2
    else:
      cnt += (v*(v-1))/2
  print(int(cnt))

### FIXED CODE ###

n = int(input(''))
stra = input('')

alist = stra.split(' ')
dic = {}
for i in range(0,len(alist)):
  if alist[i] in dic.keys():
    dic[alist[i]]+=1
  else:
    dic[alist[i]] = 1

all_cnt = 0    
for k,v in dic.items():
  all_cnt += (v*(v-1))/2

    
for k in range(0,n):
  cnt = 0
  key = alist[k]
  minus_cnt1 = (dic[key] * (dic[key]-1))/2
  minus_cnt2 = ((dic[key]-1) * (dic[key]-2))/2
  print(int(all_cnt -  minus_cnt1 + minus_cnt2))
### BUGGY CODE ###

import sys
n,q=map(int,input().split())
p=[]
for e in sys.stdin:
 s,k=e.split()
 p+=[[s,int(k)]]
b=[1]*n
t=0
while sum(b):
 for i in range(n):
  if b[i]:
   a=p[i]
   if a[1]>q:a[1]-=q;t+=q
   else:b[i]=0;t+=a[1];print(a[0],t)


### FIXED CODE ###

import sys
from collections import deque
def m():
 s=sys.stdin.readlines()
 q=int(s[0].split()[1])
 f=lambda x,y:(x,int(y))
 d=deque(f(*e.split())for e in s[1:])
 t,a=0,[]
 while d:
  k,v=d.popleft()
  if v>q:v-=q;t+=q;d.append([k,v])
  else:t+=v;a+=[f'{k} {t}']
 print('\n'.join(a))
if'__main__'==__name__:m()
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()

A = [LIST() for _ in range(N)]
graph = csr_matrix(A)
dist_matrix = floyd_warshall(graph, directed=False)

ans = 0
for i in range(N-1):
    for j in range(i+1, N):
        if A[i][j] != dist_matrix[i][j]:
            print(-1)
            exit()
        for k in range(N):
            if i == k or j == k:
                continue
            if A[i][k] + A[k][j] == A[i][j]:
                break
        else:
            ans += A[i][j]

print(ans)


### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()

def warshall_floyd(v_count: int, matrix: list) -> list:
    for i in range(v_count):
        for j, c2 in enumerate(row[i] for row in matrix):
            for k, (c1, c3) in enumerate(zip(matrix[j], matrix[i])):
                if c1 > c2+c3:
                    matrix[j][k] = c2+c3
    return matrix

A = [LIST() for _ in range(N)]
dist_matrix = warshall_floyd(N, deepcopy(A))

ans = 0
for i, j in combinations(range(N), 2):
    if A[i][j] != dist_matrix[i][j]:
        print(-1)
        break
    for k in range(N):
        if i == k or j == k:
            continue
        if A[i][k] + A[k][j] == A[i][j]:
            break
    else:
        ans += A[i][j]
else:
    print(ans)
### BUGGY CODE ###

from collections import Counter


n = int(input())
s = "z" + input() + "z"


ans = float("INF")
for i in range(1, n+1):
    leader = s[i]
    w = list(s[1:i])
    e = list(s[i+1::])
    cnt_w2e = Counter(w)
    cnt_e2w = Counter(e)
    change = cnt_w2e["W"] + cnt_e2w["E"]
    ans = min(change, ans)
print(ans)


### FIXED CODE ###

# 写経

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


cnt = s[1:].count("E")
ans = cnt
for i in range(1, n):
    if s[i-1] == "W":
        cnt += 1
    if s[i] == "E":
        cnt -= 1
    ans = min(ans, cnt)


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

N = int(input())
S = input()
array = ["RGB", "RBG", "BGR", "BRG", "GRB", "GBR"]
count = 0

for a in array:
    for i in range(N):
        if S[i] == a[0]:
            for j in range(i + 1, N):
                if S[j] == a[1]:
                    for k in range(j + 1, N):
                        if S[k] == a[2] and j - i != k - j:
                            count += 1

print(count)

### FIXED CODE ###

N = int(input())
S = input()

if N == 1 or N == 2:
    ans = 0
else:
    R = S.count('R')
    G = S.count('G')
    B = S.count('B')
    rgb = R * G * B

    count = 0
    for i in range(N - 2):
        for j in range(i + 1, N - 1):
            k = 2 * j - i
            if k >= N:
                break 
            if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
                count += 1
    ans = rgb - count

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

s = input()
ans = 0
num = 0
for i in range(num,len(s)-3):
    for j in range(i+4,len(s)):
        if  (int(s[i:j+1]) % 2019 == 0):
            ans += 1
            if (i == num+1 and i != 1):
                ans += 1
            num = j
            break
print(ans)

### FIXED CODE ###

s = input()
ans = 0
mod = [0]*2019
t = s[len(s)-1]
n = 1
for i in range(len(s)-1,-1,-1):
#     mod.append(int(s[i:])%2019)
    mod[int(t)%2019] += 1
#     t = int(t) + (10**(len(s)-i-1))*int(s[i])
    t = int(t) + n*10*int(s[i-1])
    n = n*10%2019
for i in range(0,2019):
    ans += mod[i]*(mod[i]-1)/2
ans += mod[0]
print(int(ans))