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

from collections import defaultdict

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

res = 0

if p not in [2,5]:
    crem = 0
    dic_p = defaultdict(lambda : 0)
    for i,subs in enumerate(s[::-1]):
        crem += (int(subs) * 10**i) % p
        crem %= p

        if crem == 0:
            res += 1
        res += dic_p[crem]

        dic_p[crem] += 1
        
else:
    for i,subs in enumerate(s[::-1]):
        if int(subs) % p == 0:
            res += n - i
    
print(res)

### FIXED CODE ###

from collections import defaultdict

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

res = 0

if p not in [2,5]:
    crem = 0
    
    crem_10 = [1]
    for i in range(1,n):
        crem_10 += [(crem_10[-1] * (10%p)) % p]
        
    dic_p = defaultdict(lambda : 0)
    for i,subs in enumerate(s[::-1]):
        crem += (int(subs) % p * crem_10[i]) % p
        crem %= p

        if crem == 0:
            res += 1
        res += dic_p[crem]

        dic_p[crem] += 1
        
else:
    for i,subs in enumerate(s[::-1]):
        if int(subs) % p == 0:
            res += n - i
    
print(res)
### BUGGY CODE ###

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

import numpy as np
dp = [np.Inf for i in range(N)]

# 初期化
dp[0] = 0; 
# dp[1] = np.abs(A[1] - A[0]);

for i in range(1,N):
  lim = min(i,K);
  for k in range(lim,0,-1):
    dp[i] = min(dp[i], dp[i-k] + np.abs(A[i]-A[i-k]))  
print(dp[-1])

### FIXED CODE ###

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

dp = [float('inf') for i in range(N)]

# 初期化
dp[0] = 0; 

for i in range(1,N):
  lim = min(i,K);
  for k in range(lim,0,-1):
    dp[i] = min(dp[i], dp[i-k] + abs(A[i]-A[i-k]))  
print(dp[-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline


def main():
    n = int(input())
    A = [int(i) for i in input().split()]

    MOD = 10 ** 9 + 7
    A.sort()
    A.append(MOD)

    ans = 0
    if A[0] != A[1]:
        ans += 1

    for i in range(1, n):
        if A[i] == A[i + 1]:
            continue

        for j in range(i):
            if A[i] % A[j] == 0:
                break
        else:
            ans += 1
            # print(f"{i = }, {j = }, {ans = }")

    print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import numpy as np
import sys
input = sys.stdin.readline


def main():
    n = int(input())
    A = np.array([int(i) for i in input().split()])

    max_dp = np.max(A) + 1
    dp = np.zeros(max_dp, dtype="int32")

    for a in A:
        if dp[a] >= 2:
            continue
        fancy = np.arange(a, max_dp, a)
        dp[fancy] += 2
        dp[a] -= 1
    print(np.sum(dp == 1))


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

import sys
import heapq
import math
N, K = map(int, sys.stdin.readline().rstrip().split())
A = list(map(int, sys.stdin.readline().rstrip().split()))
F = list(map(int, sys.stdin.readline().rstrip().split()))
A.sort()
F.sort()

cost = []
for i in range(N):
    cost.append((-A[i] * F[N - 1 - i], A[i], F[N - 1 - i], A[i]))
heapq.heapify(cost)

while K > 0:
    max_1, a_1, f_1, nokori_1 = heapq.heappop(cost)
    max_2, a_2, f_2, nokori_2 = heapq.heappop(cost)
    if max_1 == 0:
        break
    c = math.ceil((max_2 - max_1 + 1) / f_1)
    num = min(K, c)
    if num <= nokori_1:
        heapq.heappush(cost, (min(max_1 + f_1 * num, 0), a_1, f_1, nokori_1 - num))
        heapq.heappush(cost, (max_2, a_2, f_2, nokori_2))
        K -= num
    else:
        heapq.heappush(cost, (min(max_1 + f_1 * a_1, 0), a_1, f_1, nokori_1 - a_1))
        heapq.heappush(cost, (max_2, a_2, f_2, nokori_2))
        break

print(-cost[0][0])

### FIXED CODE ###

import sys
import math
N, K = map(int, sys.stdin.readline().rstrip().split())
A = list(map(int, sys.stdin.readline().rstrip().split()))
F = list(map(int, sys.stdin.readline().rstrip().split()))
A.sort()
A = A[::-1]
F.sort()

def test(x):
    res = 0
    for i in range(N):
        t = A[i] * F[i]
        if t > x:
            res += math.ceil((t - x) / F[i])
    
    return res <= K

ng = -1
ok = 10**18

while ng + 1 < ok:
    mid = (ng + ok) // 2
    if test(mid):
        ok = mid
    else:
        ng = mid
print(ok)
### BUGGY CODE ###

MOD = 10 ** 9 + 7
pow_10_i_13 = [pow(10, i, 13) for i in range(6)]

s = input()

dp = [0] * 13
dp[0] = 1
for i, c in enumerate(reversed(s)):
    if c == '?':
        tmp = [0] * 13
        for j in range(10):
            shift = j * pow_10_i_13[i % 6] % 13
            for k in range(13):
                tmp[k] += dp[k-shift]
                tmp[k] %= MOD
        dp = tmp
    else:
        shift = int(c) * pow_10_i_13[i % 6] % 13
        dp = dp[-shift:] + dp[:-shift]

print(dp[5])


### FIXED CODE ###

MOD = 10 ** 9 + 7
pow_10_i_13 = [pow(10, i, 13) for i in range(6)]

s = input()

dp = [0] * 13
dp[0] = 1
for i, c in enumerate(reversed(s)):
    if c == '?':
        tmp = [0] * 13
        for j in range(10):
            shift = j * pow_10_i_13[i % 6] % 13
            for k in range(13):
                tmp[k] += dp[k-shift]
                tmp[k] %= MOD
        dp = tmp
    else:
        shift = int(c) * pow_10_i_13[i % 6] % 13
        dp = dp[-shift:] + dp[:-shift]

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

from sys import setrecursionlimit
from fractions import gcd

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

#nを素因数分解したリストを返す
# def prime_decomposition(n):
#     i = 2
#     table = []
#     while i * i <= n:
#         while n % i == 0:
#             n //= i
#             table.append(i)
#         i += 1
#     if n > 1:
#         table.append(n)
#     return table


memo = {}
# n個の数字でmを作る場合のmax
def dfs(n, m):
    if n == 1:
        return m
    elif n >= m:
        return 1
    else:
        if (n, m) in memo:
            return memo[n, m]
        else:
            # print(n, m)
            ans = []
            for first in range(2, m - n + 2):
                # print(first, m - first)
                ans_first = gcd(first, dfs(n - 1, m - first))
                ans.append(ans_first)
                # ans_first = dfs(n - 1, m - first)
            # print(ans)
            # ans.append(gcd(first, dfs(n - 1, m - first)))
            # return 1  # max(ans)
            memo[n, m] = max(ans)
            return memo[n, m]


# print(N, M, prime_decomposition(M))
print(dfs(N, M))

### FIXED CODE ###

# (o) recursionはダメ
# (o) 素因数はO(sqrt(N))で求められる
# (x) 具体的な計算

"""
Memo:
- A=[a1,...,an]の最大公約数をDとする
- sum(A)=MもDで割り切れる，よってDはMの約数 (Mも割れる)

2条件
- DがMの約数であって，M >= N * Dであるとき
    - a1=...=an-1=D, an = M - (N - 1) * D は全てDで割り切れる (最大公約数)
- Mの約数かつM // N以下の整数で最大
"""

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


# 約数を求める
factors = []
i = 1
while i * i <= M + 1:
    if M % i == 0:
        factors.append(i)
        if M // i != i:
            factors.append(M // i)
    i += 1

factors.sort(reverse=True)
# Mの約数でM // N以下の最大
for f in factors:
    if M // f >= N:
        print(f)
        exit()

# ans = 1
# for factor in factors:
#     if factor <= M // N:
#         ans = factor
# print(ans)
### BUGGY CODE ###

n=int(input())
def gcd(a,b):
    if b==0: return a
    else:
        return gcd(b,a%b)
def lcm(a,b):
    return a*b//gcd(a,b)


ans=0
for i in range(1,n+1):
    for j in range(1,n+1):
        for k in range(1,n+1):
            ans+= gcd(i,gcd(j,k))
print(ans)

### FIXED CODE ###

n=int(input())
def gcd(a,b):
    if b==0: return a
    else:
        return gcd(b,a%b)
def lcm(a,b):
    return a*b//gcd(a,b)


ans=0
for i in range(1,n+1):
    for j in range(1,n+1):
        for k in range(1,n+1):
            ans+= gcd(i,gcd(j,k))
print(ans)
### BUGGY CODE ###

inf=10**9+1
n=int(input())
array_a=sorted([a for a in map(int, input().split())])+[inf]
array_b=sorted([a for a in map(int, input().split())])+[inf]
array_c=sorted([a for a in map(int, input().split())])
nums_b=[0 for _ in range(n)]
cur=0
for (idx,b) in enumerate(array_b[:-1]):
    while(array_a[cur]<b):
        cur+=1
    nums_b[idx]=cur
nums_c=[0 for _ in range(n)]
cur=0
for (idx,c) in enumerate(array_c):
    while(array_b[cur]<c):
        cur+=1
    nums_c[idx]=sum(nums_b[:cur])
print(sum(nums_c))

### FIXED CODE ###

inf=10**9+1

n=int(input())
array_a=sorted([a for a in map(int, input().split())])+[inf]
array_b=sorted([a for a in map(int, input().split())])+[inf]
array_c=sorted([a for a in map(int, input().split())])

nums_b=[0 for _ in range(n)]
cur=0
for (idx,b) in enumerate(array_b[:-1]):
    while(array_a[cur]<b):
        cur+=1
    nums_b[idx]=cur


cur=0
res=0
for (idx,c) in enumerate(array_c):
    while(array_b[cur]<c):
        res+=nums_b[cur]*(n-idx)
        cur+=1
print(res)
### BUGGY CODE ###

N = int(input())
# N = (2 ** 16) * (3 ** 16)
ans = 0
t = []
primeList = [2]
maxNumber = 2 * 10 ** 5
for x in range(3, maxNumber):
    for y in primeList:
        if x % y == 0:
            break
    else:
        primeList.append(x)  # 割り切れるものがなければリストに追加

for i in primeList:
    for x in range(1, 40):
        y = i ** x
        if N // y == N / y:
            ans += 1
            N = N // y
        else:
            break

if N > 10 ** 5:
    ans += 1
print(ans)


### FIXED CODE ###

N = int(input())
ans = 0
for i in range(2, 10 ** 6 + 1):
    for x in range(1, 40):
        y = i ** x
        if N // y == N / y:
            ans += 1
            N = N // y
        else:
            while N // i == N / i:
                N = N // i
            break


if N > 10 ** 6:
    ans += 1
print(ans)
### BUGGY CODE ###

from functools import reduce

n, m, k = map(int,input().split())
modi = 998244353


def ncr(a, b):
    if b == 0:
        return 1
    else:
        num = reduce(lambda x, y: x * y % modi, range(a, a-b, -1))
        den = reduce(lambda x, y: x * y % modi, range(1, b+1))
        return num * pow(den, modi - 2, modi) % modi


res = 0
for i in range(k + 1):
    res += m % modi * pow(m - 1, n - i - 1, modi) * ncr(n - 1, i)
    res %= modi
print(res)


### FIXED CODE ###

lim = 200001
n, m, k = map(int, input().split())
modi = 998244353

fa = [1] * (lim + 1)
fa_inv = [1] * (lim + 1)

for i in range(lim):
    fa[i+1] = fa[i] * (i+1) % modi

fa_inv[-1] = pow(fa[-1], modi - 2, modi)
for i in range(lim - 1, 0, -1):
    fa_inv[i] = fa_inv[i+1] * (i+1) % modi


def ncr(a, b):
    if a < b:
        return 0
    else:
        return fa[a] * fa_inv[b] % modi * fa_inv[a - b] % modi


prt = [1] * (n + 1)
for i in range(n):
    prt[i+1] = prt[i] * (m - 1) % modi

res = 0
for i in range(k + 1):
    res += m * prt[n - i - 1] * ncr(n - 1, i) % modi
    res %= modi
print(res)
### BUGGY CODE ###

n=int(input())
a=[]
for i in range(n):
    s=input()
    if s not in a:
        a.append(s)

print(len(a))


### FIXED CODE ###

n=int(input())
a=[0]*n

for i in range(n):
    a[i]=input()
a=sorted(a)
ans=1
for i in range(n-1):
    if a[i]!=a[i+1]:
        ans+=1
print(ans)
### BUGGY CODE ###

n = input()
a = list(map(int, input().split()))
sum = 1
for i in a:
  sum *= i

if sum > 10**18:
  sum = -1
print(sum)

### FIXED CODE ###

n = input()
a = input().split()
a = [int(s) for s in a]
a.sort(reverse=True)

if a[-1] == 0:
  print(0)
else :
  sum = 1
  for i in a:
    sum *= i
    if sum > 10**18:
      sum = -1
      break
  print(sum)
### BUGGY CODE ###

import numpy as np


def main():
    N, M, Q = list(map(int, input().split(' ')))
    x = np.zeros((N + 1, N + 1), dtype=int)
    for _ in range(M):
        left, right = list(map(int, input().split(' ')))
        x[left, right] += 1
    x = np.apply_along_axis(np.cumsum, axis=1, arr=x)
    queries = [list(map(int, input().split(' '))) for _ in range(Q)]
    for q in queries:
        print(x[q[0]:(q[1] + 1), q[1]].sum())


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N, M, Q = list(map(int, input().split(' ')))
    x = [[0 for _ in range(N)] for _ in range(N)]
    for _ in range(M):
        left, right = list(map(int, input().split(' ')))
        x[left - 1][right - 1] += 1
    for i in range(N):
        for j in range(1, N):
            x[i][j] += x[i][j - 1]
    for j in range(N):
        for i in range(N - 2, -1, -1):
            x[i][j] += x[i + 1][j]
    queries = [list(map(int, input().split(' '))) for _ in range(Q)]
    for q in queries:
        print(x[q[0] - 1][q[1] - 1])


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

n = int(input())
a = list(map(int, input().split()))
p = 10**9 + 7
num_a = [0]*60
str_a = []
for i in a:
  a_str = format(i, 'b').zfill(60)
  str_a.append(a_str)
  for j in range(len(a_str)):
    if a_str[-1-j] == '1':
      num_a[j] += 1
ans = 0
cnt = 0

for i, j in enumerate(num_a):
  ans =  (ans + j*(n-j)*2**i)%p

print(ans)

### FIXED CODE ###

import numpy as np
n = int(input())
a = np.array(list(map(int, input().split())))
p = 10**9 + 7
ans = 0
for i in range(60):
  c = np.count_nonzero(a & 1)
  ans = (ans + c*(n-c)*2**i) % p
  a = a >> 1
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import collections
import copy
def dellist(items, indexes):
    for index in sorted(indexes, reverse=True):
        del items[index]

def solve(N: int, A: "List[int]"):
    counter = sorted(list(collections.Counter(A).values()),reverse=True)
    for i in range(1,N+1):
        if len(counter) < i:
            print(0)
            continue
        c = copy.deepcopy(counter)
        answer = 0
        while c:
            if len(c) < i:
                break
            remove_index = []
            for j in range(i):
                c[j]-=1
                if c[j] == 0:
                    remove_index.append(j)
            if remove_index:
                dellist(c,remove_index)
            answer += 1

        print(answer)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import collections

def solve(N: int, A: "List[int]"):
    counter = sorted(list(collections.Counter(A).values()),reverse=True)
    c_index = 0
    k=0
    for i in range(1,N+1):
        k+=1
        if len(counter)<i:
            print(0)
            continue
        while counter[c_index]*k > N and c_index<len(counter)-1:
            N-=counter[c_index]
            c_index+=1
            k-=1
        print(N//k)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

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

import collections
import numpy as np

def reverse_counting_sort(collection, max):
    bucket = [0]*(max+1)
    for c in collection:
        bucket[c] += 1
    arr = []
    for i in range(max,-1,-1):
        if bucket[i] != 0:
            arr.extend([i]*bucket[i])
    return arr


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

for k in range(1, n+1):
    counts = collections.Counter(a).values()
    counts = reverse_counting_sort(list(counts), n)
    
    eat = 0
    while True:
        if np.count_nonzero(counts) < k:
            break
        else:
            for i in range(k):
                counts[i] -= 1
            eat += 1
            counts = reverse_counting_sort(list(counts), n)
            
    print(eat)

### FIXED CODE ###

import collections
import numpy as np

# リストarrからx個の同じ長さの列を取り出す時の最大の長さ
# 発想: x個取り出す時、ある文字をx個より多く取り出して列に含むことはない
#       一方ある文字をその文字がある数よりも取り出して使うこともできない
#       つまり、min(arr.count(a), x)で、x個の同じ長さの列に使えるaの数がわかる
#       さらに、sum(min(arr.count(a),x))で、x個の同じ長さの列に使える文字の数がわかる
#       よって、sum(min(arr.count(a),x))//xで、x個の同じ長さの列の長さがわかる
#       発展的に、longest(arr,x)までの計算状況からlongest(arr,x+1)が計算できる
# def longest(arr, x):    # legacy
#     return sum(min(arr.count(a), x) for a in arr) // x


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

counter = collections.Counter(a)        #O(n)
nums = list(counter.values())           #O(n)
num_counter = collections.Counter(nums) #O(n)
lastest_add = np.count_nonzero(nums)    #O(n)
building, longests = [0], [0]
for i in range(1, n+1):                 #O(n)
    appended = building[-1] + lastest_add   #O(1)
    building.append(appended)               #O(1)
    longests.append(appended // i)          #O(1)
    lastest_add -= num_counter[i]           #O(1)


lastest_longest = 0
k_most = []
for i, x in enumerate(reversed(longests)):
    while x > lastest_longest:
        lastest_longest += 1
        k_most.append(n-i)

k_most.extend([0]*(n-len(k_most)))      # zero padding

for longests_num in k_most:
    print(longests_num)

# print('----------------')
# for k in range(1, n+1):
#     maxindexes = list(i for i, x in enumerate(longests) if x >= k)
#     if maxindexes:
#         print(maxindexes[-1])
#     else:
#         print(0)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

import math

def main():
    n = int(input())
    a_li = list(map(int, input().strip().split()))

    for i in range(1, n+1):
        print(a_li.count(i))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    n = int(input())
    a_li = list(map(int, input().strip().split()))

    a_dict = {}

    for a in a_li:
        if str(a) in a_dict:
            a_dict[str(a)] += 1
        else:
            a_dict[str(a)] = 1

    for i in range(1, n+1):
        if str(i) in a_dict:
            print(a_dict[str(i)])
        else:
            print(0)

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

n=int(input())
x=str(input())
for i in range(n):
    if x[i]=='0':
        tmp=x[:i]+'1'+x[(i+1):]
    elif x[i]=='1':
        tmp=x[:i]+'0'+x[(i+1):]
    cnt=0
    if tmp.count('1')==0:
        print(0)
    else:
        while True:
            r=int(tmp,2)%tmp.count('1')
            tmp='{:b}'.format(r)
            cnt+=1
            if tmp=='0':
                print(cnt)
                break

### FIXED CODE ###

n=int(input())
X=input()
x=X.count('1')
x_plus=int(X,2)%(x+1)
keta=n-1
if x==1:
    for i in range(n):
        tmp=0
        ans=1
        if X[i]=='0':
            tmp+=x_plus
            tmp+=pow(2,keta,(x+1))
            tmp%=(x+1)
            while tmp:
                tmp=tmp%(bin(tmp).count('1'))
                ans+=1
            print(ans)
        else:
            print(0)
        keta-=1
else:
    x_minus=int(X,2)%(x-1)
    for i in range(n):
        tmp=0
        ans=1
        if X[i]=='0':
            tmp+=x_plus
            tmp+=pow(2,keta,(x+1))
            tmp%=(x+1)
            while tmp:
                tmp=tmp%(bin(tmp).count('1'))
                ans+=1
            print(ans)
        else:
            tmp+=x_minus
            tmp-=pow(2,keta,(x-1))
            tmp%=(x-1)
            while tmp:
                tmp=tmp%(bin(tmp).count('1'))
                ans+=1
            print(ans)
        keta-=1
### BUGGY CODE ###

def is_anagram(s1: str, s2: str) -> bool:
    if len(s1) != len(s2):
        return False

    d1, d2 = dict(), dict()
    for s in list(s1):
        count = d1.get(s)
        if count is None:
            d1[s] = 1
        else:
            d1[s] = count + 1
    for s in list(s2):
        count = d2.get(s)
        if count is None:
            d2[s] = 1
        else:
            d2[s] = count + 1
    return d1 == d2


n = int(input())
ss = [input() for _ in range(n)]

counter = 0

for i in range(n):
    for j in range(i + 1, n):
        if is_anagram(ss[i], ss[j]):
            counter += 1

print(counter)


### FIXED CODE ###

from math import factorial


def combination2(num: int) -> int:
    return int(factorial(num) / (2 * factorial(num - 2)))


n = int(input())
ss = [input() for _ in range(n)]

dictionary = {}

for s in ss:
    sorted_string = "".join(sorted(s))
    count = dictionary.get(sorted_string)
    if count is None:
        dictionary[sorted_string] = 1
    else:
        dictionary[sorted_string] = count + 1

counter = 0

for count in dictionary.values():
    if count > 1:
        counter += combination2(count)

print(counter)
### BUGGY CODE ###

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

L=['R','G','B']
L_b=['R','G','B']
cnt=0
for i in range(N-2):
    for j in range(i+1,N-1):
        if S[i]!=S[j]:
            L_b=['R','G','B']
            L_b.remove(S[i])
            L_b.remove(S[j])
            index = S.rfind(L_b[0])
            for k in range(j+1,index+1):
                if S[i]!=S[j] and S[i]!=S[k] and S[j]!=S[k]  and j-i!=k-j:
                    cnt+=1

print(cnt)


### FIXED CODE ###

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

r=S.count('R')
g=S.count('G')
b=S.count('B')

cnt=0
for i in range(N):
    for j in range(i+1,N):
        k=j+j-i
        if k>=N:
            break
        if S[i]!=S[j] and S[j]!=S[k] and S[k]!=S[i]:
            cnt+=1

print((r*g*b)-cnt)
### BUGGY CODE ###

N, P = map(int, input().split())
S = input()
from collections import Counter
ans = 0
if P == 2 or P == 5:
    for i in range(N-1, -1, -1):
        t = S[i]
        if not int(t) % P:
            ans += i + 1
else:
    c = Counter()
    c[0] += 1
    t = ""
    for i in range(N-1, -1, -1):
        t = S[i] + t
        r = int(t) % P
        c[r] += 1

    for k in c.keys():
        a = c[k]
        ans += (a * (a-1)) // 2
print(ans)

### FIXED CODE ###

N, P = map(int, input().split())
S = input()
from collections import Counter
ans = 0
if P == 2 or P == 5:
    for i in range(N-1, -1, -1):
        t = S[i]
        if not int(t) % P:
            ans += i + 1
else:
    c = Counter()
    c[0] += 1
    p = 1
    t = int(S[N-1])
    c[t%P] += 1
    for i in range(N-2, -1, -1):
        p *= 10
        t = int(S[i]) * p + t
        c[t % P] += 1
        p %= P
    for a in c.values():
        ans += (a * (a-1)) // 2
print(ans)
### BUGGY CODE ###

n = int(input())
s = n
l = 0
while s > 0:
  l += 1
  s //= 10
key = [0]*2019
mod = 10
for i in range(l):
  judge = n%mod
  k = judge%2019
  key[k] += 1
  mod *= 10

ans = key[0]
for i in range(2019):
  if key[i] >= 2:
    ans += key[i]*(key[i]-1)//2
print(ans)

### FIXED CODE ###

n = input()
l = len(n)
key = [0]*2019
mod = 1
judge = 0
for i in range(l):
  judge += ((mod%2019)*int(n[l-i-1]))%2019
  judge %= 2019
  k = judge%2019
  key[k] += 1
  mod *= 10
  mod %= 2019

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

from functools import reduce
from operator import mul
n = int(input())
arr = list(map(int, input().split()))

ans = reduce(mul, arr)
print(-1 if ans > 10**18 else ans)

### FIXED CODE ###

import sys
n = int(input())
arr = list(map(int, input().split()))

if 0 in arr:
    print(0)
    sys.exit()

ans = 1
for i in arr:
    ans *= i
    if ans > 10**18:
        print(-1)
        sys.exit()

else:
    print(ans)
### BUGGY CODE ###

s = str(input())

retn = 0

loop = True
while(loop):

    x = s.find("BC")
    if (x == -1):
        break

    if (x != 0):
        bb = s.rfind("B",0,x)
        cc = s.rfind("C",0,x)

        if (cc > bb):
            bb = cc
        retn += x - bb - 1
        s = "A" * (x - bb - 1) + s[x+2:]
    else:
        s = s[x+2:]

print(retn)

### FIXED CODE ###

s = str(input())
s = s.replace("BC","X")

retn = 0
cnt = 0

for i in range(len(s)):

    if (s[i] == "A"):
        cnt += 1
    elif (s[i] == "X"):
        retn += cnt
    else:
        cnt = 0

print(retn)