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

from collections import deque
n,x,y=map(int,input().split())

L=[[0]*n for i in range(n)]
for i in range(n-1):
	L[i][i+1]=L[i+1][i]=1
L[x-1][y-1]=L[y-1][x-1]=1

R=[0]*n

def bfs(j):
	V=[-1]*n
	que=deque([])
	que.append(j)
	V[j]=0
	while que:
		p=que.popleft()
		for i in range(n):
			if V[i]==-1 and L[p][i]==1:
				que.append(i)
				V[i]=V[p]+1
	for i in range(n):
		R[V[i]]+=1
	
for j in range(n):
	bfs(j)
for i in range(1,n):
	print(R[i]//2)

### FIXED CODE ###

from collections import deque
n,x,y=map(int,input().split())

L=[[1]]
for i in range(1,n-1):
	L.append([i-1,i+1])
L.append([n-2])
L[x-1].append(y-1)
L[y-1].append(x-1)

R=[0]*n

def bfs(j):
	V=[-1]*n
	que=deque([])
	que.append(j)
	V[j]=0
	while que:
		p=que.popleft()
		for np in L[p]:
			if V[np]==-1:
				que.append(np)
				V[np]=V[p]+1
	for i in range(n):
		R[V[i]]+=1
	
for j in range(n):
	bfs(j)
for i in range(1,n):
	print(R[i]//2)
### BUGGY CODE ###

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

S_list = {}
for i in range(M):
    S_list[i+1] = 0

participants = 10000
while len(S_list) > 0:
    for i in range(N):
        for j in range(M):
            if A[i][j] in S_list:
                S_list[A[i][j]] += 1
                break
    participants = min(participants,max(S_list.values()))
    for i in S_list.keys():
        if S_list[i] == max(S_list.values()):
            del S_list[i]
            break
    for i in S_list.keys():
        S_list[i] = 0

print(participants)


### FIXED CODE ###

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

S_list = {}
for i in range(M):
    S_list[i+1] = 0

participants = 10000
while len(S_list) > 0:
    for i in range(N):
        for j in range(M):
            if A[i][j] in S_list:
                S_list[A[i][j]] += 1
                break
    participants = min(participants,max(S_list.values()))
    if participants == 1:
        break
    for i in S_list.keys():
        if S_list[i] == max(S_list.values()):
            del S_list[i]
            break
    for i in S_list.keys():
        S_list[i] = 0

print(participants)
### BUGGY CODE ###

import math

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

def prime_decomposition(n):
    p = 2
    prime = {}
    while n!=1:
        while n%p == 0:
            n = n//p
            if p not in prime:
                prime[p] = 0
            prime[p] += 1
        p += 1
    return prime

primes = prime_decomposition(m)
ans = 1

def combination(n,k):
    ret1 = 1
    ret2 = 1
    for i in range(k):
        ret1 *= n-i
        ret2 *= k-i
    return ret1//ret2

for pw in primes.values():
    comb = combination(pw+n-1, pw)
    ans *= comb
    ans %= mod

print(ans)


### FIXED CODE ###

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

def prime_decomposition(n):
    p = 2
    prime = {}
    while n!=1:
        while n%p == 0:
            n = n//p
            if p not in prime:
                prime[p] = 0
            prime[p] += 1
        p += 1
    return prime

primes = prime_decomposition(m)
# print(primes)
ans = 1

def combination(n,k):
    ret1 = 1
    ret2 = 1
    for i in range(k):
        ret1 *= n-i
        ret2 *= k-i
    return ret1//ret2

for pw in primes.values():
    comb = combination(pw+n-1, pw)
    ans *= comb
    ans %= mod

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

#xorの性質
#AxorA=0、交換法則、結合法則が成立、bitごとに独立して考える！

import numpy as np

n=int(input())
a=np.array(list(map(int,input().split())))
res=0
for j in range(60):
  s=0 #1の数
  for i in a:
    if (i>>j & 0b1)==0b1:
      s+=1
  r=2**j*(n-s)*s
  res=(res+r)%(10**9+7)
print(res)

### FIXED CODE ###

#xorの性質
#AxorA=0、交換法則、結合法則が成立、bitごとに独立して考える！

import numpy as np

n=int(input())
a=np.array(list(map(int,input().split())))
res=0
for j in range(60):
  s=0 #1の数
  """
  for i in a:
    if (i>>j & 0b1)==0b1:
      s+=1
  """
  s=np.count_nonzero(a>>j&1)
  r=2**j*(n-s)*s
  res=(res+r)%(10**9+7)
print(res)
### BUGGY CODE ###

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

for i in range(n):
  for j in range(i+1,n):
    sum += a[i]*a[j]
    
sum = sum % (10**9+7)
print(sum)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
sum = 0
m = 10**9+7

for i in range(n):
  sum = sum+a[i]

#sum = sum%m
#sum = sum*sum
ans = 0
for i in range(n):
  ans = ans + sum*a[i]
  ans = ans - a[i]*a[i]
ans = ans//2%m

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

n = int(input())
a = [int(x) for x in input().split()]
ans = 0
for x in range(100000):
    cnt = 0
    for elem in a:
        if elem == x-1 or elem == x or elem == x + 1:
            cnt += 1
    ans = max(ans, cnt)
print(ans)


### FIXED CODE ###

n = int(input())
a = [int(x) for x in input().split()]
counta = [0 for _ in range(100000)]
ans = 0

for elem in a:
    counta[elem] += 1

for x in range(1, 100000 - 1):
    ans = max(ans, counta[x-1] + counta[x] + counta[x+1])

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

S = input()
S_list = [int(S[i]) for i in range(len(S))]
ans = 0
rm_list = []
for aaa in range(len(S)//2):
    for i in range(len(S_list) - 1):
        if S_list[i] != S_list[i + 1] and i not in rm_list:
            rm_list.append(i)
            rm_list.append(i + 1)
    S_list = [S_list[i] for i in range(len(S_list)) if i not in rm_list]
    ans += len(rm_list)
    rm_list = []
print(ans)

### FIXED CODE ###

S = input()
a = sum([int(S[i]) for i in range(len(S))])
b = len(S) - a
print(2*min(a, b))
### BUGGY CODE ###

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

def half(l):
  a=-1
  for i in range(len(l)):
    if l[i]==max(l):
      a=i
  l[a]=l[a]//2
  return(l)
for i in range(M):
  half(ls)
print(sum(ls))

### FIXED CODE ###

from collections import deque
N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
q1=deque(A)
q2=deque([])
for i in range(M):
  if len(q1)!=0 and (len(q2)==0 or q1[0]>=q2[0]):
    x=q1.popleft()
  else:
    x=q2.popleft()
  q2.append(x//2)
print(int(sum(q1)+sum(q2)))
### BUGGY CODE ###


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

typ = list(set(lst))
cnt = 0
for i in range(len(typ)):
    k = typ[i]
    c = lst.count(k)
    if c > k:
        cnt += c - k
    elif c < k:
        cnt += c
print(cnt)


### FIXED CODE ###

from collections import Counter
n = int(input())
lst = Counter([int(i) for i in input().split()])

cnt = 0
for k,v in lst.items():
    if k < v:
        cnt += v-k
    elif k > v:
        cnt += v
print(cnt)
### BUGGY CODE ###

N=int(input())
a=[]
for i in range(N):
    a.append(int(input()))
ans=0
position=1
visited=[1]
while position!=2: 
    position=a[position-1]
    if position in visited:
        ans=-1
        break
    else:
        visited.append(position)
        ans+=1


print(ans)

### FIXED CODE ###

N=int(input())
a=[]
for i in range(N):
    a.append(int(input()))
ans=0
position=1
flag=True
for i in range(N):
    if position==2:
        print(ans)
        flag=False
        break 
    else:
        position=a[position-1]
        ans+=1

if flag:
    print(-1)
### BUGGY CODE ###

import numpy as np

def main(H, W, s_list):
    row_count = np.zeros((H, W))
    for i_row in range(H):
        j_col = -1    
        for i_col in range(W):
            if i_col <= j_col:
                continue
            char = s_list[i_row][i_col]
            if char == '.':
                j_col = i_col
                while(True):
                    j_col += 1
                    if j_col == W:
                        break
                    c = s_list[i_row][j_col]
                    if c == '#':
                        break

                row_count[i_row, i_col:j_col] = j_col - i_col


    col_count = np.zeros((H, W))
    for i_col in range(W):
        j_row = -1    
        for i_row in range(H):
            if i_row <= j_row:
                continue
            char = s_list[i_row][i_col]
            if char == '.':
                j_row = i_row
                while(True):
                    j_row += 1
                    if j_row == H:
                        break
                    c = s_list[j_row][i_col]
                    if c == '#':
                        break
                
                col_count[i_row:j_row, i_col] = j_row - i_row
    print(int(np.max(row_count + col_count)) - 1)



if __name__ == "__main__":
    H, W = [int(x) for x in input().split()]
    s_list = []
    for _ in range(H):
        s_list.append(input())

    main(H, W, s_list)


### FIXED CODE ###


def main(H, W, s_list):
    row_count = [[0]*W for _ in range(H)]
    for i_row in range(H):
        i_col = 0
        j_col = 0
        s = s_list[i_row]
        while(i_col < W):
            char = s[i_col]
            j_col = i_col
            
            if char == '.':
                while(True):
                    j_col += 1
                    if j_col == W:
                        break
                    c = s[j_col]
                    if c == '#':
                        break
                
                for k in range(i_col, j_col):
                    row_count[i_row][k] = j_col - i_col
            i_col = j_col + 1


    col_count = [[0]*W for _ in range(H)]
    for i_col in range(W):
        i_row = 0
        j_row = 0
        s_col = [s[i_col] for s in s_list]
        while(i_row < H):
            char = s_col[i_row]
            j_row = i_row
            if char == '.':
                while(True):
                    j_row += 1
                    if j_row == H:
                        break
                    c = s_col[j_row]
                    if c == '#':
                        break
                for k in range(i_row, j_row):
                    col_count[k][i_col] = j_row - i_row
            i_row = j_row + 1

    m = 0
    for i_row in range(H):
        for i_col in range(W):
            sumation = row_count[i_row][i_col] + col_count[i_row][i_col]
            if sumation > m:
                m = sumation
    print(int(m) - 1)



if __name__ == "__main__":
    H, W = [int(x) for x in input().split()]
    s_list = []
    for _ in range(H):
        s_list.append(input())

    main(H, W, s_list)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

n = int(input())

alist = list(map(int, input().split()))
result = 0

for i in set(alist):
    if alist.count(i) > i:
        result += alist.count(i) - i
    elif alist.count(i) < i:
        result += alist.count(i)
print(result)


### FIXED CODE ###

from collections import Counter

input()
A = map(int, input().split())
B = Counter(A)

count = 0
for key, value in B.items():
    count += value - key if value >= key else value

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

n=int(input())
a=[]
for i in range(n):
  a.append(int(input()))
print(max(a[1:]))
for j in range(1,n-1):
  b=a[:j]+(a[j+1:])
  print(max(b))
print(max(a[:n-1]))


### FIXED CODE ###

import collections
n=int(input())
a=[]
for i in range(n):
  a.append(int(input()))
b=collections.Counter(a)
d=list(b.items())
d.sort(key=lambda x:-int(x[0]))
if d[0][1]==1:
  for i in range(n):
    if a[i]==int(d[0][0]):
      print(int(d[1][0]))
    else:
      print(int(d[0][0]))
else:
  for i in range(n):
    print(int(d[0][0]))
### BUGGY CODE ###

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

def dfs(h, w, count=0):
    if s[h][w]=='#':
        count+=1
    if h==H-1 and w==W-1:
        return count
    else:
        ans = float('inf')
        if w+1<W:
            ans = min(ans, dfs(h, w+1, count=count))
        if h+1<H:
            ans = min(ans, dfs(h+1, w, count=count))
        return ans
print(dfs(0,0,0))

### FIXED CODE ###

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

dp = [[float('inf')]* W for _ in range(H)]

if s[0][0]=='#':
    dp[0][0]=1
else:
    dp[0][0]=0

for c in range(W):
    for r in range(H):
        if r > 0:
            count=0
            if s[r-1][c]=='.' and s[r][c]=='#':
                count = 1
            dp[r][c] = min(dp[r][c], dp[r-1][c]+count)
        if c > 0:
            count=0
            if s[r][c-1]=='.' and s[r][c]=='#':
                count = 1
            dp[r][c] = min(dp[r][c], dp[r][c-1]+count)
print(dp[H-1][W-1])
### BUGGY CODE ###

N, K= map(int,input().split())
A = list(map(int,input().split()))
p=0
while p<K:
  B=[0]*N
  for i in range(N):
    count = 0
    for j in range(N):
      #print(A[j])
      if A[j]+1>abs(j-i):
        count +=1
    #print(["A"]+A)  
    B[i] = count
    #print(["A"]+A)
    #print([B])
  if min(B)==N:
    break
  A = B
  p +=1
print(*A)


### FIXED CODE ###

N, K= map(int,input().split())
A = list(map(int,input().split()))
a=A[:]
for _ in range(K):
  B=[0]*(N+1)
  for i in range(N):
    t = a[i]
    B[max(i-t,0)] +=1
    B[min(i+t+1,N)] -=1
  for i in range(N):
    B[i+1] += B[i]
  a=B[:N]        
  if min(a)==N:
    break
print(*a)
### BUGGY CODE ###

def sum(ar,st,en):
    s=0
    for i in range(st,en+1):
        s+=ar[i]
    return s
max_value=999999999999999999999

def k_part(k,n,ar):
    res=max_value
    for o in range(n):
        l_min=0
        for r_min in range(l_min,n):
            min_s=sum(ar,l_min,r_min)
            dp=[[max_value for i in range(n)] for j in range(k)]
            dp[0][r_min-l_min]=min_s
            for p in range(1,k):
                for l_max in range(r_min,n):
                    for r_max in range(l_max,n):
                        max_s=sum(ar,l_max+1,r_max)
                        if max_s>=min_s:
                            dp[p][r_max]=min(dp[p][r_max],max(max_s,dp[p-1][l_max]))
            if dp[k-1][n-1]==max_value:
                continue
            res=min(res,dp[k-1][n-1]-min_s)
        tmp=[0]*n
        for i in range(n):
            tmp[(i-1+n)%n]=ar[i]
        for i in range(n):
            ar[i]=tmp[i]
    return res

k=4
n=int(input())
deps=[int(i) for i in input().strip().split(" ")]
print(k_part(k,n,deps))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
tmp = 0
lr = [0]
for a in A:
    tmp += a
    lr.append(tmp)

ans = float('inf')

f=1
g=3
for i in range(2, N - 1):

    while abs(lr[i] - lr[f] - lr[f]) > abs(lr[i] - lr[f + 1] - lr[f + 1]):
        f += 1
    while abs((lr[-1] - lr[g]) - (lr[g] - lr[i])) > abs((lr[-1] - lr[g + 1]) - (lr[g + 1] - lr[i])):
        g += 1
    l = (lr[f], lr[i] - lr[f], lr[-1] - lr[g], lr[g] - lr[i])
    ans = min(ans, max(l) - min(l))

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

N=int(input())
AB=[[0,0]for i in range(N)]
for i in range(N):
    AB[i][0],AB[i][1]=map(int,input().split())
t_delta_AB=[[0,0,i] for i in range(N)]
for i in range(N):
    t_delta_AB[i][1]=AB[i][1]-AB[i][0]
    t_delta_AB[i][0]=AB[i][0]
t_delta_AB.sort(key= lambda x:(x[0],x[1]),reverse=True)
a_delta_AB=[[0,0,i] for i in range(N)]
for i in range(N):
    a_delta_AB[i][1]=AB[i][0]-AB[i][1]
    a_delta_AB[i][0]=AB[i][1]
a_delta_AB.sort(key= lambda x:(x[0],x[1]),reverse=True)
takahashi_score=0
aoki_score=0
buf=[]
t=0
a=0
for i in range(N):
    if i%2==0:
        n=t
        while 1:
            if not(t_delta_AB[n][2] in buf):
                takahashi_score+=t_delta_AB[n][0]
                buf.append(t_delta_AB[n][2])
                t=n
                break
            n+=1
    else:
        n=a
        while 1:
            if not(a_delta_AB[n][2] in buf):
                aoki_score+=a_delta_AB[n][0]
                buf.append(a_delta_AB[n][2])
                a=n
                break
            n+=1
print(takahashi_score-aoki_score)


### FIXED CODE ###

N=int(input())
B=[0 for i in range(N)]
sum_AB=[0 for i in range(N)]
for i in range(N):
    A,B[i]=map(int,input().split())
    sum_AB[i]=A+B[i]
sum_AB.sort(reverse=True)
sum_B=sum(B)
sum_takahashi=-sum_B
i=0
while i<N:
    if i%2==0:
        sum_takahashi+=sum_AB[i]
    i+=1
print(sum_takahashi)
### BUGGY CODE ###

N, K = map(int, input().split())
LR = [tuple(map(int, input().split())) for _ in range(K)]

D = [1]
M = 1000
memo = []
for i in range(1, N):
  count = 0
  for l, r in LR:
    if l <= i:
      ll = i - min(i, r)
      rr = i - l + 1
      LL = (ll + M - 1) // M
      RR = rr // M
      if RR > LL:
        count += sum(D[ll:LL*M]) + sum(memo[LL:RR]) + sum(D[RR*M:rr])
      else:
        count += sum(D[ll:rr])
  D.append(count % 998244353)
  if len(D) % M == 0:
    memo.append(sum(D[-M:]))
print(D[-1])

### FIXED CODE ###

N, K = map(int, input().split())
LR = [tuple(map(int, input().split())) for _ in range(K)]

D = [1]
M = 100
memo = []
memo2 = []
for i in range(1, N):
  count = 0
  for l, r in LR:
    if l <= i:
      l1 = i - min(i, r)
      r1 = i - l + 1
      l2 = (l1 + M - 1) // M
      r2 = r1 // M
      l3 = (l2 + M - 1) // M
      r3 = r2 // M
      if r3 > l3:
        count += sum(D[l1:l2*M]) + sum(memo[l2:l3*M]) + sum(memo2[l3:r3]) + sum(memo[r3*M:r2]) + sum(D[r2*M:r1])
      elif r2 > l2:
        count += sum(D[l1:l2*M]) + sum(memo[l2:r2]) + sum(D[r2*M:r1])
      else:
        count += sum(D[l1:r1])
  D.append(count % 998244353)
  if len(D) % M == 0:
    memo.append(sum(D[-M:]))
    if len(memo) % M == 0:
      memo2.append(sum(memo[-M:]))
print(D[-1])
### BUGGY CODE ###

S = input()
T = input()
sl = {}
tl = {}
for i in range(len(S)):
    if S[i] in sl:
        sl[S[i]] = sl[S[i]] + str(i)
    else:
        sl[S[i]] = str(i)
    if T[i] in tl:
        tl[T[i]] = tl[T[i]] + str(i)
    else:
        tl[T[i]] = str(i)
sv = [i for i in list(sl.values()) if len(i)>=2]
tv = [i for i in list(tl.values()) if len(i)>=2]
flag = True
if len(sv) != len(tv):
    flag = False
elif len(sv) == 0 and len(tv) == 0:
    pass
else:
    for v in sv:
        if not v in tv:
            flag = False
            break
    if flag:
        for v in tv:
            if not v in sv:
                flag = False
                break
if flag:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

import sys, copy, math, heapq, bisect
from itertools import accumulate
from collections import deque, defaultdict, Counter
input = sys.stdin.readline # 文字列の入力のとき'/n'まで受け取るので注意!!!
sys.setrecursionlimit(500000)

S = input()
T = input()
N = len(S)
ds = {}
dt = {}
ss = 0
tt = 0
SS = []
TT = []
for i in range(N):
    if S[i] in ds:
        SS.append(ds[S[i]])
    else:
        ds[S[i]] = ss
        SS.append(ss)
        ss += 1
    if T[i] in dt:
        TT.append(dt[T[i]])
    else:
        dt[T[i]] = tt
        TT.append(tt)
        tt += 1
flag = True
for i in range(N):
    if SS[i]==TT[i]:
        continue
    else:
        flag = False
        break
if flag:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

N,A,B,K=map(int,input().split())
mod=998244353

def squaremod(A,p,mod):#A^p(mod p)の計算
    if p==0:
        return 1
    if p%2==1:
        return (A*squaremod(A,p-1,mod))%mod
    if p%2==0:
        return (squaremod(A,p/2,mod) %mod)**2 %mod

INV=[None]*(N+1)
for i in range(1,N+1):
    INV[i]=squaremod(i,mod-2,mod)

def Combi(n,r):
    ANS=1
    for i in range(min(r,n-r)):
        ANS *= (N-i)*INV[i+1]

    return ANS
        

ANS=0

if B>A:
    (A,B)=(B,A)

ran=K//A

for i in range(min(ran,N)+1):
    q, r = divmod(K-(A*i), B)
    if r==0 and q<=N:
        ANS = (ANS+(Combi(N,i)*Combi(N,q)))%mod
        #print(q,r,ANS)

print(ANS)


### FIXED CODE ###

N,A,B,K=map(int,input().split())
mod=998244353

INV=[None]*(N+1)
for i in range(1,N+1):
    INV[i]=pow(i,mod-2,mod)

Combi=[None]*(N+1)
Combi[0]=1
Combi[1]=N
for i in range(2,N//2+2):
    Combi[i]=Combi[i-1]*(N-i+1)*INV[i] %mod
for i in range(N//2+2,N+1):
    Combi[i]=Combi[N-i]


ANS=0

if B>A:
    (A,B)=(B,A)

ran=K//A

for i in range(min(ran,N)+1):
    q, r = divmod(K-(A*i), B)
    if r==0 and q<=N:
        ANS = (ANS+(Combi[i]*Combi[q])%mod)%mod

print(ANS)
### BUGGY CODE ###

from collections import deque

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

edges = [[] for _ in range(N)]

for _ in range(M):
    fr, to = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append(to)

for start in range(N):
    st = deque([(start, True)])
    L = deque()
    V = set()

    while st:
        now, isFirst = st.pop()
        if isFirst:
            L.append(now)

            if now in V:
                if now == start:
                    break

            V.add(now)

            st.append((now, False))

            for to in edges[now]:
                st.append((to, True))
        else:
            L.pop()
            V.remove(now)
    else:
        continue

    if L[-1] != L[0]:
        continue

    L.pop()
    print(len(L))
    ans = [v + 1 for v in L]
    print(*ans, sep='\n')
    exit()

print(-1)

### FIXED CODE ###

from collections import deque

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

edges = [[] for _ in range(N)]

for _ in range(M):
    fr, to = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append(to)

for start in range(N):
    st = deque([(start, True)])
    L = deque()
    V = set()

    while st:
        now, isFirst = st.pop()
        if isFirst:
            L.append(now)

            if now in V:
                break

            V.add(now)

            st.append((now, False))

            for to in edges[now]:
                st.append((to, True))
        else:
            L.pop()
            V.remove(now)
    else:
        continue

    print(0)
    print()
    exit()

    loopStart = L[-1]
    while L[0] != loopStart:
        L.popleft()

    print(len(L) - 1)
    ans = [v + 1 for v in L]
    print(*ans[: -1], sep='\n')
    exit()

print(-1)
### BUGGY CODE ###

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

dp = {"": 0, "A": 0, "AB": 0, "ABC": 0}
dp[""] = 1

for s in S:
    newDP = {"": 0, "A": 0, "AB": 0, "ABC": 0}
    if s == "?":
        s = "ABC"

    for i in s:
        # 入れない
        newDP[""] += dp[""]
        newDP["A"] += dp["A"]
        newDP["AB"] += dp["AB"]
        newDP["ABC"] += dp["ABC"]
        if i == "A":
            newDP["A"] += dp[""]
            newDP["A"] %= mod
        elif i == "B":
            newDP["AB"] += dp["A"]
            newDP["AB"] %= mod
        else:
            newDP["ABC"] += dp["AB"]
            newDP["ABC"] %= mod
    dp = newDP


print(dp["ABC"])

### FIXED CODE ###

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

a, ab, abc, n = 0, 0, 0, 1
for s in S:
    if s == "A":
        a += n
        a %= mod
    elif s == "B":
        ab += a
        ab %= mod
    elif s == "C":
        abc += ab
        abc %= mod
    else:
        a, ab, abc, n = 3 * a + n, 3 * ab + a, 3 * abc + ab, 3 * n
        a %= mod
        ab %= mod
        abc %= mod
        n %= mod

print(abc)