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

MOD = 998244353
HALF = (MOD + 1) // 2


def solve(a, b, c, d):
    dp1 = [[0] * (d + 1) for _ in range(c + 1)]
    dp2 = [[0] * (d + 1) for _ in range(c + 1)]
    dp3 = [[0] * (d + 1) for _ in range(c + 1)]
    dp1[a][b] = 1
    dp2[a][b] = 0
    dp3[a][b] = 0
    for i in range(a + 1, c + 1):
        dp1[i][b] = (pow(b - 1, i - a, MOD) + pow(b - 1, i - a - 1, MOD) * 1 * (i - a)) % MOD
        dp3[i][b] = (pow(b, i - a, MOD) - dp1[i][b]) % MOD
    for j in range(b + 1, d + 1):
        dp1[a][j] = (pow(a - 1, j - b, MOD) + pow(a - 1, j - b - 1, MOD) * 1 * (j - b)) % MOD
        dp2[a][j] = (pow(a, j - b, MOD) - dp1[a][j]) % MOD
    for i in range(a + 1, c + 1):
        for j in range(b + 1, d + 1):
            dp1[i][j] = (((dp1[i - 1][j] + dp2[i - 1][j]) * (j - 1) + (dp1[i][j - 1] + dp3[i][j - 1]) * (i - 1)) * HALF) % MOD
            dp2[i][j] = (dp2[i][j - 1] * i + dp1[i][j - 1] + dp3[i][j - 1]) % MOD
            dp3[i][j] = (dp3[i - 1][j] * j + dp1[i - 1][j] + dp2[i - 1][j]) % MOD

    # print(dp1, dp2, dp3)
    # print((dp1[c][d] + dp2[c][d] + dp3[c][d]) % MOD)
    return (dp1[c][d] + dp2[c][d] + dp3[c][d]) % MOD


def main():
    a, b, c, d = map(int, input().split())
    res = solve(a, b, c, d)
    print(res)


def test():
    assert solve(1, 1, 2, 2) == 3
    assert solve(1, 1, 3, 3) == 30
    assert solve(2, 1, 3, 4) == 65
    # assert solve(31, 41, 59, 265) == 387222020


if __name__ == "__main__":
    test()
    main()


### FIXED CODE ###

MOD = 998244353


def solve(a, b, c, d):
    dp1 = [[0] * (d + 1) for _ in range(c + 1)]
    dp2 = [[0] * (d + 1) for _ in range(c + 1)]
    dp3 = [[0] * (d + 1) for _ in range(c + 1)]
    dp1[a][b] = 1
    dp2[a][b] = 0
    dp3[a][b] = 0
    for i in range(a + 1, c + 1):
        dp1[i][b] = (pow(b - 1, i - a, MOD) + pow(b - 1, i - a - 1, MOD) * 1 * (i - a)) % MOD
        dp3[i][b] = (pow(b, i - a, MOD) - dp1[i][b]) % MOD
    for j in range(b + 1, d + 1):
        dp1[a][j] = (pow(a - 1, j - b, MOD) + pow(a - 1, j - b - 1, MOD) * 1 * (j - b)) % MOD
        dp2[a][j] = (pow(a, j - b, MOD) - dp1[a][j]) % MOD
    for i in range(a + 1, c + 1):
        for j in range(b + 1, d + 1):
            dp1[i][j] = ((dp1[i - 1][j] + dp2[i - 1][j]) * (j - 1)) % MOD
            dp2[i][j] = (dp2[i][j - 1] * i + dp1[i][j - 1] + dp3[i][j - 1]) % MOD
            dp3[i][j] = (dp3[i - 1][j] * j + dp1[i - 1][j] + dp2[i - 1][j]) % MOD

    # print(dp1, dp2, dp3)
    # print((dp1[c][d] + dp2[c][d] + dp3[c][d]) % MOD)
    return (dp1[c][d] + dp2[c][d] + dp3[c][d]) % MOD


def main():
    a, b, c, d = map(int, input().split())
    res = solve(a, b, c, d)
    print(res)


def test():
    assert solve(1, 1, 2, 2) == 3
    assert solve(1, 1, 3, 3) == 30
    assert solve(2, 1, 3, 4) == 65
    # assert solve(31, 41, 59, 265) == 387222020


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

def main():
  num, K, *line = map(int, open(0).read().split())
  dp = [float("inf")]* num
  dp[0] = 0
  for i in range(1, num):
    I = min(i + 1 , K + 1)
    dp[i] = min([dp[i - k] + abs(line[i] - line[i - k]) for k in range(1 , I)])
  #kの範囲: k = 1,2,3...K 無理なときは k = 1,2..i
  print(dp[-1])
main()

### FIXED CODE ###

def ans():
    n, k, *h = map(int, open(0).read().split())
    dp = [float("inf")] * n
    dp[0] = 0
    for i in range(1, n):
        min_j = max(0, i-k)
        dp[i] = min([dp[j] + abs(h[i] - h[j]) for j in range(min_j , i)])
    print(dp[n-1])
 
ans()
### BUGGY CODE ###

H, N = map(int, input().split())
A = []
B = []
for _ in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

dp = [float("inf")] * (H + 1)
dp[0] = 0

for h in range(0, H):
    for a, b in zip(A, B):
        tmp = dp[h] + b
        if h + a >= H and tmp < dp[H]:
            dp[H] = tmp
        elif h + a < H and tmp < dp[h + a]:
            dp[h + a] = tmp

print(dp[-1])


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    H, N = map(int, input().split())
    A = []
    B = []
    for _ in range(N):
        a, b = map(int, input().split())
        A.append(a)
        B.append(b)

    dp = [float("inf")] * (H + 1)
    dp[0] = 0

    for h in range(0, H):
        for a, b in zip(A, B):
            tmp = dp[h] + b
            if h + a >= H and tmp < dp[H]:
                dp[H] = tmp
            elif h + a < H and tmp < dp[h + a]:
                dp[h + a] = tmp

    print(dp[-1])


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

n,m=[int(x) for x in input().split()]
x=[int(x) for x in input().split()]
y=[int(x) for x in input().split()]
from itertools import product
mod=10**9+7
ans=0
for i,j in product(range(1,n),range(1,m)):
    ans=ans+(x[i]-x[i-1])*(y[j]-y[j-1])*i*(n-i)*j*(m-j)
print(ans%mod)

### FIXED CODE ###

n,m=[int(x) for x in input().split()]
x=[int(x) for x in input().split()]
y=[int(x) for x in input().split()]
mod=10**9+7
ans=0
ysum=0
for j in range(1,m):
    ysum+=(y[j]-y[j-1])*j*(m-j)
for i in range(1,n):
    ans=ans+(x[i]-x[i-1])*i*(n-i)*ysum
print(ans%mod)
### BUGGY CODE ###

S = input()

MOD = int(1e9+7)
N = len(S)

dp = [[0] * 13 for i in range(N)]

for i in range(N):
  idx = N-i-1
  if i == 0:
    if S[idx] != '?':
      dp[i][int(S[idx])] = 1
    else:
      for j in range(10):
        dp[i][j] = 1
  else:
    amari = (10 ** i) % 13
    if S[idx] != '?':
      shift = int(S[idx]) * amari % 13
      for j in range(13):
        if j+shift < 13:
          dp[i][j+shift] = dp[i-1][j]
        else:
          dp[i][j+shift-13] = dp[i-1][j]
    else:
      for k in range(10):
        shift = k * amari % 13
        for j in range(13):
          if j+shift < 13:
            dp[i][j+shift] = (dp[i][j+shift] + dp[i-1][j]) % MOD
          else:
            dp[i][j+shift-13] = (dp[i][j+shift-13] + dp[i-1][j]) % MOD
            
print(dp[N-1][5])
#print(dp)

### FIXED CODE ###

import copy
S = input()
S = S[::-1]
dp = [0 for _ in range(13)]
dp[0] = 1

mod = int(1e9+7)

def calc(dp,i,k):
  dpw = [0 for _ in range(13)]
  if S[i] == '?':
    X = [i for i in range(10)]
  else:
    X = [int(S[i])]
  for j in range(13):
    for x in X:
      dpw[(j+x*k)%13] += dp[j]  
      dpw[(j+x*k)%13] %= mod
  return dpw

keta = 1
for i in range(len(S)):
  dp = calc(dp,i,keta)
  keta = keta * 10 % 13

#print(dp)
print(dp[5])
#print(sum(dp))
### BUGGY CODE ###

from bisect import bisect_left
N = int(input())
L = sorted(list(map(int, input().split())))

ans = 0
for i in range(N-2):  # １番短い棒 #どうせ増えないからＮでも多分大丈夫
  for j in range(i + 1, N-1):  # 真ん中の長さの棒
    ans += bisect_left(L[j+1:], L[i] + L[j]) 

print(ans)

### FIXED CODE ###

from bisect import bisect_left
N = int(input())
L = sorted(list(map(int, input().split())))

ans = 0
for i in range(N):  # １番短い棒
    for j in range(i + 1, N):  # 真ん中の長さの棒
        ans += bisect_left(L, L[i] + L[j]) - (j + 1)

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

h,w,k = map(int,input().split())
x1,y1,x2,y2 = map(int,input().split())
c = []
for i in range(h):
  c.append(list(input()))

q = [(0,x1-1,y1-1,0,())]
while(q):
  qq = []
  for a,x,y,kk,d in q:
    #print(x,y,c[x][y])
    if c[x][y] == '.':
      c[x][y] = a
    else:
      if a <= c[x][y]:
        c[x][y] = a
      else:
        continue
    # c[x][y] = min(c[x][y],a)
    # c[x][y] = a
    for dx,dy in ((0,-1),(0,1),(-1,0),(1,0)):
      if 0 <= x+dx < h and 0 <= y+dy < w and c[x+dx][y+dy] != '@':
        if kk == 0 or d != (dx,dy):
          nk = k-1
          na = a+1
          if c[x+dx][y+dy] == '.' or c[x+dx][y+dy] >= na:
            qq.append((na,x+dx,y+dy,nk,(dx,dy)))
        else:
          nk = kk-1
          na = a
          if c[x+dx][y+dy] == '.' or c[x+dx][y+dy] > na:
            qq.append((na,x+dx,y+dy,nk,(dx,dy)))
  #print(qq)
  q = qq[:]

print(-1 if c[x2-1][y2-1] == '.' else c[x2-1][y2-1])
#print(c)


### FIXED CODE ###

h,w,k = map(int,input().split())
x1,y1,x2,y2 = map(int,input().split())
c = []
for i in range(h):
  c.append(list(input()))

q = [(1,x1-1,y1-1)]
c[x1-1][y1-1] = 0
while(q):
  qq = []
  for a,x,y in q:
    for dx,dy in ((0,-1),(0,1),(-1,0),(1,0)):
      for kk in range(1,k+1):
        xx = x+dx*kk
        yy = y+dy*kk
        if not (0 <= xx < h) or not (0 <= yy < w) or c[xx][yy] == '@' or (c[xx][yy] != '.' and c[xx][yy] < a):
          break
        if c[xx][yy] == '.' or (c[xx][yy] != '.' and c[xx][yy] > a):
          c[xx][yy] = a
          qq.append((a+1,xx,yy))
  #print(qq)
  q = qq[:]

print(-1 if c[x2-1][y2-1] == '.' else c[x2-1][y2-1])
#print(c)
### BUGGY CODE ###

from itertools import permutations
l, r = map(int,input().split())
a = []
for i in range(l,r+1):
    tmp = i%2019
    if tmp not in a:
        a.append(tmp)
perm = permutations(a,2)
min = 2019
for i in list(perm):
    tmp = i[0]*i[1]%2019
    if tmp == 0:
        min = tmp
        break
    if min > tmp:
        min = tmp
print(min)


### FIXED CODE ###

import sys
l, r = map(int, input().split())
if r-l>=2019:
    print("0")
elif r%2019==0 or l%2019==0:
    print("0")
else:
    min = 2019
    for i in range(l,r):
        for j in range(i+1,r+1):
            tmp = i*j%2019
            if min > tmp:
                min = tmp
            if min == 0:
                print("0")
                sys.exit()
    print(min)
### BUGGY CODE ###

def main():
    import sys
    # input = sys.stdin.readline

    S = list(input())

    N = len(S)

    c = 0
    for i in range(0, N-3):
        for j in range(i+4, N+1):
            num = int(''.join(S[i:j]))
            if num % 2019 == 0:
                c += 1
    print(c)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    import sys

    S = list(input())
    N = len(S)

    # c = 0
    # for i in range(0, N-3):
    #     for j in range(i+4, N+1):
    #         num = int(''.join(S[i:j]))
    #         if num % 2019 == 0:
    #             c += 1
    #             print(num)
    # print(c)

    P = 2019
    num = [0] * P
    num[0] = 1
    now, ans = 0, 0
    _10 = 1
    for i in range(N-1, -1, -1):
        now = (now + int(S[i])*_10) % P
        _10 *= 10
        _10 %= P
        ans += num[now]
        num[now] += 1
    print(ans)


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

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

import sys
input = sys.stdin.buffer.readline

n, q = map(int, input().split())
clst = list(map(int, input().split()))
lr = [list(map(int, input().split())) + [i] for i in range(q)]
lr.sort(key=lambda x:x[1])
bit = Bit(n)
pos = 0
last = [-1 for _ in range(n)]
ans = []
for i, c in enumerate(clst):
    bit.add(i + 1, 1)
    if last[c - 1] != -1:
        bit.add(last[c - 1] + 1, -1)
    last[c - 1] = i
    while lr[pos][1] == i + 1:
        l = lr[pos][0]
        r = lr[pos][1]
        ans.append([bit.sum(r) - bit.sum(l - 1), lr[pos][2]])
        pos += 1
        if pos == q:
            break
    if pos == q:
        break
ans.sort(key=lambda x:x[1])
for num, _ in ans:
    print(num)



### FIXED CODE ###

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

import sys
input = sys.stdin.buffer.readline

n, q = map(int, input().split())
clst = list(map(int, input().split()))
lr = []
for i in range(q):
    l, r = map(int, input().split())
    lr.append([l, r, i])
lr.sort(key=lambda x:x[1])
bit = Bit(n)
pos = 0
last = [-1 for _ in range(n)]
ans = [-1 for _ in range(q)]
for i, c in enumerate(clst):
    bit.add(i + 1, 1)
    if last[c - 1] != -1:
        bit.add(last[c - 1] + 1, -1)
    last[c - 1] = i
    while lr[pos][1] == i + 1:
        l = lr[pos][0]
        r = lr[pos][1]
        ans[lr[pos][2]] = bit.sum(r) - bit.sum(l - 1)
        pos += 1
        if pos == q:
            break
    if pos == q:
        break
    
print(*ans, sep="\n")
### BUGGY CODE ###

N, M = map(int, input().split( ))
datas = list(map(int, input().split( )))
datas.sort()
Ms = M - 1

dest = list()
K = 0
i = 0
for i in range(Ms):
  K = datas[i+1] - datas[i]
  dest.append(K)
  dest.sort()

L = 0
MN = M - N
for j in range(MN):
  L = L + dest[j]

print(L)

### FIXED CODE ###

N, M = map(int, input().split( ))
datas = list(map(int, input().split( )))
datas.sort()
Ms = M - 1

dest = list()
K = 0
i = 0
for i in range(Ms):
  K = datas[i+1] - datas[i]
  dest.append(K)

dest.sort()
L = 0
MN = M - N
for j in range(MN):
  L = L + dest[j]

print(L)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000000)

N,M=map(int,input().split())
xy = [list(map(int, input().split())) for _ in range(M)]
to = [[]*(N+1) for _ in range(N+1)]
for i in range(M):
    x,y=xy[i]
    to[x].append(y)

dp = [0]*(N+1)

def saiki(v):
    for u in to[v]:
        if dp[u] < dp[v]+1:
            dp[u]=dp[v]+1
            saiki(u)

count = [True]*(N+1)
count[0] = False
for i in range(M):
    count[xy[i][1]] = False

for i in range(1,N+1):
    if count[i]:
        saiki(i)
print(max(dp))


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000000)

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

to = [[]*(N+1) for _ in range(N+1)]
for i in range(M):
    x,y=map(int,input().split())
    to[x].append(y)

dp = [-1]*(N+1)

def saiki(v):
    if dp[v]!=-1: return dp[v]
    res = 0
    for u in to[v]:
        res=max(res,saiki(u)+1)
    dp[v]=res
    return res

ans=0
for i in range(1,N+1):
    ans = max(ans,saiki(i))
print(max(dp))
### BUGGY CODE ###

#!/usr/bin/python
# -*- coding: utf-8 -*-


def main():
    while True:
        terms = int(raw_input())
        if terms == 0:
            break

        data = []
        for i in xrange(terms):
            data.append(int(raw_input()))

        print(max_sum_sequence(data))


def max_sum_sequence(data):
    max = 0
    num_data = len(data)
    for l in xrange(num_data + 1):
        sum = max_at_length(data, l)
        if sum > max:
            max = sum

    return max


def max_at_length(data, length):
    max = 0
    num_data = len(data)
    for begin in xrange(num_data):
        sum = 0
        for i in xrange(begin, begin + length):
            if i >= num_data:
                continue

            sum += data[i]

        if sum > max:
            max = sum

    return max


main()

### FIXED CODE ###

#!/usr/bin/python


def main():
    while True:
        try:
            num_data = int(raw_input())
            if num_data == 0:
                break

            data = []
            for i in xrange(num_data):
                data.append(int(raw_input()))

            max = max_sum_sequence(data)
            print(max)
        except:
            break


def max_sum_sequence(data):
    sum = [0]
    n = len(data)

    for i in xrange(n):
        sum.append(sum[-1] + data[i])

    mx = - (1 << 30)
    for i in xrange(n):
        for j in xrange(i + 1, n + 1):
            mx = max(mx, sum[j] - sum[i])

    return mx


main()
### BUGGY CODE ###

from sys import stdin


def main():
    _in = [_.rstrip() for _ in stdin.readlines()]
    S =     _in[0]   # type:str
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    len_S = len(S)
    cnt = 0
    for i in range(len_S):
        for j in range(i+3,len_S):
            if j == i+3:
                mod = int(S[len_S-j-1:len_S-i])%3
            else:
                mod = (mod+int(S[len_S-j-1]))%3
            if mod == 0:
                _ = int(S[len_S-j-1:len_S-i])
                if _%673==0:
                    cnt += 1
                    break
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)


def ans():
    _in = [_.rstrip() for _ in stdin.readlines()]
    S =     _in[0]   # type:str
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    len_S = len(S)
    cnt = 0
    mod_arr = {}
    for i in range(2019):
        mod_arr[i] = 0
    mod_arr[0] += 1
    for i in range(0,len_S+1):
        _ = int(S[len_S-i-1:])
        if i>0: mod = (mod+int(S[len_S-i-1])*10**i)%2019
        else:   mod = _%2019
        mod_arr[mod]+=1
    for i in range(2019):
        if mod_arr[i] > 0:
            cnt += mod_arr[i]*(mod_arr[i]-1)//2
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)


if __name__ == "__main__":
    #main()
    ans()


### FIXED CODE ###

from sys import stdin


def main():
    _in = [_.rstrip() for _ in stdin.readlines()]
    S =     _in[0]   # type:str
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    len_S = len(S)
    cnt = 0
    for i in range(len_S):
        for j in range(i+3,len_S):
            if j == i+3:
                mod = int(S[len_S-j-1:len_S-i])%3
            else:
                mod = (mod+int(S[len_S-j-1]))%3
            if mod == 0:
                _ = int(S[len_S-j-1:len_S-i])
                if _%673==0:
                    cnt += 1
                    break
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)


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

    _in = [_.rstrip() for _ in stdin.readlines()]
    S =     _in[0]   # type:str
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    cnt = 0
    mod_arr = [0] * 2019
    mod_arr[0] += 1

    num, dec = 0, 1
    for s in S[::-1]:
        num += int(s)*dec
        num %= 2019
        dec *= 10
        dec %= 2019
        mod_arr[num] += 1

    for i in range(2019):
        if mod_arr[i] > 0:
            cnt += mod_arr[i]*(mod_arr[i]-1)//2
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)
### BUGGY CODE ###

S = input()
n = len(S)
mod = 10**9+7
dp = [[0]*13 for _ in range(n+1)]
dp[0][0] = 1
mul = 1
for i in range(n):
    x = S[-(i+1)]
    if x == "?":
        for k in range(10):
            for j in range(13):
                dp[i+1][(k*mul+j)%13] += dp[i][j]
                dp[i+1][(k*mul+j)%13] %= mod
    else:
        k = int(x)
        for j in range(13):
            dp[i+1][(k*10**i+j)%13] += dp[i][j]
            dp[i+1][(k*10**i+j)%13] %= mod
    mul = mul*10%13
print (dp[n][5])

### FIXED CODE ###

INF = 10 ** 9 + 7

S = input()
# dp[i][j]はうしろからi桁を13で割った余りがjであるものの個数
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
mul = 1

for i in range(len(S)):
    x = S[-(i + 1)]
    if x == "?":
        for k in range(10):
            for j in range(13):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                dp[i + 1][(mul * k + j) % 13] %= INF
    else:
        k = int(x)
        for j in range(13):
            dp[i + 1][(mul * k + j) % 13] += dp[i][j]
            dp[i + 1][(mul * k + j) % 13] %= INF
    mul = mul * 10 % 13  # 計算量削減のためここで13で割っている

print(dp[len(S)][5])
### BUGGY CODE ###

N, M = map(int, input().split())
ES = []
D = {}

*parent, = range(M)
def root(x):
    if x == parent[x]:
        return x
    parent[x] = y = root(parent[x])
    return y
def unite(x, y):
    px = root(x); py = root(y)
    if px < py:
        parent[py] = px
    else:
        parent[px] = py

E = {}
for i in range(M):
    p, q, c = map(int, input().split()); p -= 1; q -= 1
    ES.append((p, q, c))
    if (p, c) in D:
        unite(D[p, c], i)
    D[p, c] = i
    E.setdefault(p, set()).add(c)
    if (q, c) in D:
        unite(D[q, c], i)
    D[q, c] = i
    E.setdefault(q, set()).add(c)
#P = [[] for i in range(M)]
P = {}
for i in range(M):
    j = root(i)
    p, q, c = ES[i]
    s = P.setdefault(j, set())
    s.add(p); s.add(q)

from collections import deque
que = deque([(0, 0, 0)])
INF = 10**18
dist = [INF]*N
dist[0] = 0
gdist = [INF]*M

while que:
    cost, v, t = que.popleft()
    if t:
        # edge
        if gdist[v] < cost or v not in P:
            continue
        for w in P[v]:
            if cost + 1 < dist[w]:
                dist[w] = cost + 1
                que.append((cost + 1, w, 0))
    else:
        # node
        if dist[v] < cost or v not in E:
            continue
        for c in E[v]:
            w = root(D[v, c])
            if cost < gdist[w]:
                gdist[w] = cost
                que.appendleft((cost, w, 1))

print(dist[N-1] if dist[N-1] < INF else -1)


### FIXED CODE ###

N, M = map(int, input().split())
ES = []
D = {}

*parent, = range(M)
def root(x):
    if x == parent[x]:
        return x
    parent[x] = y = root(parent[x])
    return y
def unite(x, y):
    px = root(x); py = root(y)
    if px < py:
        parent[py] = px
    else:
        parent[px] = py

E = {}
for i in range(M):
    p, q, c = map(int, input().split()); p -= 1; q -= 1
    ES.append((p, q, c))
    if (p, c) in D:
        unite(D[p, c], i)
    D[p, c] = i
    E.setdefault(p, set()).add(c)
    if (q, c) in D:
        unite(D[q, c], i)
    D[q, c] = i
    E.setdefault(q, set()).add(c)
#P = [[] for i in range(M)]
P = {}
for i in range(M):
    j = root(i)
    p, q, c = ES[i]
    s = P.setdefault(j, set())
    s.add(p); s.add(q)

from collections import deque
que = deque([(0, 0, 0)])
INF = 10**18
dist = [INF]*N
dist[0] = 0
gdist = [INF]*M

while que:
    cost, v, t = que.popleft()
    if t:
        # edge
        if gdist[v] < cost or v not in P:
            continue
        for w in P[v]:
            if cost + 1 < dist[w]:
                dist[w] = cost + 1
                que.append((cost + 1, w, 0))
    else:
        # node
        if dist[v] < cost or v not in E:
            continue
        for c in E[v]:
            w = root(D[v, c])
            if cost < gdist[w]:
                gdist[w] = cost
                que.appendleft((cost, w, 1))

print(dist[N-1] if dist[N-1] < INF else -1)
### BUGGY CODE ###

def is_ok(x):
    result = 0
    for i in range(N):
        a = A[i]
        t = x // F[i]
        if t < a:
            result += a - t
    return result <= K


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

A.sort()
F.sort(reverse=True)

ng = -1
ok = A[-1] * F[0]
while ok - ng > 1:
    m = ng + (ok - ng) // 2
    if is_ok(m):
        ok = m
    else:
        ng = m
print(ok)


### FIXED CODE ###

def f(x, A, F):
    result = 0
    for i in range(N):
        t = x // F[i]
        if t < A[i]:
            result += A[i] - t
    return result


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

A.sort()
F.sort(reverse=True)

lo = 0
hi = A[-1] * F[0]
while lo < hi:
    mid = (lo+hi)//2
    if K - f(mid, A, F) < 0:
        lo = mid+1
    else:
        hi = mid
print(lo)
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()

S = list(input())
n = len(S)

dp = [0] * 2019
dp[0] = 1
tmp = 0
for i in range(n):
    tmp += int(S[n-1-i]) * (10**i)
    dp[tmp%2019] += 1
# print(dp)

ans = 0
for i in dp:
    if i >= 2:
        ans += i*(i-1)//2
        # print(i, dp[i])
print(ans)

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()

S = list(input())
n = len(S)

dp = [0] * 2019
dp[0] = 1
tmp = 0
ten = 1
for i in range(n):
    tmp += int(S[n-1-i]) * ten
    tmp %= 2019
    ten *= 10
    ten %= 2019
    dp[tmp%2019] += 1
# print(dp)

ans = 0
for i in dp:
    if i >= 2:
        ans += i*(i-1)//2
        # print(i, dp[i])
print(ans)