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

def prepare(n, MOD):
 
    # 1! - n! の計算
    f = 1
    factorials = [1]  # 0!の分
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    # n!^-1 の計算
    inv = pow(f, MOD - 2, MOD)
    # n!^-1 - 1!^-1 の計算
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
     
    return factorials, invs


MOD = 10**9 + 7
f, inv = prepare(10**5+1, MOD)

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

a.sort(reverse=True)


cnt = 0
for i in range(n-k+1):
    for j in range(i+k-1, n):
        cd = a[i] - a[j]
        cn = j - i - 1
        ck = k - 2
        if not(cn == 0 and ck > 1):
            combi = f[cn] * inv[ck] % MOD * inv[cn - ck] % MOD
            cnt += cd * combi % MOD
            cnt %= MOD
        
print(cnt)

### FIXED CODE ###

def prepare(n, MOD):
 
    # 1! - n! の計算
    f = 1
    factorials = [1]  # 0!の分
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    # n!^-1 の計算
    inv = pow(f, MOD - 2, MOD)
    # n!^-1 - 1!^-1 の計算
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
     
    return factorials, invs


MOD = 10**9 + 7
f, inv = prepare(10**5+100, MOD)

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

a.sort(reverse=True)

p = 0
m = 0
for i in range(n):
    if n - i >= k:
        cn = n - i - 1
        ck = k - 1
        if cn >= ck:
            combi = f[cn] * inv[ck] % MOD * inv[cn - ck] % MOD
            if a[i] >= 0:        
                p += (a[i] * combi) % MOD
            else:
                p += (a[i] * combi) % -MOD
            if p >= 0:
                p %= MOD
            else:
                p %= -MOD
    if i >= k - 1:
        cn = i
        ck = k - 1
        if cn >= ck:
            combi = f[cn] * inv[ck] % MOD * inv[cn - ck] % MOD
            if a[i] >= 0:        
                m += (a[i] * combi) % MOD
            else:
                m += (a[i] * combi) % -MOD
            if m >= 0:
                m %= MOD
            else:
                m %= -MOD
        
print((p - m)%MOD)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
seta = list(set(a))

if len(a) <= len(seta)+1:
  print(0)
  exit()

seta.sort(reverse=True)
c2 = []
c4 = 0
for i in seta:
  if a.count(i)>=2:
    c2.append(i)
    if len(c2) == 2:
      break
  
for i in seta:
  if a.count(i)>=4:
    c4=i
    break

if c4 == 0 and len(c2)<2:
  print(0)
elif c4 == 0 and len(c2)>=2:
  print(c2[0]*c2[1])
elif c4 > 0 and len(c2)<2:
  print(c4**2)
else:
  print(max(c4**2,c2[0]*c2[1]))

### FIXED CODE ###

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

e=[]
a.sort(reverse=True)
for i in range(len(a)-1):
  if a[i] == a[i+1] and a[i] not in e:
    e.append(a[i])
    if len(e) == 2:
      break
e.sort(reverse=True)

c4 = 0
for i in e:
  if a.count(i)>=4:
    c4=i
    break

if c4 == 0 and len(e)<2:
  print(0)
elif c4 == 0 and len(e)>=2:
  print(e[0]*e[1])
elif c4 > 0 and len(e)<2:
  print(c4**2)
else:
  print(max(c4**2,e[0]*e[1]))
### BUGGY CODE ###

H,W = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(H)]
B = [list(map(int,input().split())) for _ in range(H)]
dp1 = [[False]*((H+W)*80) for _ in range(W)]
dp2 = [[False]*((H+W)*80) for _ in range(W)]
for w in range(W):
    dp1[w][0] = True

for h in range(H):
    for w in range(W):
        va = A[h][w]
        vb = B[h][w]
        for v in range((H+W)*80):
            if dp1[w][v]:
                dp2[w][abs(v+va-vb)] = True
                dp2[w][abs(v-va+vb)] = True
        if w!=0:
            for v in range((H+W)*80):
                if dp2[w-1][v]:
                    dp2[w][abs(v+va-vb)] = True
                    dp2[w][abs(v-va+vb)] = True
    dp1 = dp2
    dp2 = [[False]*((H+W)*80) for _ in range(W)]

for v in range((H+W)*80):
    if dp1[W-1][v]:
        ans = v
        break

print(ans)

### FIXED CODE ###

H,W = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(H)]
B = [list(map(int,input().split())) for _ in range(H)]
D = [[abs(A[h][w]-B[h][w]) for w in range(W)] for h in range(H)]
def cal():
    dp1 = [set() for _ in range(W)]
    dp2 = [set() for _ in range(W)]
    for h in range(H):
        for w in range(W):
            d = D[h][w]
            if h==0 and w==0:
                dp2[0].add(d)
            for v in dp1[w]:
                v1 = v+d
                v2 = v-d if v>=d else -v+d
                dp2[w].add(v1)
                dp2[w].add(v2)
            if 0 < w:
                for v in dp2[w-1]:
                    v1 = v+d
                    v2 = v-d if v>=d else -v+d
                    dp2[w].add(v1)
                    dp2[w].add(v2)
        dp1 = dp2
        dp2 = [set() for _ in range(W)]
    return min(dp1[W-1])
ans = cal()
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=2019
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    A=list(map(int,list(input())))
    N=len(A)
    d=[0]*2019
    for i in range(2019):
        d[i]=(i*10)%MOD
    dp=[[0]*2019 for _ in range(N+1)]
    ans=0
    for i,x in enumerate(A):
        for j in range(2019):
            dp[i+1][(d[j]+x)%MOD]+=dp[i][j]
        dp[i+1][x]+=1
        ans+=dp[i+1][0]
    print(ans)

    

if __name__ == '__main__':
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=2019
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    A=list(map(int,list(input())[::-1]))
    N=len(A)
    S=[0]*(N+1)
    for i in range(N):
        S[i+1]=(S[i]+A[i]*pow(10,i,MOD))%MOD
    l=[0]*2019
    ans=0
    for i in range(N+1):
        ans+=l[S[i]]
        l[S[i]]+=1
    print(ans)


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

import sys
pos=input()
pos=pos.split()
N=int(pos[0])
P=int(pos[1])
T=int(pos[2])
point=[P]*N

for i in range(0,T):
    c=input()
    point=[p-1 for p in point]
    point[int(c)-1]+=1

for i in range(0,N):
    if(point[i]>0):
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

pos=input()
pos=pos.split()
N=int(pos[0])
P=int(pos[1])
T=int(pos[2])
point=[0]*N

for i in range(0,T):
    c=input()
    point[int(c)-1]+=1
point=[P-T+d for d in point]
for i in range(0,N):
    if(point[i]>0):
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

H, W = map(int, input().split())
Map = []
for _ in range(H):
  List = list(input())
  Map.append(List)
L = [[0]*W for _ in range(H)]
D = [[0]*W for _ in range(H)]
R = [[0]*W for _ in range(H)]
U = [[0]*W for _ in range(H)]
for i in range(H):
  for j in range(W):
    if Map[i][j] == '#':
      L[i][j] = 0
    elif j == 0:
      L[i][j] = 1
    else:
      L[i][j] = L[i][j-1] + 1
for i in range(H):
  for j in range(W):
    if Map[i][j] == '#':
      D[i][j] = 0
    elif i == 0:
      D[i][j] = 1
    else:
      D[i][j] = D[i-1][j] + 1
for i in reversed(range(H)):
  for j in reversed(range(W)):
    if Map[i][j] == '#':
      R[i][j] = 0
    elif j == W - 1:
      R[i][j] = 1
    else:
      R[i][j] = R[i][j+1] + 1
for i in reversed(range(H)):
  for j in reversed(range(W)):
    if Map[i][j] == '#':
      U[i][j] = 0
    elif i == H - 1:
      U[i][j] = 1
    else:
      U[i][j] = U[i+1][j] + 1

Answer = 0
for i in range(H):
  for j in range(W):
    tmp = L[i][j] + R[i][j] + D[i][j] + U[i][j] -3
    if tmp > Answer:
      Answer = tmp
print(Answer)

### FIXED CODE ###

import numpy as np
H,W = map(int,input().split())
Map=[list(input()) for h in range(H)]
Map=[[1 if s=='.' else 0 for s in Map[h]] for h in range(H)]
Map=np.array(Map,dtype=int)
L=Map.copy()
R=Map.copy()
U=Map.copy()
D=Map.copy()
for w in range(1,W):
    L[:,w]=(L[:,w-1]+1)*Map[:,w]
    R[:,-(1+w)]=(R[:,-w]+1)*Map[:,-(1+w)]
for h in range(1,H):
    U[h,:]=(U[h-1,:]+1)*Map[h,:]
    D[-(1+h),:]=(D[-h,:]+1)*Map[-(1+h),:]
print((L+R+U+D).max()-3)
### BUGGY CODE ###

import math
N,K=map(int,input().split())
A=list(map(int,input().split()))
multi=math.factorial(N)//(math.factorial(K-1)*math.factorial(N-K+1))
A.sort(reverse=True)
count=0
for i in range(N-K+1):
    multi=multi*(N-K+1-i)//(N-i)
    count+=((A[i]-A[N-1-i])*multi)
    count%=10**9+7
print(count)

### FIXED CODE ###

import math
n_ = 10**5 + 3
mod = 10**9+7
fun = [1]*(n_+1)
for i in range(1,n_+1):
    fun[i] = fun[i-1]*i%mod
rev = [1]*(n_+1)
rev[n_] = pow(fun[n_],mod-2,mod)
for i in range(n_-1,0,-1):
    rev[i] = rev[i+1]*(i+1)%mod
def nCr(n,r):
    if n <= 0 or r < 0 or r > n: return 0
    return fun[n]*rev[r]%mod*rev[n-r]%mod
N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
count=0
for i in range(N-K+1):
    count=(count+((A[i]-A[N-1-i])*nCr(N-i-1,K-1)))%(10**9+7)
print(count)
### BUGGY CODE ###

import bisect

# ある自然数未満までのエラトステネスの篩をつくる
def mark(s, x):
    for i in range(x + x, len(s), x):
        s[i] = False


def eratosthenes(n):
    s = [True] * n
    for x in range(2, int(n ** 0.5) + 1):
        if s[x]: mark(s, x)
    return [i for i in range(0, n) if s[i] and i > 1]


primes = eratosthenes(10 ** 5+1)
like2017 = list(filter(lambda x: (x+1)/2 in primes, primes))
num_like2017 = len(like2017)

Q = int(input())
for i in range(Q):
    l, r = map(int, input().split())
    left = bisect.bisect_left(like2017, l)
    right = num_like2017 - bisect.bisect_right(like2017, r)

    print(num_like2017 - left - right)




### FIXED CODE ###

# ある自然数未満までのエラトステネスの篩をつくる
def mark(s, x):
    for i in range(x + x, len(s), x):
        s[i] = False


def eratosthenes(n):
    s = [True] * n
    for x in range(2, int(n ** 0.5) + 1):
        if s[x]: mark(s, x)
    return s

Q = int(input())
LR = [list(map(int, input().split())) for i in range(Q)]

primes = eratosthenes(10 ** 5+1)
primes[0] = False
primes[1] = False

ruiseki = [0] * (10**5 + 1)
for i in range(3, 10**5 + 1, 2):
    if (primes[i]) and (primes[int((i+1)/2)]):
        ruiseki[i] = ruiseki[i-2] + 1
    else:
        ruiseki[i] = ruiseki[i-2]

for l, r in LR:
    print(ruiseki[r] - ruiseki[l-2])
### BUGGY CODE ###

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

ans = 0
for _ in range(k):
    if a > 0:
        a -= 1
        ans += 1
    elif b > 0:
        b -=1
    elif c > 0:
        c -= 1
        ans -= 1

print(ans)



### FIXED CODE ###

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

out = min(a,k) - max(0,k-a-b)
print(out)
### BUGGY CODE ###

def n_gram(seq, n):
    return {seq[i: i+n] for i in range(len(seq) - n + 1)}

def main(s, k):
    tmp = set()
    for i in range(1, len(s) + 1):
            tmp = tmp | n_gram(s, i)
    substr = sorted(list(tmp))
    print(substr[k-1])



if __name__ == '__main__':
    main(input(), int(input()))

### FIXED CODE ###

def n_gram(seq, n):
    return {seq[i: i+n] for i in range(len(seq) - n + 1)}

def main(s, k):
    tmp = set()
    for i in range(1, 6):
        tmp = tmp | n_gram(s, i)
    substr = sorted(list(tmp))
    print(substr[k-1])

if __name__ == '__main__':
    main(input(), int(input()))
### BUGGY CODE ###

import fractions
from functools import reduce

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
  
N = int(input())
A = list(map(int, input().split()))

ans = 0
MOD = 10**9 + 7
LCM = lcm_list(A)

for a in A:
  ans += LCM//a
  ans = ans%MOD
  
print(ans)

### FIXED CODE ###

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

ans = 0
MOD = 10**9 + 7

LCM = A[0]
for i in range(1, N):
    LCM *= A[i]//fractions.gcd(LCM, A[i])
    
for a in A:
  ans += LCM//a
  
print(ans%MOD)
### BUGGY CODE ###

isstr=input()
n,m = [int(i) for i in isstr.split(' ')]
l=[0]*m
r=[0]*m
for i in range(m):
    l[i],r[i]=[int(i)-1 for i in input().split(' ')]
a=[0]*n
for i in range(m):
    for j in range(l[i],r[i]+1):
        a[j]+=1
print(len([i for i in a if i==m]))

### FIXED CODE ###

isstr=input()
n,m = [int(i) for i in isstr.split(' ')]
l=[0]*m
r=[0]*m
for i in range(m):
    l[i],r[i]=[int(i)-1 for i in input().split(' ')]
x=min(r)-max(l)+1
x=x if x>0 else 0
print(x)
### BUGGY CODE ###

from functools import reduce

n = int(input())
s = input().strip()

MOD = 998244353

R = 1
G = 2
B = 4
RG = R + G
RB = R + B
GB = G + B
RGB = R + G + B
table = {'R': R, 'G': G, 'B': B}
counts = {
    0: 0,
    R: 0, G: 0, B: 0,
    RG: 0, RB: 0, GB: 0,
}
patterns = 1
for cv in [table[c] for c in s]:
    rest = RGB - cv
    if counts[rest] > 0:
        patterns *= counts[rest]
        counts[rest] -= 1
    elif sum([counts[v] for v in [R, G, B] if v != cv]) > 0:
        for bc in [R, G, B]:
            if rest & bc != 0 and counts[bc] > 0:
                patterns *= counts[bc]
                counts[bc] -= 1
                counts[bc + cv] += 1
                break
    else:
        counts[cv] += 1

print((patterns * reduce(lambda o, v: o * v, range(1, n + 1), 1)) % MOD)


### FIXED CODE ###

from functools import reduce

n = int(input())
s = input().strip()

MOD = 998244353

R = 1
G = 2
B = 4
RG = R + G
RB = R + B
GB = G + B
RGB = R + G + B
table = {'R': R, 'G': G, 'B': B}
counts = {
    0: 0,
    R: 0, G: 0, B: 0,
    RG: 0, RB: 0, GB: 0,
}
patterns = 1
for cv in [table[c] for c in s]:
    rest = RGB - cv
    if counts[rest] > 0:
        patterns = (patterns * counts[rest]) % MOD
        counts[rest] -= 1
    elif R != cv and counts[R] > 0:
        patterns = (patterns * counts[R]) % MOD
        counts[R] -= 1
        counts[R + cv] += 1
    elif G != cv and counts[G] > 0:
        patterns = (patterns * counts[G]) % MOD
        counts[G] -= 1
        counts[G + cv] += 1
    elif B != cv and counts[B] > 0:
        patterns = (patterns * counts[B]) % MOD
        counts[B] -= 1
        counts[B + cv] += 1
    else:
        counts[cv] += 1

print((patterns * reduce(lambda o, v: (o * v) % MOD, range(1, n + 1), 1)) % MOD)
### BUGGY CODE ###

import numpy as np
import copy
import queue


q = queue.Queue()

n, m = map(int, input().split())
l = [[0 for _ in range(n)] for _ in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    l[a-1][b-1] = 1
    l[b-1][a-1] = 1


l = np.array(l)
lc = copy.deepcopy(l)
li = [-1 for _ in range(n)]

def search(x):
    if sum(lc[x]) == 0:
        q.queue = False
        return
    
    ind_lis = np.where(lc[x] == 1)[0]
    ind_lis = [e for e in ind_lis if li[e] == -1]
#     print(li)

    for e in ind_lis:
#         print(e+1)

        lc[x][e] =0
        lc[e][x] =0
        if li[e] == -1:
            li[e] = x
#             print('q', e+1)
            q.put(e)
x = 0
search(x)
while q.queue:
    search(q.get())

if li[1:].count(-1) == 0:
    print('Yes')
    for e in li[1:]:
        print(e+1)
else:
    print('No')


### FIXED CODE ###

# import numpy as np
# import copy
from collections import defaultdict
import queue


q = queue.Queue()

n, m = map(int, input().split())
graph = defaultdict(list)
for _ in range(m):
    a, b = map(lambda x: int(x), input().split())
    graph[a].append(b)
    graph[b].append(a)


# l = np.array(l)
# lc = copy.deepcopy(l)
li = [-1 for _ in range(n)]
li[0] = 1

def search(x):
#     if sum(l[x]) == 0:
#         q.queue = False
#         return
    
#     ind_lis = np.where(lc[x] == 1)[0]
#     ind_lis = [e for e in ind_lis if li[e] == -1]
#     print(li)
#     print(lc[x])
    for e in graph[x]:
#         print(e)
        if li[e-1] != -1:
            continue
        li[e-1] = x
#         print('q', i+1)
        q.put(e)
x = 1
search(x)
while q.queue:
    search(q.get())

if li[1:].count(-1) == 0:
    print('Yes')
    for e in li[1:]:
        print(e)
else:
    print('No')
### BUGGY CODE ###

N = int(input())
# サイズが下の方が大きくないとダメtop<mid<bottom
tops = sorted(list(map(int, input().split(" "))))
mids = list(map(int, input().split(" ")))
bottoms = sorted(list(map(int, input().split(" "))))
# print(tops)
# print(mids)
# print(bottoms)


def left_binary_search(check_list, num, left, right):
    if left > right:
        return left
    mid = (left + right) // 2
    if check_list[mid] >= num:
        return left_binary_search(check_list, num, left, mid - 1)
    else:
        return left_binary_search(check_list, num, mid + 1, right)


def right_binary_search(check_list, num, left, right):
    if left > right:
        return left
    mid = (left + right) // 2
    if check_list[mid] > num:
        return right_binary_search(check_list, num, left, mid - 1)
    else:
        return right_binary_search(check_list, num, mid + 1, right)


total_count = 0
for mid in mids:
    bottom_start_index = right_binary_search(bottoms, mid, 0, N - 1)
    top_end_index = left_binary_search(tops, mid, 0, N - 1)
    total_count += ((N - bottom_start_index) * top_end_index)
print(total_count)


### FIXED CODE ###

import bisect
N = int(input())
# サイズが下の方が大きくないとダメtop<mid<bottom
tops = sorted(list(map(int, input().split(" "))))
mids = list(map(int, input().split(" ")))
bottoms = sorted(list(map(int, input().split(" "))))
# print(tops)
# print(mids)
# print(bottoms)


# def left_binary_search(check_list, num, left, right):
#     if left > right:
#         return left
#     mid = (left + right) // 2
#     if check_list[mid] >= num:
#         return left_binary_search(check_list, num, left, mid - 1)
#     else:
#         return left_binary_search(check_list, num, mid + 1, right)


# def right_binary_search(check_list, num, left, right):
#     if left > right:
#         return left
#     mid = (left + right) // 2
#     if check_list[mid] > num:
#         return right_binary_search(check_list, num, left, mid - 1)
#     else:
#         return right_binary_search(check_list, num, mid + 1, right)


total_count = 0
for mid in mids:
    # bottom_start_index = right_binary_search(bottoms, mid, 0, N - 1)
    bottom_start_index = bisect.bisect_right(bottoms, mid)
    # top_end_index = left_binary_search(tops, mid, 0, N - 1)
    top_end_index = bisect.bisect_left(tops, mid)
    total_count += ((N - bottom_start_index) * top_end_index)
print(total_count)
### BUGGY CODE ###

import sys
import math
sys.setrecursionlimit(10 ** 6)  # 再帰関数の再帰の深さを設定
to_index = lambda x: int(x) - 1  # 入力した数字に1を引いたものを返す
print_list_in_2D = lambda x: print(*x, sep="\n")  # リストの要素を改行を挟んで表示する関数

# 入力を整数に変換して受け取る
def input_int():
    return int(input())

II = input_int

def map_int_input():
    return map(int, input())

MII = map_int_input

def MII_split():
    return map(int, input().split())

def MII_to_index():
    return map(to_index, input())

def MII_split_to_index():
    return map(to_index, input().split())

# 入力全てを整数に変換したものの配列を受け取る
def list_int_inputs():
    return list(map(int, input()))

LII = list_int_inputs

def LII_split():
    return list(map(int, input().split()))

# 2次元リスト化
def LII_2D(rows_number):
    return [LII() for _ in range(rows_number)]

def LII_split_2D(rows_number):
    return [LII_split() for _ in range(rows_number)]

S = input()
N = len(S)
# N 文字の文字列 S から、長さ N+1 の累積和 s[0], s[1], ..., s[N] を作る
# これを 2019 で割ったあまりで分類する (具体的には counter[ r ] := あまりが r のやつが何個あるか)
# 各 r ごとに、counter[r] 個から 2 個選ぶ方法の数を、足し上げる

subs = [int(S[N - i:]) if S[N - i:] else 0 for i in range(N + 1)]
counter = dict()
for num in subs:
    rest = num % 2019
    if rest in counter:
        counter[rest] += 1
    else:
        counter[rest] = 1

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

ans = 0
for r in counter.values():
    if r >= 2:
        ans += combinations_count(r, 2)
print(ans)

### FIXED CODE ###

S = list(input())
N = len(S)
# N 文字の文字列 S から、長さ N+1 の ---累積和--- s[0], s[1], ..., s[N] を作る
# これを 2019 で割ったあまりで分類する (具体的には counter[ r ] := あまりが r のやつが何個あるか)
# 各 r ごとに、counter[r] 個から 2 個選ぶ方法の数を、足し上げる

counter = [0] * 2019
k = 10
for i in range(N + 1):
    if i == 0:
        sub = 0
    elif i == 1:
        sub = int(S[N - 1])
    else:
        sub += int(S[N - i]) * k
        k *= 10
        k %= 2019
    rest = sub % 2019
    counter[rest] += 1

ans = 0
for r in counter:
    ans += r * (r - 1) // 2
print(ans)
### BUGGY CODE ###

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

#%%
C = {}
for i in A:
    if i in C.keys():
        C[i] += 1
    else:
        C[i] = 1

for i in A:
    ans = 0
    D = C.copy()
    D[i] += -1
    for j in D:
        ans += (D[j] * (D[j]-1)) // 2
    print(ans)

### FIXED CODE ###

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

#%%
C = {}
for i in A:
    if i in C:
        C[i] += 1
    else:
        C[i] = 1

ans = 0    
for i in C.keys():
    ans += C[i] * (C[i]-1) // 2
    
for i in A:
    dec =  C[i] * (C[i]-1) // 2 - (C[i]-1) * (C[i]-2) //2
    print(ans - dec)
### BUGGY CODE ###

n=int(input())
s=[""]*n
for ii in range(n):
  s[ii]=input()
ss=list(set(s))
ss.sort()
c=[0]*len(ss)
for ii in range(n):
  c[ss.index(s[ii])]+=1
#print(c)
mx=max(c)
for ii in range(len(ss)):
  if c[ii]==mx:
    print(ss[ii])
  


### FIXED CODE ###

n=int(input())
ss=set()
d=dict()
for ii in range(n):
  s=input()
  if s in ss:
    d[s]+=1
  else:
    ss.add(s)
    d[s]=1
ss=list(ss)
ss.sort()
mx=max(d.values())
for ii in ss:
  if d[ii]==mx:
    print(ii)
### BUGGY CODE ###

import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N, M = map(int, input().split())
        A = list(map(int, input().split()))

        for _ in range(M):
            A.sort()
            A[-1] //= 2

        print(sum(A))


# Run main
if __name__ == '__main__':
    AtCoder().main()


### FIXED CODE ###

import bisect
import heapq
import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N, M = map(int, input().split())
        hq = []
        for c in input().split():
            heapq.heappush(hq, -1 * int(c))

        for _ in range(M):
            heapq.heappush(hq, int(heapq.heappop(hq) / 2))

        print(-1 * sum(hq))


# Run main
if __name__ == '__main__':
    AtCoder().main()
### BUGGY CODE ###

S = int(len(input()))

cnt = "x"
length = 0
a = "x"

while S != length:
    cnt = cnt + a
    length = len(cnt)

print(cnt)


### FIXED CODE ###

S = len(input())
cnt = ""
length = 0
a = "x"
for i in range(S):
    cnt = cnt + a
print(cnt)
### BUGGY CODE ###

import sys
N, M = map(int, input().split())

graph = [dict() for _ in range(N)]
for i in range(M):
    x, y = map(int, input().split())
    graph[x - 1][y - 1] = 1

dp = [0 for _ in range(N)]

sys.setrecursionlimit(10 ** 9)


def dfs(num_v):
    if len(graph[num_v]) == 0:
        return
    for to in graph[num_v].keys():
        dp[to] = max(dp[to], dp[num_v] + 1)
        dfs(to)


ans = 0
for i in range(N):
    dfs(i)
    ans = max(ans, max(dp))
print(ans)


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 8)

N, M = map(int, input().split())
graph = [dict() for _ in range(N)]

for i in range(M):
    x, y = map(int, input().split())
    graph[y - 1][x - 1] = 1

dp = [0 for _ in range(N)]


def dfs(u):
    if dp[u] != 0:
        return dp[u]
    max_dis = 0
    for f in graph[u].keys():
        if max_dis < dfs(f) + 1:
            max_dis = dfs(f) + 1

    dp[u] = max_dis
    return dp[u]


for i in range(N):
    dfs(i)
print(max(dp))