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

from collections import Counter as counter
from sys import stdin 

N = int(stdin.readline())
char_counts = list(map(counter, [stdin.readline().rstrip() for _ in range(N)]))
counts = [list(map(lambda x: x == c, char_counts[i+1:])) for i, c in enumerate(char_counts)]
match_count = sum(list(map(sum, counts)))
print(match_count)

### FIXED CODE ###

N = int(input())
dic = {}
count = 0
for _ in range(N):
  s = ''.join(sorted(input()))
  if s in dic.keys():
    count += dic[s]
    dic[s] += 1
  else:
    dic[s] = 1
print(count)
### BUGGY CODE ###

N=int(input())
A=[int(i) for i in input().split()]
 
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])
 
    if temp != 1:
        arr.append([temp, 1])
 
    if arr == []:
        arr.append([n, 1])
 
    return arr
 
 
mat = [1]
divs_set = set()
divs_powers = {}
tmp=[0]*len(A)
for j,a in enumerate(A):
    tmp[j] = factorization(a)
    for div in tmp[j]:
        if div[0] not in divs_set:
            divs_set.add(div[0])
            divs_powers[div[0]] = div[1]
        else:
            if divs_powers[div[0]] < div[1]:
                divs_powers[div[0]] = div[1]
 
all_dict = []
all_set = []
for i,t in enumerate(tmp):
    each_dict = {}
    each_set = set()
    for tt in t:
        each_dict[tt[0]] = tt[1]
        each_set.add(tt[0])
    all_dict.append(each_dict)
    all_set.append(each_set)
 
B = [1] * N
for i, a in enumerate(A):
    for k in divs_set:
        if k in all_set[i]:
            B[i] = B[i]*(k**(divs_powers[k]-all_dict[i][k]))
        else:
            B[i] = B[i]*(k**divs_powers[k])
 
print(int(sum(B)) % (10 ** 9 + 7))

### FIXED CODE ###

import math
from collections import defaultdict

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

divisor_primes = defaultdict(int)

def prime_factrizer(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

for a in A:
    factrized_a = prime_factrizer(a)
    for prime in factrized_a:
        divisor_primes[prime[0]] = max(divisor_primes[prime[0]],prime[1])

invs = [1] * (max(A) + 1)
for i in range(2, max(A) + 1):
    invs[i] = mod - invs[mod % i] * (mod//i) % mod

lcm = 1
for key in divisor_primes.keys():
    power = divisor_primes[key]
    div = 1
    for i in range(power):
        div *= key
        div %= mod
    lcm *= div

ans = 0

for a in A:
    ans += invs[a]
    ans %= mod
ans *= lcm
ans %= mod
print(ans)
### BUGGY CODE ###

n = int(input())
moto = [int(i) for i in input().split()]
 
array=[0]*n
 
for i in reversed(range(1,n+1)):
  sum = 0
  for j in range(i,n+1,i):
    sum += array[j-1]
  if array[i-1] != (sum-moto[i-1])%2:
    array[i-1] = 1
    
m = array.count(1)
ans = ""
for i in range(n):
  if array[i] == 1:
    ans = ans + str(i+1) + " "
print(m)
if ans != "":
  print(ans[:-1])

### FIXED CODE ###

n = int(input())
moto = [int(i) for i in input().split()]
 
array=[0]*n
 
for i in reversed(range(1,n+1)):
  if sum(array[i-1::i])%2 != moto[i-1]:
    array[i-1] = 1
    
m = sum(array)
print(m)
ans = ""
for i in range(n):
  if array[i] == 1:
    print(i+1, end=" ")
### BUGGY CODE ###

import heapq
import copy
N = input()
A = [-int(input()) for _ in range(int(N))]
A_heap = copy.deepcopy(A)
for idx, a in enumerate(A):
    heapq.heapify(A_heap)
    pop_A = heapq.heappop(A_heap)
    pop_A_list = []
    pop_A_list.append(pop_A)
    if pop_A == a:
        pop_A2 = heapq.heappop(A_heap)
        print(-(pop_A2))
        heapq.heappush(A_heap, pop_A)
        heapq.heappush(A_heap, pop_A2)
        continue

    print(-(pop_A))
    heapq.heappush(A_heap, pop_A)

### FIXED CODE ###

import heapq
import copy
N = input()
A = [-int(input()) for _ in range(int(N))]
A_heap = copy.deepcopy(A)
heapq.heapify(A_heap)
for idx, a in enumerate(A):
    pop_A = heapq.heappop(A_heap)
    pop_A_list = []
    pop_A_list.append(pop_A)
    if pop_A == a:
        pop_A2 = heapq.heappop(A_heap)
        print(-(pop_A2))
        heapq.heappush(A_heap, pop_A)
        heapq.heappush(A_heap, pop_A2)
        continue

    print(-(pop_A))
    heapq.heappush(A_heap, pop_A)
### BUGGY CODE ###

#!/usr/bin/env python3

S = input()
Q = int(input())

reverse = False

ans = S

for i in range(Q):
    query = input()
    if query == "1":
        reverse = not reverse

    else:
        a,b,c = list(query.split())
        if (b == "1" and not reverse) or (b == "2" and reverse):
            ans = c + ans
        else:
            ans = ans + c

if reverse:
    print(ans[::-1])
else:
    print(ans)
            


### FIXED CODE ###

#!/usr/bin/env python3

S = input()
Q = int(input())

reverse = False

mae = []
ushiro = []

for i in range(Q):
    query = input()
    if query == "1":
        reverse = not reverse

    else:
        a,b,c = list(query.split())
        if (b == "1" and not reverse) or (b == "2" and reverse):
            mae.append(c)
        else:
            ushiro.append(c)

if reverse:
    origin = [S[::-1]]
    ans = ushiro[::-1]
    ans.extend(origin)
    ans.extend(mae)
    print(''.join(ans))
else:
    ans = mae[::-1]
    origin = [S]
    ans.extend(origin)
    ans.extend(ushiro)
    print(''.join(ans))
### BUGGY CODE ###

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

L = [0] * N
R = [0] * N
L[0] = A[0]
R[-1] = A[-1]
for i in range(1, N):
    L[i] = max(L[i-1], A[i])
for i in range(N-1)[::-1]:
    R[i] = max(R[i+1], A[i])

for i in range(N):
    print(max(L[:i] + R[i+1:]))

### FIXED CODE ###

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

L = [0] * N
R = [0] * N
L[0] = A[0]
R[-1] = A[-1]
for i in range(1, N):
    L[i] = max(L[i-1], A[i])
for i in range(N-1)[::-1]:
    R[i] = max(R[i+1], A[i])

for i in range(N):
    print(max(0 if i == 0 else L[i-1], 0 if i == N-1 else R[i+1]))
### BUGGY CODE ###

n = int(input())
a = [0 for _ in range(n+1)]
for i in range(n):
    a[i+1] = list(map(int, input().split()))
todo = [0] * (n+1)
days = 0
while True:
    update = []
    for i in range(1, n+1):
        if todo[i] < n - 1:
            p = a[i][todo[i]]
            if a[p][todo[p]] == i:
                update.append(i)
    for j in update:
        todo[j] += 1
    days += 1
    #print(todo)
    if todo[1:] == [n - 1] * n:
        break
    elif update == []:
        days = -1
        break
print(days)

### FIXED CODE ###

n = int(input())
a = []
for _ in range(n+1):
    a.append([-1])
for i in range(n):
    inp = list(map(int, input().split()))
    for j in range(n-2, -1, -1):
        a[i+1].append(inp[j])
matched = [i for i in range(1, n+1)]
finish = 0
days = 0
while True:
    used = set()
    while matched != []:
        i = matched.pop()
        p = a[i][-1]
        if p != -1 and a[p][-1] == i and (i not in used) and (p not in used) :
            a[i].pop()
            a[p].pop()
            used.add(i)
            used.add(p)
            if a[i][-1] == -1:
                finish += 1
            if a[p][-1] == -1:
                finish += 1
    days += 1
    matched = list(used)
    if len(used) == 0:
        days = -1
        break
    elif finish == n:
        break
print(days)
### BUGGY CODE ###

n = int(input())
h = list(map(int, input().split()))
ans = True

for i in range(len(h)-1):
    if h[i] > (min(h[i+1:]) + 1):
        ans = False
if ans:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

n = int(input())
h = list(map(int, input().split()))
ans = True
m = h[0]
for i in range(1, len(h)):
    if h[i] + 1 < m:
        ans = False
    m = max(m, h[i])
if ans:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

A = 0
B = 1
mid = []
ab = []

n, m = map(int, input().split())
for i in range(m):
    a,b = map(int, input().split())
    if a == 1:
        mid.append(b)
    else:
        ab.append([a, b])

for _ab in ab:
    if _ab[B] == n and _ab[A] in mid:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

### FIXED CODE ###

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

A = 0
B = 1
mid = [0] * (n+1)
goal = [0] * (n+1)
ab = []

for i in range(m):
    a,b = map(int, input().split())
    ab.append([a, b])
    if a == 1:
        mid[b] += 1
    elif b == n:
        goal[a] += 1

# print(mid)
# print(goal)

for i in range(n+1):
    if mid[i] == 1 and goal[i] == 1:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")
### BUGGY CODE ###

n = int(input())
s = []

for nn in range(n):
    s.append(sorted(input()))

ans = 0

sorted(s)

l = len(s)

for ss in range(0, l):
    for sss in range(ss+1, l):

        if s[ss] == s[sss]:
            ans += 1

print(ans)

### FIXED CODE ###

n = int(input())
sraw = dict()

for nn in range(n):
    i = "".join(sorted(input()))
    if i in sraw:
        sraw[i] += 1
    else:
        sraw[i] = 1

ans = 0

for ss in sraw:
    ans += round(sraw[ss]*(sraw[ss]-1)/2)

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

from itertools import combinations

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

mod = 10**9+7
c = combinations(A, 2)
ans = 0

for v in c:
    ans += v[0] * v[1]
print(ans%mod)


### FIXED CODE ###

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

mod = 10**9+7
s = sum(A)
ans = 0

for i in range(N-1):
    s -= A[i]
    ans += A[i] * s
print(ans%mod)
### BUGGY CODE ###

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


### FIXED CODE ###

N = int(input())
res = 1
for i in range(1, N+1):
    if res >= (10**9+7):
        res %= (10**9+7)
        res *= i
    else:
        res *= i
print(res % (10**9+7))
### BUGGY CODE ###

# dp[i] := i番目の人が選ばれたときの踏み台

def main():
    # INF = 10 ** 9
    N = int(input())
    A = list(map(int, input().split()))

    # initialize
    dp = [0] * (N + 10)
    dp[0] = A[0]

    res = 0
    for i in range(1, N):
        for j in range(10**9):
            if dp[i-1] <= (tmp := A[i] + j):
                dp[i] = tmp
                res += j
                break
    print(res)

if __name__ == "__main__":
    main()

### FIXED CODE ###

# maをi-1番目までにでてる最大値としてi番目との差分を足していく

def main():
    # INF = 10 ** 9
    N = int(input())
    A = list(map(int, input().split()))

    # initialize
    ma = A[0]

    res = 0
    for i in range(1, N):
        if A[i] <= ma:
            res += ma - A[i]
        else:
            ma = A[i]
    print(res)

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

import sys
from collections import Counter
read = sys.stdin.buffer.read
n, *lst = map(int, read().split())

def convert(A):
    return [x ^ y for x, y in zip(A, A[1:])] + [A[-1] ^ A[0]]


al = lst[:n]
bl = lst[n:]
a = convert(al)
b = convert(bl)

alal, aa = al + al, a + a
k = 0
while k < n:
    i = 0
    while i < n and aa[k + i] == b[i]:
        i += 1
    if i == n:
        x = alal[k] ^ bl[0]
        print(k, x)
    k += 1


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())

A = list(map(int, readline().split()))
B = list(map(int, readline().split()))


def convert(A):
    return [x ^ y for x, y in zip(A, A[1:])] + [A[-1] ^ A[0]]


C = convert(A)
D = convert(B)


def Z_algorithm(S):
    # 共通接頭辞の長さを返す
    N = len(S)
    arr = [0] * N
    arr[0] = N
    i, j = 1, 0
    while i < N:
        while i + j < N and S[j] == S[i + j]:
            j += 1
        arr[i] = j
        if not j:
            i += 1
            continue
        k = 1

        while i + k < N and k + arr[k] < j:
            k += 1
        i += k
        j -= k

    return arr


Z = Z_algorithm(D + [-1] + C + C)[N + 1:N + N + 1]

K = [i for i, x in enumerate(Z) if x == N]
X = [A[k] ^ B[0] for k in K]

print('\n'.join('{} {}'.format(k, x) for k, x in zip(K, X)))
### BUGGY CODE ###

import math

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

c = 0
ans = -1
for i in range(1,10**18) :
    x = b*i-1
    if x > n :
        x = n
        c = 1
    if ans > math.floor((a*x)/b)-a*math.floor(x/b) :
        break
    ans = math.floor((a*x)/b)-a*math.floor(x/b)
    if c == 1 :
        break

print(ans)

### FIXED CODE ###

import math

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

c = 0
ans = -1
for i in range(1,10**7) :
    x = b*i-1
    if x > n :
        x = n
        c = 1
    if ans > math.floor((a*x)/b)-a*math.floor(x/b) :
        break
    ans = math.floor((a*x)/b)-a*math.floor(x/b)
    if c == 1 :
        break

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

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

for i in range(n):
    b.append(a[i])
    b.reverse()

print(*b, sep=' ')

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
even = []
odd = []
b = []

for i in range(n):
    if i % 2 == 0:
        even.append(a[i])
    else:
        odd.append(a[i])

if n % 2 != 0:
    even.reverse()
    b = even + odd
else:
    odd.reverse()
    b = odd + even

print(*b, sep=' ')
### BUGGY CODE ###

import sys

N = int(input())

argv = input().split()
divisible = 0
count = 0
  
for i in range(N):
  divisible = 0
  for j in range(N):
    if i == j:
      continue
    elif (int(argv[i]) % int(argv[j])) == 0:
      divisible = 1
      break
      
  if divisible == 0:
    count += 1
    
print(count)

### FIXED CODE ###

N = int(input())

intList = list(map(int, input().split()))
intList.sort()

cntList = [1] * (intList[-1] + 1)

i = 0
j = 1
ans = 0

while i < (N - 1):
  base = intList[i]
  j = 1
  num = base
  if cntList[num] == 1:
    while num <= intList[-1]:
      if cntList[num] == 1:
        cntList[num] = 0
      j += 1
      num = base * j
    if intList[i] != intList[i+1]:
      ans += 1
  i += 1

if cntList[intList[-1]] == 1:
  ans += 1
  
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 1
flg = 0
for i in range(N):
    ans = ans * A[i]

if ans > 10**18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort()
A.reverse()
ans = 1
flg = 0
if A[-1] == 0:
    print(0)
else:
    for i in range(N):
        ans = ans * A[i]
        if ans > 10**18:
            flg = 1
            break


    if flg == 1:
        print(-1)
    else:
        print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
H = list(map(int,input().split()))
ten = [[0]*N for _ in range(N)]

good = 0

for r in range(M):
    A, B = map(int, input().split())
    ten[A-1][B-1] = H[B-1]
    ten[B-1][A-1] = H[A-1]

for i in range(N):
    if max(ten[i]) < H[i]:
        good += 1

print(good)


### FIXED CODE ###

N, M = map(int, input().split())
H = list(map(int,input().split()))
michi = [0]*N
hikui = [0]*N
good = 0

for _ in range(M):
    A, B = map(int, input().split())
    michi[A - 1] += 1
    michi[B - 1] += 1
    if H[A - 1] > H[B - 1]:
        hikui[A - 1] += 1
    if H[B - 1] > H[A - 1]:
        hikui[B - 1] += 1

for i in range(N):
    if michi[i] == hikui[i]:
        good += 1

print(good)
### BUGGY CODE ###

def resolve():
    N = int(input())
    S = list(input())

    ans = 0

    for i in range(N):
        for ii in range(i + 1, N):
            for iii in range(ii + 1, N):
                if ((ii - i) == (iii - ii)):
                    continue
                if (S[i] != S[ii] and S[ii] != S[iii] and S[i] != S[iii]):
                    ans += 1

    print(ans)


resolve()

### FIXED CODE ###

from collections import Counter


def resolve():
    n = int(input())
    s = input()
    cnt = Counter(s)
    ans = cnt['R'] * cnt['G'] * cnt['B']

    for i in range(n - 1):
        for j in range(i + 1, n):
            ken = j * 2 - i
            if (ken >= n):
                continue
            if (s[i] != s[j] and s[j] != s[ken] and s[i] != s[ken]):
                ans -= 1

    print(ans)

resolve()
### BUGGY CODE ###

import sys

sys.setrecursionlimit(1000000)
n, q = map(int, input().split())

ki = [[] for i in range(n + 1)]
for i in range(n - 1):
    a, b = map(int, input().split())
    ki[a].append(b)
    ki[b].append(a)
# print(ki)

cnt = [0] * (n + 1)
for i in range(q):
    p, x = map(int, input().split())
    cnt[p] += x


# print(cnt)


def d(y, parent):
    for i in ki[y]:
        if i == parent:
            continue
        cnt[i] += cnt[y]
        d(i, y)


d(1, -1)
print(*cnt[1:])

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
n, q = map(int, input().split())

ki = [[] for i in range(n + 1)]
for i in range(n - 1):
    a, b = map(int, input().split())
    ki[a].append(b)
    ki[b].append(a)
# print(ki)

cnt = [0] * (n + 1)
for i in range(q):
    p, x = map(int, input().split())
    cnt[p] += x


# print(cnt)


def d(y, parent):
    for i in ki[y]:
        if i == parent:
            continue
        cnt[i] += cnt[y]
        d(i, y)


d(1, -1)
print(*cnt[1:])
### BUGGY CODE ###

def bubble_sort(a):
    cnt = 0
    for i in range(len(a)):
        for j in range(len(a) - 1, i, -1):
            if a[j] < a[j-1]:
                a[j], a[j - 1] = a[j - 1], a[j]
                cnt += 1
    return cnt

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

### FIXED CODE ###

SENTINEL = 10 ** 9 +1
cnt = 0
def merge(A, left, mid, right):
    global cnt

    L = A[left:mid] + [SENTINEL]
    R = A[mid:right] + [SENTINEL]
    
    i = j = 0
    for k in range(left, right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
            cnt += mid - left - i  # ☆

def merge_sort(A, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        merge_sort(A, left, mid)
        merge_sort(A, mid, right)
        merge(A, left, mid, right)

n = input()
A = list(map(int, input().split()))
merge_sort(A,0,len(A))
print(cnt)
### BUGGY CODE ###

import sys
n, p = [int(i) for i in sys.stdin.readline().split()]
s = input()

memo_ls = [{0:0} for j in range(n)]
memo_ls[0][int(s[0]) % p] = 1
for i, _s in enumerate(s[1:], 1):
    _s = int(_s)
    if memo_ls[i].get(_s % p) is None:
        memo_ls[i][_s % p] = 0
    memo_ls[i][_s % p] += 1
    for k, v in memo_ls[i-1].items():
        if memo_ls[i].get((k * 10 + _s) % p) is None:
            memo_ls[i][(k * 10 + _s) % p] = 0
        memo_ls[i][(k * 10 + _s) % p] += v

print(sum([memo_ls[i][0] for i in range(n)]))

### FIXED CODE ###

import sys
from collections import Counter
n, p = [int(i) for i in sys.stdin.readline().split()]
s = sys.stdin.readline().strip()
if p == 2:
    ans = 0
    for i, _s in enumerate(s, 1):
        if int(_s) % 2 == 0:
            ans += i
    print(ans)
elif p == 5:
    ans = 0
    for i, _s in enumerate(s, 1):
        if int(_s) in {0, 5}:
            ans += i
    print(ans)
else:
    us = Counter([])
    cur = ""
    ans = 0
    mod = 0
    keta_mod = 1
    for i, _s in enumerate(s[::-1]):
        keta_mod = keta_mod * 10 % p
        mod = (keta_mod * int(_s) + mod) % p
        if mod == 0:
            ans += us[mod] + 1
        else:
            ans += us[mod]
        us.update([mod])
    print(ans)
### BUGGY CODE ###

def prime(x):
    if x == 2:
        return 2
    num_list = list(range(3, (10 ** 5) * 2, 2))
    n = 3
    while (n < x):        
        num_list = [num for num in num_list if ((num % n) != 0)]
        n = num_list.pop(0)
    return n

x = int(input())
print(prime(x))

### FIXED CODE ###

import math


def is_prime(x):
    for i in range(3, math.ceil((x ** 0.5) + 1), 2):
        if x % i == 0:
            return False
    return True

x = int(input())

if x == 2:
    print(2)
else:
    if x % 2 == 0:
        x += 1
    while (not is_prime(x)):
        x += 2
    print(x)
### BUGGY CODE ###

N=int(input())
data=list(map(int,input().split()))
s=1
for d in data:
    if d == 0:
        print(0)
        break
else:
    for d in data:
        s *= d
    if s > 10**18:
        print(-1)
    else:
        print(s)

### FIXED CODE ###

N=int(input())
data=list(map(int,input().split()))
if 0 in data:
    print(0)
else:
    s=1
    for f in data:
        s *= f
        if s > 10**18:
            break
    if s > 10**18:
        print(-1)
    else:
        print(s)
### BUGGY CODE ###

import sys


N,P = map(int,input().split())
S = list(sys.stdin.readline().rstrip())

A = [0]*(N)
A[-1] = int(S[-1])
A[-1] %= P
base = 10
for i in reversed(range(N-1)):
    A[i] = A[i+1] + base*int(S[i])
    A[i] %= P
    base *= 10


ans = 0
if P==2 or P==5:
    for i in reversed(range(N)):
        if int(S[i])%P==0:
            ans += i+1
else:
    nums = {}
    for a in A:
        nums[a] = 0
    for a in A:
        nums[a] += 1
    
    for n in nums.keys():
        k = nums[n]
        if n==0:
            ans += k*(k+1)//2
        else:
            ans += k*(k-1)//2
    
print(ans)    



### FIXED CODE ###

import sys


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

A = [0]*(N)
A[-1] = int(S[-1])
A[-1] %= P
base = 10 % P
for i in reversed(range(N-1)):
    A[i] = A[i+1] + base*int(S[i])
    A[i] %= P
    base *= 10
    base %= P


ans = 0
if P==2 or P==5:
    for i in reversed(range(N)):
        if int(S[i])%P==0:
            ans += i+1
else:
    nums = {}
    for a in A:
        if not (a in nums):
            nums[a] = 1
        else:
            nums[a] += 1
    
    for n in nums.keys():
        k = nums[n]
        if n==0:
            ans += k*(k+1)//2
        else:
            ans += k*(k-1)//2
    
print(ans)
### BUGGY CODE ###

import sys
n = int(sys.stdin.readline())
S = sys.stdin.readline().rstrip()


dp = [[0 for i in range(n)] for j in range(n)]
#初期条件
for j in range(1, n):
    if S[0] == S[j]:
        dp[0][j] = 1
    else:
        dp[0][j] = 0

#print(dp)

for i in range(1, n-1):
    for j in range(i+1, n):
        if S[i] ==S[j]:
            dp[i][j] = min(dp[i-1][j-1] +1, n//2)
        else:
            dp[i][j] = 0

maxp = 0
for i in range(1, n-1):
    for j in range(i+1, n):
        if maxp < dp[i][j]:
            maxp = dp[i][j]
#print(dp)
print(maxp)

### FIXED CODE ###

import sys
n = int(sys.stdin.readline())
S = sys.stdin.readline().rstrip()


dp = [[0 for i in range(n)] for j in range(n)]
#初期条件
for j in range(1, n):
    if S[0] == S[j]:
        dp[0][j] = 1

#print(dp)

for i in range(1, n-1):
    for j in range(i+1, n):
        if S[i] ==S[j]:
            dp[i][j] = min(dp[i-1][j-1] +1, j-i)

maxp = 0
for i in range(n-1):
    for j in range(i+1, n):
        if maxp < dp[i][j]:
            maxp = dp[i][j]
#print(dp)
print(maxp)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(int(1e9))
mod = int((1e9) + 7)

S = input()
N = len(S)

rS = S[::-1]
p = [1] * (N+1)
for i in range(1, N+1):
    p[i] = p[i-1]
    if rS[i-1] == '?':
        p[i] = p[i] * 3
p.reverse()

mem = [[0] * 3 for _ in range(N)]
used = [[0] * 3 for _ in range(N)]
ch = ['A', 'B', 'C']



def dfs(idx, num):
    if num == 3:
        return 1 * p[idx]
    
    if idx == N:
        return 0
    
    if used[idx][num]:
        return mem[idx][num]
    used[idx][num] = 1

    a, b = (0, 0);
    if S[idx] == '?':
        a = dfs(idx + 1, num + 1)    
        b = 3 * dfs(idx + 1, num)
    else:
        if S[idx] == ch[num]:
            a = dfs(idx + 1, num + 1)
        b = dfs(idx + 1, num)
        
    res = (a + b)%mod
    mem[idx][num] = res
    return res

ans = dfs(0, 0)
print (ans)
    


### FIXED CODE ###

import sys
sys.setrecursionlimit(int(1e9))
mod = int((1e9) + 7)

S = input()
N = len(S)

p = [1] * (N+1)
for i in range(1, N+1):
    p[i] = p[i-1]
    if S[N-i] == '?':
        p[i] = p[i] * 3 % mod
p.reverse()

mem = [[0] * 3 for _ in range(N)]
used = [[0] * 3 for _ in range(N)]
ch = ['A', 'B', 'C']



def dfs(idx, num):
    if num == 3:
        return 1 * p[idx]
    
    if idx == N:
        return 0
    
    if used[idx][num]:
        return mem[idx][num]
    used[idx][num] = 1

    a, b = (0, 0);
    if S[idx] == '?':
        a = dfs(idx + 1, num + 1)    
        b = 3 * dfs(idx + 1, num)
    else:
        if S[idx] == ch[num]:
            a = dfs(idx + 1, num + 1)
        b = dfs(idx + 1, num)
        
    res = (a + b) % mod
    mem[idx][num] = res
    return res

ans = dfs(0, 0) % mod
print (ans)