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

S=input()
lens=len(S)

mod=10**9+7

Alist=[0]*lens
Blist=[0]*lens
Clist=[0]*lens
qlist=[0]*lens

for i in range(lens):
    if S[i]=="A":
        Alist[i]=1
    elif S[i]=="B":
        Blist[i]=1
    elif S[i]=="C":
        Clist[i]=1
    elif S[i]=="?":
        qlist[i]=1


Asum=[0]*lens
Bsum=[0]*lens
Csum=[0]*lens
qsum=[0]*lens

for i in range(lens):
    Asum[i]=Asum[i-1]+Alist[i]
    Bsum[i]=Bsum[i-1]+Blist[i]
    Csum[i]=Csum[i-1]+Clist[i]
    qsum[i]=qsum[i-1]+qlist[i]

ASUM=Asum[lens-1]
CSUM=Csum[lens-1]
QSUM=qsum[lens-1]


count=0
for i in range(1,lens-1):
    if S[i]=="B":
        count+=Asum[i-1]*(CSUM-Csum[i])*(3**max(0,QSUM))%mod
        count+=Asum[i-1]*(QSUM-qsum[i])*(3**max(0,(QSUM-1)))%mod
        count+=qsum[i-1]*(CSUM-Csum[i])*(3**max(0,(QSUM-1)))%mod
        count+=qsum[i-1]*(QSUM-qsum[i])*(3**max(0,(QSUM-2)))%mod


    if S[i]=="?":
        count+=Asum[i-1]*(CSUM-Csum[i])*(3**max(0,(QSUM-1)))%mod
        count+=Asum[i-1]*(QSUM-qsum[i])*(3**max(0,(QSUM-2)))%mod
        count+=qsum[i-1]*(CSUM-Csum[i])*(3**max(0,(QSUM-2)))%mod
        count+=qsum[i-1]*(QSUM-qsum[i])*(3**max(0,(QSUM-3)))%mod

        
    



#count=0
#for a in range(lens-2):
#    if S[a]=="A" or S[a]=="?":
#        for b in range(a+1,lens-1):
#            if S[b]=="B" or S[b]=="?":
#                for c in range(b+1,lens):
#                    if S[c]=="C" or S[c]=="?":
#                        count+=1
print(count%mod)


            


### FIXED CODE ###

S=input()
lens=len(S)

mod=10**9+7


Asum=[0]*lens
#Bsum=[0]*lens
Csum=[0]*lens
qsum=[0]*lens

for i in range(lens):
    if S[i]=="A":
        Asum[i]=Asum[i-1]+1
        Csum[i]=Csum[i-1]
        qsum[i]=qsum[i-1]
    elif S[i]=="C":
        Asum[i]=Asum[i-1]
        Csum[i]=Csum[i-1]+1
        qsum[i]=qsum[i-1]
    elif S[i]=="?":
        Asum[i]=Asum[i-1]
        Csum[i]=Csum[i-1]
        qsum[i]=qsum[i-1]+1
    else:
        Asum[i]=Asum[i-1]
        Csum[i]=Csum[i-1]
        qsum[i]=qsum[i-1]        

CSUM=Csum[lens-1]
QSUM=qsum[lens-1]


count=0
for i in range(1,lens-1):
    if S[i]=="B":
        count+=Asum[i-1]*(CSUM-Csum[i])*pow(3,max(0,QSUM),mod)%mod
        count+=Asum[i-1]*(QSUM-qsum[i])*pow(3,max(0,QSUM-1),mod)%mod
        count+=qsum[i-1]*(CSUM-Csum[i])*pow(3,max(0,QSUM-1),mod)%mod
        count+=qsum[i-1]*(QSUM-qsum[i])*pow(3,max(0,QSUM-2),mod)%mod


    elif S[i]=="?":
        count+=Asum[i-1]*(CSUM-Csum[i])*pow(3,max(0,QSUM-1),mod)%mod
        count+=Asum[i-1]*(QSUM-qsum[i])*pow(3,max(0,QSUM-2),mod)%mod
        count+=qsum[i-1]*(CSUM-Csum[i])*pow(3,max(0,QSUM-2),mod)%mod
        count+=qsum[i-1]*(QSUM-qsum[i])*pow(3,max(0,QSUM-3),mod)%mod
        
    



#count=0
#for a in range(lens-2):
#    if S[a]=="A" or S[a]=="?":
#        for b in range(a+1,lens-1):
#            if S[b]=="B" or S[b]=="?":
#                for c in range(b+1,lens):
#                    if S[c]=="C" or S[c]=="?":
#                        count+=1
print(count%mod)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
aa = a+a
g = sum(a)//2
ans = []
for i in range(n):
    temp = sum([aa[i+1+j*2] for j in range(n//2)])
    ans.append(g-temp)
for k in ans:
    print(2*k,end=" ")
        

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
aa = a+a
g = sum(a)//2
ans = []
for i in range(1):
    temp = sum([aa[i+1+j*2] for j in range(n//2)])
    ans.append(g-temp)
temp = ans[0]
for i in range(1,n):
    temp = a[i-1] - temp
    ans.append(temp)
for k in ans:
    print(2*k,end=" ")
### BUGGY CODE ###

import itertools

s = input()
K = int(input())

l = len(s)
substr = []
for i, j in itertools.combinations_with_replacement(list(range(0, l)), 2):
    substr.append(s[i:j+1])

substr = list(set(substr))
substr.sort()
print(substr[K-1])


### FIXED CODE ###

s = input()
K = int(input())

l = len(s)
substr = []

for i in range(l):
    for k in range(K):
        substr.append(s[i:i+k+1])
        if i+k+1 >= l: break

substr = list(set(substr))
substr.sort()
print(substr[K-1])
### BUGGY CODE ###

n,m = map(int,input().split())
alis = list(map(int,input().split()))
lis = [list(map(int,input().split())) for x in range(m)]
clis = [[x[1]]*x[0] for x in lis]
clis = [x for y in clis for x in y]
l = len(clis)
clis.sort(reverse=True)
alis.sort()
ans = 0
for x,y in zip(alis,clis):
    ans += max(x,y)
if n>l:
    ans += sum(alis[l:])
print(ans)


### FIXED CODE ###

n,m = map(int,input().split())
alis = list(map(int,input().split()))
lis = [list(map(int,input().split())) for x in range(m)]
for x in alis:
    lis.append([1,x])
lis.sort(reverse=True,key=lambda x:x[1])
ans = 0
for x in lis:
    (number,point) = x
    if number >= n:
        number = n
        ans += number * point
        #print(n)
        #print(ans,'+=',number,'*',point)
        break
    ans += number * point
    n -= number
    #print(n)
    #print(ans,'+=',number,'*',point)
print(ans)
#print(lis)
### BUGGY CODE ###

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

order = []


for i in range(1,n+1):
    order.append(str(a.index(i)+1))
    


print(' '.join(order))

### FIXED CODE ###

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

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

for i in range(n):
    ans[a[i]-1] = i+1

print(' '.join(map(str,ans)))
### BUGGY CODE ###

from collections import deque


def main():
    n, m = map(int, input().split())
    g = [[] for _ in range(n)]
    for _ in range(m):
        a, b = map(lambda x: int(x) - 1, input().split())
        g[a].append(b)
        g[b].append(a)
    max_val = 10 ** 9 + 7
    dist = [max_val for _ in range(n)]
    prev = [-1 for _ in range(n)]
    dist[0] = 0

    q = deque([0])
    while q:
        now = q.pop()
        for next in g[now]:
            if prev[next] < 0 or dist[now] + 1 < dist[next]:
                if prev[next] < 0:
                    q.append(next)
                else:
                    q.appendleft(next)
                prev[next] = now + 1
                dist[next] = dist[now] + 1
    if all(prev[i] > 0 for i in range(1, n)):
        print("Yes")
        for i in range(1, n):
            print(prev[i])
    else:
        print("No")


if __name__ == '__main__':
    main()



### FIXED CODE ###

from collections import deque


def main():
    n, m = map(int, input().split())
    g = [[] for _ in range(n)]
    for _ in range(m):
        a, b = map(lambda x: int(x) - 1, input().split())
        g[a].append(b)
        g[b].append(a)
    max_val = 10 ** 9 + 7
    dist = [max_val for _ in range(n)]
    prev = [-1 for _ in range(n)]
    dist[0] = 0
    q = deque([0])
    cnt = 0
    while q:
        now = q.popleft()
        for next in g[now]:
            if prev[next] < 0:
                if prev[next] < 0:
                    q.append(next)
                    cnt += 1
                prev[next] = now + 1
                dist[next] = dist[now] + 1
    if cnt == n:
        print("Yes")
        for i in range(1, n):
            print(prev[i])
    else:
        print("No")


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

from collections import deque

H, W = map(int, input().split())
S = [input() for i in range(H)]
l = []
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

for i in range(H):
    for j in range(W):
        if S[i][j] == '.':
            l.append((i, j))

m = -1
for start in l:
    for goal in l:
        visited = [[-1]*W for i in range(H)]
        d = deque()
        d.appendleft(start)
        visited[start[0]][start[1]] = 0
        while d:
            now = d.pop()
            for direction in directions:
                next = (now[0]+direction[0], now[1]+direction[1])
                if not (next[0] in range(H) and next[1] in range(W)):
                    continue
                if visited[next[0]][next[1]] != -1:
                    continue
                if S[next[0]][next[1]] == '.':
                    visited[next[0]][next[1]] = visited[now[0]][now[1]] + 1
                    d.appendleft(next)

        m = max(visited[goal[0]][goal[1]], m)

print(m)

### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
S = [input() for i in range(H)]
l = []
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

for i in range(H):
    for j in range(W):
        if S[i][j] == '.':
            l.append((i, j))

m = -1
N = len(l)
for i in range(N-1):
    for j in range(i+1, N):
        start = l[i]
        goal = l[j]
        visited = [[-1]*W for i in range(H)]
        d = deque()
        d.appendleft(start)
        visited[start[0]][start[1]] = 0
        while d:
            now = d.pop()
            for direction in directions:
                next = (now[0]+direction[0], now[1]+direction[1])
                if not (next[0] in range(H) and next[1] in range(W)):
                    continue
                if visited[next[0]][next[1]] != -1:
                    continue
                if S[next[0]][next[1]] == '.':
                    visited[next[0]][next[1]] = visited[now[0]][now[1]] + 1
                    d.appendleft(next)
                if next == goal:
                    m = max(visited[goal[0]][goal[1]], m)
                    d = deque()

print(m)
### BUGGY CODE ###

import numpy as np

N, W = map(int, input().split())
wv = [[0,0]]
for _ in range(N):
    wv.append( list(map(int, input().split())))
# N,W = 3, 8
# wv = [[0,0],[3,30], [4,50], [5,60]]
dp = np.array([ [0]*(W+1) ] * (N+1))
# print(dp.shape)
# print(np.array(dp))

for n in range(1,N+1):
    for w_lim in range(1,W+1):
        # print(n, w_lim)
        # print(np.array(dp))
        # v[n]を追加するとき
        if w_lim - wv[n][0] >= 0 :
            dp[n][w_lim] = max( dp[n-1][w_lim], dp[n-1][w_lim-wv[n][0]]+wv[n][1] )
        else :
            dp[n][w_lim] = dp[n-1][w_lim]

# print('\n',np.array(dp))
print(dp[N][W])


### FIXED CODE ###

import numpy as np

N, W = map(int, input().split())
dp = np.array([ [0]*(W+1) ] * (N+1))
for n in range(1,N+1):
    w, v = map(int, input().split() )
    dp[n][:] = dp[n-1][:]
    dp[n][w:W+1] = np.maximum(dp[n-1][w:W+1], dp[n-1][:W+1-w]+v )
    # for w_lim in range(1,W+1):
    #     if w_lim - wv[n][0] >= 0 :
    #         dp[n][w_lim] = max( dp[n-1][w_lim], dp[n-1][w_lim-wv[n][0]]+wv[n][1] )
    #     else :
    #         dp[n][w_lim] = dp[n-1][w_lim]
print(dp[N][W])
### BUGGY CODE ###

inf = input().split()
N = int(inf[0])
M = int(inf[1])
cards = [int(a) for a in input().split()]
cards.sort()
for i in range(M):
  inf = input().split()
  C = int(inf[0])
  B = int(inf[1])
  i = 0
  while cards[i] < B:
    cards[i] = B
    i+=1
    C -= 1
    if C==0:
      break
  cards.sort()

print(sum(cards))

### FIXED CODE ###

from collections import defaultdict
inf = input().split()
N = int(inf[0])
W = int(inf[1])
dic = defaultdict(int)

line = input().split()

for a in line:
    dic[int(a)] += 1

for w in range(W):
    inf = input().split()
    b = int(inf[0])
    c = int(inf[1])
    dic[c] += b
    
keys = list(dic.keys())

keys.sort(reverse=True)

count = 0
ans = 0
for k in keys:
    while dic[k]>0:
        if count == N:
            break
        ans += k
        dic[k] -= 1
        count += 1
    if count == N:
        break

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

import math
from operator import mul
from functools import reduce
n, a, b = map(int, input().split())
s=0
def combinations_count(n, r):
    #return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom
if n==2:
    print('0')
else:
    if n%2==1:
        for i in range(1,int(n/2)+1):
            s+=combinations_count(n, i)
        s=s*2
        s+=1
        s-=combinations_count(n, a)
        s-=combinations_count(n, b)
    else:
        for i in range(1,int(n/2)):
            s+=combinations_count(n, i)
        s=s*2
        s+=combinations_count(n, int(n/2))
        s+=1
        s-=combinations_count(n, a)
        s-=combinations_count(n, b)
    print(s)

### FIXED CODE ###


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
n, a, b = map(int, input().split())
mod = pow(10, 9) + 7
 
def comb(N, x):
    numerator = 1
    for i in range(N-x+1, N+1):
        numerator = numerator * i % mod
    denominator = 1
    for j in range(1, x+1):
        denominator = denominator * j % mod
    d = pow(denominator, mod-2, mod)
    return numerator * d
 
a = comb(n, a)
b = comb(n, b)
 
print((pow(2, n, mod) -1 -a -b) % mod)
### BUGGY CODE ###

N = int(input())
S = list(map(int,input().split()))
counter = int(0)
tmp = int(0)
breakPoint = int(0)

if N == 1:
  print("1")

else:
  for i in S:
    tmp = tmp + 1
    if tmp == 1:
      counter = counter + 1
      continue
    for j in range(0,tmp-1):
      if S[j] < i:
        breakPoint = 1
        break
      else:
        continue
    if breakPoint == 0:
      counter = counter + 1
    else:
      breakPoint = 0
  print(counter)

### FIXED CODE ###

N = int(input())
S = list(map(int,input().split()))
counter = int(0)
minNum = S[0]

if N == 1:
  print("1")

else:
  for i in range(N):
    if minNum >= S[i]:
      minNum = S[i]
      counter = counter + 1
    
  print(counter)
### BUGGY CODE ###

from copy import deepcopy
dp = {}

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

balls = {}
fact = 1
for (i, a) in enumerate(A):
  if a in balls:
    balls[a] += 1
  else:
    balls[a] = 1

for a in A:
  check_balls = deepcopy(balls)
  check_balls[a] -= 1
  res = 0
  for count in check_balls.values():
    if not count in dp:
      dp[count] = count * (count-1) // 2
    res += dp[count]
  print(res)

### FIXED CODE ###

from copy import deepcopy
dp = {0: 0}

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

balls = {}
fact = 1
for (i, a) in enumerate(A):
  count = i+1
  dp[count] = count * (count-1) // 2
  if a in balls:
    balls[a] += 1
  else:
    balls[a] = 1

res = 0
for count in balls.values():
  res += dp[count]

for a in A:
  print(res - dp[balls[a]] + dp[balls[a]-1])
### BUGGY CODE ###

from operator import itemgetter

N = int(input())
l = [list(map(int, input().split())) for _ in range(N)]
ans = []
for i in range(N):
  l[i].append(l[i][0] - l[i][1])
  l[i].append(l[i][0] + l[i][1])
  del l[i][:2]
l.sort(key = itemgetter(1))
cnt = 0
for i in range(1, N):
  for j in range(i, -N, -1):
    if l[j-1][0] == - 10 ** 9:
      continue
    if l[i][0] < l[j-1][1]:
        l[i][0] = - 10 ** 9
        l[i][1] = - 10 ** 9
        cnt += 1
    break
print(N-cnt)

### FIXED CODE ###

from operator import itemgetter

N = int(input())
l = []
for i in range(N):
  a, b = map(int, input().split())
  s = [a-b, a+b]
  l.append(s)

l.sort(key = itemgetter(1))
cnt = 0
s = - 10 ** 10
for i in range(N):
  if l[i][0] >= s:
    s = l[i][1]
  else:
    cnt += 1
print(N-cnt)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
b = 0
for m in range(n-1):
    d = 0
    for o in range(m+1,n):
        d = d+a[o]
    b = b + a[m]*d
c = b % (10**9+7)
print(c)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
b = 0
d = sum(a)
for m in range(n-1):
    d = d -a[m]
    b = b + a[m]*d
    if b >= 10**9+7:
        b = b % (10**9+7)
print(b)
### BUGGY CODE ###

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

for _ in range(m):
  i = a.index(max(a))
  a[i] //= 2

print(sum(a))

### FIXED CODE ###

import heapq
n,m=map(int,input().split())
a=list(map(lambda x: x*(-1),map(int,input().split())))
heapq.heapify(a)

for _ in range(m):
    k = heapq.heappop(a)*(-1) // 2
    heapq.heappush(a,k*(-1))
print(sum(a)*(-1))
### BUGGY CODE ###

S = input()
mod = 2019
L = [0]*mod
n = 0
for i in range(len(S)-1, -1, -1):
    n += (int(S[i])*10**(len(S)-i-1))%mod
    n %= mod
    L[n] += 1

ans = 0
L[0] += 1
for l in L:
    ans += l*(l-1)//2
print(ans)

### FIXED CODE ###

S = input()
mod = 2019
L = [0]*mod
n = 0
for i in range(len(S)-1, -1, -1):
    n += int(S[i])*pow(10, len(S)-i-1, mod)
    n %= mod
    L[n] += 1

ans = 0
L[0] += 1
for l in L:
    ans += l*(l-1)//2
print(ans)
### BUGGY CODE ###


S = input()
mod = 10**9+7
N = len(S)

dp = [[0 for _ in range(13)] for _ in range(N+1)]
dp[0][0] = 1

for i in range(N):
    for j in range(13):
        if S[i] == '?':
            for k in range(10):
                dp[i+1][(j*10+k)%13] += dp[i][j]
                dp[i+1][(j*10+k)%13] %= mod
        else:
            dp[i+1][(j*10+int(S[i]))%13] += dp[i][j]
            dp[i+1][(j*10+int(S[i]))%13] %= mod

print(dp[N][5])


### FIXED CODE ###


S = input()
mod = 10**9+7
N = len(S)

dp = [[0 for _ in range(13)] for _ in range(N+1)]
dp[0][0] = 1

for i in range(N):
    for j in range(13):
        if S[i] == '?':
            for k in range(10):
                dp[i+1][(j*10+k)%13] += dp[i][j]
                dp[i+1][(j*10+k)%13] %= mod
        else:
            dp[i+1][(j*10+int(S[i]))%13] += dp[i][j]
            dp[i+1][(j*10+int(S[i]))%13] %= mod

print(dp[N][5])
### BUGGY CODE ###

import numpy as np
n=int(input())
l=np.array(list(map(int,input().split())))
r=list(np.arange(1,n)-l[1:])
rx=sorted(r)
for i in range(n-1):
  r[i]=[r[i],i]
r=sorted(r)
t=list(l+np.arange(n))
ans=0
import bisect
for i in range(n):
  le=bisect.bisect_left(rx,t[i])
  ri=bisect.bisect_right(rx,t[i])
  for j in range(ri-le):
    if i<r[le+j][1]:
      ans+=1
print(ans)  

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
r=[0]*(n-1)
t=[0]*(n)
dr={}
dt={l[0]:[0]}
for i in range(1,n):
  x=i-l[i]
  y=i+l[i]
  if x in dr:
    dr[x].append(i)
  else:
    dr[x]=[i]
  if y in dt:
    dt[y].append(i)
  else:
    dt[y]=[i]
ans=0
for x in dr.keys():
  if x>0 and x in dt:
    y=dr[x]
    z=dt[x]
    ans+=len(z)*len(y)
print(ans)
### BUGGY CODE ###

import math



def search2(S):
    harf = int(len(A)/2)
    for i, a in enumerate(A[harf:]):
        if a < S:
            A[i] = S
            return 
    return

def search(S):

    for i, a in enumerate(A):
        if a < S:
            A[i] = S
            return 
    return



def main():
    N = int(input())
    A[0] = int(input())
    m = A[0]
    harf = 0
    for _ in range(N-1):
        S = int(input())
        if S <= m:
            A.append(S)
        if S <= m:
            search2(S)
        else:
            search(S)
        m = A[-1]
        harf = A[int(len(A)/2)]
    print(len(A))

    

if __name__ == "__main__":
    A = [0]
    main()


### FIXED CODE ###

from bisect import bisect


def main():
    N = int(input())
    A = [-int(input()) for _ in range(N)]
    L = [A[0]]
    for a in A[1:]:
        if a >= L[-1]:
            L.append(a)
        else:
            L[bisect(L, a)] = a
    print(len(L))


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

from collections import Counter
N = int(input())
S = Counter(input() for _ in range(N))
if len(S) == 1:
    print(list(S)[0])
    exit()
for k, val in sorted(S.most_common()):
    if val == max(S.values()):
        print(k)

### FIXED CODE ###

from collections import Counter
N = int(input())
S = Counter([input() for _ in range(N)])
v = max(S.values())
s = sorted(S.most_common())
if len(S) == 1:
    print(list(S)[0])
    exit()
for k, val in s:
    if val == v:
        print(k)
### BUGGY CODE ###

import fractions
from functools import reduce
MOD = 10**9 + 7
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

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

num = lcm_list(a)
ans = 0
for i in a:
    ans += num // i
    ans %= MOD
    
print(ans)




### FIXED CODE ###

import fractions
from functools import reduce
MOD = 10**9 + 7
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

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

num = lcm_list(a)
ans = 0
for i in a:
    ans += num // i

ans %= MOD
print(ans)
### BUGGY CODE ###

from collections import defaultdict


def p_e():
    s = input()
    t = input()
    l = defaultdict(list)

    for i, c in enumerate(list(s)):
        l[c].append(i + 1)

    for c in list(t):
        if c not in l.keys():
            print(-1)
            exit()

    N = 0
    current = 0
    for c in list(t):
        R = l[c]

        if current >= R[-1]:
            current = R[0]
            N += 1
            continue

        for i in R:
            if current < i:
                current = i
                break

    print(N * len(s) + current)


if __name__ == '__main__':
    p_e()


### FIXED CODE ###

from collections import defaultdict
from bisect import *


def p_e():
    s = input()
    t = input()
    l = defaultdict(list)

    for i, c in enumerate(list(s)):
        l[c].append(i + 1)

    for c in list(t):
        if c not in l.keys():
            print(-1)
            exit()

    N = 0
    current = -1
    for c in list(t):
        R = l[c]

        x = bisect(R, current)

        if len(R) == x:
            N += 1
            current = R[0]
        else:
            current = R[x]

    print(N * len(s) + current)


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

n = int(input())
a = list(map(int,input().split()))
pair = 0
for i in range(0,n-1):
    for j in range(i+1,n):
        if a[i]==j+1 and a[j]==i+1:
            pair += 1
print(pair)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
pair = 0
for i in range(0,n):
    if a[a[i]-1]==i+1:
        pair+=1
print(pair//2)
### BUGGY CODE ###

n,m=map(int,input().split())
s=list(map(int,input().split()))
t=list(map(int,input().split()))
dp=[[0]*(m+1) for _ in range(n+1)]
for i in range(n+1):
  dp[i][0]=1
for i in range(m+1):
  dp[0][i]=1
mod=pow(10,9)+7
for i in range(n):
  for j in range(m):
    dp[i+1][j+1]=sum((dp[i][j+1],dp[i+1][j],-dp[i][j]))%mod
    if s[i]==t[j]:dp[i+1][j+1]+=dp[i][j]
    dp[i+1][j+1]%=mod
print(dp[-1][-1])
#print(dp)

### FIXED CODE ###

n,m=map(int,input().split())
s=list(map(int,input().split()))
t=list(map(int,input().split()))
dp=[[0]*(m+1) for _ in range(n+1)]
for i in range(n+1):
  dp[i][0]=1
for i in range(m+1):
  dp[0][i]=1
mod=pow(10,9)+7
for i in range(n):
  for j in range(m):
    dp[i+1][j+1]=sum((dp[i][j+1],dp[i+1][j],-dp[i][j]))%mod
    if s[i]==t[j]:dp[i+1][j+1]+=dp[i][j]
    dp[i+1][j+1]%=mod
print(dp[-1][-1])
#print(dp)
### BUGGY CODE ###

s = input()
s = list(s.replace("BC", "D"))
pos = 0
str_len = len(s)
count = 0
state = 0
seq_a = 0
seq_d = 0


while pos < str_len:
    if state == 0:
        if s[pos] == "A":
            state = 1
            seq_a = 1
        pos += 1
    elif state == 1:
        if s[pos] == "A":
            state = 1
            seq_a += 1
            pos += 1
        elif s[pos] == "D":
            while pos < str_len and s[pos] == "D":
                seq_d += 1
                pos += 1
            tmp_pos = pos - seq_a
#            for i in range(tmp_pos-seq_d, tmp_pos):
#                s[i] = "D"
            for i in range(tmp_pos, pos):
                s[i] = "A"
            pos = tmp_pos
            count += seq_a * seq_d
            state = 0
            seq_a = 0
            seq_d = 0
        else:
            state = 0
            pos += 1

print(count)


### FIXED CODE ###

s = input()
pos = 0
str_len = len(s)
count = 0
seq_a = 0
seq_bc = 0

while pos < str_len:
    if s[pos] == "A":
        while pos < str_len and s[pos] == "A":
            seq_a += 1
            pos += 1
        if pos + 1 < str_len and s[pos] == "B" and s[pos+1] == "C":
            while pos < str_len and s[pos] == "B" and pos + 1 < str_len and s[pos+1] == "C":
                seq_bc += 1
                pos += 2
            count += seq_a * seq_bc
            if pos < str_len and s[pos] != "A":
                seq_a = 0
            seq_bc = 0
        else:
            pos += 1
            seq_a = 0
    else:
        pos += 1
        seq_a = 0

print(count)