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

L, R = map(int, input().split())
res = 10 ** 15
for i in range(L, R):
    for j in reversed(range(i + 1, R + 1)):
        res = min((i % 2019) * (j % 2019) % 2019, res)

print(res)


### FIXED CODE ###

L, R = map(int, input().split())

if R - L > 2030:
    print(0)
else:
    res = 2018
    for i in range(L, R):
        for j in range(i + 1, R + 1):
            res = min(res, (i * j) % 2019)
    print(res)
### BUGGY CODE ###

def solve(s1, s2, s3, S):
	key = 0
	L = [s1, s2, s3]
	for i in range(len(S)):
		if S[i] == L[key]:
			key += 1
			if key == 3:
				return True
	return False


if __name__ == "__main__":
	N = int(input())
	S = input()
	ans = 0
	for s1 in range(0, 10):
		for s2 in range(0, 10):
			for s3 in range(0, 10):
				if solve(str(s1), str(s2), str(s3), S):
					# print(str(s1) + str(s2) + str(s3))
					ans += 1
	print(ans)

### FIXED CODE ###

import itertools

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

left_index = [[-1] * (N+1) for _ in range(10)]

for i,x in enumerate(S,1):
	for j in range(10):
		left_index[j][i] = left_index[j][i-1]
	left_index[x][i] = i


answer = 0
for a,b,c in itertools.product(range(10),repeat=3):
	i = N
	bl = True
	for x in [a,b,c]:
		i = left_index[x][i] - 1
		if i < -1:
			bl = False
			break
	if bl:
		answer += 1

print(answer)
### BUGGY CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
s_a=[0]
for i in a:
	s_a.append((s_a[-1]+i)%m)
res = 0
for i in range(m):
	c = s_a.count(i)
	res += c*(c-1)//2
print(res)

### FIXED CODE ###

from collections import defaultdict as dd
n,m = map(int,input().split())
a = list(map(int,input().split()))
a_s = [0]
for i in range(n):
    a_s.append((a_s[-1]+a[i])%m)
d = dd(int)
for i in a_s:
    d[i] += 1
res = 0
for k in d.values():
    if k>=2:
        res += k*(k-1)//2
print(int(res))
### BUGGY CODE ###

import os
import sys
from collections import defaultdict

from functools import lru_cache

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18

N, M = list(map(int, sys.stdin.readline().split()))
UV = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]
S, T = list(map(int, sys.stdin.readline().split()))

graph = defaultdict(set)
for u, v in UV:
    graph[u].add(v)


@lru_cache(maxsize=None)
def dest(v, count):
    if count <= 1:
        return graph[v]
    ret = set()
    for u in graph[v]:
        ret |= dest(u, count - 1)
    return ret


checked = set()
vs = {S}
i = 0
prev = 0
while True:
    i += 1
    s = set()
    for v in vs:
        if v not in checked:
            s |= dest(v, 3)
    checked |= vs
    if T in s:
        print(i)
        break
    if len(checked) == prev:
        print(-1)
        break
    vs = s
    prev = len(checked)


### FIXED CODE ###

import bisect
import heapq
import itertools
import math
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18

N, M = list(map(int, sys.stdin.readline().split()))
UV = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]
S, T = list(map(int, sys.stdin.readline().split()))

graph = [[] for _ in range(N + 1)]
for u, v in UV:
    graph[u].append(v)

que = deque()
que.append((S, 0))
reached = np.zeros((N + 1, 3), dtype=bool)
reached[S, 0] = True

while que:
    u, step = que.popleft()
    for v in graph[u]:
        s = step + 1
        if not reached[v, s % 3]:
            reached[v, s % 3] = True
            que.append((v, s))
        if v == T and s % 3 == 0:
            print(s // 3)
            exit()
print(-1)
### BUGGY CODE ###

def dfs(s, n):
    if s.find('WR') == -1:
        return n
    else:
        w_count = s.count('W')
        r_count = s.count('R')
        m = min(w_count, r_count)

        i, j = 0, -1
        while True:
            if s[j] == 'R':
                break
            else:
                j -= 1

        while True:
            if s[i] == 'W':
                break
            else:
                i += 1

        s = list(s)
        s[i] = 'R'
        s[j] = 'W'
        s = ''.join(s)
        return min(dfs(s, n+1), m)

N = int(input())
s = input()
print(dfs(s, 0))

### FIXED CODE ###

from collections import Counter
N = int(input())
s = input()
c = Counter(s)
w, r = 0, c['R']
ans = max(w, r)
for i in range(N):
    if s[i] == 'W': w += 1
    else: r -= 1 
    ans = min(ans, max(w, r))

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

s = input()
num = int(input())
for i in range(num):
    a = input().split(" ")
    if(a[0] == "1"):
        s = s[::-1]
    else:
        if(a[1] == "1"):
            s = a[2] + s
        else:
            s = s + a[2]

print(s)



### FIXED CODE ###

s = input()
b = ""
f = ""
change_flag = 1
for i in range(int(input())):
    a = input().split(" ")
    if(a[0] == "1"):
        change_flag *= -1
    else:
        if((a[1] == "1" and change_flag == 1) or (a[1] == "2" and change_flag == -1)):
            b = a[2] + b
        else:
            f = f + a[2]

if(change_flag == -1):
    print(f[::-1]+s[::-1]+b[::-1])
else:
    print(b+s+f)
### BUGGY CODE ###

n = int(input())

if n == 1:
  print(0)
elif n == 2:
  print(2)
else:
  sn = n*"9"
  count = 0
  for i in range(1,int(sn)+1):
    check = str(i).zfill(n)
    if "0" in check and "9" in check:
      count += 1
  print(count)

### FIXED CODE ###

n = int(input())
count = 10**n - 9**n - 9**n +8**n
print(count%(10**9+7))
### BUGGY CODE ###

# encoding: utf-8

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

def get_distance(s,H):
    distance=0

    for i in range(s,len(H)-1):
        if H[i+1] <= H[i]:
            distance += 1
        else:
            break
    
    return distance

ans = 0
i=0

while i < N:
    t = get_distance(i,H)
    if ans < t:
        ans = t
    i += 1

print(ans)

### FIXED CODE ###

# encoding: utf-8

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

def get_distance(s,H):
    distance=0

    for i in range(s,len(H)-1):
        if H[i+1] <= H[i]:
            distance += 1
        else:
            break
    
    return distance

ans = 0
i=0

while i < N:
    t = get_distance(i,H)
    if ans < t:
        ans = t
    i += t + 1

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

import sys

input = sys.stdin.readline

n = int(input())
graph = [[] for i in range(n + 1)]
cost = [[[] for i in range(n + 1)] for j in range(n + 1)]
for i in range(n - 1):
    u, v, w = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)
    cost[u][v] = w
    cost[v][u] = w
ans = [] * (n + 1)


def dfs(a):
    dist = [-1] * (n + 1)
    stack = [a]
    dist[a] = 0
    while stack:
        v = stack.pop()
        for w in graph[v]:
            if dist[w] == -1:
                dist[w] = (dist[v] + cost[w][v])%2
                stack.append(w)
            else:
                continue
    return dist


dist = dfs(1)
print(*dist[1:], sep="\n")


### FIXED CODE ###

import sys

input = sys.stdin.readline

n = int(input())
graph = [[] for i in range(n + 1)]
for i in range(n - 1):
    u, v, w = map(int, input().split())
    graph[u].append((v, w))
    graph[v].append((u, w))


def dfs(a):
    dist = [-1] * (n + 1)
    stack = [a]
    dist[a] = 0
    while stack:
        v = stack.pop()
        for b, w in graph[v]:
            if dist[b] == -1:
                dist[b] = (dist[v] + w) % 2
                stack.append(b)
            else:
                continue
    return dist


dist = dfs(1)
print(*dist[1:], sep="\n")
### BUGGY CODE ###

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

R,G,B = reversed([R,G,B])
r = 0
count = 0
r_max = N // R
g_max = N // G

while r <= r_max:
    
    g = 0
    while g <= g_max:
        b = (N-r*R-g*G)/B
        if b.is_integer() and b >= 0:
            count += 1

        g += 1
    
    r += 1

print(count)

### FIXED CODE ###

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

count = 0
for r in range(0,N+1,R):
    for g in range(r,N+1,G):
        b = (N-g)/B
        if b.is_integer() and b >= 0:
            count += 1

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

def ex(x):
    return (x+1)/2

n, k = map(int, input().split())
lst = list(map(int, input().split()))
source = [ex(i) for i in range(1, 1001)]
exlst = [source[l-1] for l in lst]
maxmum = -1
for i in range(n-k+1):
    val = sum(exlst[i:i+k])
    if val > maxmum:
        maxmum = val
print(maxmum)

### FIXED CODE ###

def ex(x):
    return (x+1)/2
 
n, k = map(int, input().split())
lst = list(map(int, input().split()))
source = [ex(i) for i in range(1, 1001)]
exlst = [source[l-1] for l in lst]
maxmum = -1

cumulative = [0]
total = 0
for ex in exlst:
    total += ex
    cumulative.append(total)

maxmum = -1
for i in range(n-k+1):
    sum_ = cumulative[i+k] - cumulative[i]
    if sum_ > maxmum:
        maxmum = sum_
print(maxmum)
### BUGGY CODE ###

n, k = map(int, input().split())
 
p = list(map(int, input().split()))
s_max = 0
 
p = [(e+1) / 2 for e in p]
 
for i in range(n-k+1):
  s = sum(p[i:i+k])
  if s_max < s:
    s_max = s
    
print(s_max)

### FIXED CODE ###

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

m = [(e + 1) / 2 for e in p]

t = sum(m[0:K])
result = t
for i in range(N - K):
    t -= m[i]
    t += m[i + K]
    if t > result:
        result = t
print(result)
### BUGGY CODE ###

from math import ceil

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

m = 10**6+100
n_map = {}
v_a = []
nn_map = {}
for i in a:
    if i not in n_map:
        n_map[i] = 1
    else:
        n_map[i] += 1
    if i in nn_map:
        continue
    for j in range(2, ceil(m / i) + 1):
        nn_map[i * j] = True


res = 0
for k, v in n_map.items():
    if v != 1:
        continue
    if k in nn_map:
        continue
    res += 1

print(res)

### FIXED CODE ###

from math import ceil

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

m = 10 ** 6
n_map = {}
v_a = []
for i in a:
    if i not in n_map:
        n_map[i] = 1
    else:
        n_map[i] += 1
v_a = [(k,v) for k, v in n_map.items()]

v_a.sort(key=lambda x: x[0])
res = 0
nn_map = {}
for i, v in v_a:
    if i in nn_map:
        continue
    for j in range(1, ceil(m / i) + 1):
        nn_map[i * j] = True
    if v == 1:
        res += 1
print(res)
### BUGGY CODE ###

N = int(input())

L = list(list(map(int,input().split())) for i in range(N))
#print(L)
turn = "taka"
takapoint = 0
aokipoint = 0

while len(L) :
    if turn == "taka" :
        L = sorted(L,key=lambda x: x[1],reverse=True)
        L = sorted(L,key=lambda x: x[0],reverse=True)
        takapoint += L[0][0]
        L.pop(0)
        turn = "aoki"
    else :
        L = sorted(L,key=lambda x: x[0],reverse=True)
        L = sorted(L,key=lambda x: x[1],reverse=True)
        aokipoint += L[0][1]
        L.pop(0)
        turn = "taka"
ans = takapoint - aokipoint

print(ans)


### FIXED CODE ###

N = int(input())
L = []
ans = 0
for i in range(N) :
    a,b = map(int,input().split())
    L.append([a,b,a+b])
L = sorted(L,key=lambda x:x[2],reverse=True)
takapoint = 0
aokipoint = 0
for i in range(N) :
    if i % 2 == 0 :
        takapoint += L[i][0]
    else :
        aokipoint += L[i][1]
ans = takapoint - aokipoint
print(ans)
### BUGGY CODE ###

S=int(input())
X1=0
Y1=0

if S<=10**9:
    X2=0
    Y2=1
    X3=S
    Y3=0
elif S%10**9==0:
    X2=0
    Y2=S//10**9
    X3=10**9
    Y3=0
else:
    t=S%(10**9)
    A=10**9-t#x2 , y3
    v=(S+A)//10**9#x3=10**9 , y2=v

    K=A
    while A%2==0:
        A//=2
        if A<=10**9:
            X2=K//A
            Y3=A
        
    i=3
    while True:
        if A%i==0:
            A//=i
            if A<=10**9:
                X2=K//A
                Y3=A
                break
        else:
            i+=2

    X3=10**9
    Y2=v
    
L=[X1,Y1,X2,Y2,X3,Y3]
print(" ".join([str(x) for x in L]))


### FIXED CODE ###

S=int(input())
X1=0
Y1=0
flag=True
if S<=10**9:
    X2=0
    Y2=1
    X3=S
    Y3=0
elif S%10**9==0:
    X2=0
    Y2=S//10**9
    X3=10**9
    Y3=0
else:
    t=S%(10**9)
    A=10**9-t#x2 , y3
    v=(S+A)//10**9#x3=10**9 , y2=v
    
    K=A
    if A<=10**9:
        X2=1
        Y3=A
        flag=False
        
    if flag:
        while A%2==0:
            A//=2
            if A<=10**9:
                X2=K//A
                Y3=A
            
        i=3
        while True:
            if A%i==0:
                A//=i
                if A<=10**9:
                    X2=K//A
                    Y3=A
                    break
                
            else:
                i+=2
    
    X3=10**9
    Y2=v
    
L=[X1,Y1,X2,Y2,X3,Y3]
print(" ".join([str(x) for x in L]))
### BUGGY CODE ###

import copy
N = int(input())
numList = list(map(int, input().split()))

for i in range(0,N):
	numListCopy = copy.deepcopy(numList)
	numListCopy.pop(i)
	numListCopy.sort()
	medIndex = int(len(numListCopy)/2)
	print(numListCopy[medIndex])

### FIXED CODE ###

import copy
N = int(input())
numList = list(map(int, input().split()))
numListCopy = copy.deepcopy(numList)
numList = sorted(numList)
medIndex = int((N)/2)
med1 = numList[medIndex-1]
med2 = numList[medIndex]


for i in range(0,N):
	if numListCopy[i] <= med1:
		print(med2)
	elif med2 <= numListCopy[i]:
		print(med1)
### BUGGY CODE ###

import bisect
import collections

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

s.sort()

while len(s) > 1:#最も体力のあるのが攻撃を受ける
    temp = s.pop()
    for j in s:
        temp -= (temp//j)*j
    if temp != 0:
        index = bisect.bisect_left(s,temp)
        s.insert(index,temp)

print(s[0])





### FIXED CODE ###

import math

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

tmp = a[0]
for i in range(1,len(a)):
    tmp = math.gcd(tmp,a[i])
print(tmp)
### BUGGY CODE ###

n, m = map(int, input().split())
a = []
b = []
al = []
ans = 0
for i in range(n):
    al.append(list(map(int, input().split())))

for i in range(n):
    a.append(al[i][0])
    b.append(al[i][1])

while(m):
    if len(a) > 1:
        ind = a.index(min(a))
    else:
        ind = 0
    while(b[ind]):
        b[ind] -= 1
        ans += min(a)
        m -= 1
        if (b[ind] == 0):
            a[ind] = 1000000000
            if len(a) > 1:
                ind = a.index(min(a))
            else:
                ind = 0
        if (m == 0):
            break
print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
ab = sorted([list(map(int,input().split()))for i in range(n)],key=lambda x:x[0])
ans = 0
i = 0
while m-ab[i][1]>0:
    m -= ab[i][1]
    ans += ab[i][0]*ab[i][1]
    i += 1
ans += ab[i][0] * m
print(ans)
### BUGGY CODE ###

import sys
import heapq


def dfs(u,s,target, vs):
    vs[u] = 1
    if(u == target):
        global h
        heapq.heappush(h,s)
        return
    for j in range(e):
        if(e_1[j] == u):
            if(vs[e_2[j]] != 1):
                count = s + e_w[j]
                print(s,e_2[j],vs)
                dfs(e_2[j],count,target,vs[0:])

def dijsktra(start, v, e):
    d = [0]*v
    prev = [0]*v
    v_q=[];

    INF = 9999999999999999999
    for u in range(v):
        if(u != start):
            d[u] = INF
        else:
            d[u] = 0 
        prev[u] = -1

    heapq.heappush(v_q,(0,start))
    heapq.heappush(v_q,(INF,0))
    

    while(True):
        cost,u = heapq.heappop(v_q)
        if(cost == INF):
            break
        if(cost > d[u]):
            continue
        for j in range(e):
            if(u == e_1[j]):
                alt = d[u]+e_w[j]
                if(d[e_2[j]] > alt):
                    d[e_2[j]] = alt
                    prev[e_2[j]] = u
                    heapq.heappush(v_q,(alt,e_2[j]))
    for i in range(v):
        if(d[i] != INF):
            print(d[i])
        else:
            print("INF")

v,e,r=map(int, input().split());

e_1=[0]*e;
e_2=[0]*e;
e_w=[0]*e;

for i in range(e):
    e_1[i], e_2[i], e_w[i] = map(int, input().split());

dijsktra(r,v,e)



### FIXED CODE ###

import sys
from collections import deque

v,e,r=map(int, input().split());

edge_info=[0]*v;
for i in range(v):
    edge_info[i] = []

for i in range(e):
    e1, e2, w = map(int, input().split());
    edge_info[e1].append((e2,w))

v_q=deque();

INF = 9999999999999999999
d = [INF for i in range(v)]
d[r] = 0
v_q.append((0,r))
while(len(v_q) != 0):
    cost,u = v_q.popleft()
    if(cost > d[u]):
        continue
    for j in range(len(edge_info[u])):
        e2,w = edge_info[u][j]
        alt = cost+w
        if(d[e2] > alt):
            d[e2] = alt
            v_q.append((alt,e2))

for i in range(v):
    if(d[i] != INF):
        print(d[i])
    else:
        print("INF")
### BUGGY CODE ###

n, y = map(int,input().split())
ans = 0
for a in range(0, y//10000+1):
    if ans == 0:
        for b in range(0, y//5000+1):
            if ans == 0:
                for c in range(0, y//1000+1):
                    if a+b+c==n and 10000*a + 5000*b + 1000*c == y:
                        print(a, b, c)
                        ans = 1
                        break
    else:
        break
if ans == 0:
    print(-1, -1, -1)


### FIXED CODE ###

n, y = map(int,input().split())
ans = 0
for a in range(0, n+1):
    for b in range(0, n+1):
        c = n - a - b
        if 10000*a + 5000*b + 1000*c == y and c >= 0 and ans ==0:
            print(a, b, c)
            ans = 1
if ans == 0:
    print(-1, -1, -1)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 5+1)


def dfs(p):
    for edge in G[p]:
        if X[edge[0]] is not None:
            if X[edge[0]] - X[p] != edge[1]:
                print('No')
                exit()
        else:
            X[edge[0]] = X[p] + edge[1]
            dfs(edge[0])


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

for i in range(M):
    L, R, D = map(int, input().split())
    L -= 1
    R -= 1
    G[L].append((R, D))
    G[R].append((L, -D))

X = [None] * N
for i in range(N):
    if X[i] is None:
        X[i] = 0
        dfs(i)

print('Yes')


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 5+1)


def dfs(p):
    for edge in G[p]:
        if X[edge[0]] is not None:
            if X[edge[0]] - X[p] != edge[1]:
                print('No')
                exit()
        else:
            X[edge[0]] = X[p] + edge[1]
            dfs(edge[0])


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

for i in range(M):
    L, R, D = map(int, input().split())
    L -= 1
    R -= 1
    G[L].append((R, D))
    G[R].append((L, -D))

X = [None] * N
for i in range(N):
    if X[i] is None:
        X[i] = 0
        dfs(i)

print('Yes')
### BUGGY CODE ###

n,w=map(int,input().split())
we=[]
va=[]
for j in range(n):
    w1,v=map(int,input().split())
    we.append(w1)
    va.append(v)
dp=[[ 0 for _ in range(w+1)]for _ in range(n+1)]
for i in range(n+1):
    for j in range(w+1):
        if i==0 or j==0:
            dp[i][j]=0
        else:
            if j>=we[i-1]:
                dp[i][j]=max(va[i-1]+dp[i-1][j-we[i-1]],dp[i-1][j])
            else:
                dp[i][j]=dp[i-1][j]
print(dp[n][w])

### FIXED CODE ###

n,w=map(int,input().split())
val=[]
we=[]
for i in range(n):
  a,b=map(int,input().split())
  we.append(a)
  val.append(b)
dp=[[0 for _ in range(w+1)]for _ in range(n+1)]
for i in range(n+1):
  for j in range(w+1):
    if i==0 or j==0:
      continue
    if we[i-1]>j:
      dp[i][j]=dp[i-1][j]
    else:
      dp[i][j]=max(dp[i-1][j],val[i-1]+dp[i-1][j-we[i-1]])
print(dp[n][w])
### BUGGY CODE ###

S = input()
count = 0
while True:
    tmp = S.count('BW')
    if tmp == 0:
        break
    count += tmp
    S = S.replace('BW','WB')
print(count)

### FIXED CODE ###

S = input()
ans = 0
wcount = 0
for i in range(len(S)):
    if S[i] == 'W':
        ans += i-wcount
        wcount += 1
print(ans)
### BUGGY CODE ###

import collections
n = int(input())
l = list(map(int, input().split()))
a = int(input())
c = collections.Counter(l)
for i in range(a):
    j,k =  map(int, input().split())
    save = c[j]
    del c[j]
    c[k] += save
    answer = 0
    for q,r in c.items():
        answer += int(q)*int(r)
    print(answer)


### FIXED CODE ###

import collections
n = int(input())
l = list(map(int, input().split()))
a = int(input())
c = collections.Counter(l)
answer = sum(l)
for i in range(a):
    j,k =  map(int, input().split())
    save = c[j]
    del c[j]
    c[k] += save
    answer = answer + k*save - j*save
    print(answer)
### BUGGY CODE ###

K = str(input())
D = int(input())

N = len(K)

MOD = 10 ** 9 + 7

# if D == 1:
#     print (K)
#     exit()
# elif D == 2:
#     print (int(K) // 2)
#     exit()
# elif D == 5:
#     print (int(K) // 5)

dp0 = [[0] * D for _ in range(N + 1)]
dp1 = [0] * (N + 1)

for i in range(N):
    next_ = int(K[i])
    tmp = dp1[i]

    dp1[i + 1] = (tmp + next_) % D
    
    for j in range(next_):
        dp0[i + 1][(tmp + j) % D] += 1
    # print (dp0[i + 1])
    for j in range(D):
        for k in range(10):
            dp0[i + 1][(j + k) % D] += dp0[i][j]
    
    for j in range(D):
        dp0[i + 1][j] %= MOD


# for tmp in dp0:
#     print (tmp)

# print (dp1)


ans = dp0[N][0] - 1
if dp1[N] == 0:
    ans += 1

print (ans % MOD)

### FIXED CODE ###

K = str(input())
D = int(input())

N = len(K)

MOD = 10 ** 9 + 7

# if D == 1:
#     print (K)
#     exit()
# elif D == 2:
#     print (int(K) // 2)
#     exit()
# elif D == 5:
#     print (int(K) // 5)

dp0 = [[0] * D for _ in range(N + 1)]
dp1 = [0] * (N + 1)

for i in range(N):
    next_ = int(K[i])
    tmp = dp1[i]

    dp1[i + 1] = (tmp + next_) % D
    
    for j in range(next_):
        dp0[i + 1][(tmp + j) % D] += 1
    # print (dp0[i + 1])
    for j in range(D):
        for k in range(10):
            dp0[i + 1][(j + k) % D] += dp0[i][j]
    
    for j in range(D):
        dp0[i + 1][j] %= MOD


# for tmp in dp0:
#     print (tmp)

# print (dp1)


ans = dp0[N][0] - 1
if dp1[N] == 0:
    ans += 1

print (ans % MOD)
### BUGGY CODE ###

N = int(input())
L = [input()]

for _ in range(N-1):
    a = input()
    imin = 0
    imax = len(L)-1
    l = 0

    while (imin<imax):
        l = (imin+imax)//2
        if (a==L[l]):
            break
        elif (a>L[l]):
            imin = min(l+1,len(L)-1)
        else:
            imax = max(l-1,0)    
    l = (imin+imax)//2       
    if (a>L[l]):
        L.insert(l+1,a)
    elif (a<L[l]):
        L.insert(l,a)
            
print(len(L))

### FIXED CODE ###

N = int(input())
L = set([input() for _ in range(N)])
print(len(L))
### BUGGY CODE ###

s = list(input())
idx = ['s', 'e']
for i in range(len(s)):
    if s[i] == 'A':
        idx[0] = i
        break
for i in range(len(s)):
    if s[::-1][i] == 'Z':
        idx[1] = -i
        break
if idx[1] == 0:
    print(len(s[idx[0]:]))
else:
    print(len(s[idx[0]:idx[1]]))

### FIXED CODE ###

s = str(input())
print(s.rfind('Z') - s.find('A') + 1)
### BUGGY CODE ###

import sys
input=sys.stdin.buffer.readline
sys.setrecursionlimit(10**9)
n,q=map(int,input().split())
cnt=[0]*n
used=[0]*n
edges=[0]*n
for i in range(n):
    edges[i]=[]
for i in range(n-1):
    a,s=map(int,input().split())
    edges[a-1].append(s-1);edges[s-1].append(a-1)

def f(now):
    for to in  edges[now]:
        if used[to]:continue
        cnt[to]+=cnt[now]
        used[to]=1
        f(to)
for i in range(q):
    p,x=map(int,input().split())
    cnt[p-1]+=x

used[0]=1
f(0)
print(*cnt)

### FIXED CODE ###

import sys
input=sys.stdin.buffer.readline
sys.setrecursionlimit(10**9)
n,q=map(int,input().split())
cnt=[0]*(n)
edges=[0]*n
for i in range(n):
    edges[i]=[]
for i in range(n-1):
    a,s=map(int,input().split())
    edges[a-1].append(s-1);edges[s-1].append(a-1)

from collections import deque
dq=deque([])
#pop/append/(append,pop)_left/in/len/count/[]/index/rotate()(右へnずらす)
for i in range(q):
    p,x=map(int,input().split())
    cnt[p-1]+=x

for i in edges[0]:
    dq.append((0,i))
while dq:
    f,t=dq.popleft()
    cnt[t]+=cnt[f]
    for to in edges[t]:
        if to!=f:dq.append((t,to))
    
print(*cnt)