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

import math
from collections import Counter

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

def combinations_count(n, r):
    if n==1:
        return 0
    else:
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

for k in range(N):
    tmp=Balls[k]
    del Balls[k]

    array_k = Balls
    sum_k=0
    c= Counter(array_k)
    for j in list(c.values()):
        sum_k += combinations_count(j,2)
    
    Balls.insert(k,tmp)
    print(sum_k)




### FIXED CODE ###

import math
from collections import Counter

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

def combinations_count(n, r):
    if n==1:
        return 0
    else:
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
c = Counter(Balls)
d={}
ALL_SUM=0
for i,j in c.most_common():
    d[i]=j
    ALL_SUM+=combinations_count(j,2)
for k in Balls:
    print(ALL_SUM-(d[k] - 1))

# for k in range(N):
#     tmp=Balls[k]
#     array_k = Balls
#     sum_k=0
#     c= Counter(array_k)


#     for j in list(c.values()):
#         sum_k += combinations_count(j,2)
    
#     Balls.insert(k,tmp)
#     print(sum_k)
### BUGGY CODE ###

H,W = map(int,input().split())
maze = [list(input()) for j in range(H)]

def bfs(h,w):
  checked = [(h,w)]
  q = [(h,w,0)] if maze[h][w]=="." else []
  g_n = 0
  while q:
    h_,w_,n = q.pop(0)
    g_n = max(n, g_n)
    for i,j in zip([0,0,-1,1],[-1,1,0,0]):
      if (0<=h_+i<H) and (0<=w_+j<W):
        pt = (h_+i,w_+j)
        if pt in checked: continue
        checked.append(pt)
        q = q + [pt+(n+1,)] if maze[pt[0]][pt[1]]=="." else q
  return g_n

n = 0
for i in range(H):
  for j in range(W):
    n = max(n, bfs(i,j))
print(n)

### FIXED CODE ###

H,W = map(int,input().split())
maze = [list(input()) for j in range(H)]

def bfs(h,w):
  checked = [[False for i in range(W)] for j in range(H)]
  q = [(h,w,0)] if maze[h][w]=="." else []
  checked[h][w] = True
  g_n = 0
  while q:
    h_,w_,n = q.pop(0)
    g_n = max(n, g_n)
    for i,j in zip([0,0,-1,1],[-1,1,0,0]):
      if (0<=h_+i<H) and (0<=w_+j<W):
        if checked[h_+i][w_+j]: continue
        checked[h_+i][w_+j] = True
        if maze[h_+i][w_+j]==".": q.append((h_+i,w_+j,n+1))
  return g_n

n = 0
for i in range(H):
  for j in range(W):
    n = max(n, bfs(i,j))
print(n)
### BUGGY CODE ###

def bfs(graph, start, weight, ):
	queue = [start]
	while queue:
		label = queue.pop(0)
		cnt[label-1] += weight
		queue += graph.get(label,[])

n, q = list(map(int, input().split()))
a = [list(map(int, input().split())) for i in range(n-1)]
b = [list(map(int, input().split())) for i in range(q)]

cnt = [0 for i in range(n)]
dic = {}
for i in range(n-1):
	if a[i][0] not in dic:
		dic[a[i][0]] = [a[i][1]]
	else:
		dic[a[i][0]].append(a[i][1])

for i in range(q):
	bfs(dic, b[i][0], b[i][1])
print(*cnt)

### FIXED CODE ###

N, Q = map(int, input().split())
edges = [[] for _ in range(N)]
count = [0]*N

for _ in range(N-1):
    a, b = map(int, input().split())
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

for _ in range(Q):
    p, x = map(int, input().split())
    count[p-1] += x

not_yet = [1]*N
not_yet[0] = 0
stack = [0]

while stack:
    parent = stack.pop()
    # print(parent)
    
    for child in edges[parent]:
        if not_yet[child]:
            count[child] += count[parent]
            not_yet[child] = 0
            stack.append(child)

print(*count)
### BUGGY CODE ###

from functools import reduce
MOD = 10**9+7
n = int(input())
A = list(map(int, input().split()))


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


def lcm(a, b):
    return (a*b)//gcd(a, b)


x = reduce(lcm, A)

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

### FIXED CODE ###

from collections import defaultdict
MOD = 10**9+7
n = int(input())
A = list(map(int, input().split()))


def factorization(n):
    retval = []
    tmp = n
    for i in range(2, int(-(-n**.5//1))+1):
        if tmp % i == 0:
            cnt = 0
            while tmp % i == 0:
                cnt += 1
                tmp //= i
            retval.append((i, cnt))
    if tmp != 1:
        retval.append((tmp, 1))
    return retval


x = defaultdict(int)
for a in A:
    for p, q in factorization(a):
        if x[p] < q:
            x[p] = q

mod_x = 1
for p, q in x.items():
    mod_x *= pow(p, q, MOD)
mod_x %= MOD

B = [mod_x*pow(a, MOD-2, MOD) % MOD for a in A]
print(sum(B) % MOD)
### BUGGY CODE ###

#coding: UTF-8

N = int(input())

a = [int(input()) for i in range(N)]

ans = set()

for i in range(N-1):
    Rj = int(a.pop(0));
    tmp = max(a);
    ans.add(tmp - Rj);

print(max(ans))

### FIXED CODE ###

#coding: UTF-8

N = int(input())

a = [int(input()) for i in range(N)]

ans = set()

maxv = -9999999999
minv = a[0]
for i in range(1,N):
    if (a[i] - minv) > maxv:
        maxv = a[i] - minv
    if a[i] < minv:
        minv = a[i]

print(maxv)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N=int(input())
A=tuple(map(int,input().split()))
X=[None]*N
for i in range(N) :
    X[i]=str(A.index(i+1)+1)
print(" ".join(X))

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
X=[None]*N
for i in range(N) :
    X[A[i]-1]=i+1
print(*X)
### BUGGY CODE ###

import numpy as np


def read():
    N = int(input().strip())  # N <= 10**5
    edges = dict()
    for i in range(N-1):
        # u[i] < v[i] は保証されている
        u, v, w = list(map(int, input().strip().split()))
        if u - 1 in edges.keys():
            edges[u - 1].update({v - 1: w % 2})
        else:
            edges.update({u - 1: {v - 1: w % 2}})
        if v - 1 in edges.keys():
            edges[v - 1].update({u - 1: w % 2})
        else:
            edges.update({v - 1: {u - 1: w % 2}})
    return N, edges


def solve(N, edges):
    c = np.empty((N, ), dtype=np.int32)
    c.fill(-1)
    stack = list()
    c[0] = 0
    stack.append(0)
    while len(stack) > 0:
        s = stack.pop()
        for t in edges[s].keys():
            if c[t] == -1:
                if edges[s][t]:
                    c[t] = 1 - c[s]
                else:
                    c[t] = c[s]
                stack.append(t)
    return c


if __name__ == '__main__':
    inputs = read()
    colors = solve(*inputs)
    for col in colors:
        print("%d" % col)


### FIXED CODE ###

import numpy as np


def read():
    N = int(input().strip())  # N <= 10**5
    to = [[] for _ in range(N)]
    cost = [[] for _ in range(N)]
    for i in range(N-1):
        # u[i] < v[i] は保証されている
        u, v, w = list(map(int, input().strip().split()))
        to[u-1].append(v-1)
        to[v-1].append(u-1)
        cost[u-1].append(w % 2)
        cost[v-1].append(w % 2)
    return N, to, cost


def solve(N, to, cost):
    c = [-1] * N  # -1: unvisited, 0: white, 1: black
    q = list()
    c[0] = 0
    q.append(0)
    while len(q) > 0:
        s = q.pop()
        for t, co in zip(to[s], cost[s]):
            if c[t] == -1:
                if co:
                    c[t] = 1 - c[s]
                else:
                    c[t] = c[s]
                q.append(t)
    return c


if __name__ == '__main__':
    inputs = read()
    colors = solve(*inputs)
    for col in colors:
        print("%d" % col)
### BUGGY CODE ###

import sys
def input():
	return sys.stdin.readline()[:-1]
from collections import deque
H, W, K = map(int, input().split())
sh, sw, gh, gw = map(int, input().split())
c = ["@" * (W+2)] + ["@" + input() + "@" for _ in range(H)] + ["@" * (W+2)]
INF = 10**6+5
dist = [INF for _ in range((W+2) * (H+2))]
dist[sh*(W+2)+sw] = 0
q = deque()
q.append(sh*(W+2)+sw)
DI = [1, 0, -1, 0]
DJ = [0, 1, 0, -1]
while q:
	l = q.popleft()
	i, j = l//(W+2), l%(W+2)
	for di, dj in zip(DI, DJ):
		for k in range(1, K+1):
			ii, jj = i+di*k, j+dj*k
			if c[ii][jj] == "." and dist[ii*(W+2)+jj] > dist[i*(W+2)+j]:
				dist[ii*(W+2)+jj] = dist[i*(W+2)+j] + 1
				if ii == gh and jj == gw:
					print(dist[ii*(W+2)+jj])
					sys.exit()
				q.append(ii*(W+2) + jj)
			else:
				break
print(-1)

### FIXED CODE ###

import sys
def input():
	return sys.stdin.readline()[:-1]
from collections import deque
H, W, K = map(int, input().split())
sh, sw, gh, gw = map(int, input().split())
c = ["@" * (W+2)] + ["@" + input() + "@" for _ in range(H)] + ["@" * (W+2)]
INF = 10**6+5
dist = [[INF for _ in range(W+2)] for _ in range(H+2)]
dist[sh][sw] = 0
q = deque()
q.append(sh*(W+2)+sw)
DI = [1, 0, -1, 0]
DJ = [0, 1, 0, -1]
while q:
	l = q.popleft()
	i, j = l//(W+2), l%(W+2)
	for di, dj in zip(DI, DJ):
		for k in range(1, K+1):
			ii, jj = i+di*k, j+dj*k
			if c[ii][jj] == "@":
				break
			if dist[ii][jj] <= dist[i][j]:
				break
			if dist[ii][jj] > dist[i][j] + 1:
				dist[ii][jj] = dist[i][j] + 1
				if ii == gh and jj == gw:
					print(dist[ii][jj])
					sys.exit()
				q.append(ii*(W+2) + jj)
print(-1)
### BUGGY CODE ###

H, N = map(int, input().split())
#Cost=[]
#for i in range(N):
#  A, B = map(int, input().split())
#  Cost.append([A, B])
Cost=[[int(x) for x in input().split()] for _ in range(N)]
#  Cost.append((A, B, A/B))
#Cost = sorted(Cost, key=lambda row: row[0], reverse=True)
#sortedCost = sorted(Cost, key=lambda row: row[2], reverse=True)
#print(Cost)

DP=[float('inf')]*(H+2)
DP[0]=0
DP[1]=0
for i in range(2,H+2):
    for j in range(N):
      if i-Cost[j][0]>=0:
          DP[i]=min(DP[i], DP[i-Cost[j][0]]+Cost[j][1])
      else:
          DP[i]=min(DP[i], Cost[j][1])

print(DP[H+1])

### FIXED CODE ###

H, N = map(int, input().split())
#Cost=[]
#for i in range(N):
#  A, B = map(int, input().split())
#  Cost.append([A, B])
Cost=[[int(x) for x in input().split()] for _ in range(N)]
#  Cost.append((A, B, A/B))
#Cost = sorted(Cost, key=lambda row: row[0], reverse=True)
#sortedCost = sorted(Cost, key=lambda row: row[2], reverse=True)
#print(Cost)

DP=[float('inf')]*(H+2)
DP[0]=0
DP[1]=0
for i in range(2,H+2):
    for j in range(N):
      if i-Cost[j][0]>=0:
          DP[i]=min(DP[i], DP[i-Cost[j][0]]+Cost[j][1])
      else:
          DP[i]=min(DP[i], Cost[j][1])

print(DP[H+1])
### BUGGY CODE ###

#-*-coding:utf-8-*-

def main():
    n = int(input())
    numbers=[]
    answers=[]
    number=0
    numbers=[int(input()) for _ in range(n)]

    for number in numbers:
        if len(answers)==0:
            answers.append(number)
        else:
            if number in answers:
                answers.remove(number)
            else:
                answers.append(number)
    print(len(answers))

if __name__=="__main__":
    main()

### FIXED CODE ###

#-*-coding:utf-8-*-

from collections import Counter

def main():
    n = int(input())
    numbers=[]
    answers=[]
    number=0
    numbers=[int(input()) for _ in range(n)]
    Numbers_col = Counter(numbers)

    for number in Numbers_col.values():
        if number%2!=0:
            answers.append(number)
    print(len(answers))

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

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

ans = 1
for i in range (n):
    if array[i] == 0:
        ans = 0

for i in range (n):
    ans *= array[i]

if ans > 1e18:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

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

ans = 1
a.sort()
if a[0] == 0:
  ans = 0
for i in range (n):
  ans *= a[i]
  if ans > 1e18:
    ans = -1
    break

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

import sys
input = sys.stdin.readline

N = int(input())
A = [int(input()) for _ in range(N)]

for i in range(N):
    a = A.copy()
    del a[i]
    print(max(a))

### FIXED CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]
a = sorted(A.copy())
a1 = a[len(A)-1]
a2 = a[len(A)-2]

for i in A:
    if i == a1:
        print(a2)
    else:
        print(a1)
### BUGGY CODE ###

from collections import Counter
N = input()
count=0
S=[0]
mod_count=[]
ans=0
for K in range(1,len(N)+1):
  S.append(int(N[-K:]))
for X in S:
  mod_val=(X % 2019)
  mod_count.append(str(mod_val))

c = Counter(mod_count)

for Y in c.values():
  ans+= Y*(Y-1)/2
print(int(ans))

### FIXED CODE ###

from collections import Counter
N = input()
S=0
mod_count=[0]
ans=0
i=0
for X in N[::-1]:
  S = int(X)*pow(10,i,2019) % 2019
  S=mod_count[i]+S
  mod_count.append(S%2019)
  i+=1

c = Counter(mod_count)
ans = sum(Y * (Y-1)/2 for Y in c.values())
print(int(ans))
### BUGGY CODE ###

def find_tree(v):
    for tree in forest:
        if v in tree:
            return tree

nv, ne = map(int, input().split(' '))
edges = []
for i in range(ne):
    s, t, w = map(int, input().split(' '))
    edges.append((s, t, w))

sum = 0
forest = [[v] for v in range(nv)]
edges.sort(key=lambda tup: tup[2])
for s, t, w in edges:
    u = find_tree(s)
    v = find_tree(t)
    if u != v:
        [u.append(i) for i in v]
        forest.remove(v)
        sum += w
    if len(forest) == 1:
        break

print(sum)
exit()

### FIXED CODE ###

def find(x):
    if parents[x] != x:
        parents[x] = find(parents[x])
    return parents[x]

nv, ne = map(int, input().split(' '))
parents = [i for i in range(nv)]
edges = []
for i in range(ne):
    s, t, w = map(int, input().split(' '))
    edges.append((s, t, w))

sum = 0
edges.sort(key=lambda tup: tup[2])
for s, t, w in edges:
    u = find(s)
    v = find(t)
    if u != v:
        parents[u] = v
        sum += w

print(sum)
### BUGGY CODE ###

import itertools

def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]

N = int(input())
S = [int(c) for c in input()]

a = [b for b in itertools.combinations(S, 3)]

print(len(get_unique_list(a))) 

### FIXED CODE ###

N = int(input())
S = [int(c) for c in input()]

count = 0

for i in range(10):
    if i in S[:N-2]:
        a = S.index(i)
        for j in range(10):
            if j in S[a+1:N-1]:
                b = S[a+1:N-1].index(j) +a+1
                for k in range(10):
                    if k in S[b+1:]:
                        count +=1
print(count)
### BUGGY CODE ###

L, R = [int(i) for i in(input().split(' '))]
minn=2019
for i in range(L,R):
    for j in range(i+1,R+1):
        mo = i*j
        amari = mo%2019
        minn = min(amari,minn)
        if minn==0:
          break
print(minn)

### FIXED CODE ###

L, R = [int(i) for i in(input().split(' '))]
minn=2019
if R-L+1>2019:
  print(0)
  exit()
for i in range(L,R):
    for j in range(i+1,R+1):
        mo = i*j
        amari = mo%2019
        minn = min(amari,minn)
        if minn==0:
          break
print(minn)
### BUGGY CODE ###

N,K = list(map(int,input().split(' ')))
pi = list(map(int,input().split(' ')))
candidate = [sum([(n+1)/2 for n in pi[i:K+i]]) for i in range(N-K+1)]
value = max(candidate)
print(value)

### FIXED CODE ###

N,K = list(map(int,input().split(' ')))
pi = list(map(int,input().split(' ')))
value = sum(pi[:K])
max_value = value
for i in range(N-K):
  value -= pi[i]
  value += pi[i+K]
  max_value = max(value, max_value)
print((max_value+K)/2)
### BUGGY CODE ###

m, n = map(int,input().split())
s = input()
dp = [1]*m
#print(s)
for i in range(n):
  t, d = map(str,input().split())
  for j in range(m):
    if s[j] == t and j == 0:
      if d == 'L':
        dp[j] = 0
      elif d == 'R':
        dp[j+1] += dp[j]
        dp[j] = 0
        #print(dp)
    elif s[j] == t and j == m-1:
      if d == 'R':
        dp[j] = 0
      elif d == 'L':
        dp[j-1] += dp[j]
        dp[j] = 0
        #print(dp)
    elif s[j] == t:
      if d == 'L':
        dp[j-1] += dp[j]
        dp[j] = 0
        #print(dp)
      elif d == 'R':
        dp[j+1] += dp[j]
        dp[j] = 0
        #print(dp)
#print(dp)
print(sum(dp))

### FIXED CODE ###

n, q = map(int,input().split())
s = "_" + input() + "_"
l, r = 0, n+1

for (t,d) in [input().split() for i in range(q)][::-1]:
  L = d == 'L'
  R = d == 'R'
  l += (t==s[l+1] and L) - (t==s[l] and R)
  r += (t==s[r] and L) - (t==s[r-1] and R)
print(r-l-1)
### BUGGY CODE ###

from collections import defaultdict
from heapq import heappop, heappush

class Graph(object):

    def __init__(self):
        self.graph = defaultdict(list)

    def add_edge(self, a, b, w):
        self.graph[a].append((b, w))


class Dijkstra(object):
    def __init__(self, graph, s):
        self.g = graph.graph
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[s] = 0

        self.Q = []
        heappush(self.Q, (self.dist[s], s))
        while self.Q:
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, w in self.g[u]:
                alt = dist_u + w
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    heappush(self.Q, (alt, v))

    def s_d(self, goal):
        return self.dist[goal]



xs, ys, xg, yg = list(map(int, input().split()))
xyr = []
xyr.append([xs, ys, 0])
N = int(input())

for i in range(N):
    xyr.append(list(map(int, input().split())))
xyr.append([xg, yg, 0])

g_a = Graph()
for i in range(N + 1):
    for j in range(i + 1, N + 2):
        a, b = i, j
        R = ((xyr[i][0] - xyr[j][0]) * (xyr[i][0] - xyr[j][0]) + (xyr[i][1] - xyr[j][1]) * (xyr[i][1] - xyr[j][1])) ** 0.5
        if R > xyr[i][2] + xyr[j][2]:
            r = R - xyr[i][2] - xyr[j][2]
        else:
            r = 0
        g_a.add_edge(a, b, r)
        g_a.add_edge(b, a, r)

d_a = Dijkstra(g_a, 0)
print(d_a.s_d(N + 1))

### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

class Graph(object):

    def __init__(self):
        self.graph = defaultdict(list)

    def add_edge(self, a, b, w):
        self.graph[a].append((b, w))


class Dijkstra(object):
    def __init__(self, graph, s):
        self.g = graph.graph
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[s] = 0

        self.Q = []
        heappush(self.Q, (self.dist[s], s))
        while self.Q:
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, w in self.g[u]:
                alt = dist_u + w
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    heappush(self.Q, (alt, v))

    def s_d(self, goal):
        return self.dist[goal]


xs, ys, xg, yg = list(map(int, input().split()))
xyr = []
xyr.append([xs, ys, 0])
N = int(input())

for i in range(N):
    xyr.append(list(map(int, input().split())))
xyr.append([xg, yg, 0])

g_a = Graph()
for i in range(N + 1):
    for j in range(i + 1, N + 2):
        R = ((xyr[i][0] - xyr[j][0]) * (xyr[i][0] - xyr[j][0]) + (xyr[i][1] - xyr[j][1]) * (xyr[i][1] - xyr[j][1]))
        R = R ** 0.5
        if R > xyr[i][2] + xyr[j][2]:
            r = R - xyr[i][2] - xyr[j][2]
        else:
            r = 0
        g_a.add_edge(i, j, r)
        g_a.add_edge(j, i, r)

d_a = Dijkstra(g_a, 0)
print(d_a.s_d(N + 1))
### BUGGY CODE ###

n, m = map(int, input().split())
 
a_list=[]
 
for index in range(m):
    a_list.append(int(input()))
 
ans_list=[]
 
for index in range(n + 1):
    ans_list.append(0)
 
for index in range(n + 1):
    if index == 0:
        ans_list[index] += 1
        continue
    if index == 1 and (index not in a_list):
        ans_list[index] += ans_list[index - 1]
        continue
    
    if index not in a_list:
        if (index - 1) not in a_list:
            ans_list[index] += ans_list[index - 1]
            ans_list[index] %= 1000000007
        if (index - 2) not in a_list:
            ans_list[index] += ans_list[index - 2]
            ans_list[index] %= 1000000007
 
print(ans_list[n])

### FIXED CODE ###

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

a_set=set()

for index in range(m):
    a_set.add(int(input()))

ans_list=[]

for index in range(n + 1):
    ans_list.append(0)

for index in range(n + 1):
    if index == 0:
        ans_list[index] += 1
        continue
    if index == 1 and (index not in a_set):
        ans_list[index] += ans_list[index - 1]
        continue
    
    if index not in a_set:
        if (index - 1) not in a_set:
            ans_list[index] += ans_list[index - 1]
            ans_list[index] %= 1000000007
        if (index - 2) not in a_set:
            ans_list[index] += ans_list[index - 2]
            ans_list[index] %= 1000000007

print(ans_list[n])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import Counter
# sys.setrecursionlimit(100000)
# input = sys.stdin.buffer.readline
INF = 2**62-1

def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(S):
    # 2019 = 3 * 673

    rl = Counter([0])
    ans = 0
    for c in S:
        n = int(c)
        nrl = Counter([0])
        for r, m in rl.items():
            r = (r * 10 + n) % 2019
            if r == 0:
                ans += m
            nrl[r] += m
        rl = nrl
        # print(rl)

    return ans


def main():
    S = read_str()
    print(slv(S))

    # import random
    # S = ''.join(map(str, random.choices(range(1, 10), k=2*10**5)))
    # print(slv(S))


if __name__ == '__main__':
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import Counter
# sys.setrecursionlimit(100000)
# input = sys.stdin.buffer.readline
INF = 2**62-1

def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(S):
    # 2019 = 3 * 673
    L = 2019
    rl = [0] * L
    rl[0] = 1
    ans = 0
    for c in S:
        n = int(c)
        nrl = [0] * L
        nrl[0] = 1
        for r in range(L):
            m = rl[r]
            r = (r * 10 + n) % 2019
            if r == 0:
                ans += m
            nrl[r] += m
        rl = nrl
        # print(rl)

    return ans


def main():
    S = read_str()
    print(slv(S))

    # import random
    # S = ''.join(map(str, random.choices(range(1, 10), k=2*10**5)))
    # print(slv(S))


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

N, K = map(int, input().split())
S = []

for _ in range(K):
  L, R = map(int, input().split())
  S.extend(range(L,R+1))

DP =[0]*N
DP[0] = 1

for i in range(1,N):
  for j in S:
    if i >= j:
      DP[i] += DP[i-j]
      
print(DP[-1]%998244353)

### FIXED CODE ###

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

L = []
R = []

for _ in range(K):
  l, r = map(int, input().split())
  L.append(l)
  R.append(r)
  
dp = [0]*(N+5)
dp[1] = 1

for i in range(2, N+1):
  dp[i] = dp[i-1]
  for j in range(K):
    if i-L[j] >= 0:
      dp[i] += dp[i-L[j]]
    if i-R[j]-1 >= 0:
      dp[i] -= dp[i-R[j]-1]
    dp[i] %= 998244353
    
print((dp[N]-dp[N-1])%998244353)