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

mod = 998244353
n, s = map(int, input().split())
arr = list(map(int, input().split()))
dp = [[0] * (s + 1) for _ in range(n + 1)]
dp[0][0] = 1

for i in range(1, n + 1):
    var = arr[i - 1]
    for j in range(0, s + 1):
        dp[i][j] = 2 * dp[i - 1][j]
        dp[i][j] %= mod
        if j - var >= 0 and dp[i - 1][j - var] != 0:
            dp[i][j] += dp[i - 1][j - var]
            dp[i][j] %= mod
print(int(dp[n][s]))


### FIXED CODE ###

mod = 998244353
n, s = map(int, input().split())
arr = list(map(int, input().split()))
dp = [[0] * (s + 1) for _ in range(n + 1)]
dp[0][0] = 1

for i in range(1, n + 1):
    var = arr[i - 1]
    for j in range(0, s + 1):
        dp[i][j] = 2 * dp[i - 1][j]
        dp[i][j] %= mod
        if j - var >= 0 and dp[i - 1][j - var] != 0:
            dp[i][j] += dp[i - 1][j - var]
            dp[i][j] %= mod
print(int(dp[n][s]))
### BUGGY CODE ###

R, G, B, N = map(int, input().split())
ans = 0
for r in range(N // R + 1):
  for g in range(N // G + 1):
    d = N - R * r - G * g
    if d == 0 or (d > 0 and d % B == 0):
      ans += 1
print(ans)

### FIXED CODE ###

R, G, B, N = map(int, input().split())
ans = 0
for r in range(N // R + 1):
  d = N - R * r
  for g in range(d // G + 1):
    dd = d - G * g
    if dd == 0 or (dd > 0 and dd % B == 0):
      ans += 1
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(200000)
from collections import defaultdict
from bisect import bisect_left, bisect, insort_left, insort
q = int(input())
for _ in range(q):
    x = input()
    y = input()
    len_x = len(x)
    len_y = len(y)
    if len_x < len_y:
        len_x, len_y = len_y, len_x
        x, y = y, x
    c = defaultdict(list)
    for i, s in enumerate(x):
        c[s].append(i)
    ans = 0
    def f(x_i, y_i, cnt):
        if x_i >= len_x or y_i >= len_y:
            global ans
            if ans < cnt:
                ans = cnt
            return
        f(x_i, y_i + 1, cnt)
        s = bisect_left(c[y[y_i]], x_i)
        if s < len(c[y[y_i]]) and c[y[y_i]][s] < len_x:
            f(c[y[y_i]][s] + 1, y_i + 1, cnt + 1)
    f(0, 0, 0)
    print(ans)



### FIXED CODE ###

for _ in range(int(input())):
    a = input()
    b = input()
    if len(a) < len(b):
        a, b = b, a
    indices = []
    for cb in b:
        bgn_idx = 0
        for i, cur_idx in enumerate(indices):
            chr_idx = a.find(cb, bgn_idx) + 1
            if not chr_idx:
                break
            if chr_idx < cur_idx:
                indices[i] = chr_idx
            bgn_idx = cur_idx
        else:
            chr_idx = a.find(cb, bgn_idx) + 1
            if chr_idx:
                indices.append(chr_idx)
    print(len(indices))
### BUGGY CODE ###

import numpy as np

memo = {}
def dp(v, d, c):
    if memo.get((v, d), False):
        return None

    memo[(v, d)] = True
    if d == 0:
        res[v-1] = c
        return None

    dp(v, d-1, c)
    for e in dic.get(v, []):
        dp(e, d-1, c)


N, M = tuple(map(int, input().split(' ')))

dic = {}

for m in range(M):
    a, b = tuple(map(int, input().split(' ')))
    dic[a] = dic.get(a, []) + [b]
    dic[b] = dic.get(b, []) + [a]

Q = int(input())

vdc = [None]*Q

for q in range(Q):
    vdc[q] = tuple(map(int, input().split(' ')))

res = np.zeros(N)

for q in range(Q-1, -1, -1):
    v, d, c = vdc[q]
    dp(v, d, c)


for i in range(N):
    print(int(res[i]))


### FIXED CODE ###

import numpy as np

def dp(v, d, c):
    if memo[v-1][d]:
        return

    memo[v-1][d] = True
    if d == 0:
        res[v-1] = str(c)
        return

    dp(v, d-1, c)
    for e in dic[v-1]:
        dp(e, d-1, c)


N, M = [int(e) for e in input().split(' ')]

dic = [[] for _ in range(N)]
memo = [[False]*11 for _ in range(N)]

for m in range(M):
    a, b = [int(e) for e in input().split(' ')]
    dic[a-1].append(b)
    dic[b-1].append(a)

Q = int(input())


vdc = [[int(e) for e in input().split(' ')] for _ in range(Q)]

res = ['0']*N

[dp(v, d, c) for v, d, c in vdc[::-1]]


print('\n'.join(res))
### BUGGY CODE ###

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

# dp table
INF = float('inf')
dp = [INF]*N
dp[0] = 0

for i in range(N):
    for j in range(1,K+1):
        if i-j>=0:
            dp[i] = min(dp[i], dp[i-j]+abs(h[i]-h[i-j]))
print(dp[N-1])

### FIXED CODE ###

def chmin(a,b):
    if a > b:
        return b
    else:
        return a


N, K = map(int, input().split())
h = list(map(int, input().split()))
INF = float('inf')
dp = [INF] * N
dp[0] = 0


for i in range(N):
    for j in range(1,K+1):
        if i+j < N:
            dp[i+j] = chmin(dp[i+j], dp[i] + abs(h[i] - h[i+j]))

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

def main():
  import sys
  sys.setrecursionlimit(10**7)
  N,W=list(map(int,sys.stdin.readline().split()))

  dp=[[0]*N for _ in range(W+1)]#W*N

  WL=[0]* N
  VL=[0]*N

  for i in range(N):
      w,v=list(map(int,sys.stdin.readline().split()))
      WL[i]=w
      VL[i]=v


  def dfs(W,i):
      if i==N:
          return 0
      if dp[W][i]:
          return dp[W][i]
      if W-WL[i]>=0:
          dp[W][i]=max(dfs(W,i+1),dfs(W-WL[i],i+1)+VL[i])
          return dp[W][i]
      else:
          dp[W][i]=dfs(W,i+1)
          return dp[W][i]

  print(dfs(W,0))

main()

### FIXED CODE ###

def main():
    import sys
    sys.setrecursionlimit(10**7)
    N,W=list(map(int,sys.stdin.readline().split()))

    dp=[[0]*(W+1) for _ in range(N+1)]#N*W

    WL=[0]*N
    VL=[0]*N

    for i in range(N):
        w,v=list(map(int,sys.stdin.readline().split()))
        WL[i]=w
        VL[i]=v

    for i in range(1,N+1):
        for w in range(1,W+1):
            if w>=WL[i-1]:
                a=dp[i-1][w-WL[i-1]]+VL[i-1]
                b=dp[i-1][w]
                dp[i][w]=max(a,b)
            else:
                dp[i][w]=dp[i-1][w]
    print(dp[-1][-1])
main()
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
if n % 2 == 0:
    for i in range(n//2):
        if not a.count(2*i+1) == 2:
            print(0)
            break
    else: print(2**(n//2))
else:
    for i in range(1,n//2+1):
        if not a.count(2*i) == 2:
            print(0)
            break
    else:
        if a.count(0) == 1:
            print(2**(n//2))
        else: print(0)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a.sort()
if n % 2 == 1:
    if a[0] != 0:
        print(0)
    else:
        for i in range(2, n, 2):
            if not i == a[i-1] == a[i]:
                print(0)
                break
        else: print((2**(n//2))%1000000007)
else:
    for i in range(1, n, 2):
        if not i == a[i-1] == a[i]:
            print(0)
            break
    else: print((2**(n//2))%1000000007)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from itertools import product
from heapq import heappop, heappush
import numpy as np

def solve():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))

    X, Y = [N]+A, [N]+B
    dp = np.zeros((4,N+1), dtype=int)
    dp[0] = np.arange(N+1)
    for i,w in product(range(1,4), range(1,N+1)):
        dp[i][w] = max(dp[i-1][w-X[i]*j]+Y[i]*j for j in range(0,w//X[i]+1) if w>=X[i]*j) if w>=X[i] else dp[i-1][w]
    N = dp[3][N]
    #print(dp)
    X, Y = [N]+B, [N]+A
    dp = np.zeros((4,N+1), dtype=int)
    dp[0] = np.arange(N+1)
    for i,w in product(range(1,4), range(1,N+1)):
        dp[i][w] = max(dp[i-1][w-X[i]*j]+Y[i]*j for j in range(0,w//X[i]+1) if w>=X[i]*j) if w>=X[i] else dp[i-1][w]
    res = dp[3][N]
    #print(dp)
    return res

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

### FIXED CODE ###

# -*- coding: utf-8 -*-
from itertools import product
from heapq import heappop, heappush

def small_dp(N,A,B):
    *X, = filter(lambda c: int.__sub__(*c)<0, zip(A,B))
    k = len(X)
    if k == 0:
        return N
    if k == 1:
        return X[0][1]*(N//X[0][0]) + N%X[0][0]
    if k == 2:
        c = 0
        for i in range(N//X[0][0]+1):
            j = (N-i*X[0][0])//X[1][0]
            c = max(X[0][1]*i + X[1][1]*j + (N-i*X[0][0])%X[1][0], c)
        return c
    if k == 3:
        if (N//X[1][0]+1)*(N//X[0][0]+1) <= 10**6 :
            return max(X[0][1]*i + max(X[1][1]*j + X[2][1]*((N-i*X[0][0]-j*X[1][0])//X[2][0]) + ((N-i*X[0][0]-j*X[1][0])%X[2][0]) for j in range((N-i*X[0][0])//X[1][0]+1)) for i in range(N//X[0][0]+1))
        else:
            import numpy as np
            dp = np.zeros(N+1, dtype=int)
            for w in range(1,N+1):
                dp[w] = max(dp[w-X[i][0]]+X[i][1] if w>=X[i][0] else w for i in range(k))
            N = dp[-1]
            return N

def solve():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    res = small_dp(small_dp(N, A, B), B, A)

    return str(res)

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

from collections import deque

N = int(input())
G = [deque() for _ in range(N)]
E = dict() # (a, b) -> [idx, color]
for i in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    G[a].append(b)
    E[(a, b)] = [i, 0]
    

K = 0
new_color = [i for i in range(N-1, 0, -1)]
used_color = set()
queue = deque()
node2colors = [set() for _ in range(N)]
def bfs(v):
    global K
    # seen[v] = 1
    queue.append(v)
    while queue:
        q = queue.popleft()
        # if seen[q]:
            # continue
        for edge in range(len(G[q])):
            nex = G[q][edge]
            dif = used_color.difference(node2colors[q])
            if dif:
                usd_c = dif.pop()
                dif.add(usd_c)
                E[(q, nex)][1] = usd_c
                node2colors[q].add(usd_c)
                node2colors[nex].add(usd_c)
            else:
                new_c = new_color.pop()
                E[(q, nex)][1] = new_c
                node2colors[q].add(new_c)
                node2colors[nex].add(new_c)
                used_color.add(new_c)
                K += 1
            queue.append(nex)

bfs(0)
ans_list = [value for value in E.values()]
ans_list.sort()
print(K)
for i in range(N-1):
    print(ans_list[i][1])

### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline
    
def bfs(v, N, G, E):
    visited = [0]*N
    queue = deque()
    K = -1
    node2color = [-1 for _ in range(N)]
    queue.append(v)
    visited[v] = 1
    while queue:
        q = queue.popleft()
        color = 0
        for nex in G[q]:
            if visited[nex]:
                continue
            visited[nex] = 1
            color += 1
            if color == node2color[q]:
                color += 1
            
            node2color[nex] = color
            E[(min(q, nex), max(q, nex))] = color
            queue.append(nex)
        K = max(K, color)
    return K

def main():
    N = int(input())
    G = [deque() for _ in range(N)]
    E = dict() # (a, b) -> [idx, color]
    for i in range(N-1):
        a, b = map(lambda x: int(x)-1, input().split())
        G[a].append(b)
        G[b].append(a)
        E[(a, b)] = 0
    K = bfs(0, N, G, E)
    # ans_list = [value for value in E.values()]
    print(K)
    for value in E.values():
        print(value)
main()
### BUGGY CODE ###

from itertools import combinations as f
L, R = map(int, input().split())

s = set(map(lambda x:x%2019, range(L, R+1)))

print(min([i*j%2019 for i, j in f(s, 2)]))


### FIXED CODE ###

from itertools import combinations as f
L, R = map(int, input().split())

s = set(map(lambda x:x%2019, range(L, R+1)[:2019]))

print(min([i*j%2019 for i, j in f(s, 2)]))
### BUGGY CODE ###

if __name__ == '__main__':
    import sys
    input = sys.stdin.readline
    n, k = map(int, input().split())
    hs = [int(x) for x in  input().split()]
    if n <= k+1:
        print(abs(hs[0]-hs[-1]))
        exit()
    ans_list = [0]*n
    for i in range(1,k+1):
        ans_list[-i] = abs(hs[-1] - hs[-i])
    for i in range(k+1,n+1):
        ans_list[-i] = min([abs(hs[-i]-hs[-i+x])+ans_list[-i+x] for x in range(1,k+1)])
    print(ans_list[0])


### FIXED CODE ###

if __name__ == '__main__':
    import sys
    input = sys.stdin.readline
    n, k = map(int, input().split())
    hs = list(map(int, input().split()))
    if n <= k+1:
        print(abs(hs[0]-hs[-1]))
        exit()
    ans_list = [0]*n
    last_hs = hs[-1]
    for i in range(1,k+2):
        ans_list[-i] = abs(last_hs - hs[-i])
    for i in range(k+2,n+1):
        hs_i = hs[-i]
        ans_list[-i] = min([abs(hs_i-x)+y for x,y in zip(hs[1-i:k+1-i],ans_list[1-i:k+1-i])])
    print(ans_list[0])
### BUGGY CODE ###

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

count = 0
for i in range(len(S)):
  for j in range(i,len(S)):
    if S[i] == S[j]: continue
    for k in range(j,len(S)):
      if k-j == j-i: continue
      if S[i] == S[k] or S[j] == S[k]:continue
      count+=1
print(count)
      

### FIXED CODE ###

N=int(input())
S=input()
r,g,b = S.count('R'),S.count('G'),S.count('B')
total = r*g*b

count = 0
for d in range(1,N):
  for i in range(N-2*d):
    if S[i]!=S[i+d] and S[i+d]!=S[i+2*d] and S[i+2*d] != S[i]:
      count+=1

print(total-count)
### BUGGY CODE ###

n, k = map(int, input().split())
r, s, p = map(int, input().split())
h = {"r":p, "s":r, "p":s}
t = input()
lst = []
for i in range(k):
  lst.append([t[j] for j in range(len(t)) if j%k==i])
ans = 0
#print(lst)
for b in lst:
  tmp = ""
  for i in b:
    if i==tmp:
      tmp=""
    else:
      ans+=h[i]
      tmp=i
print(ans)


### FIXED CODE ###

n, k = map(int, input().split())
r, s, p = map(int, input().split())
d = {"r":p, "s":r, "p":s}
t = list(input())
dp = [0]*n
for i in range(n):
  if i>=k and t[i]==t[i-k]:
    dp[i] = 0
    t[i] = "x"
  else:
    dp[i] = d[t[i]]
print(sum(dp))
### BUGGY CODE ###

import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    N, K = NMI()
    A = NLI()
    F = NLI()
    A.sort()
    F.sort(reverse=True)
    ok = 10**13
    ng = 0
    for i in range(50):
        mid = (ok+ng) // 2
        limits = [mid//f for f in F]
        ks = [max(a-l, 0) for a, l in zip(A, limits)]
        if sum(ks) <= K:
            ok = mid
        else:
            ng = mid

    print(ok)


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    N, K = NMI()
    A = NLI()
    F = NLI()
    A.sort()
    F.sort(reverse=True)
    ok = 10**13
    ng = 0
    for i in range(100):
        mid = (ok+ng) // 2
        limits = [mid//f for f in F]
        ks = [max(a-l, 0) for a, l in zip(A, limits)]
        if sum(ks) <= K:
            ok = mid
        else:
            ng = mid

    print(ok)


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

# -*- coding: utf-8 -*-
import sys
N, K = map(int, input().split())
if K == 1:
  print(0)
  sys.exit()
  
min = N
a = abs(N-K)
while abs(a - K) < a:
  a = abs(a-K)
  
print(a)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys

N, K = map(int, input().split())
if K == 1:
  print(0)
  sys.exit()
  
if N / K > 1:
  N = N - int(N / K) * K
a = abs(N-K)
while abs(a - K) < a:
  a = abs(a-K)

print(int(a))
### BUGGY CODE ###

n,q = map(int,input().split())
S = input()
for i in range(q):
    l,r = map(int,input().split())
    A = S[l-1:r]
    print(A.count('AC'))

### FIXED CODE ###

n,q = map(int,input().split())
S = input()
N = [0]*(10**5+1)
for i in range(1,n):
    if S[i-1]=='A'and S[i]=='C':
        N[i] = 1
SUM = [0]*(10**5+1)
for i in range(1,n):
    SUM[i] += SUM[i-1]+N[i]
for i in range(q):
    l,r = map(int,input().split())
    print(SUM[r-1]-SUM[l-1])
### BUGGY CODE ###

s = input()
q = int(input())
for i in range(q):
    query = input()
    if query == "1":
        s = s[::-1]
    else:
        t,f,c = query.split()
        if f == "1":
            s = c + s
        else:
            s = s + c
print(s)

### FIXED CODE ###

s = input()
q = int(input())

from collections import deque
s = deque(s)
count = 0
for i in range(q):
    query = input()
    if query == "1":
        count += 1
    else:
        t,f,c = query.split()
        if f == "1":
            if count % 2 == 0:
                s.appendleft(c)
            else:
                s.append(c)
        else:
            if count % 2 == 0:
                s.append(c)
            else:
                s.appendleft(c)
s = "".join(s)
if count % 2 == 0:
    print(s)
else:
    print(s[::-1])
### BUGGY CODE ###

A,B,M=map(int,input().split())
x=[0]*M
y=[0]*M
c=[0]*M
a=list(map(int,input().split()))
b=list(map(int,input().split()))
for i in range(M):
    x[i],y[i],c[i]=map(int,input().split())
min=a[0]+b[0]
min1=0
for i in range(A):
    for j in range(B):
        for t in range(M):
            if i+1==x[t] and j+1==y[t]:
                min1=a[i]+b[j]-c[t]

            else:
                min1=a[i]+b[j]
            if min >= min1:
                min = min1
print(min)


### FIXED CODE ###

A,B,M=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))

price=[0]*(M+1)
price[0]=min(a)+min(b)

for i in range(M):
    x,y,c=map(int,input().split())
    price[i+1]=a[x-1]+b[y-1]-c

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

import sys
input = sys.stdin.readline

def main():
  h, w = map(int, input().split())
  A = []
  B = []
  for i in range(h):
    row = list(map(int, input().split()))
    A.append(row)
  for i in range(h):
    row = list(map(int, input().split()))
    B.append(row)
 
  dp = [[set([]) for j in range(w+1)] for i in range(h+1)]
  dp[0][0].add(abs(A[0][0] - B[0][0]))
  for i in range(h):
    for j in range(w):
      for item in dp[i][j]:
        if j < w - 1:
          dif = abs(A[i][j+1] - B[i][j+1])
          dp[i][j+1].add(item+dif)
          dp[i][j+1].add(abs(item-dif))
        if i < h - 1:
          dif = abs(A[i+1][j] - B[i+1][j])
          dp[i+1][j].add(item+dif)
          dp[i+1][j].add(abs(item-dif))
  print(min(dp[h-1][w-1]))
if __name__ == '__main__':
  main()


### FIXED CODE ###

import sys
def main():
  input = sys.stdin.readline
  h, w = map(int, input().split())
  A = []
  AB = []
  A_append = A.append
  AB_append = AB.append
  for i in range(h):
    row = list(map(int, input().split()))
    A_append(row)
  for i in range(h):
    row = [abs(A[i][j] - int(b)) for j, b in enumerate(input().split())]
    AB_append(row)
 
  dp_cur = [set([]) for _ in range(w)]
  dp_cur[0].add(AB[0][0])
  for i in range(h):
    dp_next = [set([]) for _ in range(w)]
    for j in range(w):
      if j < w - 1:
        add1 = dp_cur[j+1].add
        dif1 = AB[i][j+1]
      if i < h - 1:
        add2 = dp_next[j].add
        dif2 = AB[i+1][j]
      for item in dp_cur[j]:
        if j < w - 1:
          add1(item+dif1)
          add1(abs(item-dif1))
        if i < h - 1:
          add2(item+dif2)
          add2(abs(item-dif2))
    if i == h - 1:
      break
    dp_cur = dp_next
  print(min(dp_cur[w-1]))
if __name__ == '__main__':
  main()
### BUGGY CODE ###

s = input()
K = int(input())
lst = []
for end in range(1, len(s)+1):
    start = 0
    while end < len(s)+1:
        if s[start:end] not in lst:
            lst.append(s[start:end])
        start += 1
        end += 1
lst.sort()
print(lst[K-1])

### FIXED CODE ###

s = input()
K = int(input())
lst = []
for end in range(1, min(K+1, len(s)+1)):
    start = 0
    while end < len(s)+1:
        if s[start:end] not in lst:
            lst.append(s[start:end])
        start += 1
        end += 1
lst.sort()
print(lst[K-1])
### BUGGY CODE ###

N = int(input())
x = []
for i in range(N):
    a1,b1,c1,d1=[int(i) for i in input().split()]
    x.append([a1,b1,c1,d1])
for i in range(N):
  y = x[i]
  if y[0] < y[1]:
    print("No")
  elif y[1] > y[3]:
    print("No")
  elif y[1] > y[2]:
    ama = y[0] % y[1]
    mita = set()
    while True:
      if ama in mita:
        print("Yes")
        break
      mita.add(ama)
      if ama <= y[2] and ama>= 0:
        ama += y[3]
      if ama < y[1]:
        print("No")
        break
      ama %= y[1]
  else:
    print("Yes")
    

### FIXED CODE ###

import fractions
N = int(input())
x = []
for i in range(N):
    a1,b1,c1,d1=[int(i) for i in input().split()]
    x.append([a1,b1,c1,d1])
for i in range(N):
  y = x[i]
  if y[0] < y[1]:
    print("No")
  elif y[1] > y[3]:
    print("No")
  elif y[1] > y[2]:
    ama = y[0] % y[1]
    mo = y[3] %  y[1]
    if mo == 0:
      if ama<= y[2]:
        print("Yes")
      else:
          print("No")
    elif mo <= y[1]-y[2]-1:
      print("No")
    else:
        to = y[1] % mo
        if to == 0:
          if ama<= y[2]:
            print("Yes")
          else:
              print("No")
        else:
          are = fractions.gcd(to, y[1])
          if are <= y[1]-y[2]-1:
            print("No")
          else:
            print("Yes")
          
  else:
    print("Yes")
### BUGGY CODE ###

N=int(input())
S=list(input())
ans=0
R=[]
G=[]
B=[]
for i in range(N):
    if S[i]=="R":
        R.append(i)
    elif S[i]=="G":
        G.append(i)
    else:
        B.append(i)
lenb=len(B)
for r in R:
    for g in G:
        flag=0
        for b in B:
            a=r+g+b
            if a%3==0:
                a=a//3
                if a==r or a==g or a==b:
                    flag=flag+1
        ans=ans+lenb-flag
print(ans)

### FIXED CODE ###

N=int(input())
S=list(input())
ans=0
R=0
G=0
B=0
for i in range(N):
    if S[i]=="R":
        R=R+1
    elif S[i]=="G":
        G=G+1
    else:
        B=B+1
ans=R*G*B
for i in range(N-2):
    for j in range(i+1,N-1):
        if S[i]!=S[j]:
            k=2*j-i
            if N<=k:
                continue
            if S[i]!=S[k] and S[k]!=S[j]:
                ans=ans-1
print(ans)
### BUGGY CODE ###

from collections import deque

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

ans = deque(s)

reverse_num = 0
for i in range(q):
  if int(Q[i][0]) == 1:
    reverse_num += 1
  else:
    if int(Q[i][1]) == 1:
      if reverse_num % 2 == 0:
        ans.appendleft(Q[i][2])
      else:
        ans.append(Q[i][2])
    else:
      if reverse_num % 2 != 0:
        ans.appendleft(Q[i][2])
      else:
        ans.append(Q[i][2])

res = ''
if reverse_num % 2 == 0: 
  for i in range(len(ans)):
    res += ans[i]
  print(res)
else:
  for i in range(len(ans)):
    res += ans[-i-1]
  print(res)


### FIXED CODE ###

from collections import deque

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

ans = deque(s)

reverse_num = 0
for i in range(q):
  if int(Q[i][0]) == 1:
    reverse_num += 1
  else:
    if int(Q[i][1]) == 1:
      if reverse_num % 2 == 0:
        ans.appendleft(Q[i][2])
      else:
        ans.append(Q[i][2])
    else:
      if reverse_num % 2 != 0:
        ans.appendleft(Q[i][2])
      else:
        ans.append(Q[i][2])

res = ''
if reverse_num % 2 == 0: 
  for i in range(len(ans)):
    res += ans.popleft()
  print(res)
else:
  for i in range(len(ans)):
    res += ans.pop()
  print(res)
### BUGGY CODE ###

from collections import defaultdict, deque

S = input()

L = deque()
D1 = defaultdict(set)
D2 = {}
for i in range(len(S)-3):
  ii = i
  j = i + 4
  r = 0
  while j <= len(S):
    X = r + int(S[ii:j])
    r = X % 2019
    ii = j
    if r == 0:
      L.append(i)
      D1[i].add(j)
      D2[j] = i
      break
    elif r < 2:
      j += 4
      r *= 10000
    elif r < 20:
      j += 3
      r *= 1000
    elif r < 201:
      j += 2
      r *= 100
    else:
      j += 1
      r *= 10

for x in reversed(L):
  if x in D2:
    D1[D2[x]] += D1[x]
print(sum(len(x) for x in D1.values()))

### FIXED CODE ###

from collections import defaultdict

S = input()

D = defaultdict(int)
D[0] += 1
x = 0
d = 1
for s in reversed(S):
  x = (x + int(s) * d) % 2019
  D[x] += 1
  d = (d * 10) % 2019

print(sum(x * (x-1) // 2 for x in D.values()))