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

maps = [s for s in str(input())]
people = [{'pos': i, 'prev': -1, 'loop': -1} for i in range(len(maps))]
max_count = 10**100


def update(people, index):
    for p in people:
        if maps[p['pos']] == 'R':
            if p['prev'] == p['pos'] + 1:
                p['loop'] = index
            p['prev'] = p['pos']
            p['pos'] += 1
        else:
            if p['prev'] == p['pos'] - 1:
                p['loop'] = index
            p['prev'] = p['pos']
            p['pos'] -= 1


def get_output(people):
    output = [0] * len(people)

    for p in people:
        output[p['pos']] += 1

    return ' '.join(str(i) for i in output)


for index in range(max_count):
    # print(index, 'before', get_output(people))
    update(people, index)
    # print(index, 'after', get_output(people))

    if len([p for p in people if p['loop'] < 0]) == 0:
        # print(get_output(people))
        for p in people:
            mod = (max_count - p['loop'] + 1) % 2
            # print(mod)
            for i in range(mod):
                if maps[p['pos']] == 'R':
                    p['prev'] = p['pos']
                    p['pos'] += 1
                else:
                    p['prev'] = p['pos']
                    p['pos'] -= 1
        # print(get_output(people))
        break

print(get_output(people))


### FIXED CODE ###

maps = input()
people = [0] * len(maps)

counter = 0
for i in range(len(maps)):
    if maps[i] == 'R':
        counter += 1
        if maps[i+1] == 'L':
            people[i] += (counter+1) // 2
            people[i+1] += counter // 2
    else:
        counter = 0

counter = 0
for i in range(len(maps) - 1, 0, -1):
    if maps[i] == 'L':
        counter += 1
        if maps[i-1] == 'R':
            people[i] += (counter+1) // 2
            people[i-1] += counter // 2
    else:
        counter = 0

print(*people)
### BUGGY CODE ###

def main():
    A,B,K=map(int, input().split())
    if A + B <= K:
        print('0 0')
        return
    for _ in range(K):
        if A >= 1:
            A -= 1
        else:
            if B >= 1:
                B -= 1
    print(A,B)
main()

### FIXED CODE ###


A,B,K=map(int, input().split())

if A >= K:
    print(f'{A-K} {B}')
elif (A+B) >= K:
    print(f'0 {B-(K-A)}')
else:
    print('0 0')
### BUGGY CODE ###

from sys import exit, stderr, stdin
input = stdin.readline
import heapq
from collections import defaultdict
# setrecursionlimit(10**7)

def debug(var, name="hoge"):
    print(name +":" + str(type(var)) + " = " + repr(var), file=stderr)
    return


def main():
    N,M = [int(n) for n in input().split()]
    # {期限:価値}
    jobs = defaultdict(list)
    v = 0
    for i in range(N):
        a,b = [int(n) for n in input().split()]
        if a <= M:
            jobs[a].append(-b)
    cand = []
    ans = 0
    for i in range(1,M+1):
        if i in jobs:
            cand += jobs[i]
        # debug(cand,"cand")
        heapq.heapify(cand)
        if len(cand) != 0:
            ans -= cand[0]
            heapq.heappop(cand)
    print(ans)



if __name__ == "__main__":
    main()


### FIXED CODE ###

from sys import exit, stderr, stdin
input = stdin.readline
import heapq
# from collections import defaultdict
# setrecursionlimit(10**7)

def debug(var, name="hoge"):
    print(name +":" + str(type(var)) + " = " + repr(var), file=stderr)
    return


def main():
    N,M = [int(n) for n in input().split()]
    # {期限:価値}
    jobs = [[]]*N
    v = 0
    for i in range(N):
        jobs[i] = [int(n) for n in input().split()]
    # 価値降順→期間昇順
    jobs = sorted(jobs,key=lambda x:-x[1])
    jobs = sorted(jobs,key=lambda x:x[0])
    cur = 0
    ans = 0
    cand = []
    for i in range(1,M+1):
        while(cur < N and i >= jobs[cur][0]):
            heapq.heappush(cand,-jobs[cur][1])
            cur += 1
        if len(cand) != 0:
            ans -= cand[0]
            heapq.heappop(cand)
    print(ans)



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

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

print(ans)

### FIXED CODE ###

def max(a,b):
    if a > b:
        return a
    else:
        return b
n, k = [int(i) for i in input().split()]
ans = 0


for b in range(1,n+1):
    p = n // b
    r = n % b
    ans += p * max(0,b-k)+max(0,r-k+1)
if k == 0:
    ans -= n
    
print(ans)
### BUGGY CODE ###

L,R= [int(i) for i in input().split()]
n=[]
for i in range(R-L+1):	
	for j in range(i+1,R-L+1):
		n.append((L+i)*(L+j)%2019)
print(min(n))


### FIXED CODE ###

L,R= [int(i) for i in input().split()]
n=[]
for i in range(R-L+1):	
	for j in range(i+1,R-L+1):
		a = ((L+i)*(L+j))%2019
		if a == 0:
			print(0)
			exit()
		else: 
			n.append(((L+i)*(L+j))%2019)
print(min(n))
### BUGGY CODE ###

import re
import sys


input = sys.stdin.readline

n, q = [int(i) for i in input().strip().split()]
s = input().strip()
for i in range(q):
    l, r = [int(i) for i in input().strip().split()]
    l -= 1
    substr = s[l:r]
    print(len(re.findall(r"AC", substr)))


### FIXED CODE ###

n, q = [int(i) for i in input().split()]
s = input()

count = [0] * (n + 1)
for i in range(n):
    count[i+1] += count[i]
    if s[i:i+2] == "AC":
        count[i+1] += 1
for i in range(q):
    l, r = [int(i) for i in input().split()]
    print(count[r-1] - count[l-1])
### BUGGY CODE ###

INF = 10**9

N, M, R = list(map(int, input().split()))
r = list(map(int, input().split()))
X = [list(map(int, input().split())) for _ in range(M)]
W = [[INF for _ in range(N+1)] for __ in range(N+1)]

for i in range(1, N+1):

     W[i][i] = 0

for x in X:
     A, B, C = x
     W[A][B] = C
     W[B][A] = C

for k in range(1, N+1):
     for j in range(1, N+1):
         if W[k][j] >= INF:
             continue
         for i in range(j, N+1):
             W[i][j] = min(W[i][j], W[i][k]+W[k][j])
             W[j][i] = W[i][j]

from itertools import permutations

ans = INF
for r_ in permutations(r):
    count = 0
    for i in range(R-1):
        x = W[r_[i]][r_[i+1]]
        if x >= INF:
            break
        count += x
        if count >= ans:
            break
    else:
        ans = count
print(ans)

### FIXED CODE ###

INF = 10**9

N, M, R = list(map(int, input().split()))
r = list(map(int, input().split()))
W = [[INF for _ in range(N+1)] for __ in range(N+1)]
for i in range(1, N+1):
    W[i][i] = 0

for _ in range(M):
    A, B, C = list(map(int, input().split()))
    W[A][B] = C
    W[B][A] = C

import heapq

for i in range(1, N+1):
    heap = []
    checked = [False for _ in range(N+1)]
    for j in range(1, i+1):
        heapq.heappush(heap, (W[i][j], j))
    while len(heap) > 0:
        wij, j = heapq.heappop(heap)
        if checked[j]:
            continue
        for k in range(i+1, N+1):
            wik = wij + W[j][k]
            if wik <= W[i][k]:
                W[i][k] = wik
                W[k][i] = wik
                heapq.heappush(heap, (wik, k))
        checked[j] = True

from itertools import permutations

ans = INF
for r_ in permutations(r):
    count = 0
    for i in range(R-1):
        x = W[r_[i]][r_[i+1]]
        if x >= INF:
            break
        count += x
        if count >= ans:
            break
    else:
        ans = count
print(ans)
### BUGGY CODE ###

import sys

input_int = lambda:int(input())
input_ints = lambda:map(int,input().split())
input_ints_list = lambda:list(input_ints())
input_str = lambda:input()
input_strs = lambda:input().split()
input_lines = lambda n,f:[f() for _ in range(n)]

import functools,fractions
gcd = lambda a:functools.reduce(fractions.gcd,a) # 最大公約数（リスト）
lcm_base = lambda a,b:(a*b)//fractions.gcd(a,b) # 最小公倍数(2値)
lcm = lambda a:functools.reduce(lcm_base,a,1) # 最小公倍数(リスト)

init_dp = lambda v,n:[v]*(n)

import math
# 四捨五入はround
ceil = lambda a:math.ceil(a) # 切り上げ
floor = lambda a:math.floor(a) # 切り捨て

def dfs(i,N):
    s = str(i)
    if i > N:return 0
    ans = dfs(i+1,N)
    if all(c in s for c in '753') and all(c in '753' for c in s):
        ans += 1
    return ans

def solution():
    N = input_int()
    sys.setrecursionlimit(N+10)
    ans = dfs(100,N)
    print(ans)

if __name__ == '__main__':
    solution()

### FIXED CODE ###

import itertools

n = int(input())

count = 0
for i in range(3, 11):
    for itr in itertools.product('357', repeat=i):
        if '3' not in itr or '5' not in itr or '7' not in itr:
            continue
        value = 0
        for j in range(i):
            value += int(itr[j])*10**j
        if value <= n:
            count += 1
print(count)
### BUGGY CODE ###

s = list(input())
q = int(input())
for i in range(1,q+1):
  queue = list(input().split())
  if len(queue) == 1:
    s.reverse()
  else:
    if queue[1] == '1':
      s.insert(0,queue[2])
    else:
      s.append(queue[2])
print(''.join(s))

### FIXED CODE ###

from collections import deque
S=deque(input())
Q=int(input())
ref=0
for i in range(Q):
    T=input().split()
    if T[0] == '2':
        if (T[1]=='1' and ref%2==0):
            S.appendleft(T[2])
        elif (T[1]=='2' and ref%2==0):
            S.append(T[2])
        elif (T[1]=='1' and ref%2==1):
            S.append(T[2])
        elif (T[1]=='2' and ref%2==1):
            S.appendleft(T[2])
    else:
        ref+=1
for i in range(len(S)):
    if ref%2==0:
        char=S.popleft()
        print(char,end='')
    else:
        char=S.pop()
        print(char,end='')
### BUGGY CODE ###

N = int(input())
L = [input() for i in range(N)]
ans = {}
for i in range(len(L)):
    a = L[i]
    if a in ans:
        ans[a] += 1
    else:
        ans[a] = 1

ans2 = [k for k, v in ans.items() if v == max(ans.values())]
ans2.sort()
[print(i) for i in ans2]


### FIXED CODE ###

N = int(input())
ans = {}
for i in range(N):
    a = input()
    ans[a] = ans.get(a,0) + 1

t = max(ans.values())
ans2 = [k for k, v in ans.items() if v ==t ]
ans2.sort()
[print(i) for i in ans2]
### BUGGY CODE ###

k,s = map(int,input().split())
cnt = 0
for x in range(k+1):
    for y in range(x,k+1):
        for z in range(y,k+1):
            if x+y+z == s:
                if x==y==z:
                    cnt+=1
                elif (x==y and x!=z) or (x!=y and x==z) or (x!=y and y==z):
                    cnt+=3
                else:
                    cnt+=6
print(cnt)

### FIXED CODE ###

k, s = map(int, input().split())
c = 0

for i in range(k+1):
    for j in range(k+1):
        z = s - i - j
        if z >= 0 and z <= k:
            c += 1
print(c)
### BUGGY CODE ###

N = int(input())
ans = N-1
fi = (N)//2
for i in range(1,fi):
    if N%i==0:
        a= N//i
        tmp = (i-1)+(a-1)
        if ans > tmp:
            ans =tmp
print(ans)


### FIXED CODE ###

import math
N = int(input())
ans = N-1
n = math.sqrt(N)
n = int(n)+1
for i in range(1, n):
    if N%i==0:
        tmp = N//i
        ans = (tmp-1)+(i-1)

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

def main():
    N = int(input())
    A = [int(v) for v in input().split()]
    C = [0] * (N + 1)

    for i in A:
        C[i] += 1


    for i in range(N):
        C[A[i]] -= 1
        ans = 0
        for cnt in C:
            ans +=  (cnt * (cnt - 1)) >> 1

        C[A[i]] += 1
        print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N = int(input())
    A = [int(v) for v in input().split()]
    C = [0] * (N + 1)

    for i in A:
        C[i] += 1

    b = 0
    
    for cnt in C:
        b += ((cnt * (cnt - 1)) // 2)

    for i in range(N):
        p = ((C[A[i]] - 1) * (C[A[i]] - 2)) >> 1
        m = (C[A[i]] * (C[A[i]] - 1)) >> 1
        print(b - m + p)


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

N, S=list(map(int,input().split()))
A=list(map(int,input().split()))
A=[0]+A
dp=[[0 for j in range(S+1)] for i in range(N+1)]
dp[0][0]=1
for i in range(1,N+1):
    for j in range(S+1):
        dp[i][j]=(dp[i][j]+2*dp[i-1][j]) %998244353 # x[i]を入れないが、大きい方に入れるか入れないかが二通り
    for j in range(S-A[i]+1):
        dp[i][j+A[i]]=(dp[i][j+A[i]]+dp[i-1][j]) %998244353 # x[i]を入れる
print(dp[N][S])

### FIXED CODE ###

N, S=list(map(int,input().split()))
A=list(map(int,input().split()))
A=[0]+A
dp=[[0 for j in range(S+1)] for i in range(N+1)]
dp[0][0]=1
for i in range(1,N+1):
    for j in range(S+1):
        dp[i][j]=(dp[i][j]+2*dp[i-1][j]) %998244353 # x[i]を入れないが、大きい方に入れるか入れないかが二通り
    for j in range(S-A[i]+1):
        dp[i][j+A[i]]=(dp[i][j+A[i]]+dp[i-1][j]) %998244353 # x[i]を入れる
print(dp[N][S])
### BUGGY CODE ###

def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    n = int(input())
    A = list(map(int, input().split()))
    q = int(input())
    import numpy as np
    A.sort()
    ans = sum(A)
    from bisect import bisect_left,bisect_right

    for i in range(q):
        b,c = map(int, input().split())
        insert = bisect_left(A,c)
        start = bisect_left(A,b)
        end = bisect_right(A,b)
        A = A[:insert] + [c]*(end-start) + A[insert:]
        if b > c:
            A = A[:end] + A[2*end-start:]
        else:
            A = A[:start] + A[end:]
        ans += (c-b)* (end-start)
        print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    n = int(input())
    A = list(map(int, input().split()))
    q = int(input())
    import numpy as np
    A.sort()
    ans = sum(A)
    from bisect import bisect_left,bisect_right
    from collections import Counter
    count = Counter(A)
    for i in range(q):
        b,c = map(int, input().split())
        k = count[b]
        if k != 0:
            count[c] += count.pop(b)
        ans += (c-b)* k
        print(ans)


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

N, M = list(map(int, input().split()))
A = list([0] * N)   # A yen
B = list([0] * N)   # B hon
for i in range(N):
    A[i], B[i] = list(map(int, input().split()))

require = M
price = 0
while(require > 0):
#    print("require = {}, price = {}".format(require, price))
    minidx = A.index(min(A))
#    print("found idx = " + str(minidx))
    a = A.pop(minidx)
    b = B.pop(minidx)
    if(require >= b):
#        print("buy = {}, price = {}".format(b, a))
        price = price + a * b
        require = require - b
    else:
#        print("buy = {}, price = {}".format(require, A[minidx]))
        price = price + a * require
        require = 0

print(price)


### FIXED CODE ###

YEN = 0
NUM = 1

N, M = list(map(int, input().split()))
shop = list([])
for i in range(N):
    a, b = list(map(int, input().split()))
    shop.append([a, b])
shop.sort()

require = M
price = 0
minidx = 0
while(require > 0):
#    print("require = {}, price = {}".format(require, price))
#    print("idx = {}, num = {}, price = {}".format(minidx, shop[minidx][NUM], shop[minidx][YEN]))
    if(require >= shop[minidx][NUM]):
        price = price + shop[minidx][YEN] * shop[minidx][NUM]
        require = require - shop[minidx][NUM]
        minidx = minidx + 1
    else:
#        print("buy = {}, price = {}".format(require, A[minidx]))
        price = price + shop[minidx][YEN] * require
        require = 0

print(price)
### BUGGY CODE ###

import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 累積和、dp、しゃくとり
MOD = 998244353
N, S = lr()
A = lr()
# dp[k][j] kから始めた合計の個数
dp = np.array([[0] * (S+1) for _ in range(N)])
dp[:, 0] = 1
answer = 0
cur = [0] * (N)
#print(dp)
for i, a in enumerate(A):
    # iが現在地
    for j in range(i+1):
        prev = dp[j].copy()
        dp[j][a:] += prev[:-a]
        temp = dp[j][S] - cur[j]
        answer += temp * (N-i)
        cur[j] = dp[j][S]

print(answer % MOD)


### FIXED CODE ###

import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 998244353
N, S = lr()
A = lr()
dp = [0] * (S+1)
answer = 0
for a in A:
    dp[0] += 1 # Lの数は１個ずつ加わる
    prev = dp.copy()
    for i in range(S-a+1):
        dp[i+a] += prev[i]
    answer += dp[-1] # その位置Rとした時

print(answer % MOD)
# 26
### BUGGY CODE ###

S = list(input())
Q = int(input())

for _ in range(Q):
  item = list(input().split())
  if item[0] == '1':
    S.reverse()

  else:
    if item[1] == '1':
      S.insert(0, item[2])

    else:
      S.append(item[2])

print(''.join(S))

### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline

S_deque = list(input())
S_deque = deque(S_deque[:-1])
Q = int(input())

top_flag = 1 # 0なら末尾、1なら最初

for _ in range(Q):
  item = list(input().split())
  if item[0] == '1':
    if top_flag == 0:
      top_flag = 1
    else:
      top_flag = 0

  else:
    in_flag = top_flag + int(item[1])
    if in_flag % 2 == 0:
      S_deque.appendleft(item[2])
    else:
      S_deque.append(item[2])

if top_flag == 0:
  S_deque.reverse()
else:
  pass

print(''.join(S_deque))
### BUGGY CODE ###

def solve():
  N, K = list(map(int, input().split(" ")))
  h = input().split(" ")
  h = [int(number) for number in h]

  minimumCostToReach = [0 for i in range(N)]

  minimumCostToReach[0] = 0
  for currentIndex in range(1, N):
    minimumCostToReach[currentIndex] = 1000000000

    for previousIndex in range(max(currentIndex - K, 0), currentIndex):
      cost = minimumCostToReach[previousIndex] + abs(h[currentIndex] - h[previousIndex])
      minimumCostToReach[currentIndex] = min(minimumCostToReach[currentIndex], cost)

  print(minimumCostToReach[N - 1])

solve()

### FIXED CODE ###

def solve():
  N, K = [int(i) for i in input().split()]
  H = [int(i) for i in input().split()]
  dp = [0] * N

  for i in range(1, N):
    dp[i] = min(dp[j] + abs(H[i] - H[j]) for j in range(max(i - K, 0), i))

  return dp[N - 1]

print(solve())
### BUGGY CODE ###

n,x = map(int, input().split())
a = [int(i) for i in input().split()]
ans = 0
if a[0]>x:
  ans += a[0]-x
  a[0]=x  
else:
  pass
j = 1
while j <= n-1:
  if a[j-1]+a[j]<=x:
    pass
  else:
    ans += a[j]-x
    a[j]=x
print(ans)

### FIXED CODE ###

n,x = map(int, input().split())
a = [int(i) for i in input().split()]
ans = 0
if a[0]>x:
  ans += a[0]-x
  a[0]=x  
else:
  pass
j = 1
while j <= n-1:
  if a[j-1]+a[j]<=x:
    j += 1
  else:
    ans += a[j]-x+a[j-1]
    a[j]=x-a[j-1]
    j += 1
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

def toId(i, j):
    pair = A[i][j]
    if i > pair:
        i, pair = pair, i
    return ids[i][pair]

def dfs(x):
    if dp[x] != -1:
        if done[x]:
            return dp[x]
        else:
            return -1
    dp[x] = 1
    for y in G[x]:
        res = dfs(y)
        if res == -1:
            return -1
        if res+1 > dp[x]:
            dp[x] = res+1
        #dp[x] = max(dp[x], res+1)
    done[x] = True
    return dp[x]

N = int(input())
A = [list(map(lambda x: int(x)-1, input().split())) for i in range(N)]
ids = [[0]*N for i in range(N)]
num = 0
for i in range(N):
    for j in range(N):
        if i < j:
            ids[i][j] = num
            num += 1
allv = N*N
G = [[] for i in range(allv)]
for i in range(N):
    for j in range(N-2):
        G[toId(i,j+1)].append(toId(i,j))
dp = [-1]*allv
done = [False]*allv
ans = 0
for i in range(allv):
    res = dfs(i)
    if res == -1:
        print(-1)
        exit()
    if res > ans:
        ans = res
    #ans = max(ans, res)
print(ans)

### FIXED CODE ###

N = int(input())
A = [list(map(lambda n: int(n)-1, input().split())) for i in range(N)]
cur = [0 for i in range(N)]
que = [i for i in range(N)]
ans = 0
while len(que) > 0:
    done = {}
    que2 = []
    for n in que:
        if done.get(n):
            continue
        pair = A[n][cur[n]]
        if done.get(pair):
            continue
        if n == A[pair][cur[pair]]:
            cur[n] += 1
            cur[pair] += 1
            done[n] = True
            done[pair] = True
            if cur[n] < N-1:
                que2.append(n)
            if cur[pair] < N-1:
                que2.append(pair)
    if len(done) > 0:
        ans += 1
    que = que2
ok = True
for i in range(N):
    if cur[i] < N-1:
        ok = False
if ok:
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

import math
k = int(input())

ans = 0
for i in range(1, k+1):
    for x in range(1, k+1):
        for z in range(1, k+1):
            ans += math.gcd(z,math.gcd(i, x))
            

print(ans)

### FIXED CODE ###

from math import gcd
k = int(input())

ans = 0
for i in range(1, k + 1):
    for x in range(1, k + 1):
        gcdix = gcd(i, x)
        for z in range(1, k + 1):
            ans += gcd(z, gcdix)
print(ans)
### BUGGY CODE ###

from collections import Counter
import math

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

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

dic = Counter(A)

for i in range(N):
    a = A[i]
    dic[a] -= 1
    ans = 0
    for v in dic.values():
        if v >= 2:
            ans += combinations_count(v, 2)
    dic[a] += 1
    print(ans)


### FIXED CODE ###

from collections import Counter
import math

def combinations_count(n):
    return (n * (n - 1)) // 2

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

combs = {}
dic = Counter(A)
for k, v in dic.items():
    combs[k] = combinations_count(v)
ans = sum(combs.values())

for i in range(N):
    a = A[i]
    ans_i = ans
    if combs[a] < 2:
        ans_i -= combs[a]
        print(ans_i)
    else:
        ans_i -= dic[a] - 1
        print(ans_i)
### BUGGY CODE ###

s = input()
num_query = int(input())

for _ in range(0, num_query):
    query = input()
    if query[0] == "1":
        s = s[::-1]
    else:
        _, pos, character = query.split()
        if pos == "1":
            s = character + s
        else:
            s = s + character
print(s)


### FIXED CODE ###

s = input()
num_query = int(input())

former = ""
latter = ""
is_rev = False

for _ in range(0, num_query):
    query = input()
    if query[0] == "1":
        is_rev = not is_rev
    else:
        pos = query[2]
        character = query[4]
        if pos == "1":
            if is_rev:
                latter += character
            else:
                former = character + former
        else:
            if is_rev:
                former = character + former
            else:
                latter += character

if is_rev:
    ans = latter[::-1] + s[::-1] + former[::-1]
else:
    ans = former + s + latter
print(ans)
### BUGGY CODE ###

N, S = map(int, input().split())
A = list(map(int, input().split()))
MOD = 998244353

dp = [0] * (S + 1)
ans = 0

for i, a in enumerate(A):
    for s in range(S + 1)[:: -1]:
        if s + a <= S:
            dp[s + a] += dp[s]
    if a <= S:
        dp[a] += (i + 1)
    ans += dp[S]

print(ans % MOD)

### FIXED CODE ###

N, S = map(int, input().split())
A = list(map(int, input().split()))
MOD = 998244353

dp = [0] * (S + 1)
ans = 0

for i, a in enumerate(A):
    for s in range(S + 1)[:: -1]:
        if s + a <= S:
            dp[s + a] += dp[s]
    if a <= S:
        dp[a] += (i + 1)
    ans += dp[S]

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

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

### FIXED CODE ###

S = input()
mod_bucket = [0] * 2019
mod_bucket[0] = 1
 
_S = S[::-1]
mod = 0
p = 1
for i in range(len(S)):
    mod = (p * int(_S[i]) + mod) % 2019
    mod_bucket[mod] += 1
    p = p*10%2019

ans = sum([mod*(mod-1)/2 for mod in mod_bucket])
print(int(ans))