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

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

ans = 0

if p == 2 or p == 5:
    for i in range(n):
        if int(s[i])%p == 0:
            ans += i+1
else:
    arr = [int(s[i:])%p for i in range(n)]
    from collections import Counter
    cnt = Counter(arr)
    
    for i in cnt:
        ans += (cnt[i]-1)*cnt[i]
    ans //= 2
    if 0 in arr:
        ans += cnt[0]
    
print(ans)

### FIXED CODE ###

n,p = list(map(int,input().split())); s = [int(i) for i in input()]

ans = 0

if p == 2 or p == 5:
    for i in range(n):
        if s[i]%p == 0:
            ans += i+1
    print(ans)
    
else:
    s = s[::-1]
    res = [0] * p
    arr = [0] * n
    tmp = 0
    for i in range(n):
        tmp += s[i]*pow(10,i,p)
        tmp %= p
        arr[i] = tmp
    for i in arr:
        res[i] += 1
    for i in res:
        ans += i*(i-1)
    ans //= 2
    ans += res[0]
        
    print(ans)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**6)
mod=10**9+7
N=int(input())
G=[[] for _ in range(N+1)]
for _ in range(N-1):
    x, y = map(int, input().split())
    G[x].append(y)
    G[y].append(x)
b=[1]*(N+1)
w=[1]*(N+1)
def dfs(pre,n):
  for i in G[n]:
    if i==pre:
      continue
    dfs(n,i)
    b[n]*=w[i]
    b[n]%=mod
    w[n]*=b[i]+w[i]
    w[n]%=mod

dfs(0,1)
print((b[1]+w[1])%mod)

### FIXED CODE ###

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**6)
mod=10**9+7
N=int(input())
G=[[] for _ in range(N+1)]
for _ in range(N-1):
    x,y=map(int, input().split())
    G[x].append(y)
    G[y].append(x)
b=[1]*(N+1)
w=[1]*(N+1)
def dfs(pre,n):
  for i in G[n]:
    if i==pre:
      continue
    dfs(n,i)
    b[n]*=w[i]
    b[n]%=mod
    w[n]*=b[i]+w[i]
    w[n]%=mod

dfs(0,1)
print((b[1]+w[1])%mod)
### BUGGY CODE ###

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

R = {}
for i in range(M):
  a, b = UB[i]
  a -= 1
  b -= 1
  if a not in R: R[a] = [[b, i]]
  else: R[a].append([b, i])
  if b not in R: R[b] = [[a, i]]
  else: R[b].append([a, i])

DD = [[0] * 2 for _ in range(N)]
for i in range(N):
  DD[i][0] = D[i]
  DD[i][1] = i
DD.sort()
L = [0] * N
H = [0] * M
LL = [[-1] * 2 for _ in range(N)]
for i in range(N):
  h, x = DD[i]
  if L[x] == 0:
    if LL[x][0] == -1:
      for n, m in R[x]:
        LL[n] = [x, m]
        if D[n] == D[x] or L[n] != 0:
          H[m] = h
          if L[n] == 1:
            L[n] = 1
            L[x] = 2
          else:
            L[n] = 2
            L[x] = 1
          break
      else:
        print(-1)
        exit()
    else:
      n, m = LL[x]
      H[m] = h
      if L[n] == 1:
        L[n] = 1
        L[x] = 2
      else:
        L[n] = 2
        L[x] = 1

t = ""
for i in range(N):
  if L[i] == 1:
    t += "B"
  else:
    t += "W"
print(t)
for i in range(M):
  if H[i] == 0:
    print(10 ** 9)
  else:
    print(H[i])


### FIXED CODE ###

import sys
input = sys.stdin.readline
N, M = list(map(int, input().split()))
D = list(map(int, input().split()))
UB = [list(map(int, input().split())) for _ in range(M)]

LL = [[-1] * 2 for _ in range(N)]
for i in range(M):
  a, b = UB[i]
  a -= 1
  b -= 1
  if D[a] < D[b]:
    LL[b] = [a, i]
  elif D[a] > D[b]:
    LL[a] = [b, i]
  else:
    LL[a] = [b, i]
    LL[b] = [a, i]

DD = [[0] * 2 for _ in range(N)]
for i in range(N):
  DD[i][0] = D[i]
  DD[i][1] = i
DD.sort()
L = [0] * N
H = [0] * M

for i in range(N):
  h, x = DD[i]
  if L[x] == 0:
    if LL[x][0] == -1:
      print(-1)
      exit()
    else:
      n, m = LL[x]
      H[m] = h
      if L[n] == 1:
        L[n] = 1
        L[x] = 2
      else:
        L[n] = 2
        L[x] = 1

for i in range(N):
  if L[i] == 1:
    L[i] = "B"
  else:
    L[i] = "W"
print("".join(list(map(str, L))))
for i in range(M):
  if H[i] == 0:
    print(10 ** 9)
  else:
    print(H[i])
### BUGGY CODE ###

import sys

def insertHeap(H, A, key):
    A[H] = key
    i = H

    while i > 1 and A[i] > A[i // 2]:
        A[i], A[i // 2] = A[i // 2], A[i]
        i //= 2

def popHeap(H, A):
    max_ = A[1]

    A[1] = A[H]
    maxHeapify(H - 1, A, 1)

    return max_

def maxHeapify(H, A, i):
    left = 2 * i
    right = 2*i + 1

    if left <= H and A[left] > A[i]:
        largest = left
    else:
        largest = i
    if right <= H and A[right] > A[largest]:
        largest = right

    if largest != i:
        A[i], A[largest] = A[largest], A[i]
        maxHeapify(H, A, largest)

def buildMaxHeap(H, A):
    for i in range(H // 2, 0, -1):
        maxHeapify(H, A, i)

MAX_ = 2 * 10**6
H = 0
A = [None] * (MAX_ + 1)

while 1:
    cmd = sys.stdin.readline().split()
    # print(A, file=sys.stderr)

    if cmd[0] == 'end':
        break

    if cmd[0] == 'extract':
        print(popHeap(H, A))
        H -= 1
    else:
        H += 1
        insertHeap(H, A, int(cmd[1]))

### FIXED CODE ###

import sys
from heapq import heappush, heappop

heap = []

while 1:
    cmd = sys.stdin.readline().split()

    if cmd[0] == 'end':
        break

    if cmd[0] == 'extract':
        print(-heappop(heap))
    else:
        heappush(heap, -int(cmd[1]))
### BUGGY CODE ###

import itertools
import time

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

F = []
L = []

# t1 = time.time()
# for i in range(N):
#     if S[i] == 'o':
#         if len(F) == 0:
#             F.append(i)
#         elif F[-1] + C < i:
#             F.append(i)
#     if len(F) >= K:
#         break
# print(F)
# t2 = time.time()
i = 0
while len(F) < K:
    if S[i] == 'o':
        if len(F) == 0:
            F.append(i)
        elif F[-1] + C < i:
            F.append(i)
    i += 1
# print(F)
# t3 = time.time()

# print(t2 - t1, t3 - t2)

i = N - 1
while len(L) < K:
    if S[i] == 'o':
        if len(L) == 0:
            L.append(i)
        elif L[-1] - C > i:
            L.append(i)
    i -= 1

[print(i + 1) for i in F if i in L]

### FIXED CODE ###

# import time

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

F = []
L = []

# t1 = time.time()
# for i in range(N):
#     if S[i] == 'o':
#         if len(F) == 0:
#             F.append(i)
#         elif F[-1] + C < i:
#             F.append(i)
#     if len(F) >= K:
#         break
# print(F)
# t2 = time.time()
i = 0
while len(F) <= K and i < N:
    if S[i] == 'o':
        if len(F) == 0:
            F.append(i)
        elif F[-1] + C < i:
            F.append(i)
    i += 1
# print(F)
# t3 = time.time()

# print(t2 - t1, t3 - t2)

i = N - 1
while len(L) <= K and i >= 0:
    if S[i] == 'o':
        if len(L) == 0:
            L.append(i)
        elif L[-1] - C > i:
            L.append(i)
    i -= 1

if len(F) == K and len(L) == K:
    ans = [i + 1 for i in set(F) & set(L)]
    if len(ans) != 0:
        ans.sort()
        [print(i) for i in ans]
### BUGGY CODE ###

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

cnt = 0
for i in range(N):
  for j in range(i+1,N):
    if A[i] +A[j] == abs(i-j):
      cnt += 1
      
print(cnt)

### FIXED CODE ###

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

p = collections.Counter() # +
n = collections.Counter() # -
for i in range(N):
  p[i+A[i]] += 1
  n[i-A[i]] += 1
  
ans = 0
for i in p.keys():
  ans += p[i]*n[i]
print(ans)
### BUGGY CODE ###

s=input()
k=int(input())
ans=[]

for i in range(len(s)):
  for j in range(i+1,len(s)+1):
    ans.append(s[i:j])

ans=list(set(ans))
ans.sort()
print(ans[k-1])


### FIXED CODE ###

s=input()
k=int(input())
ans=[]

for i in range(len(s)):
  for j in range(i+1,min(k+i+1,len(s)+1)):
    ans.append(s[i:j])

ans=list(set(ans))
ans.sort()
print(ans[k-1])
### BUGGY CODE ###

S = str(input())
Q = int(input())
cnt = 2
for _ in range(Q):
    L = input().split()
    if L[0] == "1":
        cnt += 1
    elif L[0] == "2":
        if L[1] == "1" and (cnt)%2 == 0:
            S = str(L[2]) + S
        elif L[1] == "1" and (cnt)%2 != 0:
            S =  S + str(L[2])
        elif L[1] == "2" and (cnt)%2 == 0:
            S =  S + str(L[2])
        elif L[1] == "2" and (cnt)%2 != 0:
            S = str(L[2]) + S
if cnt%2 != 0:
    print(S[::-1])
else:
    print(S)

            
        
    

### FIXED CODE ###

from collections import deque

S = deque(input())
Q = int(input())
cnt = 2
for _ in range(Q):
    L = input().split()
    if L[0] == "1":
        cnt += 1
    elif L[0] == "2":
        if L[1] == "1" and (cnt)%2 == 0:
            S.appendleft(str(L[2]))
        elif L[1] == "1" and (cnt)%2 != 0:
            S.append(str(L[2]))
        elif L[1] == "2" and (cnt)%2 == 0:
            S.append(str(L[2]))
        elif L[1] == "2" and (cnt)%2 != 0:
            S.appendleft(str(L[2]))
S ="".join(S)
if cnt%2 != 0:
        print(S[::-1])
else:
        print(S)
### BUGGY CODE ###

count = int(input())
if count == 0:
  result = 0
else:
  nums_str = input().split()
  nums_int = []
  for strn in nums_str:
    nums_int.append(int(strn))

    if 0 in nums_int:
      result = 0
    else:
      result = 1
      for intn in nums_int:
        result *= intn
        if result > 1000000000000000000:
          result = -1
          break
    
print(result)

### FIXED CODE ###

def process():
  count = int(input())
  nums_str = input().split()
  nums_int = []
  for strn in nums_str:
    nums_int.append(int(strn))

  if 0 in nums_int:
    result = 0
    return result
  else:
    result = 1
    for intn in nums_int:
      result *= intn
      if result > 1000000000000000000:
        result = -1
        return result
    return result
    
print(process())
### BUGGY CODE ###

n, k = map(int, input().split())
v = list(map(int, input().split()))
# 再帰関数でいけそうだぞい
def dfs(que, cost, value):
    if cost <= 0:
        return value
    elif len(que) > 1:
        tmp1 = max(dfs(que[1:], cost-1, value+que[0]), dfs(que[1:], cost-2, value))
        tmp2 = max(dfs(que[:-1], cost-1, value+que[-1]), dfs(que[:-1], cost-2, value))
    else:
        tmp1 = value + que[0]
        tmp2 = value + que[-1]
    return max(tmp1, tmp2)

ans = dfs(v, k, 0)
print(ans)


### FIXED CODE ###

n, k = map(int, input().split())
v = list(map(int, input().split()))

ans = 0
for a in range(min(n, k) + 1):
    for b in range(min(n - a, k - a) + 1):
        v_use = v[:a] + v[-b:] if b >= 1 else v[:a]
        t = k - a - b
        s = 0
        for j in sorted(v_use):
            if j < 0 and t > 0:
                s += -j
                t -= 1
        ans = max(ans, sum(v_use) + s)

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

from collections import defaultdict
def decomp(m):
    pf=defaultdict(int)
    for i in range(2,int(m**0.5)+1):
        while m%i==0:
            pf[i]+=1
            m//=i
    if m>1:pf[m]=1
    return (pf[2], pf[5])

n=int(input())
table=[[0]*50 for _ in range(50)]
ans=0
for i in range(n):
    a=input()
    ax=round(float(a)*(10**9))
    p2,p5=decomp(ax)
    if i!=0:
        for j in range(18-p2,19):
            ans+=sum(table[j][18-p5:])
    table[p2][p5]+=1

print(ans)

### FIXED CODE ###

def decomp(m):
    p2=0
    p5=0
    while m%2==0:
        m//=2
        p2+=1
    while m%5==0:
        m//=5
        p5+=1
    return p2,p5

n=int(input())
table=[[0]*50 for _ in range(50)]
ans=0
for i in range(n):
    a=input().split('.')
    if len(a)==1:
        ax=int(a[0]+'0'*9)
    else:
        ax=int(a[0]+a[1]+'0'*(9-len(a[1])))
    p2,p5=decomp(ax)
    if i!=0:
        for j in range(18-p2,50):
            ans+=sum(table[j][18-p5:])
    table[p2][p5]+=1

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

def abs(x):
    if x>0:
        return x
    else:
        return x * (-1)

if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split()))
    a_mi = list(a[idx] - (idx + 1) for idx in range(len(a)))
    a_mi_sorted = sorted(a_mi)
    a_mi_sorted.append(a_mi_sorted[-1]+1)##bのrangeを取るため
    setAMI = sorted(list(set(a_mi_sorted)))

    ##print(a_mi_sorted)
    ans = float('inf')
    for i in range(n):
        #i番目までa[i]-bが0以下（absで負扱い）
        buf = sum(a_mi_sorted[:n]) - 2 * (sum(a_mi_sorted[:i+1]))
        for b in range(a_mi_sorted[i], setAMI[setAMI.index(a_mi_sorted[i])+1]):
            ans = min(ans, buf + (2 * (i + 1) - n) * b)
            ##print(i,b,ans)
    print(ans)

### FIXED CODE ###

N = int(input())
A = map(int, input().split())
B = list(A_i - (i + 1) for i, A_i in enumerate(A))
B_sorted = sorted(B)

ans = []
##中央値のインデックスmを求める
if N % 2 == 1:
    ##Nが奇数: 中央値のインデックスを求める
    m = int((N - 1) / 2 + 1) - 1
    b = B_sorted[m]
    ans += [sum(abs(x - b) for x in B_sorted)]
else:
    ##Nが偶数: 中央値を計算する元になる2数のインデックスを求める
    for m in range(int(N / 2) - 1, int(N / 2) + 1):
        b = B_sorted[m]
        ans += [sum(abs(x - b) for x in B_sorted)]    
print(min(ans))
### BUGGY CODE ###

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

for i in range(q):
    l, r = lr[i]
    ans = s[l-1:r].count('AC')
    print(ans)

### FIXED CODE ###

n, q = map(int, input().split())
s = input()
lr = [tuple(map(int, input().split())) for i in range(q)]
arr = [0]

for i in range(1, n):
    tmp = 0
    if s[i-1:i+1] == 'AC':
        tmp = 1
    arr.append(arr[i-1] + tmp)

for i in range(q):
    l, r = lr[i]
    ans = arr[r-1] - arr[l-1]
    print(ans)
### BUGGY CODE ###

n,k,q = map(int, input().split())
l=[int(input()) for x in range(q)]
pl=[k]*n
con=0
for j in range(q):
    for i in range(n):
        if i != l[con]-1:
            pl[i]=pl[i]-1
    con+=1
for k in range(n):
    if pl[k]>=1:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

n,k,q = map(int, input().split())
l=[int(input()) for x in range(q)]
p=[0]*n
for i in l:
    p[i-1]=p[i-1]+1
for i in p:
    if i>=(q-k)+1:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

N = int(input())
a = [''.join(sorted(list(input()))) for _ in range(N)]

ans = 0
for n in range(1,N):
  if a[n] in a[:n]:
    ans += a[:n].count(a[n])
print(ans)

### FIXED CODE ###

N = int(input())
a = [''.join(sorted(list(input()))) for _ in range(N)]
import collections
c = collections.Counter(a)
c_ls = list(c.values())
ans = 0
for i in range(len(c_ls)):
  ans += c_ls[i] * (c_ls[i]-1)//2
print(ans)
### BUGGY CODE ###

def ncr(n, r):
    ret = 1
    for i in range(n, n-r, -1):
        ret *= i
    for i in range(1, r+1):
        ret //= i
    return ret


rem = 10**9 + 7
n, k = (int(v) for v in input().split())
for opcnt in range(1, k+1):
    print((ncr(k-1, opcnt-1) * ncr(n-k+1, opcnt)) % rem)


### FIXED CODE ###

mod = 10**9 + 7
vmax = 2000
fac = [1, 1] + [0] * (vmax - 1)
finv = [1, 1] + [0] * (vmax - 1)
inv = [0, 1] + [0] * (vmax - 1)
for i in range(2, vmax+1):
    fac[i] = fac[i - 1] * i % mod
    inv[i] = mod - inv[mod % i] * (mod // i) % mod
    finv[i] = finv[i - 1] * inv[i] % mod


def com(n, k):
    if n < k or n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod


n, k = (int(v) for v in input().split())
for opcnt in range(1, k+1):
    print((com(k-1, opcnt-1) * com(n-k+1, opcnt)) % mod)
### BUGGY CODE ###

from sys import stdin

n = int(stdin.readline().rstrip())
an = list(map(int, input().split()))

sum = 0
for i in range(n-1):
    for j in range(i+1, n):
        if j-i == (an[i]+an[j]):
            sum += 1

print(sum)


### FIXED CODE ###

from sys import stdin

n = int(stdin.readline().rstrip())
an = list(map(int, input().split()))

l = {}
r = {}

for i in range(n):
    x = i + an[i]
    if x not in l:
        l[x] = [i]
    else:
        l[x].append(i)

    x = i - an[i]
    if x not in r:
        r[x] = [i]
    else:
        r[x].append(i)

sum = 0
for k in l:
    if k in r:
        sum += len(l[k])*len(r[k])

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


n,k = map(int, input().split())
h = list(map(int,input().split()))
dp = [0] * n
dp[0] = 0
dp[1] = abs(h[1] - h[0])
for i in range(2,n):
    # dp[i] = min(abs(h[i]-h[i-1])+dp[i-1], abs(h[i]-h[i-2])+dp[i-2])
    ans = 10000000000000000
    for j in range(1,k+1):
        if i-j >= 0:
            tmp = abs(h[i]-h[i-j])+dp[i-j]
            ans = min(tmp, ans)
    dp[i] = ans
# dp[2] = min((h[2] - h[1])+dp[1], (h[2]-h[0])+dp[0])
# dp[3] = min((h[3] - h[2])+dp[2], (h[3]-h[1])+dp[1], (h[3]-h[0])+dp[0])

print(dp[-1])

### FIXED CODE ###

n,k = map(int,input().split())
h = list(map(int,input().split()))
dp = [0]*n
dp[0] = 0
dp[1] = abs(h[1]-h[0])
# dp[2] = min(abs(h[2]-h[0]), dp[1]+abs(h[2]-h[1]))
# dp[3] = min((abs(h[3]-h[1])+dp[1]), abs(h[3]-h[2])+dp[2])
for i in range(2,n):
    ans = 10000000000000000000000000
    for j in range(1,k+1):
        if i-j >= 0:
            tmp = abs(h[i]-h[i-j])+dp[i-j]
            ans = min(ans,tmp)
    # dp[i] = min((abs(h[i]-h[i-2])+dp[i-2]), abs(h[i]-h[i-1])+dp[i-1])
    dp[i] = ans
print(dp[-1])
### BUGGY CODE ###

n,k = map(int,input().split())
p = list(map(int,input().split()))
ave = []
ans = 0
s = 0

for i in range(n):
  ave.append((p[i]+1)/2)

for i in range(n-k+1):
  for j in range(i,i+k):
    s += ave[j]
  ans = max(ans,s)
  s = 0

print(ans)

### FIXED CODE ###

n,k = map(int,input().split())
p = list(map(int,input().split()))
ave = []
ans = 0
tmp = 0

for i in range(n):
  ave.append((p[i]+1)/2)

for j in range(n):
  tmp += ave[j]
  if j >= k:
    tmp -= ave[j-k]
    
  ans = max(ans,tmp)


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

H, W, K = map(int, input().split())
S = [list(map(int, input())) for _ in range(H)]

ans = 10000
for i in range(2**H):
    cnt = 0
    temp = i
    group = [0]*H
    for j in range(H):
        group[j] = cnt
        if temp & 1:
            cnt += 1
        temp >>= 1
    div = [0]*H
    for l in range(H):
        div[group[l]] += S[l][0]
    for j in range(W-1):
        for k in range(H):
            if div[group[k]] + S[k][j+1] > K:
                cnt += 1
                div = [0]*H
                for l in range(H):
                    div[group[l]] += S[l][j+1]
                break
            else:
                div[group[k]] += S[k][j+1]
    ans = min(ans, cnt)
print(ans)
    


### FIXED CODE ###

H, W, K = map(int, input().split())
S = [list(map(int, input())) for _ in range(H)]

ans = 100000
for i in range(2**H):
    cnt = 0
    temp = i
    group = [0]*H
    for j in range(H):
        group[j] = cnt
        if temp & 1:
            cnt += 1
        temp >>= 1
    div = [0]*H
    for j in range(W):
        for k in range(H):
            if div[group[k]] + S[k][j] > K:
                cnt += 1
                div = [0]*H
                for l in range(H):
                    div[group[l]] += S[l][j]
                    if div[group[l]] > K:
                        cnt = 100000
                break
            else:
                div[group[k]] += S[k][j]
    ans = min(ans, cnt)
print(ans)
### BUGGY CODE ###

# Prime Number

import sys
import math


primes = [2]

for prime in xrange(3, 1000000, 2):
	for i in xrange(3, int(math.sqrt(prime)) + 1):
		if prime % i == 0:
			break
	else:
		primes.append(prime)

datas = []

for line in sys.stdin:
	datas.append(int(line))

for data in datas:
	count = 0
	for prime in primes:
		if prime <= data:
			count += 1
		else:
			break
	print count

### FIXED CODE ###

# Prime Number

import sys


MAX_NUM = 1000000
ROOT_MAX_NUM = 1000

primes = [1] * MAX_NUM

primes[0] = primes[1] = 0

for i in xrange(2, ROOT_MAX_NUM):
	if not primes[i]:
		continue
	for j in xrange(i+i, MAX_NUM, i):
		primes[j] = 0

datas = []

for line in sys.stdin:
	datas.append(int(line))

for data in datas:
	count = 0
	for i in xrange(data+1):
		if primes[i]:
			count += 1
	print count
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import numpy as np
H,W = map(int,input().split())
Gd = [list(input()) for _ in range(H)]
L=[np.arange(1, W+1)]*H
R=[np.arange(W, 0, -1)]*H
U=[np.arange(H, 0, -1)]*W
D=[np.arange(1, H+1)]*W
L=np.array(L)
R=np.array(R)
U=np.array(U)
D=np.array(D)
HL=range(H)
WL=range(W)
for h in HL:
  for w in WL:
    if Gd[h][w]=='#':
      L[h][w:]=L[h][w:]-L[h][w]
    wr=W-w-1
    if Gd[h][wr]=='#':
      R[h][:wr+1]=R[h][:wr+1]-R[h][wr]
for w in WL:
  for h in HL:
    if Gd[h][w]=='#':
      D[w][h:]=D[w][h:]-D[w][h]
    hr=H-h-1
    if Gd[hr][w]=='#':
      U[w][:hr+1]=U[w][:hr+1]-U[w][hr]
print(np.max(D.T+U.T+L+R-3))

### FIXED CODE ###

import numpy as np
H,W = map(int,input().split())
HL=list(range(H))
WL=list(range(W))
Gd = np.array([list(input()) for _ in HL])
Gd = np.where(Gd=='.', 1, 0)
L=np.zeros((H,W),dtype=np.int64)
R=np.zeros((H,W),dtype=np.int64)
U=np.zeros((H,W),dtype=np.int64)
D=np.zeros((H,W),dtype=np.int64)

for w in WL:
  R[:,w]=(R[:,w-1]+1)*Gd[:,w]
  L[:,-w-1]=(L[:,-w]+1)*Gd[:,-w-1]
for h in HL:
  D[h,:]=(D[h-1,:]+1)*Gd[h,:]
  U[-h-1,:]=(U[-h,:]+1)*Gd[-h-1,:]
print(np.max(D+U+L+R-3))
### BUGGY CODE ###

from collections import deque
h, w, m = map(int, input().split())
hl=[0]*h
wl=[0]*w
mh=0
mw=0
mhi=deque([])
dic = {}
mwi=deque([])
#ans =[[0]*w for i in range(h)]
s = [list(map(int, input().split())) for i in range(m)]
 
for i in range(m):
  a, b = s[i]
  a-=1
  b-=1
  if not a in dic:
    dic[a] = deque([b])
  else:
    dic[a].append(b)
 
  hl[a]+=1
  if hl[a]>mh:
    mh=hl[a]
    mhi = [a]
  elif hl[a]==mh:
    mhi.append(a)
  
  wl[b]+=1
  if wl[b]>mw:
    mw=wl[b]
    mwi=[b]
  elif wl[b]==mw:
    mwi.append(b)
 
  #ans[a][b]+=1 
for i in mhi:
  for j in mwi:
    if not j in dic[i]:
      print(mw+mh)
      quit()

print(mh+mw-1)

### FIXED CODE ###

from collections import deque
h, w, m = map(int, input().split())
hl=[0]*h
wl=[0]*w
mh=0
mw=0
mhi=deque([])
dic = {}
mwi=deque([])
#ans =[[0]*w for i in range(h)]
s = [list(map(int, input().split())) for i in range(m)]
 
for i in range(m):
  a, b = s[i]
  a-=1
  b-=1
  if not a in dic:
    dic[a] = {}
    dic[a][b]=1
  else:
    dic[a][b]=1
 
  hl[a]+=1
  if hl[a]>mh:
    mh=hl[a]
    mhi = [a]
  elif hl[a]==mh:
    mhi.append(a)
  
  wl[b]+=1
  if wl[b]>mw:
    mw=wl[b]
    mwi=[b]
  elif wl[b]==mw:
    mwi.append(b)
 
  #ans[a][b]+=1

for i in mhi:
  for j in mwi:
    if not j in dic[i]:
      print(mw+mh)
      quit()

print(mh+mw-1)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import math
S = input()
remainder = [0 for _ in range(2019)]
for i in range(len(S)):
  s = int(S[len(S)-1-i:])
  remainder[s % 2019] += 1
ans = 0
for i in range(2019):
  if i == 0:
      ans += remainder[i]
  else:
    if remainder[i] > 1:
      # 組み合わせ
      ans += (math.factorial(remainder[i]) // (math.factorial(remainder[i] - 2) * math.factorial(2)))
print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import math
S = input()[::-1]
remainder = [0] * 2019

# 2つ選ぶ組み合わせにおいて余り0の場合は1つしか選ばなくて良いので
# 2つ目に0を選んだ場合として便宜的に設定
remainder[0] = 1

num = 0
d = 1
for s in S:
  num += int(s) * d
  remainder[num % 2019] += 1
  d *= 10
  
  # numが大きくなりすぎると計算量が膨大になってしまうのを防ぐ
  # num%2019を計算するので、先に%2019で計算しても結果は変わらない
  d %= 2019
ans = 0
for i in range(2019):
  ans += remainder[i] * (remainder[i]-1) // 2
print(ans)