Harryxun/stf_run huggingface dataset:
import math


def main():
    n = int(input())
    a = list(map(int, input().split()))
    print(solution(n, a))  
    gcd_left = [0]
    gcd_right = [0]
    for i in range(n):
        gcd_left.append(math.gcd(gcd_left[i], a[i]))
        # 順に(0とa[-1]), (a[-1]とa[-2]),...の比較
        # 要は右端から順にgcdを求めている
        gcd_right.append(math.gcd(gcd_right[i], a[-(i + 1)]))

    gcd_right = gcd_right[::-1]  # gcd_right[i]がi番目以降のgcdとなるように反転

    ans = []
    for i in range(n):
        ans.append(math.gcd(gcd_left[i], gcd_right[i + 1]))


    return max(ans)

if __name__ == '__main__':
  
    main()

### FIXED CODE ###

import unittest
import fractions


def solution(n, a):
    gcd_left = [0]
    gcd_right = [0]
    for i in range(n):
        gcd_left.append(fractions.gcd(gcd_left[i], a[i]))
        # 順に(0とa[-1]), (a[-1]とa[-2]),...の比較
        # 要は右端から順にgcdを求めている
        gcd_right.append(fractions.gcd(gcd_right[i], a[-(i + 1)]))

    gcd_right = gcd_right[::-1]  # gcd_right[i]がi番目以降のgcdとなるように反転

    ans = []
    for i in range(n):
        ans.append(fractions.gcd(gcd_left[i], gcd_right[i + 1]))


    return max(ans)


class MyTestCase(unittest.TestCase):
    def test1(self):
        self.assertEqual(solution(3, [7, 6, 8]), 2)

    def test2(self):
        self.assertEqual(solution(3, [12, 15, 18]), 6)

    def test3(self):
        self.assertEqual(solution(2, [1000000000, 1000000000]), 1000000000)




if __name__ == '__main__':

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

    unittest.main()
N, M, Q = map(int, input().split())
dp = [[0]*N for i in range(N)]
for i in range(M):
  l, r = map(int, input().split())
  dp[r-1][l-1] += 1
for i in range(N):
  for j in range(N, 0, -1):
    dp[i][j-1] += dp[i][j]
for j in range(N):
  for i in range(N-1):
    dp[i+1][j] += dp[i][j]
for i in range(Q):
  p, q = map(int, input().split())
  print(dp[q-1][p-1])

### FIXED CODE ###

N, M, Q = map(int, input().split())
dp = [[0]*N for i in range(N)]
for i in range(M):
  l, r = map(int, input().split())
  dp[r-1][l-1] += 1
for i in range(N):
  for j in range(N-1, 0, -1):
    dp[i][j-1] += dp[i][j]
for j in range(N):
  for i in range(N-1):
    dp[i+1][j] += dp[i][j]
for i in range(Q):
  p, q = map(int, input().split())
  print(dp[q-1][p-1])
#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) # dijkstra# floyd_warshall
#from scipy.sparse import csr_matrix
 
from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)
#input=sys.stdin.readline  #危険！基本オフにしろ！
 
def main():
    s=input()
    t=input()
    ans=0
    for i in range(3):
        if s[i]==t[i]:
            ans+=1
    print(ans)
    
    
    
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) # dijkstra# floyd_warshall
#from scipy.sparse import csr_matrix
 
from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)
#input=sys.stdin.readline  #危険！基本オフにしろ！
 
def main():
    a,b=map(int,input().split())
    if b>1:
        if b<=a:
            print(1)
        else:
            b-=a
            print((b-1)//(a-1)+2)
    else:
        print(0)
if __name__ == '__main__':
    main()
import collections

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(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 unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        else:
            self.parent[x] = y

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

for i in range(M):
    A, B = map(int, input().split())
    tree.unite(A-1, B-1)

roots = [tree.find(p) for p in tree.parent]
count = collections.Counter(roots).most_common(1)[0][1]
print(count)


### FIXED CODE ###

import collections

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * 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 unite(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 self.find(x) == self.find(y)

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

for i in range(M):
    A, B = map(int, input().split())
    tree.unite(A-1, B-1)

roots = [tree.find(p) for p in tree.parent]
count = collections.Counter(roots).most_common(1)[0][1]
print(count)
N, M = map(int, input().split())

R = [[] for _ in range(M)]
for i in range(M):
    a, b = map(int, input().split())
    R[a-1].append(b-1)
    R[b-1].append(a-1)

S = [-1] * N
S[0] = 0
NXT = [[] for _ in range(N)]  # 最大ステップ
NXT[0] = [0]

for s in range(N):
    for k in NXT[s]:  # sステップ目で到達
        for i in R[k]:
            if S[i] == -1:  # 未更新
                S[i] = k
                NXT[s+1].append(i)

    if S.count(-1) == 0:
        break

print("Yes")
for i in range(1,N):
    print(S[i]+1)

### FIXED CODE ###

from collections import deque

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

R = [[] for _ in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    R[a-1].append(b-1)
    R[b-1].append(a-1)

def bfs(u):
    
    q = deque()
    q.append(u)
    while q:
        r = q.popleft()
        for v in R[r]:
            if S[v] == -1:
                S[v] = r
                q.append(v)

S = [-1] * N
S[0] = 0

bfs(0)

print("Yes")
for i in range(1,N):
    print(S[i]+1)
H, W = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
B = [list(map(int, input().split())) for _ in range(H)]

AB = [list(map(lambda x, y: abs(x - y), a, b)) for a, b in zip(A, B)]

dp = [[[0] * 10001 for _ in range(W + 1)] for _ in range(H + 1)]
dp[0][0][0] = 1

for h in range(H):
    for w in range(W):
        ab = AB[h][w]
        for i in range(10000):
            if dp[h][w][i] == 1:
                dp[h+1][w][i+ab] = 1
                dp[h+1][w][abs(i-ab)] = 1
                dp[h][w+1][i+ab] = 1
                dp[h][w+1][abs(i-ab)] = 1

for i in range(10000):
    if dp[H][W-1][i] == 1:
        print(i)
        break


### FIXED CODE ###

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

AB = [list(map(lambda x, y: abs(x - y), a, b)) for a, b in zip(A, B)]
dp = [[[0] * 12801 for _ in range(W + 1)] for _ in range(H + 1)]
dp[0][0][0] = 1

for h in range(H):
    for w in range(W):
        ab = AB[h][w]
        for i in range(10000):
            if dp[h][w][i] == 1:
                dp[h+1][w][i+ab] = 1
                dp[h+1][w][abs(i-ab)] = 1
                dp[h][w+1][i+ab] = 1
                dp[h][w+1][abs(i-ab)] = 1

for i in range(1000):
    if dp[H][W-1][i] == 1:
        print(i)
        break
R=input()
print(R*3.1415)

### FIXED CODE ###

print(3.1415*int(input())*2)
import math
A, B, N = map(int, input().split())

if (B > N+1):
  x = N
  print(math.floor(A*x/B)-A*math.floor(x/B))
else:
  x = N-N%(B-1)
  print(math.floor(A*x/B)-A*math.floor(x/B))

### FIXED CODE ###

import math
A, B, N = map(int, input().split())

if (B == 1):
  print(0)
elif (B > N+1):
  x = N
  print((A*x)//B-A*(x//B))
else:
  x = N-N%(B-1)
  print((A*x)//B-A*(x//B))
n=int(input())
l=list(map(int,input().split()))
f=1
for i in range(n-1):
	if l[i]==l[i+1]:
        f=0
        break
if f:
	print("YES")
else:
	print("NO")


### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
if len(set(l))==n:
    print("YES")
else:
    print("NO")
N, M = map(int, input().split())
A = list(map(int, input().split()))
 
goukei = sum(A)
 
if goukei > N:
  print(-1)
  
else:
  print(N-goukei)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import math
 
inp = float(input())
 
print(inp*2*math.pi)
n,x,t=map(int,input().split())

if n%x=0:
   a=n//x
else:
   a=n//x+1

b=int(a*t)

print(b)


### FIXED CODE ###

n,x,t=map(int,input().split())

if n%x==0:
   a=int(n//x)
else:
   a=int(n//x+1)

b=int(a*t)

print(b)
n, k = map(int, input().split())
L = list(map(int, input().split()))
L = L.sort(reverse=True)
sum = 0

for i in L:
  sum += L[i]

### FIXED CODE ###

N, K = map(int, input().split())
l = list(map(int, input().split()))
l.sort(reverse=True)
ans = []

for i in range(K):
    ans.append(l[i])
    
print(sum(ans))
a,b = map(int,input().splilt())
print((a + b) % 24)

### FIXED CODE ###

a,b = map(int,input().split())
print((a + b) % 24)
S = input()
K = input()
if S[0] == '1':
    if K == 1:
        print(S[0])
    else:
        print(S[1])
else:
    print(S[0])

### FIXED CODE ###

S = input()
K = int(input())
ans = 1
for i, s in enumerate(S):
    if i+1 == K:
        ans = s
        break
    if s == '1':
        continue
    else:
        ans = s
        break

print(ans)
a_,b_=input().split()
a=(str)(a_)
b=(str)(b_)

if a%2==0:
  print("Even")
elif b%2==0:
  print("Even")
else:
  print("Odd")


### FIXED CODE ###

a_, b_ = input().split()
a = (int)(a_)
b = (int)(b_)

if a%2==0:
    print("Even")
elif b%2==0:
    print("Even")
else:
    print("Odd")
c = 0
for s in input():
  if s = '+':c += 1
  else:c-= 1
print(c)

### FIXED CODE ###

c = 0
for s in input():
  if s == '+':c += 1
  else:c-= 1
print(c)
S,T=input().split()
A,B=(int(x) for x in input().split())
U = input()
 
if S == U:
  A = A - 1
  print(A +" " + B)
  
else:
  B = B - 1
  print(A + " " + B)

### FIXED CODE ###

S,T=input().split()
A,B=(int(x) for x in input().split())
U = input()
 
if S == U:
  A = A - 1
  print(A, B)
  
else:
  B = B - 1
  print(A, B)
n,k=map(int,input().split())
lst=[int(input()) for _ in range(n)]
lst=sorted(lst)
ab=lst[k-1]-lst[0]
cd=lst[-1]-lst[-k]
print(ans=min(ab,cd))

### FIXED CODE ###

n,k=map(int,input().split())
lst=[int(input()) for _ in range(n)]
lst=sorted(lst)
ans=float("inf")
for i in range(n+1-k):
  ans=min(ans,lst[k-1+i]-lst[i])
print(ans)
import math
import bisect

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

def XX(A, M):
  if M <= 0:
    return
  A[0] = A[0]/2
  M -= 1
  for i in range(1, len(A)):
    if A[i] > A[0] and M > 0:
      A[i] = A[i]/2
      M -= 1
    else:
      break
  A.sort(reverse = True)
  XX(A, M)
  
XX(A, M)
A = list(map(math.floor, A))
print(sum(A))
  
           

### FIXED CODE ###

import math
import bisect

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

def XX(A, M):
  if M <= 0 or A[0]<1:
    return
  A[0] = A[0]/2
  M -= 1
  for i in range(1, len(A)):
    if A[i] > A[0] and M > 0:
      A[i] = A[i]/2
      M -= 1
    else:
      break
  A.sort(reverse = True)
  XX(A, M)
  
XX(A, M)
A = list(map(math.floor, A))
print(sum(A))
N = int(input())
A = list(map(int,input().split()))
mod = 10**9+7
for i in range(N):
    for j in range(i,N):
        ans += (i^j)%mod
print(ans%mod)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
mod = 10**9+7
ans = 0

for bit in range(60):
    m = 1 << bit
    # bit桁目のbitが立っている時の数
    c = sum(a&m for a in A) >> bit
    # bit桁目の1の合計
    ans += (c*(N-c))<<bit
    # 繰り上がりのない足し算
    ans %= mod
print(ans)
# coding= utf-8
rab=input("")
ab=rab.split(" ")
a=int(rab[0])
b=int(rab[1])
if (a*b)%2 == 0:
  print("Even")
else:
  print("Odd")

### FIXED CODE ###

# coding= utf-8
rab=input("")
ab=rab.split(" ")
a=int(ab[0])
b=int(ab[1])
if a*b%2==0:
  print("Even")
else:
  print("Odd")
import sys
sys.setrecursionlimit(200000)
input = sys.stdin.readline
def main():
    N, Q = map(int,input().split())
    G = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = map(int,input().split())
        G[a-1].append(b-1)

    V = [0]*N
    for _ in range(Q):
        p, x = map(int,input().split())
        V[p-1] += x

    def dfs(ima):
        for tsugi in G[ima]:
            V[tsugi] += V[ima]
            dfs(tsugi)
    dfs(0)
    print(*V)
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(200010)

def main():
    input = sys.stdin.readline
    N, Q = map(int,input().split())
    G = [[] for k in range(N+1)]
    for k in range(N-1):
        a, b = map(int,input().split())
        G[a].append(b)
    kyori = [0 for k in range(N+1)]
    for k in range(Q):
        p, x = map(int,input().split())
        kyori[p] -= x
    def dfs(now, dist):
        for tsugi in G[now]:
            if kyori[tsugi] <= 0:
                kyori[tsugi] = -kyori[tsugi]
                kyori[tsugi] += dist
                dfs(tsugi, kyori[tsugi])
    kyori[1] = -kyori[1]
    dfs(1,kyori[1])
    print(*kyori[1:], sep = " ")

if __name__ == '__main__':
    main()
sample = input()
new = []
for i in sample:
  new.append(i)
if "A" in new:
  a_pos = list.index(new)
if "Z" in new:
  z_pos = list.index(new)
if a_post < z_pos:
	out = new[a_pos:(z_pos+1)]
    
new_string = ""
for i in out:
  new_string += i
print(len(new_string))


### FIXED CODE ###

sample = input()
#new = list(sample)
#if "A" in new:
a_pos = sample.index('A')
#if "Z" in new:
z_pos = sample.rfind('Z')
print(z_pos-a_pos+1)
T1,T2 = map(int,input().split())
A1,A2 = map(int,input().split())
B1,B2 = map(int,input().split())

len1 = T1 * A1 + T2 * A2
len2 = T1 * B1 + T2 * B2
if len1 == len2:
  print("infinity")
  quit()

ans = 0
subs = 0  
sub1 = T1 * (A1 - B1)
sub2 = T2 * (A2 - B2)
X = [1, 1]
i = 0
while (X != [0, 0]):
  i += 1
  if subs != 0:
    if (subs + sub1)(subs) <= 0:
      ans += 1
      X[0] = 1
    else:
      X[0] = 0
  subs = subs + sub1
  if subs != 0:
    if subs(subs + sub2) <= 0:
      ans += 1
      X[1] = 1
    else:
      X[1] = 0
  subs = subs + sub2

print(ans)
   
    

### FIXED CODE ###

T1,T2 = map(int,input().split())
A1,A2 = map(int,input().split())
B1,B2 = map(int,input().split())

len1 = T1 * A1 + T2 * A2
len2 = T1 * B1 + T2 * B2
if len1 == len2:
  print("infinity")
  quit()

ans = 0
subs = 0  
sub1 = T1 * (A1 - B1)
sub2 = T2 * (A2 - B2)

if sub1 > 0:
  if len1 - len2 > 0:
    ans = 0
  else:
    S = (-1 * sub1) // (sub1 + sub2)
    T = (-1 * sub1) % (sub1 + sub2)
    if T == 0:
      ans = 2 * S
    else:
      ans = 2 * S + 1
else:
  if len1 - len2 < 0:
    ans = 0
  else:
    S = (-1 * sub1) // (sub1 + sub2)
    T = (-1 * sub1) % (sub1 + sub2)
    if T == 0:
      ans = 2 * S
    else:
      ans = 2 * S + 1
    
print(ans)
N, K = map(int, input().split())
A_list = list(map(int, input().split()))
out_loop = [1]
flag = [0, 1] + [0]* (N - 1)

for a in A_list:
    if flag[a] == 0:
        out_loop.append(a)
    else:
        loop = out_loop[out_loop.index(a):]
        
if K <= (len(out_loop) - 1):
    print(out_loop[K])
else:
    k = K - len(out_loop) - 1
    k %= len(loop)
    print(loop[k - 1])


### FIXED CODE ###

N, K = map(int, input().split())
A_list = [-1] + list(map(int, input().split()))
out_loop = [1]
flag = [0, 1] + [0]* (N - 1)
a = A_list[1]
while flag[a] == 0:
    out_loop.append(a)
    flag[a] = 1
    a = A_list[a]
    

        
if K <= (len(out_loop) - 1):
    print(out_loop[K])
else:
    loop = out_loop[out_loop.index(a):]
    k = K - (len(out_loop) - 1)
    k %= len(loop)
    print(loop[k - 1])
s=str(input())
t=str(input())
ans=0
f=[]
r=0
g=len(s)
h=len(t)
for i in range(g-h):
    for j in range(h):
        if s[i+j]!=t[j]:
            ans+=1
        else:
            r=+1
    f.append(ans)
    ans=0
f.sort()
print(f[0])



### FIXED CODE ###

S = input()
T = input()
n = len(S)
m = len(T)
x = int(1e9)
for i in range(n-m+1):
  cnt = 0
  for j in range(m):
    cnt += (S[i+j] != T[j])
  x = min(x, cnt)
print(x)
n, m = map(int, input().split())
g = [input() for _ in range(n)]
maze = np.array(list(map(list, g)))

from collections import deque


def dfs(s, maze):
    H, W = maze.shape

    visited = np.array([[-1 for _ in range(W)] for _ in range(H)])
    visited[s[0]][s[1]] = 0

    actions = [(-1,0),(1,0),(0,-1),(0,1)]
    queue = deque([s])

    while queue:
        x,y = queue.popleft()
        for action in actions:
            nx = x + action[0]
            ny = y + action[1]
            if nx in range(H) and ny in range(W) and maze[(nx,ny)]=='.' and visited[(nx,ny)]==-1:
                visited[(nx,ny)] = visited[(x,y)] + 1
                queue.append((nx,ny))
    return np.max(visited)
    
ret = -1

for sx in range(H):
    for sy in range(W):
        if maze[sx][sy] == '.':
            ret = max(dfs((sx,sy), maze), ret)
print(ret)     

### FIXED CODE ###

import numpy as np
n, m = map(int, input().split())
g = [input() for _ in range(n)]
maze = np.array(list(map(list, g)))

from collections import deque


def dfs(s, maze):
    H, W = maze.shape

    visited = np.array([[-1 for _ in range(W)] for _ in range(H)])
    visited[s[0]][s[1]] = 0

    actions = [(-1,0),(1,0),(0,-1),(0,1)]
    queue = deque([s])

    while queue:
        x,y = queue.popleft()
        for action in actions:
            nx = x + action[0]
            ny = y + action[1]
            if nx in range(H) and ny in range(W) and maze[(nx,ny)]=='.' and visited[(nx,ny)]==-1:
                visited[(nx,ny)] = visited[(x,y)] + 1
                queue.append((nx,ny))
    return np.max(visited)
    
ret = -1
H, W = maze.shape

for sx in range(H):
    for sy in range(W):
        if maze[sx][sy] == '.':
            ret = max(dfs((sx,sy), maze), ret)
print(ret)
k,s=[int(i) for i in input().split()]
count = 0
for y in range(k+1):
 if i < s - k * 2 or s - i < 0:
  continue
 for x in range(k+1):
   if s - x - y >= 0 and s - x - y <= k:
      count = count+1
print(count)

### FIXED CODE ###

k,s=[int(i) for i in input().split()]
count = 0
for y in range(k+1):
 if y < s - k * 2 or s - y < 0:
  continue
 for x in range(k+1):
   if s - x - y >= 0 and s - x - y <= k:
      count = count+1
print(count)
import math
def answer(x, i, j):
    lcm = (i * j) // math.gcd(i, j)
    xi = x // i
    xj = x // j
    xlcm = x // lcm
    return x - xi - xj + xlcm
a, b, c, d = map(int, input().split())
ans = answer(b, c, d) - answer(a-1, c, d)
print(ans)

### FIXED CODE ###

import fractions
def answer(x, i, j):
    lcm = (i * j) // fractions.gcd(i, j)
    xi = x // i
    xj = x // j
    xlcm = x // lcm
    return x - xi - xj + xlcm
a, b, c, d = map(int, input().split())
ans = answer(b, c, d) - answer(a-1, c, d)
print(ans)
a = input()[-1]
if a == 3:
  print('bon;)
elif a == 0 or a==1 or a==6 or a==8:
  print('pon')
else:
  print('hon')

### FIXED CODE ###

a = input()[-1]
if a == '3':
  print('bon')
elif a == '0' or a=='1' or a=='6' or a=='8':
  print('pon')
else:
  print('hon')
#
# abc086 a
#
a, b = map(input().split())
if a*b % 2 == 0:
    print("Even")
else:
    priont("Odd")

### FIXED CODE ###

#
# abc086 a
#
a, b = map(int, input().split())
if a*b % 2 == 0:
    print("Even")
else:
    print("Odd")
#coding:utf-8
import sys,os
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

    N,P = LMIIS()
    S = input()[::-1]
    R = [0]*P
    R[0] = 1
    b = 1
    r = 0


    if P == 2 or P == 5:
        ans = 0:
        for i,c in enumerate(S):
            if int(c) % P == 0:
                ans += N-i
        print(ans)
        return
    for c in S:
        r += b * int(c)
        r %= P
        R[r] += 1
        b *= 10
        b %= P
    ans = 0

    for r in R:
        ans += r*(r-1)//2
    print(ans)
        

if __name__ == '__main__':
    main()

### FIXED CODE ###

#coding:utf-8
import sys,os
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

    N,P = LMIIS()
    S = input()[::-1]
    R = [0]*P
    R[0] = 1
    b = 1
    r = 0


    if P == 2 or P == 5:
        ans = 0
        for i,c in enumerate(S):
            if int(c) % P == 0:
                ans += N-i
        print(ans)
        return

    for c in S:
        r += b * int(c)
        r %= P
        R[r] += 1
        b *= 10
        b %= P
    ans = 0

    for r in R:
        ans += r*(r-1)//2
    print(ans)
        

if __name__ == '__main__':
    main()
import numpy as np

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

As = np.array(list(map(int,input().split())))
Bs = np.array(list(map(int,input().split())))

As_selected = []
Bs_selected = []

answer = 0

for i in range(N+1):
    if(As[0:i].sum() <= K):
         As_selected.append(As[0:i].sum())
    else:
        break
for i in range(M+1):
    if(Bs[0:i].sum() <= K):
         Bs_selected.append(Bs[0:i].sum())
    else:
        break

answer = 0

for i in np.arange(len(As_selected))+1:
    for j in np.arange(len(Bs_selected))+1:
        if(As_selected[-i] > K):
            break

        if(As_selected[-i] + Bs_selected[-j] <= K):
            answer = max(len(As_selected)+len(Bs_selected) -i - j, answer)
            break

print(answer)

### FIXED CODE ###


a = int(input())

print(a + a**2 + a**3)
import sys

n,m = map(int, input().split())
sc = [list(map(int, input().split())) for i in range(m)]

sc.sort()
ans = 0
d = 0
s = 0

if sc[0][1] == 0 and len(sc) != 1:
  print('-1')
  sys.exit()

for i in sc:
  if i[0] != d:
    d = i[0]
    s = i[1]
    ans += s * (10 ** (n-d))
  else:
    if i[1] != s:
      print('-1')
      sys.exit()

print(ans)

### FIXED CODE ###

import sys

n,m = map(int, input().split())

num = ['-'] * n

for i in range (m):
  s,c = map(int, input().split())
  if num[s-1] != '-' and num[s-1] != c:
    print('-1')
    sys.exit()
  else:
    num[s-1] = c

if n > 1:
  if num[0] == 0:
    print('-1')
    sys.exit()
  elif num[0] == '-':
    num[0] = 1 
  
for i in range(n):
  if num[i] == '-':
    num[i] = '0'
  else:
    num[i] = str(num[i])

print(''.join(num))
n, m = map(int, input().split())
a = [int(input()) for i in range(m)]
s = [1] + [0 for i in range(1,n+1)]
p = 1000000007
if n==1:
    print(1)
else:
    ind = 0
    if a[0] != 1:
        s[1] = 1
    else:
        ind += 1
    for i in range(2,n+1):
        if ind < m:
            if a[ind] != i:
                s[i] = (s[i-1] + s[i-2]) % p
            else:
                ind += 1
        else:
            s[i] = (s[i-1] + s[i-2]) % p
    print(s[-1])


### FIXED CODE ###

#129C
n, m = map(int, input().split())
a = [int(input()) for i in range(m)]
s = [1] + [0 for i in range(1,n+1)]
p = 1000000007
if n==1:
    print(1)
else:
    ind = 0
    if ind < m:
        if a[0] != 1:
            s[1] = 1
        else:
            ind += 1
    else:
        s[1] = 1
    for i in range(2,n+1):
        if ind < m:
            if a[ind] != i:
                s[i] = (s[i-1] + s[i-2]) % p
            else:
                ind += 1
        else:
            s[i] = (s[i-1] + s[i-2]) % p
    print(s[-1])