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

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

cnt = 0
for i in range(1, n + 1):
    for j in range(n - i + 1):
        number = int(s[j:j + i])
        if number % p == 0:
            cnt += 1

print(cnt)


### FIXED CODE ###

n, p = map(int, input(). split())
s = list(map(int, input()[::-1]))

cnt = 0
if 10 % p == 0:
    for i, c in enumerate(s):
        if int(c) % p == 0:
            cnt += n - i
else:
    accmod = [0] * p
    accmod[0] = 1
    num = 0
    for i in range(n):
        num = (num + s[i] * pow(10, i, p)) % p
        accmod[num] += 1
    for v in accmod:
        if v > 1:
            cnt += v * (v - 1) // 2
print(cnt)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
Nc = 1
e = 0
for i in range(N):
    if (N-A[i]-1) < 0:
        e = 1
        Nc = 0
        break
if e ==0:
    if A.count(0) >= 2:
        Nc *= 0
    else:
        for i in range(N-1):
                if A.count(i+1) == 2:
                    Nc *= 2
                elif A.count(i+1) ==0:
                    Nc *= 1
                else:
                    Nc *= 0
                    break

print(Nc%1000000007)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
Nc = 1
e = 0
B = [0]*N
for i in A:
    if (N-i-1) < 0:
        e = 1
        Nc = 0
        break
if e ==0:
    if A.count(0) >= 2:
        Nc *= 0
    else:
        if A.count(0) == 1:
            A.remove(0)
        for i in A:
            B[i] = B[i] + 1
        for i in B:
            if i == 2:
                Nc *= 2
            elif i == 0:
                Nc *= 1
            else:
                Nc *= 0
                break
print(Nc%1000000007)
### BUGGY CODE ###

import math
from functools import reduce

limit_num = int(input())

def gcd(*numbers):
	return reduce(math.gcd, *numbers)

result = 0
num_list =[1, 1, 1]

for num_1 in range(num_list[0], limit_num + 1):
	for num_2 in range(num_list[1], limit_num + 1):
		for num_3 in range(num_list[2], limit_num + 1):
			result = result + gcd([num_1, num_2, num_3])

print(int(result))


### FIXED CODE ###

import math
from functools import reduce
import itertools

def gcd(*numbers):
	return reduce(math.gcd, *numbers)

limit_num = int(input())
result_list = []
for num in itertools.product(range(1, limit_num + 1), repeat=3):
	result_list.append(gcd(num))

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

a,b=map(int,input().split())
for i in range(a,b+1):
  if i == a:
    c=a
  else:
    c = c ^ i
print(c)

### FIXED CODE ###

a,b=map(int,input().split())
def f(n):
  #XOR from 0 to n
  m=n//2
  if n % 4 == 0:
    return n
  elif n % 4 == 1:
    return (n-1)^n
  elif n % 4 == 2:
    return (n-2)^(n-1)^n
  else:
    return (n-3)^(n-2)^(n-1)^n
print(f(a-1)^f(b))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

INF = 10**9 + 7

res = 0

for i in range(N-1):
    for j in range(i+1,N):
        res += A[i] ^ A[j]
        res %= INF

print(res)


### FIXED CODE ###

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

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

A = np.array(A,np.int64)

mod = 10**9 + 7

res = 0

for i in range(60):
    count = np.count_nonzero(A & 1)
    res += (N - count) * count * 2 ** i
    res %= mod
    A >>= 1

print(res)
### BUGGY CODE ###

input_line1 = input()
input_line2 = input()

n = int(input_line1)
a_list = list(map(int, input_line2.split()))

for i in range(0, n):
    print(a_list[i:].count(i+1))


### FIXED CODE ###

n = int(input())
input_line2 = input()

a_list = list(map(int, input_line2.split()))

counts = [0 for i in range(n)]

for i in range(len(a_list)):
    counts[a_list[i]-1] += 1

for c in counts:
    print(c)
### BUGGY CODE ###

n=int(input())
x=1
for i in range(1,n+1):
    x=x*i
print(x%(10**9+7))

### FIXED CODE ###

n=int(input())
x=1
for i in range(1,n+1):
    x=x*i
    x=x%(10**9+7)
print(x)
### BUGGY CODE ###

from collections import Counter

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

c = Counter(a)

dp = [[[-1 for _ in range(n+1)] for _ in range(n+1)] for _ in range(n+1)]

def sushi(x, y, z):
    if dp[x][y][z] >= 0:
        return dp[x][y][z]
    if x == 0 and y == 0 and z == 0:
        return 0.0

    ret = 0.0
    if x > 0:
        ret += sushi(x-1, y, z) * x
    if y > 0:
        ret += sushi(x+1, y-1, z) * y
    if z > 0:
        ret += sushi(x, y+1, z-1) * z
    dp[x][y][z] = (ret + n) / (x + y + z)
    return dp[x][y][z]

print(sushi(c[1], c[2], c[3]))


### FIXED CODE ###

from collections import Counter

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

c = Counter(a)

dp = [[[0.0 for _ in range(n+1)] for _ in range(n+1)] for _ in range(n+1)]

for z in range(c[3] + 1):
    for y in range(c[2]+1 + c[3] - z):
        for x in range(n+1 - z - y):
            if x + y + z == 0:
                continue
            ret = 0.0
            if x > 0:
                ret += dp[x-1][y][z] * x
            if y > 0:
                ret += dp[x+1][y-1][z] * y
            if z > 0:
                ret += dp[x][y+1][z-1] * z
            dp[x][y][z] = (ret + n) / (x + y + z)

print(dp[c[1]][c[2]][c[3]])
### BUGGY CODE ###

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

### FIXED CODE ###

n,q=map(int,input().split())
s=input()
Sum=[0]
sum=0
stack="Q"
for i in range(n):
  if stack=="A" and s[i]=="C":
    sum+=1
  stack=s[i]
  Sum.append(sum)
for i in range(q):
  l,r=map(int,input().split())
  print(Sum[r]-Sum[l])
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
ans=[]
for i in range(1,N+1):
    for j in range(N):
        if i==A[j]:
            ans.append(j+1)
print(*ans)

### FIXED CODE ###

N=int(input())
values=list(map(int,input().split()))
keys=list(range(1,N+1))
d=dict(zip(keys,values))
e=sorted(d.items(), key=lambda x:x[1])
for i in range(N):
    print(e[i][0],end=" ")
### BUGGY CODE ###

A, B, C, D = map(int, input().split())

count = 0

for i in range(A, B+1):
    if i % C != 0:
        if i % D != 0:
             count += 1

print(count)

### FIXED CODE ###

import fractions

a, b, c, d = map(int, input().split())

# 最小公倍数を求める
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

def cal(num, a, b):
    x = num // a
    y = num // b
    z = num // (lcm(a, b))
    return num - (x + y - z)

num_a = cal(b, c, d)
num_b = cal(a-1, c, d)

print(num_a - num_b)
### BUGGY CODE ###

mul2019 = []
for i in range(2, 100):
    if str(i*2019).count("0")>0:
        continue
    mul2019.append(str(i*2019))
n = str(input())
cnt = 0
for j in range(4, len(n)):
    for i in range(len(n)-j+1):
        for r in mul2019:
            if str(r)==n[i:i+j]:
                cnt += 1 
print(cnt)

### FIXED CODE ###

s = input()[::-1] # 入力文字列を逆順でsに格納

counts = [0] * 2019
counts[0] = 1
#余りの数字がそれぞれ何回出たかカウント
#count[0]は「累積和的」に0%2019を考えるために1にしている

num, d = 0, 1
#numは余りの累積和、dはcharの桁数
for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d%= 2019
    counts[num] += 1
'''
charに一桁ずつ取り出す。そのMOD2019を考え、累積和をとる
しかし、それぞれの数字には10の累乗がかかっているのでそれについては別途dを用意してMOD2019をとる
つまり、numは1桁目のMOD2019、2桁目のMOD2019に1桁目のMOD2019に加える
'''

ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

print(ans) # 答えの出力
### BUGGY CODE ###

N = int(input())
A = tuple(map(int,input().split()))
mod = 1000000007
ans = 0
for i in range(N-1):
    for j in range(i+1,N):
        ans += (A[i] * A[j]) % mod
        ans %= mod
print(ans)

### FIXED CODE ###

N = int(input())
A = tuple(map(int,input().split()))
mod = 10**9+7
B = [0]*N
for i in range(N):
    B[i] = A[i]**2
s1, s2 = 0, 0 
for i in range(N):
    s1 += A[i]
    s2 += B[i]
s1 = s1**2
ans = (s1 -s2)//2%mod
print(ans)
### BUGGY CODE ###

n = int(input())
dll =[]
for i in range(n):
    command = input().split()
    if command[0] == 'insert':
        dll.insert(0, command[1])
    if command[0] == 'delete':
        for i in range(len(dll)):
            if dll[i] == command[1]: 
                dll.pop(i)
                break
    if command[0] == 'deleteFirst':
        dll.pop(0)
    if command[0] == 'deleteLast':
        dll.pop()

print(*dll)

### FIXED CODE ###

from collections import deque

n = int(input())
dll = deque()
for i in range(n):
    command = input().split()
    if command[0] == 'insert':
        dll.appendleft(command[1])
    elif command[0] == 'delete':
        try:
            dll.remove(command[1])
        except:
            pass
    elif command[0] == 'deleteFirst':
        dll.popleft()
    else:
        dll.pop()
print(*dll)
### BUGGY CODE ###

from collections import deque,defaultdict

N,M = map(int,input().split())
data = [list(map(int,input().split())) for i in range(M)]

G = defaultdict(list)
for i in range(M):
    G[data[i][0]].append(data[i][1])
    G[data[i][1]].append(data[i][0])

D = [0]+[-1]*(N)

c = 0
for i in range(1,N+1):
    if D[i] != -1:
        continue
    else:
        q = deque([i])
        while q:
            n = q.pop()
            D[n] = 0
            for d in G[n]:
                if D[d] != -1:
                    continue
                else:
                    q.append(d)
        c += 1

print(c)

### FIXED CODE ###

from collections import deque,defaultdict

N,M = map(int,input().split())
data = [list(map(int,input().split())) for i in range(M)]

G = defaultdict(list)
for i in range(M):
    G[data[i][0]].append(data[i][1])
    G[data[i][1]].append(data[i][0])

D = [0]+[-1]*(N)

c = 0
for i in range(1,N+1):
    if D[i] != -1:
        continue
    else:
        q = deque([i])
        while q:
            n = q.pop()
            D[n] = 0
            for d in G[n]:
                if D[d] != -1:
                    continue
                else:
                    q.append(d)
        c += 1

print(c)
### BUGGY CODE ###

import math
import sys
from itertools import accumulate


def E(i, x):
    if i == 1:
        return 5 * x
    return (2 * i + 1) * x


N, X = map(int, input().split())
x = list(map(int, input().split()))
x.sort()
x.reverse()
x = list(accumulate(x))
x = [0] + x
energy = sys.maxsize
for k in range(1, N + 1):
    cost = (N + k) * X
    for i in range(1, N + 1):
        if i * k <= N:
            cost += E(i, x[i * k] - x[(i - 1) * k])
        else:
            cost += E(i, x[-1] - x[(i - 1) * k])
            break
    energy = min(energy, cost)
print(energy)


### FIXED CODE ###

from itertools import accumulate
def E(i, x):
    if i == 1:
        return 5 * x
    return (2 * i + 1) * x
N, X = map(int, input().split())
x = list(map(int, input().split()))
x.sort(key=None, reverse=True)
x = list(accumulate(x))
x.insert(0, 0)
energy = 9223372036854775807
for k in range(1, N + 1):
    cost = (N + k) * X
    for i in range(1, N + 1):
        if i * k <= N:
            cost += E(i, x[i * k] - x[(i - 1) * k])
        else:
            cost += E(i, x[-1] - x[(i - 1) * k])
            break
    if cost < energy:
        energy = cost
print(energy)
### BUGGY CODE ###

n = int(input())
S = [int(a) for a in input().split()]
divisor = 10**9 + 7
tot = 0
for i in range(n-1):
  for j in range(i+1,n):
    tot += S[i]*S[j] 
    if tot >= divisor:
      tot = tot % divisor
    
print(tot)

### FIXED CODE ###

def multmod(a,b,m):
  ans = 0
  a = a % m
  
  while b:
    if (b & 1): # odd
      ans = (ans + a) % m
    
    a = (2 * a) % m
    b >>= 1 # b = b / 2
    
  return ans

n = int(input())
S = [int(a) for a in input().split()]
divisor = 10**9 + 7
tot = 0
a,b = 0,0
arr_sum = sum(S) #% divisor
arr_ssq = arr_sum*arr_sum #% divisor
isq_sum = 0
for i in range(n):
  isq_sum += S[i]*S[i] #% divisor
  
#isq_sum = isq_sum % divisor
tot = (arr_ssq - isq_sum)//2 % divisor

print(tot)
### BUGGY CODE ###

#ALDS1_4-B BinarySearch
n=input()
S=input().split()
q=input()
T=input().split()
c=0
for t in T:
    if(t in S):c+=1
print(c)

### FIXED CODE ###

#ALDS1_4-B BinarySearch
input()
S=input().split()
input()
T=input().split()
print(len(set(S)&set(T)))
### BUGGY CODE ###

l, r = map(int, input().split())

lt = []
for j in range(l, r+1, 1):
    for i in range(l, j):
        lt.append((i*j)%2019)
        
print(min(lt))

### FIXED CODE ###

l, r = map(int, input().split())

item = r-l+1
if item >= 2019:
    print(0)
else:
    lt = []
    for j in range(l, r+1):
        for i in range(l, j):
            lt.append((i*j)%2019)
    print(min(lt))
### BUGGY CODE ###

import numpy as np
import re
from sys import stdin

N, Q = [int(x) for x in stdin.readline().rstrip().split()]
S = stdin.readline().rstrip()

def func(Str):
  ac = re.findall("AC", Str)
  l_ac = len(ac)
  return l_ac

for j in range(Q):
  l,r = [int(x) for x in stdin.readline().rstrip().split()]
  print(func(S[l-1:r]))

### FIXED CODE ###

from sys import stdin

N, Q = [int(x) for x in stdin.readline().rstrip().split()]
S = stdin.readline().rstrip()

ac_idx = [0]
count = 0

for i in range(N-1):
  if S[i]=="A" and S[i+1]=="C":
    count+=1
  ac_idx.append(count)

for j in range(Q):
  l,r = [int(x) for x in stdin.readline().rstrip().split()]
  print(ac_idx[r-1]-ac_idx[l-1])
### BUGGY CODE ###

import sys
from functools import reduce

MOD = 10 ** 9 + 7

def gcd(a, b):
    while b:
        a, b = b, a % b
    return abs(a)

def lcm(a, b):
    return abs(a // gcd(a, b) * b)

n, *a = map(int, sys.stdin.read().split())

def main():
    l = reduce(lcm, a, 1)
    res = 0
    for i in a:
        res += l // i % MOD
        res %= MOD
    return res
    
if __name__ == '__main__':
    ans = main()
    print(ans)

### FIXED CODE ###

import sys

MOD = 10 ** 9 + 7

from math import floor, sqrt
from bisect import bisect_right as bi_r
from collections import defaultdict

def prime_nums(n=10**6):
    sieve = set(range(2, n + 1))
    non_prime = set(range(2 * 2, n + 1, 2))
    sieve -= non_prime
    for i in range(3, floor(sqrt(n)) + 1, 2):
        if i in sieve:
            non_prime = set(range(i * 2, n + 1, i))
            sieve -= non_prime
    return sieve

p_nums = sorted(prime_nums())

def make_inv_table(n=10**6, p=MOD):
    fac = [None] * (n + 1)
    fac[0] = 1
    for i in range(n):
        fac[i+1] = fac[i] * (i + 1) % p
    ifac = [None] * (n + 1)
    ifac[n] = pow(fac[n], p-2, p)
    for i in range(n, 0, -1):
        ifac[i-1] = ifac[i] * i % p
    inv = [None] * (n + 1)
    for i in range(1, n+1):
        inv[i] = ifac[i] * fac[i-1] % p
    return inv

inv = make_inv_table()

n, *A = map(int, sys.stdin.read().split())

def main():
    facs = defaultdict(int)
    for a in A:
        if a == 1:
            continue
        for p in p_nums[:bi_r(p_nums, sqrt(a))]:
            cnt = 0
            while not a % p:
                cnt += 1
                a //= p
            facs[p] = max(facs[p], cnt)
            if a == 1:
                break
        else:
            facs[a] = max(facs[a], 1)
    
    lcm = 1
    for f, c in facs.items():
        lcm *= pow(f, c, MOD)
        lcm %= MOD
    
    ans = 0
    for a in A:
        ans += lcm * inv[a] % MOD
        ans %= MOD
    return ans

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

N,M = map(int,input().split())
a=[0]*M
b=[0]*M
c=[] #最初の候補地

for i in range(M):
  a[i],b[i]=map(int,input().split())
  if a[i]==1:
    if b[i] not in c:
      c.append(b[i])
    
for j in range(M):
  if a[j]!=1:
    if a[j] in c:
      if b[j]==N:
        print("POSSIBLE")
        break
else:
  print("IMPOSSIBLE")

### FIXED CODE ###

N,M = map(int,input().split())
a=[0]*M
b=[0]*M
c=set() #最初の候補地

for i in range(M):
  a[i],b[i]=map(int,input().split())
  if a[i]==1:
    if b[i] not in c:
      c.add(b[i])
    
for j in range(M):
  if a[j]!=1:
    if a[j] in c:
      if b[j]==N:
        print("POSSIBLE")
        break
else:
  print("IMPOSSIBLE")
### BUGGY CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

n = INT()
a = LIST()
arr = [0 for _ in range(n + 1)]
arr[1] = a[0]
for i in range(1, n):
    arr[i + 1] = arr[i] + a[i]
setarr = set(arr)
countarr = [[0 for _ in range(max(setarr) - min(setarr) + 1)] for _ in range(n + 1)]
countarr[0][arr[0]] = 1
for i in range(1, n + 1):
    countarr[i] = deepcopy(countarr[i - 1])
    countarr[i][arr[i]] += 1
ans = 0
for i in range(n):
    s = arr[i]
    ans += countarr[n][s] - countarr[i][s]
print(ans)

### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

n = INT()
a = LIST()
arr = [0 for _ in range(n + 1)]
arr[1] = a[0]
for i in range(2, n + 1):
    arr[i] = arr[i - 1] + a[i - 1]
arr2= Counter(arr)
arr3 = list(set(arr))
ans = 0
for i in range(len(arr3)):
    ans += arr2[arr3[i]] * (arr2[arr3[i]] - 1) // 2
print(ans)
### BUGGY CODE ###

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

score = 1
for i in range(k):
  score *= arr[i]

s = 0

for i in range(k, n):
  tmp = score * arr[i] / arr[s]
  if tmp > score:
    print("Yes")
  else:
    print("No")
  score = tmp
  s += 1

### FIXED CODE ###

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

s = 0

for i in range(k, n):
  before = arr[s]
  after = arr[i]
  if after > before:
    print("Yes")
  else:
    print("No")
  s += 1
### BUGGY CODE ###

sa = str(raw_input())
sb = str(raw_input())
sc = str(raw_input())

n = 'a'
h = ''
while True:
    if n == 'a':
        if len(sa) < 1:
            break
        h, sa = sa[0], sa[1:]
        n = h
    elif n == 'b':
        if len(sb) < 1:
            break
        h, sb = sb[0], sb[1:]
        n = h
    elif n == 'c':
        if len(sc):
            break
        h, sc = sc[0], sc[1:]
        n = h

print str.upper(n)


### FIXED CODE ###

a = int(raw_input())
b = int(raw_input())
h = int(raw_input())

s = (a + b) * h/2

print s
### BUGGY CODE ###

S=(input())
Q=int(input())
cnt_re=0
for i in range(Q):
    q=list(input().split())
    if q[0]=='1':
        cnt_re+=1
    else:
        if (int(q[1])+cnt_re)%2==1:
            S=q[2]+S
        else:
            S=S+q[2]

if cnt_re%2==1:
    print(S[::-1])
else:
    print(S)

### FIXED CODE ###

S=(input())
Q=int(input())
cnt_re=0
s=''
for i in range(Q):
    q=list(input().split())
    if q[0]=='1':
        cnt_re+=1
    else:
        if (int(q[1])+cnt_re)%2==1:
            s=s+q[2]
        else:
            S=S+q[2]
if cnt_re%2==1:
    print(S[::-1]+s)
else:
    print(s[::-1]+S)
### BUGGY CODE ###

a, b = map(int, input().split())
ans = 200000
for i in range(a, b):
    for j in range(a+1, b+1):
        ans = min(ans, i*j%2019)
        if ans == 0:
            break

print(ans)

### FIXED CODE ###

a, b = map(int, input().split())
ans = 20000000
n = a//2019
m = b//2019
a = a % 2019
b = b % 2019

if a > b:
    ans = 0
else:
    for i in range(a, b):
        for j in range(a+1, b+1):
            ans = min(ans, i*j%2019)
if m != n:
    ans = 0

if a == b:
    ans = 0

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


n = int(input())
s = list([input() for i in range(n)])
q = []
c = 0
for i in range(n):
	q.append(sorted(s[i]))

for i in range(n):
	for j in range(n):
		if i != j:
			if q[i] == q[j]:
				c += 1

print(int(c/2))

### FIXED CODE ###

n = int(input())
s = list([input() for i in range(n)])
q = [''.join(sorted(x)) for x in s]

c = 0
c1 =  0
p = sorted(q)
p.append("a")

for i in range(n):
	if p[i] == p[i+1]:
		c+=1
	else:
		
		if c>0:
			for j in range(c+1):
				c1+=j
				
		c=0
print(c1)
### BUGGY CODE ###

def main():
  s = input()
  q = int(input())
  t = ""
  for i in range(q):
    tm = input()
    if tm[0] == '1':
      s = s[::-1]
    else:
      if tm[2] == '1':
        s = tm[4] + s
      else:
        s = s + tm[4]
  print(s)


main()

### FIXED CODE ###

from collections import deque
 
s = input()
q = int(input())
 
query = [input().split() for i in range(q)]
 
a = deque([s])
 
flag = True
 
for i in range(q):
    if query[i][0] == "1":
        flag = not(flag)
    else:
        if (query[i][1] == "1" and flag) or (query[i][1] != "1" and not(flag)):
            a.appendleft(query[i][2])
        else:
            a.append(query[i][2])
 
b = "".join(a)
if not(flag):
    b = b[::-1]
 
print(b)
### BUGGY CODE ###

n = int(input())
train_info = []
for _ in range(1, n):
    train_info.append(list(map(int, input().split())))

# print(train_info)

for i in range(1, n + 1):
    # print("i = {}".format(i))
    t = 0

    if i == n:
        print(0)
    else:
        for j in range(i, n):
            C_j, S_j, F_j = train_info[j - 1]
            while True:
                if (t >= S_j) & (t % F_j == 0):
                    t += C_j
                    break
                else:
                    t += 1

        print(t)


### FIXED CODE ###

n = int(input())
train_info = []
for _ in range(1, n):
    train_info.append(list(map(int, input().split())))

# print(train_info)

for i in range(1, n + 1):
    # print("i = {}".format(i))
    t = 0

    if i == n:
        print(0)
    else:
        for j in range(i, n):
            # print("t = {}".format(t))
            C_j, S_j, F_j = train_info[j - 1]
            if t <= S_j:
                t = S_j + C_j
            elif t % F_j == 0:
                t += C_j
            else:
                t += F_j - t % F_j
                t += C_j

        print(t)
### BUGGY CODE ###

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

if p == 2:
    ans = 0
    for i in range(n):
        if s[i] % 2 == 0:
            ans += i+1
    print(ans)
    exit()

if p == 5:
    ans = 0
    for i in range(n):
        if s[i] == 0 or s[i] == 5:
            ans += i+1
    print(ans)
    exit()


po10 = [1]
for i in range(n-1):
    po10.append((po10[-1]*10) % p)

for i in range(n):
    s[i] *= po10[n-1-i]
    s[i] %= p

ss = [0]

for i in range(n):
    ss.append(ss[-1]+s[i])
    ss[-1] %= p

ans = 0

for i in range(p):
    tmp = ss.count(i)
    ans += tmp*(tmp-1)//2

print(ans)


### FIXED CODE ###

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

if p == 2:
    ans = 0
    for i in range(n):
        if s[i] % 2 == 0:
            ans += i+1
    print(ans)
    exit()

if p == 5:
    ans = 0
    for i in range(n):
        if s[i] == 0 or s[i] == 5:
            ans += i+1
    print(ans)
    exit()


po10 = [1]
for i in range(n-1):
    po10.append((po10[-1]*10) % p)

for i in range(n):
    s[i] *= po10[n-1-i]
    s[i] %= p

ss = [0]

for i in range(n):
    ss.append(ss[-1]+s[i])
    ss[-1] %= p


ss = sorted(ss)

ll = len(ss)

ans = 0
tmp = [0,0]
for i in range(ll):
    if ss[i] != tmp[0]:
        ans += (i-tmp[1])*(i-tmp[1]-1) //2
        tmp[0] = ss[i]
        tmp[1] = i

ans += (ll-tmp[1])*(ll-tmp[1]-1)//2

print(ans)