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

#組み合わせnCr　１
from functools import reduce
def nCr(n,r,DIV):
  if r<n-r:
    r=n-r
  if r==0:
    return 1
  f=lambda x,y:x*y%DIV
  X=reduce(f,range(n-r+1,n+1))
  Y=reduce(f,range(1,r+1))
  return X*pow(Y,DIV-2,DIV)%DIV

n, a, b = map(int, input().split())
mod = pow(10, 9) + 7
ans = pow(2, n, mod) - nCr(n, a, mod) - nCr(n, b, mod) - 1
print(ans)

### FIXED CODE ###

def cmb(n, r, p):
    r = min(r, n - r)
    upper = 1
    for i in range(n, n - r, -1):
        upper = (upper * i) % p

    lower = 1
    for i in range(1, r + 1):
        lower = (lower * i) % p

    # フェルマーの小定理よりp素数ならupper**(p-2)は逆元
    return (upper * pow(lower, p - 2, p)) % p

mod = pow(10, 9) + 7
n, a, b = map(int, input().split())
ans = (pow(2, n, mod) - 1 - cmb(n, a, mod) - cmb(n, b, mod))%mod
print(ans)
### BUGGY CODE ###

from sys import stdin
from collections import defaultdict,deque
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n)]
        self.rank = [0]*n
        self.n = n
    def find(self,x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]
    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:return
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    def same(self,x,y):
        return bool(self.find(x)==self.find(y))

    def allset(self):
        d = defaultdict(list)
        for i in range(self.n):
            d[self.find(i)] += [i]
        t = list(d.keys())
        for i in t:
            d[i].sort()
            d[i] = deque(d[i])
        return d

def main():
    N,M = map(int,stdin.readline().split())
    uf = UnionFind(N)
    p = list(map(int,stdin.readline().split()))
    ans = 0
    for _ in range(M):
        x,y = map(int,stdin.readline().split())
        x -= 1
        y -= 1
        uf.union(x,y)
    d = uf.allset()
    for i in range(N):
        p[i] -= 1
    for i in range(N):
        tmp = p[i]
        r = uf.find(tmp)
        if uf.same(r,i):
            pre = int(p[i])
            if i in d[r]:
                new = i
                #d[r].remove(i)
            else:
                new = d[r].popleft()
            swap = p.index(new)
            p[i] = new
            p[swap] = pre
    for i in range(N):
        if p[i] == i:ans += 1
    print(ans)
    #print(*list(map(lambda x:x+1,p)))
if __name__ == "__main__":
    main()

### FIXED CODE ###

from sys import stdin
from collections import defaultdict,deque
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n)]
        self.rank = [0]*n
        self.n = n
    def find(self,x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]
    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:return
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    def same(self,x,y):
        return bool(self.find(x)==self.find(y))



def main():
    N,M = map(int,stdin.readline().split())
    uf = UnionFind(N)
    p = list(map(int,stdin.readline().split()))
    p = list(map(lambda x: x-1,p))
    ans = 0
    for _ in range(M):
        x,y = map(int,stdin.readline().split())
        x -= 1
        y -= 1
        uf.union(x,y)
    for i in range(N):
        tmp = p[i]
        if not uf.same(tmp,i):continue
        else:ans += 1
    print(ans)
    #print(*list(map(lambda x:x+1,p)))
if __name__ == "__main__":
    main()
### BUGGY CODE ###

#ABC 104 C - All Green
#順列総当たりでやる

import itertools

d, g = map(int, input().split())
#print(d)
p=[]
c=[]
ld = []
for i in range(d):
  pk, ck = map(int, input().split())
  p.append(pk)
  c.append(ck)
  ld.append(i)

jun = list(itertools.permutations(ld))
ans=10000

for j in jun:
  #順列の数だけ試す。j[番号]で調べてる順列の番号番目の数を返す
  ten = 0
  mondaisu = 0
  for k in range(d):
    bango = j[k]
    katen = (bango + 1)*100*p[bango] + c[bango]
#    print("n問目"+str(bango +1) + "加点"+ str(katen))
    if ten + katen > g:
      nokori = ((g-ten)-1)//((bango + 1)*100) + 1
      if nokori > p[bango]:#ボーナス点がないと届かない場合
        mondaisu += p[bango]
      else:
        mondaisu += nokori
      break
    else:
      ten += katen
      mondaisu += p[bango]
  if ans > mondaisu:
    ans = mondaisu
#  print(str(j) + "問題数" + str(mondaisu) +"答えリスト")
#  print(ans_list)
        
print(ans)      
  
#print(jun[0][1])

  
#print(p)
#print(c)

### FIXED CODE ###

#ABC 104 C - All Green

#ビット総当たりでやる

d, g = map(int, input().split())
#print(d)

p=[]
c=[]

for i in range(d):
  pk, ck = map(int, input().split())
  p.append(pk)
  c.append(ck)
#print(p)
#print(c)
  
ans = 10000#仮の答え

#2^d通り試す
for i in range(2 ** d):
  #右からn番目の桁が1→n+1の配点の問題を完全に解く
  ten = 0
  mondaisu = 0
  for j in range(d):
    if (i>>j)&1 == 1:
      #p[j]個あるj+1の配点の問題を完全に解く
      ten += (j+1)*100*p[j] + c[j]
      mondaisu += p[j]
    else:
      #p[j]個あるj+1の配点の問題は完全にとかない
      k = j
  #フラグの立った配点の問題を全部といた
  if ten > g:
    if ans > mondaisu:
      ans = mondaisu
  else:
    #中途半端に解かないと行けない場合p[k]の問題を中途半端に解く
    if g-ten <= (k+1)*100*p[k] :
      mondaisu += (g-ten-1)//((k+1)*100) +1
      if ans > mondaisu:
        ans = mondaisu
      #中途半端に解いて届かない場合スルー
#  print(mondaisu)    
print(ans)
### BUGGY CODE ###

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

d = [0]*60
for ai in aa:
  for e,i in enumerate(bin(ai)[:1:-1]):
    d[e]+=int(i)  

ans = 0
for i in range(len(d)):
  if d[i]==0 or d[i]==n:
    pass
  else:     
    #print(d[i]*(n-d[i])* 2**(i))
    ans += d[i]*(n-d[i])* 2**(i)
    
print(ans % (10**9+7))    

### FIXED CODE ###

## D
MOD = 10**9 + 7
n = int(input())
A = list(map(int,input().split()))

m = 1
ans = 0
for i in range(60):
  s = sum([a&m for a in A])
  s//=m
  ans = (ans + (n-s)*s * m) % MOD
  m <<= 1
  
print(ans)
### BUGGY CODE ###

import functools
import fractions
import itertools

n = int(input())
as_ = [int(i) for i in input().split()]


def gcds(list_):
    return list(itertools.accumulate(list_, fractions.gcd))


def rotate(list_):
    list_ = list_[1:] + list_[0:1]
    return list_


max_cand = []
for i in range(len(as_)):
    as_ = as_[1:] + as_[0:1]
    max_cand.append(gcds(as_)[-2])


print(max(max_cand))


### FIXED CODE ###

import fractions
import itertools

n = int(input())
as_ = [int(i) for i in input().split()]


def gcds(list_):
    return list(itertools.accumulate(list_, fractions.gcd))


def reversed_gcds(list_):
    return list(itertools.accumulate(reversed(list_), fractions.gcd))


as_accum_gcd, as_rev_accum_gcd = gcds(as_), reversed_gcds(as_)

dropped_gcds = []
for i in range(len(as_)):
    if i == 0:
        dropped_gcd = as_rev_accum_gcd[-2]
    elif i == len(as_) - 1:
        dropped_gcd = as_accum_gcd[-2]
    else:
        dropped_gcd = fractions.gcd(as_accum_gcd[i - 1], as_rev_accum_gcd[-2 - i])
    dropped_gcds.append(dropped_gcd)

print(max(dropped_gcds))
### BUGGY CODE ###

n = int(input())
S = str(input())
r = []
g = []
b = []
for i in range(n):
    if S[i] == 'R':
        r.append(i)
    elif S[i] == 'G':
        g.append(i)
    else:
        b.append(i)
#print(r, g, b)
ans=0
for R in r:
    for G in g:
        #print(R,G)
        for B in b:
            l=[R,G,B]
            l.sort()
            if l[1]-l[0]!=l[2]-l[1]:
                ans+=1
print(ans)

### FIXED CODE ###

n=int(input())
S=str(input())
r=S.count('R')
g=S.count('G')
b=S.count('B')
cnt=r*g*b
for i in range(n):
    for a in range(1,n):
        j=i+a
        k=j+a
        if k>=n:
            break
        if S[i]!=S[j] and S[j]!=S[k] and S[k]!=S[i]:
            cnt-=1

print(cnt)
### BUGGY CODE ###

N, W = map(int, input().split())
dp_pv = [0]*(W+1)

for i in range(N):
    w, v = map(int, input().split())
    
    dp = [dp_pv[j] if w > j else max(dp_pv[j], dp_pv[j-w]+v) for j in range(W+1)]
    dp_pv = dp
    #print(dp)
    
print(dp[-1])
    

### FIXED CODE ###

N, W = map(int, input().split())
dp_pv = [0]*(W+1)

for i in range(N):
    w, v = map(int, input().split())
    
    dp = [dp_pv[j] if w > j else max(dp_pv[j], dp_pv[j-w]+v) for j in range(W+1)]
    dp_pv = dp
    #print(dp)
    
print(dp[-1])
### BUGGY CODE ###

N = int(input())
As = list(map(int, input().split()))
m = 10**9 + 7
result = 0
for i in range(N-1):
  p = As[i]
  cs_mod = sum(As[i+1:]) % m
  result += ((cs_mod * p) % m)
print(result % m)

### FIXED CODE ###

N = int(input())
As = list(map(int, input().split()))
m = 10**9 + 7
result = 0
As_sum = sum(As)
for i in range(N-1):
  As_sum = As_sum - As[i]
  result += (As[i] * As_sum) % m

print(result % m)
### BUGGY CODE ###

def IsPrime(n):
    if n == 2:
        return True
    if n < 2 or n % 2 == 0:
        return False
    for i in range(3, int(n ** 0.5 + 1), 2):
        if n % i == 0:
            return False
    return True


n = int(input())
q = [list(map(int, input().split())) for _ in range(n)]
for i in range(n):
    l, r = q[i]
    cnt = 0
    for j in range(l, r + 1, 2):
        if IsPrime(j) and IsPrime((j + 1) // 2):
            cnt += 1
    print(cnt)


### FIXED CODE ###

lim = 10 ** 5

primes = [True] * (lim + 1)
primes[0], primes[1] = False, False
for i in range(2, int(lim ** 0.5) + 1):
    if primes[i]:
        for j in range(i * 2, lim, i):
            primes[j] = False

like = [False] * (lim + 1)
for i in range(1, lim + 1):
    if primes[i] and primes[(i + 1) // 2]:
        like[i] = True

cumsum = [0] * (lim + 1)
for i in range(1, lim + 1):
    if like[i]:
        cumsum[i] = cumsum[i - 1] + 1
    else:
        cumsum[i] = cumsum[i - 1]

n = int(input())
q = [list(map(int, input().split())) for _ in range(n)]
for i in range(n):
    l, r = q[i]
    ans = cumsum[r] - cumsum[l - 1]
    print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sat Jul 20 20:53:54 2019

@author: ctiuser
"""

N = int(input())
A = [int(input()) for i in range(N)]

ans = [A[0]]

for i in range(1,N):
    l,r = 0, len(ans)-1
    p = (r-0)//2 + 1
    if A[i] <= ans[r]:
        ans.append(A[i])
    elif A[i] > ans[l]:
        ans[l] = A[i]
    else:
        tmp = p
        while r - l > 1:
            if A[i] > ans[p]:
                tmp = p
                r = p
                p = (r-l-0)//2 + 0
            else:
                l = p
                p = (r-l-0)//2 + 0
        ans[tmp] = A[i]
        
#    if i == 6:
#        break
    
#    print(i,ans)
print(len(ans))



### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sat Jul 20 20:53:54 2019

@author: ctiuser
"""

N = int(input())
A = [int(input()) for i in range(N)]

ans = [A[0]]

for i in range(1,N):
    l,r = 0, len(ans)-1
    p = (r-l)//2 + 1
    if A[i] <= ans[r]:
        ans.append(A[i])
    elif A[i] > ans[l]:
        ans[l] = A[i]
    else:
        tmp = r
        while r - l > 1:
            if A[i] > ans[p]:
                tmp = p
                r = p
                p = (r-l)//2 + l
            else:
                l = p
                p = (r-l)//2 + l
        ans[tmp] = A[i]
#    print(i,ans)
print(len(ans))
### BUGGY CODE ###

N,K,Q=map(int,input().split())
Q_list=[input() for i in range(Q)]  



for i in range(1,N+1):
  a=Q_list.count(str(i))
  c=K-Q+a
  if c<=0:
    print("No")
  else:
    print("Yes")



### FIXED CODE ###

N,K,Q=map(int,input().split())

A=[K]*N
for i in range(Q):
  a=int(input())
  A[a-1] +=1
for i in range(len(A)):
  
  if A[i]-Q<=0:
    print("No")
  else:
    print("Yes")
### BUGGY CODE ###

import copy
N , C = map(int, input().split())
ds =[list(map(int, input().split())) for i in range(C)]
cs =[list(map(int, input().split())) for i in range(N)]
c0 = []
c1 = []
c2 = []
for i in range(N):
    for j in range(N):
        if (i+j) % 3 == 0:
            c0.append(cs[i][j])
        elif (i+j) % 3 == 1:
            c1.append(cs[i][j])
        else:
            c2.append(cs[i][j])
d = 10**9
l0 = len(c0)
l1 = len(c1)
l2 = len(c2)
for i in range(C):
    d0 = 0
    for l in range(l0):
         if (c0[l]-1) != i:
            d0 += ds[c0[l]-1][i]
    for j in range(C):
        if i == j:
            continue
        d1 = copy.copy(d0)
        for h in range(l1):
            if (c1[h]-1) != j:
                d1 += ds[c1[h]-1][j]
        for k in range(C):
            if i == k or j == k:
                continue
            d2 = copy.copy(d1)
            for l in range(l2):
                if (c2[l]-1) != k:
                    d2 += ds[c2[l]-1][k]
            if d > d2:
                d = d2
print(d)





### FIXED CODE ###

import collections
N , C = map(int, input().split())
ds =[list(map(int, input().split())) for i in range(C)]
cs =[list(map(int, input().split())) for i in range(N)]
c0 = collections.defaultdict(int)
c1 = collections.defaultdict(int)
c2 = collections.defaultdict(int)
for i in range(N):
    for j in range(N):
        if (i+j) % 3 == 0:
            c0[cs[i][j]] += 1
        elif (i+j) % 3 == 1:
            c1[cs[i][j]] += 1
        else:
            c2[cs[i][j]] += 1
            
d = 10**9
for i in range(C):
    for j in range(C):
        if i == j:
            continue
        for k in range(C):
            if i == k or j == k:
                continue
            d0 = 0
            for l in c0:
                d0 += c0[l] * ds[l-1][i]
            for l in c1:
                d0 += c1[l] * ds[l-1][j]
            for l in c2:
                d0 += c2[l] * ds[l-1][k]
            if d > d0:
                d = d0
            
print(d)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
QS = []

for _ in range(Q):
    l, r = map(int, input().split())
    QS.append((l, r))

ans = []
for l, r in QS:
    s = S[l - 1: r]
    print(s.count("AC"))


### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
QS = []

l = [0, 0]
last = S[0]
for i in range(1, len(S)):
    if last == 'A' and S[i] == 'C':
        l.append(l[-1] + 1)
    else:
        l.append(l[-1])
    last = S[i]

for _ in range(Q):
    left, right = map(int, input().split())
    QS.append((left, right))

# print(l)
for left, right in QS:
    ans = l[right] - l[left]
    print(ans)
### BUGGY CODE ###

n,m=list(map(int, input().split()))
a=list(map(int,input().split()))
while m>0:
  a.sort()
  for _ in range(m):
    a[n-1] //= 2
    m -= 1
    if a[n-1] < a[n-2]:
      break
print(sum(a))

### FIXED CODE ###

n,m=list(map(int, input().split()))
a=list(map(int, input().split()))
a.sort(reverse=True)
while m>0:
  a[0] //= 2
  m = m - 1
  for i in range(n-1):
    if a[0] < a[i+1] and m > 0:
      a[i+1] //= 2
      m = m - 1
    else:
      a.sort(reverse=True)
      break
print(sum(a))
### BUGGY CODE ###

N = int(input())
L = list(map(int, input().split()))
L.sort()
from numba import njit, jit
from itertools import combinations


@jit
def solve():
    ans = 0
    for a, b, c in combinations(L, r=3):
        ans += a + b > c
    return ans


print(solve())


### FIXED CODE ###

# 入力が10**5とかになったときに100ms程度早い
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


N = read_a_int()
L = read_ints()
L.sort()
# import numpy as np
# L = np.array(L)
from bisect import bisect_left

cnt = 0
for i in range(N):
    a = L[i]
    for j in range(i+1, N):
        b = L[j]
        # ここで二分探索するか
        cnt += bisect_left(L, a+b) - (j+1)
        # L_tmp = L[j+1:]
        # cnt += np.sum(L_tmp < b+a)

print(cnt)
### BUGGY CODE ###

N = int(input())
S = list(int(i) for i in input().split())  
list = []
count = 0

for i in range(N):
    if S[i] not in list:
        if S.count(S[i]) < S[i]:
            count += S.count(S[i])
        elif S.count(S[i]) > S[i]:
            count += (S.count(S[i])-S[i])
        list.append(S[i])

print(count)

### FIXED CODE ###

N = int(input())
S = list(int(i) for i in input().split())  
dict = {}
count = 0

for i in range(N):
    if S[i] not in dict:
        dict[S[i]] = 1
    else:
        dict[S[i]] += 1

for key, value in dict.items():
    if key < value:
        count += (value-key)
    elif key > value:
        count += value

print(count)
### BUGGY CODE ###

def list_counter(num_list,num):
    counter = 0
    for n in num_list:
        if n == num:
            counter +=1
    return counter

n = int(input())
a_list = [int(num) for num in input().split(" ")]
a_set = set(a_list)
total_comb = 0
for i in a_set:
    i_count = list_counter(a_list,i)
    total_comb += i_count*(i_count-1)
total_comb = int(total_comb/2)
for k in range(n):
    except_num = a_list[k]
    print(total_comb - (list_counter(a_list,except_num)-1))


### FIXED CODE ###

import collections

n = int(input())
a_list = [int(num) for num in input().split(" ")]
c_dict = collections.Counter(a_list)

total_comb = 0
for i in c_dict:
    i_count = c_dict[i]
    total_comb += int(i_count*(i_count-1)/2)
for k in range(n):
    except_num = a_list[k]
    print(total_comb - (c_dict[except_num]-1))
### BUGGY CODE ###

MAX = int(1e6)+2


n = int(input())
lis = list(map(int,input().split()))
lis2 = [0]*MAX
# lis.sort()
# m = max(lis)
ans = 0
for num in lis:
    lis2[num] += 1

for num in lis:
    for i in range(num*2, MAX, num):
        if lis2[i] > 0:
            lis2[i] += 1

print(len([i for i in lis if lis2[i] == 1]))

### FIXED CODE ###

# MAX = int(1e6)+2


n = int(input())
lis = list(map(int,input().split()))
lis.sort()
MAX = lis[-1]
lis2 = [0]*(MAX+1)
# lis.sort()
# m = max(lis)
ans = 0

for num in lis:
    for i in range(num, MAX+1, num):
            lis2[i] += 1

for j in set(lis):
    if lis2[j] == 1:
        ans += 1
print(ans)
### BUGGY CODE ###

# coding: utf-8

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

A = list(map(int,input().split()))
A.sort(reverse=True)

for i in range(M):
    B, C = list(map(int,input().split()))
    A = A + [C] * B
    A.sort(reverse=True)
    A = A[0:N]

print(sum(A))

### FIXED CODE ###

# coding: utf-8

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

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

tmp = {}
for i in A:
    if i in tmp.keys():
        tmp[i] += 1
    else:
        tmp[i] = 1 

for i in range(M):
    B, C = list(map(int,input().split()))
    if C in tmp.keys():
        tmp[C] += B
    else:
        tmp[C] = B

ans = 0
for i in sorted(tmp.keys(), reverse = True):
    if N >= tmp[i]:
        N -= tmp[i]
        ans += i * tmp[i]
    else:
        ans += i * N
        break
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
kitai = [0] * n
ans = 0
for i in range(n):
    kitai[i] += (p[i] + 1) / 2
for i in range(n):
    ans = max(sum(kitai[i:i+k]), ans)
print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
kitai = [0] * n
ans = 0
for i in range(n):
    kitai[i] += (p[i] + 1) / 2
ruiseki = [0] * (n + 1)
for i in range(1, n + 1):
    ruiseki[i] += ruiseki[i - 1] + kitai[i - 1]
for i in range(n - k + 1):
    ans = max(ans, ruiseki[k + i] - ruiseki[i])
print(ans)
### BUGGY CODE ###

l = list(map(int,input().split()))
a = l[0]
b = l[1]
n = l[2]

def floor(a,b,x):
    p = (a*x)//b - a*(x//b)
    return p

max = 0
if n < b-1:
    for i in range(n+1):
        c = floor(a,b,i)
        if c >= max:
            max = c
else:
    for i in range(b-1,n+1,b):
        c = floor(a,b,i)
        if c >= max:
            max = c

print(max)

### FIXED CODE ###

l = list(map(int,input().split()))
a = l[0]
b = l[1]
n = l[2]

def floor(a,b,x):
    p = (a*x)//b - a*(x//b)
    return p

max = 0
if b == 1:
    max = 0
elif n <= b-1:
    max = floor(a,b,n)
elif n > b-1:
    for i in range(b-1,n+1,b):
        c = floor(a,b,i)
        if c >= max:
            max = c

print(max)
### BUGGY CODE ###

import sys
if __name__ == '__main__':
    lines = sys.stdin.readlines()
    line = [a.strip('\n').split(' ') for a in lines]
    for i,v in enumerate(line):
        if i == 0:
            n = int(v[0])
            p = int(v[1])
        else:
            numbers = list(v[0])
            # print(numbers)

    count = 0
    for i in range(n):
        for j in range(i+1,n+1):
            strs = ''.join(numbers[i:j])
            num = int(strs)
            if num%p==0:
                count += 1

    print(count)

### FIXED CODE ###

from collections import Counter

N, P = map(int, input().split())
S = input()

c = 0

if P == 2 or P == 5:
    for i,v in enumerate(S):
        if int(v) % P == 0:
            c += (i+1)

else:
    T = [0]*(N+1)
    d = 1
    for i,v in enumerate(S[::-1]):
        a = (int(v) * d + T[i])% P
        T[i+1] = a
        d *= 10
        d %= P
    count = Counter(T)

    c = sum(x * (x -1) / 2 for x in count.values())

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

N = int(input())
S = [input() for _ in range(N)]
dic = {}
for s in S:
    if s in dic:
        dic[s] += 1
    else:
        dic[s] = 1

for key, value in sorted(dic.items()):
    if value == max(dic.values()):
        print(key)


### FIXED CODE ###

N=int(input())
S=[input() for i in range(N)]
dictionary={}
for word in S:
    if word in dictionary:
        dictionary[word]+=1
    else:
        dictionary[word]=1
maximum=max(dictionary.values())
for key,value in sorted(dictionary.items()):
    if value==maximum:
        print(key)