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

import sys
import itertools
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N, P = [int(x) for x in input().split()]
    S = input().strip()

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

    M = [0] * N
    for i, s in enumerate(S[::-1]):
        M[i] = (int(s) * (10 ** i)) % P

    MA = []
    MA.append(M[0])
    c = collections.Counter()
    ans = 0
    c[0] += 1
    ans += c[MA[0]]
    c[M[0]] += 1
    for i in range(1, N):
        MA.append((MA[i - 1] + M[i]) % P)
        ans += c[MA[i]]
        c[MA[i]] += 1

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import itertools
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N, P = [int(x) for x in input().split()]
    S = input().strip()

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

    M = [0] * N
    for i, s in enumerate(S[::-1]):
        M[i] = (int(s) * pow(10, i, P)) % P

    MA = []
    MA.append(M[0])
    c = collections.Counter()
    ans = 0
    c[0] += 1
    ans += c[MA[0]]
    c[M[0]] += 1
    for i in range(1, N):
        MA.append((MA[i - 1] + M[i]) % P)
        ans += c[MA[i]]
        c[MA[i]] += 1

    print(ans)


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

import heapq

N,M = (int(i) for i in input().split())
A = list(map(int,input().split()))
A.sort()

for i in range(M):
    BC = list(map(int,input().split()))
    i = 0
    while BC[1] > A[0] and i < BC[0]:
        heapq.heappop(A)
        heapq.heappush(A,BC[1])
        i += 1

print(sum(A))


### FIXED CODE ###

import heapq

N,M = (int(i) for i in input().split())
A = list(map(int,input().split()))
A.sort()
D = []
len = 0
BC = [0] * M

for i in range(M):
    BC[i] = list(map(int,input().split()))
BC.sort(key = lambda x:x[1],reverse = True)
for i in range(M):
    D.extend([BC[i][1]] * BC[i][0])
    len += BC[i][0]
    if len > N:
        break
cnt = min(N,len)
for i in range(cnt):
    if A[0] < D[i]:
        heapq.heapreplace(A,D[i])
    else:
        break
print(sum(A))
### BUGGY CODE ###

N = int(input())
A = [int(p) for p in input().split()]
Result = 1

for i in A:
    Result = Result*i

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


### FIXED CODE ###

N = int(input())
A = [int(p) for p in input().split()]
Result = 1

if(0 in A):
    print("0")
    exit()

for i in A:
    Result = Result*i
    if(Result > 10**18):
        Result = -1
        break

print(Result)
### BUGGY CODE ###

n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort()
from bisect import bisect_left
b = []
for i in range(m):
  b.append(list(map(int, input().split())))
b.sort(key=lambda x: x[1], reverse=True)
cur = 0
ans = 0
for e in b:
  t = bisect_left(a[cur:], e[1])
  ans += min(t, e[0])*e[1]
  cur += min(t, e[0])
while cur<len(a):
  ans += a[cur]
  cur += 1
print(ans)

### FIXED CODE ###

n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort()
from bisect import bisect_left
b = [list(map(int, input().split())) for i in range(m)]
b.sort(key=lambda x: x[1], reverse=True)
cur = 0
ans = 0
for e in b:
  t = bisect_left(a, e[1])
  if t>=cur:
    ans += min(t-cur, e[0])*e[1]
    cur += min(t-cur, e[0])
while cur<len(a):
  ans += a[cur]
  cur += 1
print(ans)
### BUGGY CODE ###

def gcd(x, y):
  if y == 0:
     return x
  else:
     return gcd(y, x % y)

A, B = map(int, input().split())
gcd_AB = gcd(A, B)
dA=[x for x in range(1, gcd_AB) if A%x == 0]
dB=[x for x in range(1, gcd_AB) if B%x == 0]
cd=[x for x in dA if x in dB]
cd.append(gcd_AB)
#print(A, B, gcd_AB)
#print(dA)
#print(dB)
#print(cd)
so_list = []
for i in cd[1:]:
  ok=True
  for s in so_list:
    if i % s == 0:
      ok=False
      break
  if ok:
    so_list.append(i)

print(len(so_list) + 1)


### FIXED CODE ###

import math
def gcd(x, y):
  if y == 0:
     return x
  else:
     return gcd(y, x % y)

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
    
A, B = map(int, input().split())
gcd_AB = gcd(A, B)
# 素因数分解
p_list = prime_factorize(gcd_AB)
#print(p_list)
print(len(set(p_list))+1)
### BUGGY CODE ###

N, X, Y = map(int, input().split())

distance_list = []

for i in range(1, N + 1):
    
    for j in range(i + 1, N + 1):
        
        dis_xy = abs(i - X) + 1 + abs(j - Y)
        dis = min(j - i, dis_xy)
        
        distance_list.append(dis)


for i in range(1, N):
    ans = distance_list.count(i)
    print(ans)

### FIXED CODE ###

import itertools
 
N, X, Y = map(int, input().split())
 
n_iter = itertools.combinations(list(range(1,N+1)), 2)
 
count_list = [0]*(N-1)
 
for i, j in n_iter:
  #1. abs(X - i) + abs(Y - j) + 1
  #2. abs(Y - i) + abs(X - j) + 1
  #3. abs(j - i)
  x = min(
    abs(X - i) + abs(Y - j) + 1,
    abs(j - i)
  )
  count_list[x-1] += 1
 
for i in count_list:
  print(i)
### BUGGY CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]
button = [0]*n
button1 = a[0] - 1
count = 1
try:
    fst = a.index(2)
    if fst == 0:
        print('1')
        exit()
except ValueError:
    print('-1')
    exit()

for i in range(n):
    button[button1] += 1
    button1 = a[button1] - 1
    if button[1] == 1:
        print(count)
        break
    try:
        button.remove(2)
        print('-1')
        break
    except:
        count += 1
        pass

### FIXED CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]
now = a[0]
c = 1

if now == 2:
    print(1)
    exit()

for i in range(n):
    now = a[now-1]
    c += 1
    if now == 2:
        print(c)
        exit()
print(-1)
### BUGGY CODE ###

import math
from functools import reduce

k = int(input())

ans = 0
for i in range(1,k+1):
    for j in range(1,k+1):
        for l in range(1,k+1):
            ans += reduce(math.gcd,[i,j,l])

print(ans)

### FIXED CODE ###

import math
from functools import reduce

k = int(input())

ans = 0
for i in range(1,k+1):
    for j in range(i,k+1):
        for l in range(j,k+1):
            temp = reduce(math.gcd,[i,j,l])
            if len(set([i,j,l])) == 1:
                ans += temp
            elif len(set([i,j,l])) == 2:
                ans += temp * 3
            elif len(set([i,j,l])) == 3:
                ans += temp * 6
print(ans)
### BUGGY CODE ###

s = input()
k = int(input())

n = len(s)
strs = set([])

for i in range(n):
    for j in range(i+1, n+1):
        strs.add(s[i:j])
strs = list(strs)
strs.sort()
print(strs[k-1])


### FIXED CODE ###

s = input()
k = int(input())

n = len(s)
strs = set([])

for i in range(n):
    for j in range(i+1, min(i+k+1,n+1)):
        strs.add(s[i:j])
strs = list(strs)
strs.sort()
print(strs[k-1])
### BUGGY CODE ###

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

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

for i in range(N):
  sum = sum + A[i]
  
print(sum)

### FIXED CODE ###

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

Nd = {}

for i in range(M):
  B, C = map(int, input().split())
  if C in Nd.keys():
    Nd[C] = Nd[C] + B
  else:
    Nd[C] = B
  
for a in A:
  if a in Nd.keys():
    Nd[a] = Nd[a] + 1
  else:
    Nd[a] = 1
    
Nd = sorted(Nd.items(), key=lambda x: -x[0]) # type=list
sum = 0

for key, val in Nd:
  if N >= val:
    sum = sum + key*val
    N = N-val
  else:
    sum = sum + key*N
    break;
  
print(sum)
### BUGGY CODE ###

n, W = map(int, input().split())
w, v = [], []

for i in range(n):
    temp1, temp2 = map(int, input().split())
    w.append(temp1)
    v.append(temp2)

#print(w, v)
#dp[i] = max(dp[i-1], dp[i]) + dp[i-2]

dp = [[None for i in range(W+1)] for j in range(n+1)]
#dp[0][0] = 0

#print(dp)

def solve(total, i):
    if i > n-1:
        #return dp[total][i-1]
        return 0

    if dp[i][total] is not None:
        return dp[i][total]

    weight, val = w[i], v[i]
    if total + weight <= W:
        chose = val + solve(total + weight, i+1)
        unchose = solve(total, i+1)
        dp[i][total] = max(chose, unchose)
        return dp[i][total]
    else:
        dp[i][total] = solve(total, i+1)
        return dp[i][total]
        # if i < n-1:
        #     return solve(total, i+1)
        # else:
        #     return v[i-1]


print(solve(0, 0))

### FIXED CODE ###

n, W = map(int, input().split())
w = [0]*(n+1)
v = [0]*(n+1)

#dp = [[None for i in range(W+1)] for j in range(n+1)]
dp = [[0 for i in range(W+1)] for j in range(n+1)]

for i in range(n):
    w[i], v[i] = map(int, input().split())

def knap(i, j):
    if dp[i][j] is not None:
        return dp[i][j]

    res = 0

    if i == n:
       	res = 0
    elif j < w[i]:
        res = knap(i+1, j)
    else:
        res = max(knap(i+1, j), knap(i+1, j-w[i]) + v[i])

    dp[i][j] = res
    return dp[i][j]

for i in reversed(range(n)):
    for j in range(W+1):
#        res = 0
        # if i == n-1:
        #     res = 0
        if j < w[i]:
            dp[i][j] = dp[i+1][j]
        else:
            dp[i][j] = max(dp[i+1][j], dp[i+1][j-w[i]] + v[i])

#print(knap(0, W))
print(dp[0][W])
### BUGGY CODE ###


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

    res = [[e, A.count(e)] for e in set(A) if A.count(e) > 1]

    dic = {}

    for i in range(N):
        ans = 0

        if A[i] in dic:
            print(int(dic[A[i]]))
            continue

        for r in res:
            if r[0] == A[i]:
                ans += (r[1]-1)*(r[1]-2)/2
            else:
                ans += (r[1])*(r[1]-1)/2
        dic[A[i]] = ans

        print(int(ans))


# Solve
if __name__ == "__main__":
    solve()


### FIXED CODE ###

import collections


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

    counters = collections.Counter(A)
    ans = 0
    for _, c in counters.items():
        ans += c*(c-1)//2

    for K in range(N):
        if A[K] in counters:
            c = counters[A[K]]
            if counters[A[K]] > 2:
                print(ans - (c*(c-1)//2) + ((c-1)*(c-2)//2))
            else:
                print(ans - (c*(c-1)//2))
        else:
            print(ans)


# Solve
if __name__ == "__main__":
    solve()
### BUGGY CODE ###

# D

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

 
from scipy.sparse.csgraph import dijkstra, csgraph_from_dense
import numpy as np
 
adj_matrix = [[10**9] * N for i in range(N)]
for ab in ABs:
    adj_matrix[ab[0]-1][ab[1]-1] = adj_matrix[ab[1]-1][ab[0]-1] = 1
 
csr = csgraph_from_dense(adj_matrix, null_value=10**9)
from_starts, procs = dijkstra(csr, indices=[0], return_predecessors =True)
from_start = from_starts[0]
proc = procs[0]
 
if -9999 in proc[1:]:
  print('No')
else:
  print('Yes')
  for i in range(N-1):
    print(int(proc[i+1]) + 1)

### FIXED CODE ###

# D

import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import breadth_first_order

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

row = []
col = []
for i in range(M):
    r, c = list(map(int, input().split()))
    row.append(c-1)
    col.append(r-1)

data = [1] * (M)

csr = csr_matrix((data, (row, col)), shape=(N, N))
_, proc = breadth_first_order(csr, 0, directed=False)

if -9999 in proc[1:]:
  print('No')
else:
  print('Yes')
  print('\n'.join((proc[1:]+1).astype('str')))
### BUGGY CODE ###

n, m = map(int,input().split())
l = []
for i in range(m):
    l.append(list(map(int,input().split())))
l2 = l.copy()
l2.sort()
p = 0
l3 = []
for i in l2:
    if i[0] != p:
        p = i[0]
        x = 1
    else:
        x += 1
    l3.append(str(i[0]).zfill(6)+ str(x).zfill(6))
for i in l:
    print(l3[l2.index(i)])

### FIXED CODE ###

import numpy as np
n, m = map(int,input().split())
l = [list(map(int,input().split()))+ [0] for i in range(m)]
l2 = sorted(l)
p = 0
for i in l2:
    x = 1 if i[0] != p else x + 1
    p = i[0]
    i[2] = x
for i in l:
    print(str(i[0]).zfill(6)+str(i[2]).zfill(6))
### BUGGY CODE ###

N = int(input())
X = [int(x) for x in input().split(' ')]

for i in range(N):
    tmp = X[:i]
    tmp.extend(X[i+1:])
    for j in range(int((N - 1) / 2)):
        tmp.remove(min(tmp))
    print(min(tmp))

### FIXED CODE ###

N = int(input())
x = [int(x) for x in input().split()]
y = sorted(x)
l = y[len(x)//2-1]
r = y[len(x)//2]

for xi in x:
    if xi < r: print(r)
    else: print(l)
### BUGGY CODE ###

n = int(input())
A = list(map(int,input().split()))
mod = 10**9+7
m = len(bin(max(A)))-2
zero = [0]*m
one = [0]*m
for a in A:
  for i in range(m):
    j = (a>>i)&1
    zero[i] += 1-j
    one[i] += j
ans = 0
d = [0]*m
d[0] = 1
for i in range(1,m):
  d[i] = (2*d[i-1])%mod
for i in range(m):
  ans = (ans+(zero[i]%mod)*(one[i]%mod)*d[i])%mod
print(ans)

### FIXED CODE ###

import numpy as np
n = int(input())
A = np.array(list(map(int,input().split())))
mod = 10**9+7
m = len(bin(max(A)))-2
ans = 0

for i in range(m):
  one = np.count_nonzero((A >> i)&1)
  zero = n - one
  ans += (pow(2,i,mod)*zero*one)%mod
print(ans%mod)
### BUGGY CODE ###

from sys import stdin
input = stdin.readline
import numpy as np
from collections import deque
H,W = map(int, input().rstrip().split())
CH,CW = map(int, input().rstrip().split())
DH,DW = map(int, input().rstrip().split())
[CH,CW,DH,DW] = [CH-1,CW-1,DH-1,DW-1]
S = np.array([list(input().rstrip()) for i in range(H)])
M = H * W
Distance = np.ones((H,W))*M
Distance[CH,CW] = 0
[nowH,nowW] = [CH,CW]
q = deque([])
q.append([nowH,nowW])
for n in range(0,M):
  if len(q) != 0:
    [nowH,nowW] = q.popleft()
  else:
    break
  if [nowH,nowW] == [DH,DW]:
    break
  for i in range(-2,3):
    for j in range(-2,3):
      if nowH+i >= 0 and nowW+j >= 0 and nowH+i < H and nowW+j < W:
        dis = (abs(i) + abs(j))
        if dis >= 1:
          cost = min(2,dis) - 1
          if S[nowH+i,nowW+j] == '.' and Distance[nowH,nowW] + cost < Distance[nowH+i,nowW+j]:
            if [nowH+i,nowW+j] in q:
              q.remove([nowH+i,nowW+j])
            if dis == 1:
              q.appendleft([nowH+i,nowW+j])
            else:
              q.append([nowH+i,nowW+j])
            Distance[nowH+i,nowW+j] = Distance[nowH,nowW] + cost
if Distance[DH,DW] == M:
  print(-1)
else:
  print(int(Distance[DH,DW]))

### FIXED CODE ###

from collections import deque
H,W = map(int, input().split())
CH,CW = map(lambda x: int(x) - 1, input().split())
DH,DW = map(lambda x: int(x) - 1, input().split())
S = [input() for i in range(H)]
INF = 10 ** 9
walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]
h = CH
w = CW
Distance = [[INF] * W for _ in range(H)]
Distance[h][w] = 0
q = deque(())
q.append((h,w))
while q:
  h,w = q.popleft()
  if [h,w] == [DH,DW]:
    break
  for i,j in walk:
    hwalk = h + i
    wwalk = w + j
    if 0 <= hwalk < H and 0 <= wwalk < W and S[hwalk][wwalk] == '.' and Distance[h][w] < Distance[hwalk][wwalk]:
      Distance[hwalk][wwalk] = Distance[h][w]
      q.appendleft((hwalk,wwalk))
  for i,j in warp:
    hwalk = h + i
    wwalk = w + j
    if 0 <= hwalk < H and 0 <= wwalk < W and S[hwalk][wwalk] == '.' and Distance[h][w] + 1 < Distance[hwalk][wwalk]:
      Distance[hwalk][wwalk] = Distance[h][w] + 1
      q.append((hwalk,wwalk))
print(int(Distance[DH][DW]) if Distance[DH][DW] != INF else -1)
### BUGGY CODE ###

def main():
    n = int(input())
    a = list(map(int,input().split()))
    l = len(format(max(a),'b'))
    a = [format(a[i],'0{}b'.format(l)) for i in range(n)]
    ans = [[] for i in range(n)]
    for i in range(l):
        t = []
        for j in range(n):
            t.append(int(a[j][i]))
        s = sum(t)
        b = []
        if s%2==0:
            b = t
        else:
            b = [(t[i]+1)%2 for i in range(n)]

        for j in range(n):
            ans[j].append(str(b[j]))
    for i in range(n):
        ans[i] = ''.join(ans[i])
        ans[i] = str(int(ans[i],2))
    print(' '.join(ans))

if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    n = int(input())
    a = list(map(int,input().split()))
    b = a[0] ^ a[1]
    for i in range(2,n):
        b = b ^ a[i]
    ans = []
    for i in range(n):
        ans.append(b ^ a[i])
    ans = list(map(str,ans))
    print(' '.join(ans))

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

# #!/usr/bin/env python3
# # -*- coding: utf-8 -*-


def main():
    N = int(input())
    S = list(map(int, input().split()))

    result = []

    for i in range(N):
        result.append(S.index(i + 1) + 1)

    print(*result)


if __name__ == "__main__":
    main()


### FIXED CODE ###

# #!/usr/bin/env python3
# # -*- coding: utf-8 -*-


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

    result = []
    for i, a in enumerate(A, start=1):
        result.append([i, a])
    result = sorted(result, key=lambda x: x[1])

    print(*[i for i, a in result])


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

n = int(input())
l = input().split()

for i in range(0,n):
	l[i] = int(l[i])

counting = 0
list_i = []
set_l = set(l)
for i in set_l:
	counting = 0
	for j in range(n):
		if (l[j] == i or l[j] == i-1 or l[j] == i+1):
			counting += 1		
	list_i.append(counting)
			 
print(max(list_i))

### FIXED CODE ###

n = int(input())
l = input().split()

for i in range(0,n):
	l[i] = int(l[i])

dict_i = {}
for i in range(-1,100001):
	dict_i[i] = 0
	
for j in range(n):
	dict_i[l[j]] += 1
	dict_i[l[j] + 1] += 1
	dict_i[l[j] - 1] += 1
print(max(dict_i.values()))
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=[]
from collections import Counter
d=Counter(a)
MOD=10**9+7
def comb(n,k):
    if n<k:
        return 0
    if n<0 or k<0:
        return 0
    k=min(n-k,k)
    ans=1
    inv=[1]*(k+1)
    if k>=1:
        ans*=(n-k+1)%MOD
    for i in range(2,k+1):
        inv[i]=MOD-inv[MOD%i]*(MOD//i)%MOD
        ans=ans*(n-k+i)*inv[i]%MOD
    return ans
cnt=[]
v=set()
yut=True
for i in range(n-1):
    if a[i]!=a[i+1]:
        yut=False
if yut:
    for i in range(n):
        print(comb(n-1,2))
    exit()
for i in range(n):
    g=a.count(a[i])
    v.add(a[i])
    cnt.append([a[i],comb(g,2)])
fg=0
cvg=[]
vsd=list(v)
for i in range(n):
    tt=vsd[fg]
    if cnt[i][0]==tt:
        cvg.append(cnt[i][1])
        if  fg<len(vsd)-1:
            fg+=1

sy=sum(cvg)-cvg[-1]
for i in range(n):
    h=a.count(a[i])
    tmp=sy-(h-1)
    ans.append(tmp)

for i in range(n):
    print(ans[i])

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
from collections import Counter
MOD=10**9+7

d=Counter(a)
tni=0
dv=d.values()
dv=list(dv)
for i in range(len(dv)):
    tni+=dv[i]*(dv[i]-1)//2

for i in range(n):
    r=d[a[i]]
    print(tni-(r-1))
### BUGGY CODE ###

import numpy as np
N,K,Q = map(int,input().split())
ans_list=[int(input()) for _ in range(Q)]
points=np.full((N,), K)
for ans_person in ans_list:
    points[:ans_person-1] -= 1
    points[ans_person:] -= 1

winner = points>0
for person in winner:
    if person==True:
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

import numpy as np
# 実行時間が遅いのでは早くする

N,K,Q = map(int,input().split())
# Q門について成果した人の番号
ans_list=[int(input()) for _ in range(Q)]
# 参加者ごとに正解した数
answer_num=[0 for _ in range(N)]

for ans_person in ans_list:
    answer_num[ans_person-1] += 1

for an in answer_num:
    # 持ち点から(問題数-正解数)を引いた数が残りの得点である
    if K-(Q-an) > 0:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

import sys
n = int(input())
c_ls = [int(i) for i in sys.stdin.readline().split()]
c_ls.sort(reverse=True)
MOD = 10**9+7

res = 0
for i, c in enumerate(c_ls):
    res += (2 ** (n - 2) * (i+2)) * c % MOD
    res %= MOD
res = res * (2**n) % MOD
print(int(res))

### FIXED CODE ###

import sys

n = int(input())
c_ls = [int(i) for i in sys.stdin.readline().split()]
c_ls.sort(reverse=True)
MOD = 10 ** 9 + 7

res = 0
for i, c in enumerate(c_ls):
    res += (i + 2) * c % MOD
    res %= MOD
res = res * (4 ** (n - 1)) % MOD
print(int(res))
### BUGGY CODE ###

from collections import deque

H,W = map(int,input().split())
C_h,C_w = map(lambda x:int(x)-1,input().split())
D_h,D_w = map(lambda x:int(x)-1,input().split())
S = [input() for _ in range(H)]

INF = int(1e10)
dist = [[INF]*(W) for _ in range(H)]
dist[C_h][C_w] = 0
deq = deque()
deq.append((C_h,C_w))

move_a = [(1,0),(0,1),(-1,0),(0,-1)]
move_b = [(i,j)for i in range(-2,2+1) for j in range(-2,2+1) if abs(i)+abs(j)>=2]

while len(deq):
  h,w = deq.popleft()
  for dh,dw in move_a:
    nh,nw = h+dh,w+dw
    if nh<0 or nw<0 or nh>=H or nw>=W:
      continue
    if S[nh][nw] == '#':
      continue
    if dist[nh][nw] > dist[h][w]:
      dist[nh][nw] = dist[h][w]
      deq.appendleft((nh,nw))
  for dh,dw in move_b:
    nh,nw = h+dh,w+dw
    if nh<0 or nw<0 or nh>=H or nw>=W:
      continue
    if S[nh][nw] == '#':
      continue
    if dist[nh][nw] > dist[h][w]+1:
      dist[nh][nw] = dist[h][w]+1
      deq.append((nh,nw))
  
print(dist[D_h][D_w] if dist[D_h][D_w]<INF else -1)

### FIXED CODE ###

from collections import deque

H,W = map(int,input().split())
C_h,C_w = map(lambda x:int(x)-1,input().split())
D_h,D_w = map(lambda x:int(x)-1,input().split())
S = [input() for _ in range(H)]

INF = int(1e10)
dist = [[INF]*(W) for _ in range(H)]
deq = deque()
deq.append((C_h,C_w,0))

move_a = [(1,0),(0,1),(-1,0),(0,-1)]
move_b = [(i,j)for i in range(-2,2+1) for j in range(-2,2+1) if abs(i)+abs(j)>=2]

while len(deq):
  h,w,c = deq.popleft()
  if dist[h][w] <= c:
    continue
  dist[h][w] = c
  for dh,dw in move_a:
    nh,nw = h+dh,w+dw
    if nh<0 or nw<0 or nh>=H or nw>=W:
      continue
    if S[nh][nw] == '#':
      continue
    if dist[nh][nw] > c:
      deq.appendleft((nh,nw,c))
  for dh,dw in move_b:
    nh,nw = h+dh,w+dw
    if nh<0 or nw<0 or nh>=H or nw>=W:
      continue
    if S[nh][nw] == '#':
      continue
    if dist[nh][nw] > c+1:
      deq.append((nh,nw,c+1))
  
print(dist[D_h][D_w] if dist[D_h][D_w]<INF else -1)
### BUGGY CODE ###

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

for i in range(N):
  print(A.count(i+1))

### FIXED CODE ###

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

ans = [0] * N

for i in range(len(A)):
  ans[A[i]-1] += 1

for i in range(len(ans)):
  print(ans[i])
### BUGGY CODE ###

N = int(input())
a = list(map(int, input().split()))
isCon = True
counter = 0
while(isCon):
    isDiv = False
    for i in range(len(a)):
        if(not isDiv and a[i]%2==0):
            a[i] = a[i]//2
            isDiv = True
        else:
            a[i] = a[i]*3
    if(not isDiv):
        isCon = False
    else:
        counter += 1
print(counter)


### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
isCon = True
counter = 0
for ai in a:
    while(ai % 2 == 0):
        ai = ai//2
        counter += 1
print(counter)
### BUGGY CODE ###

N,Q=[int(x) for x in input().split()]
S=input()
l=r=0
for _ in range(Q):
    l,r=[int(x) for x in input().split()]
    t=0
    for i in range(l-1,r-1):
        t += 1 if S[i]=='A' and S[i+1]=='C' else 0
    print(t)


### FIXED CODE ###

N,Q=[int(i) for i in input().split()]
S=input()

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

for _ in range(Q):
    l,r=[int(x)-1 for x in input().split()]
    print(c[r]-c[l])