The ABC number of a string T is the number of triples of integers (i, j, k) that satisfy all of the following conditions:
 - 1 ≤ i < j < k ≤ |T| (|T| is the length of T.)
 - T_i = A (T_i is the i-th character of T from the beginning.)
 - T_j = B
 - T_k = C
For example, when T = ABCBC, there are three triples of integers (i, j, k) that satisfy the conditions: (1, 2, 3), (1, 2, 5), (1, 4, 5). Thus, the ABC number of T is 3.
You are given a string S. Each character of S is A, B, C or ?.
Let Q be the number of occurrences of ? in S. We can make 3^Q strings by replacing each occurrence of ? in S with A, B or C. Find the sum of the ABC numbers of all these strings.
This sum can be extremely large, so print the sum modulo 10^9 + 7.

-----Constraints-----
 - 3 ≤ |S| ≤ 10^5
 - Each character of S is A, B, C or ?.

-----Input-----
Input is given from Standard Input in the following format:
S

-----Output-----
Print the sum of the ABC numbers of all the 3^Q strings, modulo 10^9 + 7.

-----Sample Input-----
A??C

-----Sample Output-----
8

In this case, Q = 2, and we can make 3^Q = 9 strings by by replacing each occurrence of ? with A, B or C. The ABC number of each of these strings is as follows:
 - AAAC: 0
 - AABC: 2
 - AACC: 0
 - ABAC: 1
 - ABBC: 2
 - ABCC: 2
 - ACAC: 0
 - ACBC: 1
 - ACCC: 0
The sum of these is 0 + 2 + 0 + 1 + 2 + 2 + 0 + 1 + 0 = 8, so we print 8 modulo 10^9 + 7, that is, 8.

Difficulty: interview

Starter code:

Solutions:
def main():
    mod = 10**9 + 7
    s = input()
    n = len(s)

    a_num = 0
    c_num = s.count('C')
    q_num = 0
    q_cnt = s.count('?')

    pow3, pow2, pow1, pow0 = 0, 0, 0, 0
    if q_cnt >= 3:
        pow3 = pow(3, q_cnt-3, mod)
        pow2 = pow3 * 3 % mod
        pow1 = pow2 * 3 % mod
        pow0 = pow1 * 3 % mod
    elif q_cnt == 2:
        pow2 = 1
        pow1 = 3
        pow0 = 9
    elif q_cnt == 1:
        pow1 = 1
        pow0 = 3
    else:
        pow0 = 1

    ans = 0
    for x in s:
        if x == 'A':
            a_num += 1
        elif x == 'B':
            ans += pow0 * a_num * c_num
            ans += pow1 * (q_num * c_num + a_num * (q_cnt - q_num))
            ans += pow2 * (q_num) * (q_cnt - q_num)
            ans %= mod
        elif x == 'C':
            c_num -= 1
        else:
            ans += pow1 * a_num * c_num
            ans += pow2 * (q_num * c_num + a_num * (q_cnt - q_num - 1))
            ans += pow3 * (q_num) * (q_cnt - q_num - 1)
            ans %= mod
            q_num += 1

    print(ans)

main()

s=input()
mod=10**9+7
retnum={"?":0,"A":1,"B":2,"C":3}
count=[[0 for i in range(len(s))] for j in range(4)]
for i in range(len(s)):
    for j in range(4):
        if retnum[s[i]] == j:
            count[j][i]=count[j][i-1]+1
        else:
            count[j][i]=count[j][i-1]
ans=0
g=[1]*100002
for i in range(1,100002):
    g[i]=g[i-1]*3
    g[i]%=mod
for i in range(1,len(s)-1):
    if s[i]=="B" or s[i]=="?":
        ans+=(g[max(0,count[0][i-1]-1)]*count[0][i-1]+g[count[0][i-1]]*count[1][i-1])*(g[max(0,count[0][-1]-count[0][i]-1)]*(count[0][-1]-count[0][i])+g[count[0][-1]-count[0][i]]*(count[3][-1]-count[3][i]))
        ans%=mod
print(ans)

mod = 10 ** 9 + 7
s = input()
dp = [[0] * 4 for i in range(len(s) + 1)]
dp[len(s)][3] = 1
for i in range(len(s))[::-1]:
    for j in range(4)[::-1]:
        if s[i] == "?":
            dp[i][j] = dp[i + 1][j] * 3
        else:
            dp[i][j] = dp[i + 1][j]
        if j < 3:
            if s[i] == "?" or s[i] == "ABC"[j]:
                dp[i][j] += dp[i + 1][j + 1]
        dp[i][j] %= mod
print(dp[0][0])

#!/usr/bin/env python3

s = str(input())

mod = 10**9+7
dp = [[0]*4 for i in range(len(s)+1)]
dp[0][0] = 1
for i in range(1, len(s)+1):
    for j in range(4):
        if s[i-1] == "?":
            dp[i][j] = (dp[i-1][j]*3) % mod
        else:
            dp[i][j] = (dp[i-1][j]) % mod

    if s[i-1] == "A":
        dp[i][1] += (dp[i-1][0]) % mod
    elif s[i-1] == "B":
        dp[i][2] += (dp[i-1][1]) % mod
    elif s[i-1] == "C":
        dp[i][3] += (dp[i-1][2]) % mod
    else:
        dp[i][1] += (dp[i-1][0]) % mod
        dp[i][2] += (dp[i-1][1]) % mod
        dp[i][3] += (dp[i-1][2]) % mod

# print(dp)
print((dp[-1][-1] % mod))


S = input()

dp = [[0] * 4 for _ in range(len(S) + 1)]
dp[0][0] = 1
W = 'ABC'

MOD = 10 ** 9 + 7


def update1(i):
    for j in range(4):
        dp[i + 1][j] += dp[i][j] % MOD


def update2(i, c):
    ic = W.index(c)
    dp[i + 1][ic + 1] += dp[i][ic] % MOD


for i in range(len(S)):
    if S[i] == '?':
        for c in W:
            update1(i)
            update2(i, c)
    else:
        update1(i)
        update2(i, S[i])
print((dp[len(S)][-1] % MOD))


import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
	S = SI()
	N = len(S)
	dp = make_grid(N+1, 4, 0)
	dic = {"A": [0], "B": [1], "C": [2], "?": [0,1,2]}
	dp[0][0] = 1
	for i, s in enumerate(S):
		if s == "?":
			for j in range(4):
				if j in dic[s]:
					dp[i+1][j+1] += dp[i][j] % MOD
				dp[i+1][j] += dp[i][j] * 3 % MOD
		else:
			for j in range(4):
				if j in dic[s]:
					dp[i+1][j+1] += dp[i][j] % MOD

				dp[i+1][j] += dp[i][j] % MOD

	print(dp[N][3] % MOD)



def __starting_point():
	main()
__starting_point()

MOD = 10**9+7

S = input()
N = len(S)
dp = [[0]*4 for i in range(N+1)]
dp[0][0] = 1
for i in range(N):
    s = S[i]
    for j in range(4):
        if s == "?":
            dp[i+1][j] += dp[i][j]*3
        else:
            dp[i+1][j] += dp[i][j]
        dp[i+1][j] %= MOD
        if j < 3 and (s == "?" or s == "ABC"[j]):
            dp[i+1][j+1] += dp[i][j]
            dp[i+1][j+1] %= MOD
print((dp[N][3]%MOD))


import sys
readline = sys.stdin.readline

S = readline().rstrip()
DIV = 10 ** 9 + 7

dp = [[0] * 4 for i in range(len(S) + 1)]
# dp[i + 1][0] : i文字目まで見たとき、ABCの部分文字列がまだ始まっていない場合の数
# dp[i + 1][1] : i文字目まで見たとき、ABCのAまで一致した場合の数
# dp[i + 1][2] : i文字目まで見たとき、ABCのBまで一致した場合の数
# dp[i + 1][3] : i文字目まで見たとき、ABCのCまで一致した場合の数

dp[0][0] = 1

for i in range(len(S)):
  if S[i] == "A" or S[i] == "?":
    dp[i + 1][0] += dp[i][0] # まだ始まっていない状態をそのまま
    dp[i + 1][1] += dp[i][1] # まだ始まっていない状態をそのまま
    dp[i + 1][2] += dp[i][2] # まだ始まっていない状態をそのまま
    dp[i + 1][3] += dp[i][3] # まだ始まっていない状態をそのまま
    dp[i + 1][1] += dp[i][0] # 開始状態に遷移することが出来る
    
  if S[i] == "B" or S[i] == "?":
    dp[i + 1][0] += dp[i][0] # その文字を選ばない場合
    dp[i + 1][1] += dp[i][1] # その文字を選ばない場合
    dp[i + 1][2] += dp[i][2] # その文字を選ばない場合
    dp[i + 1][3] += dp[i][3] # その文字を選ばない場合
    dp[i + 1][2] += dp[i][1] # Bを使用した状態に遷移
  
  if S[i] == "C" or S[i] == "?":
    dp[i + 1][0] += dp[i][0] # その文字を選ばない場合
    dp[i + 1][1] += dp[i][1] # その文字を選ばない場合
    dp[i + 1][2] += dp[i][2] # その文字を選ばない場合
    dp[i + 1][3] += dp[i][3] # その文字を選ばない場合
    dp[i + 1][3] += dp[i][2] # Cを使用した状態に遷移
    
  for j in range(4):
    dp[i + 1][j] %= DIV
    
# 最後の文字まで見たとき、Cまで一致した場合の数が答え
print((dp[len(S)][3]))


s = input().rstrip()
dp = [0] * 4
dp[0] = 1

for i in range(len(s)):
    if s[i] == 'A':
        dp[1] += dp[0]
    elif s[i] == 'B':
        dp[2] += dp[1]
    elif s[i] == 'C':
        dp[3] += dp[2]
    else:
        dp = [dp[0]*3, dp[1]*3+dp[0], dp[2]*3+dp[1], dp[3]*3+dp[2]]
    dp = list([x % (10**9+7) for x in dp])
print((dp[3]))


mod = 1000000007
s = input()
al = 0
cr = s.count('C')
ql = 0
qr = s.count('?')
ans = 0
for c in s:
  if c == 'C':
    cr -= 1
  elif c == '?':
    qr -= 1
    ans += (3 * al + ql) * (3 * cr + qr) * pow(3, ql + qr + mod - 3, mod)
    ans %= mod
    ql += 1
  elif c == 'B':
    ans += (3 * al + ql) * (3 * cr + qr) * pow(3, ql + qr + mod - 3, mod)
    ans %= mod
  else:
    al += 1
print(ans)


def main():
    mod = 10**9 + 7
    s = input()
    n = len(s)

    a_num = 0
    c_num = s.count('C')
    q_num = 0
    q_cnt = s.count('?')

    pows = [0] * 4
    if q_cnt >= 3:
        pows[3] = pow(3, q_cnt-3, mod)
        pows[2] = pows[3] * 3 % mod
        pows[1] = pows[2] * 3 % mod
        pows[0] = pows[1] * 3 % mod
    elif q_cnt == 2:
        pows[2] = 1
        pows[1] = 3
        pows[0] = 9
    elif q_cnt == 1:
        pows[1] = 1
        pows[0] = 3
    else:
        pows[0] = 1

    ans = 0
    for x in s:
        if x == 'A':
            a_num += 1
        elif x == 'B':
            ans += pows[0] * a_num * c_num
            ans += pows[1] * (q_num * c_num + a_num * (q_cnt - q_num))
            ans += pows[2] * (q_num) * (q_cnt - q_num)
            ans %= mod
        elif x == 'C':
            c_num -= 1
        else:
            ans += pows[1] * a_num * c_num
            ans += pows[2] * (q_num * c_num + a_num * (q_cnt - q_num - 1))
            ans += pows[3] * (q_num) * (q_cnt - q_num - 1)
            ans %= mod
            q_num += 1

    print(ans)

main()

MOD = 10**9 + 7
S = input()
res = 0
dp0 = 1 # ''
dp1 = 0 # 'a'
dp2 = 0 # 'ab'
dp3 = 0 # 'abc'

for c in S:
    if c == 'A':
        dp1 = (dp0+dp1)%MOD
    elif c == 'B':
        dp2 = (dp1+dp2)%MOD
    elif c == 'C':
        dp3 = (dp2+dp3)%MOD
    else:
        dp3 = (dp3*3+dp2)%MOD
        dp2 = (dp2*3+dp1)%MOD
        dp1 = (dp1*3+dp0)%MOD
        dp0 = (dp0*3)%MOD
print(dp3)


MOD = 10**9+7

s=input()
Anum = 0
ABnum = 0
ABCnum = 0
q = 0
for c in s:
    if c == 'A':
        Anum = (Anum+pow(3,q,MOD))%MOD
    elif c == 'B':
        ABnum = (ABnum+Anum)%MOD
    elif c == 'C':
        ABCnum = (ABCnum+ABnum)%MOD
    else:
        Anum,ABnum,ABCnum = 3*Anum+pow(3,q,MOD),3*ABnum+Anum,3*ABCnum+ABnum
        Anum,ABnum,ABCnum = Anum%MOD,ABnum%MOD,ABCnum%MOD
        q += 1
print(ABCnum)


S = input()
#dp[i][four] =: i + 1番目まで見たとき,照合したケツがfourとなるものの総数
dp = [[0 for _ in range(4)] for _ in range(len(S)+1 )]
dp[0][0] = 1
mod = 10**9 + 7
for i in range(len(S)):
    if S[i] == 'A' or S[i] == '?':
        dp[i+1][1] += dp[i][0] 
        for k in range(4): dp[i+1][k] += dp[i][k]
    if S[i] == 'B' or S[i] == '?':
        dp[i+1][2] += dp[i][1]
        for k in range(4): dp[i+1][k] += dp[i][k]
    if S[i] == 'C' or S[i] == '?':
        dp[i+1][3] += dp[i][2]
        for k in range(4): dp[i+1][k] += dp[i][k]
    for k in range(4): dp[i+1][k] %= mod
print((dp[len(S)][3]))


def main():
    MOD = 10 ** 9 + 7

    S = input()
    z, a, b, c = 1, 0, 0, 0

    for x in S:
        if x == 'C':
            c = (c + b) % MOD
        elif x == 'B':
            b = (b + a) % MOD
        elif x == 'A':
            a = (a + z) % MOD
        elif x == '?':
            z, a, b, c = z * 3 % MOD, (a * 3 + z) % MOD, (b * 3 + a) % MOD, (c * 3 + b) % MOD
    print(c)


def __starting_point():
    main()

__starting_point()

s = input()
n = len(s)
p = 10 ** 9 + 7

q = s.count('?')
l_a = [0] * n  # l_a[i] := s[i]より左にあるAの数
l_x = [0] * n  # l_x[i] := s[i]より左にある?の数
r_c = [0] * n  # r_c[i] := s[i]より右にあるCの数
r_x = [0] * n  # r_x[i] := s[i]より右にある?の数

for i in range(1, n):  # 1〜n-1
    l_a[i] = l_a[i - 1] + int(s[i - 1] == 'A')
    l_x[i] = l_x[i - 1] + int(s[i - 1] == '?')
    r_c[n - i - 1] = r_c[n - i] + int(s[n - i] == 'C')
    r_x[n - i - 1] = r_x[n - i] + int(s[n - i] == '?')

ans = 0
pow_q = []
for i in range(0, 4):
    pow_q.append(max(1, 3 ** (q - i) % p))

for i in range(n):
    if s[i] == 'B':
        ans += (l_a[i] * r_c[i] % p) * pow_q[0] % p  # ABC
        ans += (l_x[i] * r_c[i] % p) * pow_q[1] % p # ?BC
        ans += (l_a[i] * r_x[i] % p) * pow_q[1] % p # AB?
        ans += (l_x[i] * r_x[i] % p) * pow_q[2] % p # ?B?
        ans %= p
    elif s[i] == '?':
        ans += (l_a[i] * r_c[i] % p) * pow_q[1] % p # A?C
        ans += (l_x[i] * r_c[i] % p) * pow_q[2] % p # ??C
        ans += (l_a[i] * r_x[i] % p) * pow_q[2] % p # A??
        ans += (l_x[i] * r_x[i] % p) * pow_q[3] % p # ???
        ans %= p

print(ans)

s = input()
n = len(s)
mod = 10**9+7
qcnt = [[0,0]for i in range(n)]#それより左の？、右の？のこすう
Acnt = [0]*n#それより左のAのこすう
Ccnt = [0]*n#それより右のCの個数
q = 0
for i in range(n-1):
    if s[i] == '?':
        q += 1
        qcnt[i+1][0] += 1
    elif s[i] == 'A':
        Acnt[i+1] += 1
    qcnt[i+1][0] += qcnt[i][0]
    Acnt[i+1] += Acnt[i]
    qcnt[i+1][0]%=mod
    Acnt[i+1]%=mod
if s[-1] == '?':q += 1
for i in range(n-1,0,-1):
    if s[i] == '?':
        
        qcnt[i-1][1] += 1
    elif s[i] == 'C':
        Ccnt[i-1] += 1
    qcnt[i-1][1] += qcnt[i][1]
    Ccnt[i-1] += Ccnt[i]
    qcnt[i-1][1]%=mod
    Ccnt[i-1]%=mod
ans = 0
for i in range(n):
    
    if s[i] == 'B' or s[i] == '?':
        if qcnt[i][0]+qcnt[i][1]-2 <0:
            val = -(qcnt[i][0]+qcnt[i][1]-2)
            p = pow(3,val,mod)
            q = pow(p,mod-2,mod)
            ans +=q%mod*(3*Acnt[i] + qcnt[i][0])*(3*Ccnt[i]+ qcnt[i][1])%mod
        
        else:ans +=pow(3,qcnt[i][0]+qcnt[i][1]-2,mod)%mod*(3*Acnt[i] + qcnt[i][0])*(3*Ccnt[i]+ qcnt[i][1])%mod
        ans %= mod
    
    
print((ans%mod))


    


S = input()
N = len(S)
mod = 10**9+7
numofA = 0
numofAB = 0
numofABC = 0
numofquestion = 1
for i in range(N):
    if S[i] == "?":
        numofABC = (numofABC*3+numofAB) % mod
        numofAB = (numofAB*3+numofA) % mod
        numofA = (numofquestion + numofA*3) % mod
        numofquestion = (numofquestion * 3) % mod
    elif S[i] == "C":
        numofABC = (numofAB+numofABC) % mod
    elif S[i] == "B":
        numofAB = (numofAB + numofA) % mod
    else:
        numofA = (numofquestion + numofA) % mod
print(numofABC)


import sys
readline = sys.stdin.readline

S = readline().rstrip()
DIV = 10 ** 9 + 7

dp = [[0] * 4 for i in range(len(S) + 1)]
# dp[i + 1][0] : i文字目まで見たとき、ABCの部分文字列がまだ始まっていない場合の数
# dp[i + 1][1] : i文字目まで見たとき、ABCのAまで一致した場合の数
# dp[i + 1][2] : i文字目まで見たとき、ABCのBまで一致した場合の数
# dp[i + 1][3] : i文字目まで見たとき、ABCのCまで一致した場合の数

dp[0][0] = 1

for i in range(len(S)):
  # 状態を遷移しない場合
  for j in range(4):
    dp[i + 1][j] += dp[i][j] * (3 if S[i] == "?" else 1) # ?の場合は全ての遷移があり得る
  
  if S[i] == "A" or S[i] == "?":
    dp[i + 1][1] += dp[i][0] # 開始状態に遷移することが出来る
    
  if S[i] == "B" or S[i] == "?":
    dp[i + 1][2] += dp[i][1] # Bを使用した状態に遷移
  
  if S[i] == "C" or S[i] == "?":
    dp[i + 1][3] += dp[i][2] # Cを使用した状態に遷移
    
  for j in range(4):
    dp[i + 1][j] %= DIV
    
# 最後の文字まで見たとき、Cまで一致した場合の数が答え
print((dp[len(S)][3]))


s = str(input())
n = len(s)

mod = 10**9+7

X = [[0]*4 for _ in range(n+1)]
for i in range(n):
    for j in range(4):
        X[i+1][j] = X[i][j]
    if s[i] == 'A':
        X[i+1][0] += 1
    elif s[i] == 'B':
        X[i+1][1] += 1
    elif s[i] == 'C':
        X[i+1][2] += 1
    else:
        X[i+1][3] += 1

Y = [[0]*4 for _ in range(n+1)]
for i in reversed(list(range(n))):
    for j in range(4):
        Y[i][j] = Y[i+1][j]
    if s[i] == 'A':
        Y[i][0] += 1
    elif s[i] == 'B':
        Y[i][1] += 1
    elif s[i] == 'C':
        Y[i][2] += 1
    else:
        Y[i][3] += 1
#print(X)
#print(Y)
c = X[n][3]
ans = 0
for i in range(n):
    if s[i] == 'B':
        ans += X[i+1][3]*Y[i][3]*pow(3, max(0, c-2), mod)
        ans += X[i+1][0]*Y[i][2]*pow(3, c, mod)
        ans += X[i+1][3]*Y[i][2]*pow(3, max(0, X[i+1][3]-1+Y[i][3]), mod)
        ans += X[i+1][0]*Y[i][3]*pow(3, max(0, X[i+1][3]+Y[i][3]-1), mod)
        ans %= mod
    if s[i] == '?':
        ans += X[i][3]*Y[i+1][3]*pow(3, max(0, c-3), mod)
        ans += X[i+1][0]*Y[i][2]*pow(3, max(0, c-1), mod)
        ans += X[i][3]*Y[i][2]*pow(3, max(0, X[i][3]-1+Y[i+1][3]), mod)
        ans += X[i+1][0]*Y[i+1][3]*pow(3, max(0, X[i][3]+Y[i+1][3]-1), mod)
        ans %= mod
        ans %= mod
print(ans)


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

dp = [[0]*4 for i in range(len(s)+1)]
dp[0][0] = 1
for i in range(len(s)):
    
    if s[i] == "A":
        dp[i+1][1] += dp[i][0]
    elif s[i] =="B":
        dp[i+1][2] += dp[i][1]
    elif s[i] == "C":
        dp[i+1][3] += dp[i][2]
    else:
        dp[i+1][1] += dp[i][0]
        dp[i+1][2] += dp[i][1]
        dp[i+1][3] += dp[i][2]
    for j in range(4):
        if s[i] == "?":
            dp[i+1][j] = (dp[i+1][j]+dp[i][j]*3)%mod
        else:
            dp[i+1][j] = (dp[i+1][j]+dp[i][j])%mod


print((dp[-1][3]%mod))



from sys import stdin
def main():
    #入力
    readline=stdin.readline
    s=readline().strip()

    mod=10**9+7
    n=len(s)
    dp=[[0]*4 for _ in range(n+1)]
    dp[0][0]=1
    for i in range(1,n+1):
        #i文字目を選ばない
        for j in range(4):
            if s[i-1]!="?":
                dp[i][j]+=dp[i-1][j]
            else:
                dp[i][j]+=dp[i-1][j]*3

        #i文字目を選ぶ
        if s[i-1]=="A":
            dp[i][1]+=dp[i-1][0]
        elif s[i-1]=="B":
            dp[i][2]+=dp[i-1][1]
        elif s[i-1]=="C":
            dp[i][3]+=dp[i-1][2]
        elif s[i-1]=="?":
            dp[i][1]+=dp[i-1][0]
            dp[i][2]+=dp[i-1][1]
            dp[i][3]+=dp[i-1][2]

        for j in range(4):
            dp[i][j]%=mod
            
    print(dp[n][3])
def __starting_point():
    main()
__starting_point()

s = input()
n = len(s)
p = 10 ** 9 + 7

# i = 0, ..., nについて
# dp[i][0] = i文字目まででありうる文字列の数（ABCなら1、AB?なら3）
# dp[i][1] = i文字目までに含まれるAの数
# dp[i][2] = i文字目までに含まれるABのパターン数
# dp[i][3] = i文字目までに含まれるABCのパターン数
dp = [[0 for j in range(4)] for i in range(n + 1)]
dp[0][0] = 1 # ''空の文字列は1パターン
for j in range(1, 4):
    dp[0][j] = 0  # 空の文字列にはAもABもABCも入っていない

for i in range(1, n + 1):
    m = 3 if s[i - 1] == '?' else 1

    for j in range(4):
        dp[i][j] = dp[i - 1][j] * m % p

    if s[i - 1] == 'A' or s[i - 1] == '?':
        dp[i][1] =  (dp[i][1] + dp[i - 1][0]) % p
    if s[i - 1] == 'B' or s[i - 1] == '?':
        dp[i][2] = (dp[i][2] + dp[i - 1][1]) % p
    if s[i - 1] == 'C' or s[i - 1] == '?':
        dp[i][3] = (dp[i][3] + dp[i - 1][2]) % p

print(dp[n][3])

S = input()
MOD = 10**9 + 7
dp = [[0]*4 for _ in range(100005)]
dp[0][0] = 1
for i in range(len(S)):
    for j in range(4):
        if S[i] != '?':
            dp[i+1][j] += dp[i][j]
            dp[i+1][j] %= MOD
        else:
            dp[i+1][j] += 3*dp[i][j] % MOD
            dp[i+1][j] %= MOD
    if S[i] == 'A' or S[i] == '?':
        dp[i+1][1] += dp[i][0]
        dp[i+1][1] %= MOD
    if S[i] == 'B' or S[i] == '?':
        dp[i+1][2] += dp[i][1]
        dp[i+1][2] %= MOD
    if S[i] == 'C' or S[i] == '?':
        dp[i+1][3] += dp[i][2]
        dp[i+1][3] %= MOD
print((dp[len(S)][3]))


MOD = 10**9 + 7
def main():
    s = input()
    dp = [[0]*3 for _ in range(len(s)+1)]
# dp[idx][A, AB, ABC]
    tmp = 1
    for i in range(len(s)):
        c = s[i]
        if c == "A":
            dp[i][0] += tmp
            dp[i][0] %= MOD
        elif c == "B":
            dp[i][1] += dp[i][0]
            dp[i][1] %= MOD
        elif c == "C":
            dp[i][2] += dp[i][1]
            dp[i][2] %= MOD
        else:
            pre = [v for v in dp[i]]
            dp[i] = [0, 0, 0]
# ? = A
            dp[i][0] += pre[0] + tmp
            dp[i][1] += pre[1]
            dp[i][2] += pre[2]
# ? = B
            dp[i][0] += pre[0]
            dp[i][1] += pre[0] + pre[1]
            dp[i][2] += pre[2]
# ? = C
            dp[i][0] += pre[0]
            dp[i][1] += pre[1]
            dp[i][2] += pre[1] + pre[2]
            tmp *= 3
            tmp %= MOD
            dp[i][0] %= MOD
            dp[i][1] %= MOD
            dp[i][2] %= MOD
        dp[i+1][0] = dp[i][0]
        dp[i+1][1] = dp[i][1]
        dp[i+1][2] = dp[i][2]
#        print(dp[i])
    print(dp[len(s)][2] % MOD)

def __starting_point():
    main()
__starting_point()

import sys
input = sys.stdin.readline
from itertools import accumulate

MOD = 10**9+7
S = input()
n = len(S)
acc_A = [0]*n
acc_C = [0]*n
acc_Q_left = [0]*n
acc_Q_right = [0]*n
cnt = 0
for i, s in enumerate(S):
  if s == "A":
    acc_A[i] = 1
  elif s == "C":
    acc_C[i] = 1
  elif s == "?":
    acc_Q_left[i] = 1
    acc_Q_right[i] = 1
    cnt += 1
acc_A = list(accumulate(acc_A))
acc_C = list(accumulate(acc_C[::-1]))[::-1]
acc_Q_left = list(accumulate(acc_Q_left))
acc_Q_right = list(accumulate(acc_Q_right[::-1]))[::-1]
ans = 0
for i, s in enumerate(S):
  if i == 0 or i == n-1:
    continue
  if s == "B":
    ans += acc_A[i-1] * acc_C[i+1] * pow(3, cnt, MOD)
    if cnt >= 1:
      ans += acc_A[i-1] * acc_Q_right[i+1] * pow(3, cnt-1, MOD)
      ans += acc_Q_left[i-1] * acc_C[i+1] * pow(3, cnt-1, MOD)
    if cnt >= 2:
      ans += acc_Q_left[i-1] * acc_Q_right[i+1] * pow(3, cnt-2, MOD)
  elif s == "?":
    ans += acc_A[i-1] * acc_C[i+1] * pow(3, cnt-1, MOD)
    if cnt >= 2:
      ans += acc_A[i-1] * acc_Q_right[i+1] * pow(3, cnt-2, MOD)
      ans += acc_Q_left[i-1] * acc_C[i+1] * pow(3, cnt-2, MOD)
    if cnt >= 3:
      ans += acc_Q_left[i-1] * acc_Q_right[i+1] * pow(3, cnt-3, MOD)
  ans %= MOD
print(ans)

S = input()
nQ_r = S.count('?')
nC_r = S.count('C')
nQ_l = 0
nA_l = 0
N = len(S)
mod = 10**9+7

pow3 = [1]*N
p = 1
for i in range(1,N):
    pow3[i] = p = p*3%mod

ans = 0
for n, c in enumerate(S):
    if c=='C': nC_r-=1
    if c=='?': nQ_r-=1
    
    if n>0 and n<N-1 and (c=='B' or c=='?'):
        p = ( nQ_l*pow3[max(0, nQ_l-1)] + nA_l*pow3[nQ_l] ) % mod
        q = ( nQ_r*pow3[max(0, nQ_r-1)] + nC_r*pow3[nQ_r] ) % mod
        ans += p * q
        ans %= mod

    if c=='A': nA_l+=1
    if c=='?': nQ_l+=1

print(ans)

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

l = len(s)
dp = [[0] * 4 for _ in range(l + 1)]
dp[0][0] = 1

for i, e in enumerate(s, 1):
	# do not use in ABC
	for j in range(4):
		if e == "?":
			dp[i][j] += dp[i-1][j] * 3
		else:
			dp[i][j] += dp[i-1][j]

	# use in ABC
	if e == "A" or e == "?":
		dp[i][1] += dp[i-1][0]
	if e == "B" or e == "?":
		dp[i][2] += dp[i-1][1]
	if e == "C" or e == "?":
		dp[i][3] += dp[i-1][2]

	for j in range(4):
		dp[i][j] %= mod


ans = dp[l][3]
print(ans)


import sys
input = sys.stdin.readline
MOD = 10 ** 9 + 7

def main():
    string = input().strip()
    n = len(string)
    dp = [[0, 0, 0, 0] for _ in range(n + 1)]
    dp[0][0] = 1
    for i, s in enumerate(string):
        if s == "A":
            dp[i + 1][0] = dp[i][0]
            dp[i + 1][1] = dp[i][1] + dp[i][0]
            dp[i + 1][2] = dp[i][2]
            dp[i + 1][3] = dp[i][3]
        elif s == "B":
            dp[i + 1][0] = dp[i][0]
            dp[i + 1][1] = dp[i][1]
            dp[i + 1][2] = dp[i][2] + dp[i][1]
            dp[i + 1][3] = dp[i][3]
        elif s == "C":
            dp[i + 1][0] = dp[i][0]
            dp[i + 1][1] = dp[i][1]
            dp[i + 1][2] = dp[i][2]
            dp[i + 1][3] = dp[i][3] + dp[i][2]
        else:
            dp[i + 1][0] = 3 * dp[i][0]
            dp[i + 1][1] = 3 * dp[i][1] + dp[i][0]
            dp[i + 1][2] = 3 * dp[i][2] + dp[i][1]
            dp[i + 1][3] = 3 * dp[i][3] + dp[i][2]
        for j in range(4):
            dp[i + 1][j] %= MOD
    print(dp[-1][-1] % MOD)
    
main()

s=input()
mod=pow(10,9)+7
dp=[0]*4
dp[0]=1
for si in s:
  if si=='A':
    dp[1]+=dp[0]
  elif si=='B':
    dp[2]+=dp[1]
  elif si=='C':
    dp[3]+=dp[2]
  else:
    tmp3=dp[2]
    tmp2=dp[1]
    tmp1=dp[0]
    dp[3]*=3
    dp[3]+=tmp3
    dp[2]*=3
    dp[2]+=tmp2
    dp[1]*=3
    dp[1]+=tmp1
    dp[0]*=3
  dp[3]%=mod
  dp[2]%=mod
  dp[1]%=mod
  dp[0]%=mod
print((dp[3]))


import sys
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7

S = list(input())
N = len(S)

count = 0
DP = [[0] *  (N + 1) for _ in range(3)]
for i in range(1, N + 1):
    s = S[i - 1]
    if s == 'A':
        DP[0][i] = (DP[0][i - 1] + pow(3, count, MOD)) % MOD
        DP[1][i] = DP[1][i - 1]
        DP[2][i] = DP[2][i - 1]
    elif s == 'B':
        DP[0][i] = DP[0][i -1]
        DP[1][i] = (DP[1][i - 1] + DP[0][i - 1]) % MOD
        DP[2][i] = DP[2][i - 1]
    elif s == 'C':
        DP[0][i] = DP[0][i - 1]
        DP[1][i] = DP[1][i - 1]
        DP[2][i] = (DP[2][i - 1] + DP[1][i - 1]) % MOD
    else:
        DP[0][i] = (3 * DP[0][i - 1] + pow(3, count, MOD)) % MOD
        DP[1][i] = (3 * DP[1][i - 1] + DP[0][i - 1]) % MOD
        DP[2][i] = (3 * DP[2][i - 1] + DP[1][i - 1]) % MOD
        count += 1

print((DP[2][N]))

# print (DP)


s=input()
n=len(s)
mod=10**9+7
dp=[ [0]*3 for _ in range(n)]
#dp[i][0] count of A's in all possible strings u generate till i
#dp[i][1] count of AB's ''
#dp[i][2] count of ABC's ''
cnt=1
for i in range(n):
    if s[i]=='?':
        if i>0:
            dp[i][2]=dp[i-1][1]+3*dp[i-1][2]
            dp[i][2]%=mod
            dp[i][1]=dp[i-1][0]+3*dp[i-1][1]
            dp[i][1]%=mod
            dp[i][0]=3*dp[i-1][0]+1*cnt
            dp[i][0]%=mod
        else:
            dp[i][0]=1
        cnt*=3
        cnt%=mod
    elif s[i]=='C':
        if i>0:
            dp[i][2]=dp[i-1][1]+dp[i-1][2]
            dp[i][2]%=mod
            dp[i][1]=dp[i-1][1]
            dp[i][0]=dp[i-1][0]
    elif s[i]=='B':
        if i>0:
            dp[i][2]=dp[i-1][2]
            dp[i][1]=dp[i-1][0]+dp[i-1][1]
            dp[i][1]%=mod
            dp[i][0]=dp[i-1][0]
    elif s[i]=='A':
        if i>0:
            dp[i][2]=dp[i-1][2]
            dp[i][1]=dp[i-1][1]
            dp[i][0]=dp[i-1][0]+1*cnt
            dp[i][0]%=mod
        else:
            dp[0][0]=1

print((dp[-1][2]%mod))
            


S = input()
N = len(S)
a,b,c,d = 0,0,0,1
mod = 10**9+7
for x in reversed(S):
  if x == "?":
    a,b,c,d = 3*a+b, 3*b+c, 3*c+d, 3*d
  elif x == "A":
    a += b
  elif x == "B":
    b += c
  elif x == "C":
    c += d
  a %= mod; b %= mod; c %= mod; d %= mod
print(a)

s=input()
n=len(s)
mod=10**9+7
dp=[[0]*4 for _ in range(n+1)]
dp[n][3]=1
for i in reversed(list(range(n))):
    for j in reversed(list(range(4))):
        if j==3:
            if s[i]=="?":
                m=3
            else:
                m=1
            dp[i][j]+=m*dp[i+1][j]
        else:
            if s[i]=="?":
                m1=3
            else:
                m1=1
            if j==0:
                if s[i]=="A" or s[i]=="?":
                    m2=1
                else:
                    m2=0
            elif j==1:
                if s[i]=="B" or s[i]=="?":
                    m2=1
                else:
                    m2=0
            else:
                if s[i]=="C" or s[i]=="?":
                    m2=1
                else:
                    m2=0
            dp[i][j]+=m1*dp[i+1][j]+m2*dp[i+1][j+1]
        dp[i][j]%=mod
print((dp[0][0]%mod))
#print(dp)


S = input()
N = len(S)
mod = 10 ** 9 + 7
dp1 = [0 for _ in range(N+1)]
dp2 = [0 for _ in range(N+1)]
dp3 = [0 for _ in range(N+1)]
dp4 = [0 for _ in range(N+1)]
dp1[0] = 1

for i in range(N):
    if S[i] == '?':
        dp1[i+1] += 3 * dp1[i]
        dp2[i+1] += 3 * dp2[i] + dp1[i]
        dp3[i+1] += 3 * dp3[i] + dp2[i]
        dp4[i+1] += 3 * dp4[i] + dp3[i]
    else:
        dp1[i+1] += dp1[i]
        dp2[i+1] += dp2[i]
        dp3[i+1] += dp3[i]
        dp4[i+1] += dp4[i]
    if S[i] == 'A':
        dp2[i+1] += dp1[i]
    if S[i] == 'B':
        dp3[i+1] += dp2[i]
    if S[i] == 'C':
        dp4[i+1] += dp3[i]
    dp1[i+1] %= mod
    dp2[i+1] %= mod
    dp3[i+1] %= mod
    dp4[i+1] %= mod

print(dp4[N])

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)

def modinv(a,m):
    return pow(a,m-2,m)

import copy

S = input()
N = len(S)
dp = [[[0,0], [0,0,0], [0,0,0,0]] for i in range(N+1)]
mod = 10**9 + 7

for i in range(N):
    dp[i+1] = copy.deepcopy(dp[i])
    if S[i] == 'A':
        dp[i+1][0][0] += 1

    elif S[i] == 'B':
        for j in range(2):
            dp[i+1][1][j] = (dp[i+1][1][j] + dp[i][0][j])%mod

    elif S[i] == 'C':
        for j in range(3):
            dp[i+1][2][j] = (dp[i+1][2][j] + dp[i][1][j])%mod

    else:
        dp[i+1][0][1] += 1
        for j in range(2):
            dp[i+1][1][j+1] = (dp[i+1][1][j+1] + dp[i][0][j])%mod
        for j in range(3):
            dp[i+1][2][j+1] = (dp[i+1][2][j+1] + dp[i][1][j])%mod

Q = S.count('?')

inv3 = modinv(3,mod)
inv9 = inv3*inv3%mod
inv27 = inv9*inv3%mod
threeQ = pow(3,Q,mod)

ans = threeQ * (dp[N][2][0] + dp[N][2][1]*inv3 + dp[N][2][2]*inv9 + dp[N][2][3]*inv27) % mod
print(ans)

S=input()
MOD=pow(10,9)+7
dp=[0]*4
dp[0]=1
for s in S:
  if s=='A':
    dp[1]+=dp[0]
  elif s=='B':
    dp[2]+=dp[1]
  elif s=='C':
    dp[3]+=dp[2]
  else:
    tmp3=dp[2]
    tmp2=dp[1]
    tmp1=dp[0]
    dp[3]*=3
    dp[3]+=tmp3
    dp[2]*=3
    dp[2]+=tmp2
    dp[1]*=3
    dp[1]+=tmp1
    dp[0]*=3
  dp[3]%=MOD
  dp[2]%=MOD
  dp[1]%=MOD
  dp[0]%=MOD
print(dp[3])

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

A = 0
AB = 0
ABC = 0
prd = 1

for s in S:
    if s == 'A':
        A += prd
    elif s == 'B':
        AB += A
    elif s == 'C':
        ABC += AB
    else:
        a = A * 3 + prd
        ab = AB * 3 + A
        abc = ABC * 3 + AB
        A, AB, ABC = a, ab, abc
        prd *= 3
    A %= MOD
    AB %= MOD
    ABC %= MOD
    prd %= MOD

print(ABC)


S = input()
N = len(S)
dp = [[0 for _ in range(4)] for _ in range(N+1)]
dp[0][0] = 1
MOD = 10 ** 9 + 7

for i in range(N):
    if S[i] == 'A':
        dp[i+1][0] = dp[i][0] % MOD
        dp[i+1][1] = (dp[i][0] + dp[i][1]) % MOD
        dp[i+1][2] = dp[i][2] % MOD
        dp[i+1][3] = dp[i][3] % MOD
     
    if S[i] == 'B':
        dp[i+1][0] = dp[i][0] % MOD
        dp[i+1][1] = dp[i][1] % MOD
        dp[i+1][2] = (dp[i][1] + dp[i][2]) % MOD
        dp[i+1][3] = dp[i][3] % MOD
    
    if S[i] == 'C':
        dp[i+1][0] = dp[i][0] % MOD
        dp[i+1][1] = dp[i][1] % MOD
        dp[i+1][2] = dp[i][2] % MOD
        dp[i+1][3] = (dp[i][2] + dp[i][3]) % MOD
    
    if S[i] == '?':
        dp[i+1][0] = 3 * dp[i][0] % MOD
        dp[i+1][1] = (dp[i][0] + 3 * dp[i][1]) % MOD
        dp[i+1][2] = (dp[i][1] + 3 * dp[i][2]) % MOD
        dp[i+1][3] = (dp[i][2] + 3 * dp[i][3]) % MOD

print(dp[N][3] % MOD)

from collections import Counter
s = list(input())
n = len(s)
c = Counter(s)
mod = 10**9+7


left_a  = 0
left_b  = 0
left_c  = 0
left_q  = 0
right_a = c['A']
right_b = c['B']
right_c = c['C']
right_q = c['?']

def add_ans():
    lhs = left_a * pow(3, left_q, mod) + left_q*pow(3, left_q-1, mod)
    rhs = right_c * pow(3, right_q, mod) + right_q*pow(3, right_q-1, mod)
    return  (lhs * rhs)%mod

ans = 0
for i in range(n):
    if s[i] == 'A':
        left_a  += 1
    if s[i] == 'B':
        ans = (ans+ add_ans())%mod
    if s[i] == 'C':
        right_c -= 1
    if s[i] == '?':
        right_q -= 1
        ans = (ans+ add_ans())%mod
        left_q  += 1
print(ans)



mod=10**9+7
s=input()
n=len(s)
dp=[[0]*4 for _ in range(n+1)]
dp[0][0]=1
for i in range(1,n+1):
    dp[i][0]=dp[i-1][0]*((s[i-1]=="?")*2+1)
    dp[i][1]=dp[i-1][1]*((s[i-1]=="?")*2+1)
    dp[i][2]=dp[i-1][2]*((s[i-1]=="?")*2+1)
    dp[i][3]=dp[i-1][3]*((s[i-1]=="?")*2+1)
    if s[i-1]=="A" or s[i-1]=="?":
        dp[i][1]+=dp[i-1][0]
    if s[i-1]=="B" or s[i-1]=="?":
        dp[i][2]+=dp[i-1][1]
    if s[i-1]=="C" or s[i-1]=="?":
        dp[i][3]+=dp[i-1][2]
    dp[i][0]%=mod
    dp[i][1]%=mod
    dp[i][2]%=mod
    dp[i][3]%=mod
print(dp[n][3])

def main():
    MOD = 10 ** 9 + 7

    s = input()
    n = len(s)

    dp = [[0] * 4 for _ in range(n + 1)]
    dp[0][0] = 1

    for i, c in enumerate(s, start=1):
        for j in range(4):
            dp[i][j] = dp[i - 1][j]
        if c == 'A':
            dp[i][1] += dp[i - 1][0]
        elif c == 'B':
            dp[i][2] += dp[i - 1][1]
        elif c == 'C':
            dp[i][3] += dp[i - 1][2]
        else:
            for j in range(1, 4):
                dp[i][j] += dp[i - 1][j - 1]
            for j in range(4):
                dp[i][j] += dp[i - 1][j] * 2
        for j in range(4):
            dp[i][j] %= MOD

    print((dp[n][3]))


def __starting_point():
    main()

__starting_point()

s=input()
l=len(s)

dp=[4*[0]for _ in range(l+1)]
dp[0][0]=1

for i in range(1,l+1):
  si = s[i-1]
  if si == "?":
    dp[i][0] = dp[i-1][0] * 3
    dp[i][1] = dp[i-1][1] * 3
    dp[i][2] = dp[i-1][2] * 3
    dp[i][3] = dp[i-1][3] * 3
  else:
    dp[i][0] = dp[i-1][0]
    dp[i][1] = dp[i-1][1]
    dp[i][2] = dp[i-1][2]
    dp[i][3] = dp[i-1][3]
    
  if si == "A":
    dp[i][1] = dp[i-1][0] + dp[i][1]
  elif si == "B":
    dp[i][2] = dp[i-1][1] + dp[i][2]
  elif si == "C":
    dp[i][3] = dp[i-1][2] + dp[i][3]
  else:
    dp[i][1] = dp[i-1][0] + dp[i][1]
    dp[i][2] = dp[i-1][1] + dp[i][2]
    dp[i][3] = dp[i-1][2] + dp[i][3]
  
  for j in range(4):
    dp[i][j] = dp[i][j] % 1000000007
  
print(int(dp[-1][-1]))

s = input()
n = len(s)
MOD = 10 ** 9 + 7
dp = [[0] * 4 for _ in range(n + 1)]
dp[0][0] = 1

for i, x in enumerate(s):
    if x == 'A' or x == '?':
        dp[i + 1][0] += dp[i][0]
        dp[i + 1][1] += dp[i][1]
        dp[i + 1][2] += dp[i][2]
        dp[i + 1][3] += dp[i][3]
        dp[i + 1][1] += dp[i][0]
    if x == 'B' or x == '?':
        dp[i + 1][0] += dp[i][0]
        dp[i + 1][1] += dp[i][1]
        dp[i + 1][2] += dp[i][2]
        dp[i + 1][3] += dp[i][3]
        dp[i + 1][2] += dp[i][1]
    if x == 'C' or x == '?':
        dp[i + 1][0] += dp[i][0]
        dp[i + 1][1] += dp[i][1]
        dp[i + 1][2] += dp[i][2]
        dp[i + 1][3] += dp[i][3]
        dp[i + 1][3] += dp[i][2]

    for j in range(4):
        dp[i + 1][j] %= MOD

print((dp[n][3]))


mod=10**9+7
s=list(input())
s=['-']+s
l=len(s)
dp=[[0 for j in range(4)] for i in range(l)]
dp[0][0]=1
for i in range(1,l):
    for j in range(4):
        dp[i][j]=dp[i-1][j]
        if s[i]=='?':
            dp[i][j]*=3;
        if j and (s[i]=='?' or 'ABC'[j-1]==s[i]):
            dp[i][j]+=dp[i-1][j-1]
        dp[i][j]%=mod
print(dp[-1][3])

S=list(input())
n=len(S)
mod=10**9+7
dp=[[0]*4 for i in range(n+1)]
dp[0][0]=1
for i in range(1,n+1):
  if S[i-1]=="A":
    dp[i][0]=dp[i-1][0]%mod
    dp[i][1]=(dp[i-1][0]+dp[i-1][1])%mod
    dp[i][2]=dp[i-1][2]%mod
    dp[i][3]=dp[i-1][3]%mod
  elif S[i-1]=="B":
    dp[i][0]=dp[i-1][0]%mod
    dp[i][1]=dp[i-1][1]%mod
    dp[i][2]=(dp[i-1][1]+dp[i-1][2])%mod
    dp[i][3]=dp[i-1][3]%mod
  elif S[i-1]=="C":
    dp[i][0]=dp[i-1][0]%mod
    dp[i][1]=dp[i-1][1]%mod
    dp[i][2]=dp[i-1][2]%mod
    dp[i][3]=(dp[i-1][2]+dp[i-1][3])%mod
  else:
    dp[i][0]=dp[i-1][0]*3%mod
    dp[i][1]=(dp[i-1][0]+dp[i-1][1]*3)%mod
    dp[i][2]=(dp[i-1][1]+dp[i-1][2]*3)%mod
    dp[i][3]=(dp[i-1][2]+dp[i-1][3]*3)%mod
print(dp[n][3])

def main():
    MOD = 10**9 + 7
    S = input()
    N = len(S)
    CHARS = ['A', 'B', 'C']
    dp = [[0 for _ in range(4)] for _ in range(N + 1)]
    dp[N][3] = 1
    for i in range(N - 1, -1, -1):
        a = 3 if S[i] == '?' else 1
        dp[i][3] = a * dp[i + 1][3]
        dp[i][3] %= MOD
    for i in range(N - 1, -1, -1):
        a = 3 if S[i] == '?' else 1
        ch = S[i]
        for j in range(3):
            b = 1 if ch in ['?', CHARS[j]] else 0
            dp[i][j] = a * dp[i + 1][j] + b * dp[i + 1][j + 1]
            dp[i][j] %= MOD
    print(dp[0][0])


def __starting_point():
    main()
__starting_point()

s = input()
n = len(s)

#iよりleftのA、rightのC, leftの？, rightの?
la = [0 for _ in range(n)]
rc = [0 for _ in range(n)]
lq = [0 for _ in range(n)]
rq = [0 for _ in range(n)]

for i in range(n-1):
    if s[i] == 'A':
        la[i+1] = 1
    if s[i] == '?':
        lq[i+1] = 1
    if s[i+1] == '?':
        rq[i] = 1
    if s[i+1] == 'C':
        rc[i] = 1

for i in range(n-1):
    la[i+1] += la[i]
    lq[i+1] += lq[i]

for i in range(n-1, 0, -1):
    rc[i-1] += rc[i]
    rq[i-1] += rq[i]

ans = 0
mod = 10 ** 9 + 7

for i in range(n):
    if s[i] in ['B', '?']:
        l = la[i] * pow(3, lq[i], mod)
        if lq[i] > 0:
            l += lq[i] * pow(3, lq[i]-1, mod)
            l %= mod

        r = rc[i] * pow(3, rq[i], mod)
        if rq[i] > 0:
            r += rq[i] * pow(3, rq[i]-1, mod)
            r %= mod
        ans += l * r
        ans %= mod


print(ans)

MOD = 10**9 + 7
p3 = [1]

S = input()
n = len(S)

a = []
c = []
q = []
for i in range(n):
  p3.append(int(p3[i] * 3 % MOD))
  if S[i] == 'A':
    a.append(1)
  else:
    a.append(0)
  if S[i] == 'C':
    c.append(1)
  else:
    c.append(0)
  if S[i] == '?':
    q.append(1)
  else:
    q.append(0)

for i in range(1, n):
  a[i] += a[i - 1]
  c[i] += c[i - 1]
  q[i] += q[i - 1]

count = 0
for i in range(1, n - 1):
  if S[i] == 'B' or S[i] == '?':
    bq = 0 if S[i] == 'B' else 1
    count += a[i - 1] * (c[n - 1] - c[i]) * p3[q[n - 1] - bq]
    count += q[i - 1] * (c[n - 1] - c[i]) * p3[q[n - 1] - 1 - bq]
    count += a[i - 1] * (q[n - 1] - q[i]) * p3[q[n - 1] - 1 - bq]
    count += q[i - 1] * (q[n - 1] - q[i]) * p3[q[n - 1] - 2 - bq]

print((int(count % MOD)))


import numpy as np

MOD = 10 ** 9 + 7

S = input()

n = len(S)
dp = np.zeros((n+1, 4), np.int64)
dp[0, 0] = 1
for i, c in enumerate(S):
    if c == 'A' or c == '?':
        dp[i+1] += dp[i]
        dp[i+1, 1] += dp[i, 0]
    if c == 'B' or c == '?':
        dp[i+1] += dp[i]
        dp[i+1, 2] += dp[i, 1]
    if c == 'C' or c == '?':
        dp[i+1] += dp[i]
        dp[i+1, 3] += dp[i, 2]
    dp[i+1] %= MOD

print((dp[n, 3]))



import sys
input = sys.stdin.readline
MOD = 10 ** 9 + 7
 
def main():
    string = input().strip()
    n = len(string)
    dp = [[0, 0, 0, 0] for _ in range(n + 1)]
    dp[0][0] = 1
    for i, s in enumerate(string):
        if s == "A":
            dp[i + 1][0] = dp[i][0]
            dp[i + 1][1] = dp[i][1] + dp[i][0]
            dp[i + 1][2] = dp[i][2]
            dp[i + 1][3] = dp[i][3]
        elif s == "B":
            dp[i + 1][0] = dp[i][0]
            dp[i + 1][1] = dp[i][1]
            dp[i + 1][2] = dp[i][2] + dp[i][1]
            dp[i + 1][3] = dp[i][3]
        elif s == "C":
            dp[i + 1][0] = dp[i][0]
            dp[i + 1][1] = dp[i][1]
            dp[i + 1][2] = dp[i][2]
            dp[i + 1][3] = dp[i][3] + dp[i][2]
        else:
            dp[i + 1][0] = 3 * dp[i][0]
            dp[i + 1][1] = 3 * dp[i][1] + dp[i][0]
            dp[i + 1][2] = 3 * dp[i][2] + dp[i][1]
            dp[i + 1][3] = 3 * dp[i][3] + dp[i][2]
        for j in range(4):
            dp[i + 1][j] %= MOD
    print(dp[-1][-1] % MOD)
    
main()

S = input()
ans = 0
MOD = 10 ** 9 + 7
la = 0
lp = 0
rc = 0
rp = 0
for c in S:
    if c == 'C':
        rc += 1
    if c == '?':
        rp += 1
for c in S:
    if c == 'C':
        rc -= 1
    if c == '?':
        rp -= 1
    if c == '?' or c == 'B':
        if lp == 0:
            l = la * pow(3, lp, MOD)
        else:
            l = la * pow(3, lp, MOD) + lp * pow(3, lp-1, MOD)
        if rp == 0:
            r = rc * pow(3, rp, MOD)
        else:
            r = rc * pow(3, rp, MOD) + rp * pow(3, rp-1, MOD)
        ans += l*r
        ans %= MOD
    if c == 'A':
        la += 1
    if c == '?':
        lp += 1
print(ans)


s = input()

MOD = 10**9 + 7

a, ab, abc, q = 0, 0, 0, 1

for x in s:
    # Aなら状態数を足す
    if x == "A":
        a += q
        a %= MOD
    # BならこれまでAだった状態数を足す
    elif x == "B":
        ab += a
        ab %= MOD
    # CならAB→ABCが完成する
    elif x == "C":
        abc += ab
        abc %= MOD
    # ?なら色々変化する
    else:
        # 状態数が3倍になり、?がC, Bのケースも足される
        abc = (abc * 3 + ab) % MOD
        ab = (ab * 3 + a) % MOD
        a = (a * 3 + q) % MOD
        q = q * 3 % MOD

print(abc % MOD)

S = input()

MOD = 10 ** 9 + 7
dp, dp_a, dp_ab, dp_abc = 1, 0, 0, 0

for s in S:
    if s == 'A':
        dp_a += dp
    elif s == 'B':
        dp_ab += dp_a
    elif s == 'C':
        dp_abc += dp_ab
    else:
        dp, dp_a, dp_ab, dp_abc = dp * 3, dp_a * 3 + dp, dp_ab * 3 + dp_a, dp_abc * 3 + dp_ab
    dp %= MOD
    dp_a %= MOD
    dp_ab %= MOD
    dp_abc %= MOD
print(dp_abc)


S = input()
MOD = 10**9 + 7
dp = [[0, 0, 0] for i in range(len(S)+1)]

base = 1
for i, s in enumerate(S, 1):
  dp[i][0] = dp[i-1][0]
  dp[i][1] = dp[i-1][1]
  dp[i][2] = dp[i-1][2]
  if s == 'A':
    dp[i][0] += base
    dp[i][0] %= MOD
  elif s == 'B':
    dp[i][1] += dp[i-1][0]
    dp[i][1] %= MOD
  elif s == 'C':
    dp[i][2] += dp[i-1][1]
    dp[i][2] %= MOD
  else: # s == '?'
    dp[i][0] += 2*dp[i-1][0] + base
    dp[i][1] += 2*dp[i-1][1] + dp[i-1][0]
    dp[i][2] += 2*dp[i-1][2] + dp[i-1][1]
    dp[i][0] %= MOD
    dp[i][1] %= MOD
    dp[i][2] %= MOD
    base *= 3
    base %= MOD

print(dp[-1][2])

MOD = pow(10, 9) + 7
s = input()
n = len(s)
dp = [[0 for _ in range(4)] for _ in range(n + 1)]

dp[0][0] = 1
for i in range(n):
    dp[i+1][0] = dp[i][0]
    dp[i+1][1] = dp[i][1]
    dp[i+1][2] = dp[i][2]
    dp[i+1][3] = dp[i][3]
    if s[i] == 'A':
        dp[i+1][1] += dp[i][0]
    elif s[i] == 'B':
        dp[i+1][2] += dp[i][1]
    elif s[i] == 'C':
        dp[i+1][3] += dp[i][2]
    else:
        dp[i+1][0] = dp[i][0] * 3
        dp[i+1][1] = dp[i][1] * 3
        dp[i+1][2] = dp[i][2] * 3
        dp[i+1][3] = dp[i][3] * 3
        dp[i+1][1] += dp[i][0]
        dp[i+1][2] += dp[i][1]
        dp[i+1][3] += dp[i][2]
    dp[i+1][0] %= MOD
    dp[i+1][1] %= MOD
    dp[i+1][2] %= MOD
    dp[i+1][3] %= MOD

print((dp[n][3]))


S = input()

mod = 10**9+7
A = 0
AB = 0
ABC = 0
cnt = 0
for i in range(len(S)):
    if S[i] == "A":
        A += pow(3, cnt, mod)
        A %= mod
    elif S[i] == "B":
        AB += A
        AB %= mod
    elif S[i] == "C":
        ABC += AB
        ABC %= mod
    else:
        ABC = (3*ABC + AB) % mod
        AB = (3*AB + A) % mod
        A = (3*A + pow(3, cnt, mod)) % mod
        cnt += 1
        
        
print(ABC)

S=str(input())
N=len(S)
dp=[[0 for _ in range(4)] for _ in range(N+1)]
dp[0][0]=1
mod=10**9+7
for i in range(N):
  if S[i]=='A':
    dp[i+1][0]+=dp[i][0]%mod
    dp[i+1][1]+=dp[i][1]%mod+dp[i][0]%mod
    dp[i+1][2]+=dp[i][2]%mod
    dp[i+1][3]+=dp[i][3]%mod
  if S[i]=='B':
    dp[i+1][0]+=dp[i][0]%mod
    dp[i+1][1]+=dp[i][1]%mod
    dp[i+1][2]+=dp[i][2]%mod+dp[i][1]%mod
    dp[i+1][3]+=dp[i][3]%mod
  if S[i]=='C':
    dp[i+1][0]+=dp[i][0]%mod
    dp[i+1][1]+=dp[i][1]%mod
    dp[i+1][2]+=dp[i][2]%mod
    dp[i+1][3]+=dp[i][3]%mod+dp[i][2]%mod
  if S[i]=='?':
    dp[i+1][0]+=3*dp[i][0]%mod
    dp[i+1][1]+=(3*dp[i][1])%mod+dp[i][0]%mod
    dp[i+1][2]+=(3*dp[i][2])%mod+dp[i][1]%mod
    dp[i+1][3]+=(3*dp[i][3])%mod+dp[i][2]%mod
print(dp[N][3]%mod)

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

dpa = [0]*(10**5+10)
dpc = [0]*(10**5+10)

hatena_count = 0
pow3 = [1]*(10**5+10)

for i in range(1, 10**5+10):
    pow3[i] = pow3[i-1]*3 % mod

for i in range(n):
    if S[i] == "A":
        dpa[i+1] = (dpa[i] + pow3[hatena_count]) % mod
    elif S[i] == "?":
        dpa[i+1] = (3*dpa[i] + pow3[hatena_count]) % mod
        hatena_count += 1
    else:
        dpa[i+1] = dpa[i]

S.reverse()

hatena_count = 0
for i in range(n):
    if S[i] == "C":
        dpc[i+1] = (dpc[i] + pow3[hatena_count]) % mod
    elif S[i] == "?":
        dpc[i+1] = (3*dpc[i] + pow3[hatena_count]) % mod
        hatena_count += 1
    else:
        dpc[i+1] = dpc[i]

ans = 0
for i in range(1, n - 1):
    if S[i] == "B" or S[i] == "?":
        ans += dpa[n-1-i]*dpc[i]
        ans %= mod
print(ans)





mod = 10 ** 9 + 7

def main():
    s = input()

    n = len(s)

    dp = [[0 for _ in range(4)] for _ in range(n+1)]
    dp[0][0] = 1
    for i in range(n):
        if s[i] in ('A', '?'):
            dp[i+1][0] = (dp[i+1][0] + dp[i][0]) % mod
            dp[i+1][1] = (dp[i+1][1] + dp[i][1]) % mod
            dp[i+1][2] = (dp[i+1][2] + dp[i][2]) % mod
            dp[i+1][3] = (dp[i+1][3] + dp[i][3]) % mod
            dp[i+1][1] = (dp[i+1][1] + dp[i][0]) % mod
        if s[i] in ('B', '?'):
            dp[i+1][0] = (dp[i+1][0] + dp[i][0]) % mod
            dp[i+1][1] = (dp[i+1][1] + dp[i][1]) % mod
            dp[i+1][2] = (dp[i+1][2] + dp[i][2]) % mod
            dp[i+1][3] = (dp[i+1][3] + dp[i][3]) % mod
            dp[i+1][2] = (dp[i+1][2] + dp[i][1]) % mod
        if s[i] in ('C', '?'):
            dp[i+1][0] = (dp[i+1][0] + dp[i][0]) % mod
            dp[i+1][1] = (dp[i+1][1] + dp[i][1]) % mod
            dp[i+1][2] = (dp[i+1][2] + dp[i][2]) % mod
            dp[i+1][3] = (dp[i+1][3] + dp[i][3]) % mod
            dp[i+1][3] = (dp[i+1][3] + dp[i][2]) % mod

    print((dp[n][3]))

def __starting_point():
    main()

__starting_point()

MOD=10**9+7
S=input()
N=len(S)
Acum,Ccum,Qcum=[0]*(N+1),[0]*(N+1),[0]*(N+1)

for i in range(N):
    Acum[i+1]=Acum[i]+1 if S[i]=='A' else Acum[i]
    Ccum[i+1]=Ccum[i]+1 if S[i]=='C' else Ccum[i]
    Qcum[i+1]=Qcum[i]+1 if S[i]=='?' else Qcum[i]
ans=0
for i in range(N):
    if S[i]!='B' and S[i]!='?':
        continue
    a,c,l,r=Acum[i],Ccum[N]-Ccum[i+1],Qcum[i],Qcum[N]-Qcum[i+1]
    res=pow(3,l+r-2,MOD)*(3*a+l)%MOD*(3*c+r)%MOD
    ans=(ans+res)%MOD
print(ans)

S=input()
A=0 #Aの数
B=0 #ABの数
C=0 #ABCの数
n=1 #通り数
mod=10**9+7
for s in S:
    if s=="?":
        C=3*C+B
        B=3*B+A
        A=3*A+n
        n*=3
    elif s=="A":
        A+=n
    elif s=="B":
        B+=A
    else:
        C+=B
    A%=mod
    B%=mod
    C%=mod
    n%=mod
print(C)

mod = 10**9+7
S = input()
s = len(S)
dp = [[0 for i in range(4)]for j in range(s+1)]
mod = 10**9+7
 
dp[0][0] = 1
 
for j in range(4):
    for i in range(s):
        dp[i+1][j] = dp[i][j]%mod
        if S[i] == "?":
            dp[i+1][j] = dp[i][j]*3%mod
            if j > 0:
                dp[i+1][j] += dp[i][j-1]%mod
        else:
            if "ABC".index(S[i])+1 == j:
                dp[i+1][j] += dp[i][j-1]%mod
print(dp[s][3]%mod)

S=input()
pr=10**9+7
a1,a2,a3=0,0,0
c=0
for i in S:
    if i=="A":
        a1=(a1+pow(3,c,pr))%pr
    elif i=="B":
        a2=(a2+a1)%pr
    elif i=="C":
        a3=(a3+a2)%pr
    else:
        a1,a2,a3=(3*a1+pow(3,c,pr))%pr,(3*a2+a1)%pr,(3*a3+a2)%pr
        c+=1
print(a3)

# D - We Love ABC

S = list(str(input()))
MOD = 10**9 + 7
a = 0
ab = 0
abc = 0
pat = 1
for s in S:
    if s == 'A':
        a = (a + pat) % MOD
    elif s == 'B':
        ab = (ab + a) % MOD
    elif s == 'C':
        abc = (abc + ab) % MOD
    else: # s == '?'
        tmpa = a
        tmpab = ab
        a = (3*a + pat) % MOD
        ab = (3*ab + tmpa) % MOD
        abc = (3*abc + tmpab) % MOD
        pat = (pat*3) % MOD

print(abc)

data = input()
MOD = 10**9 + 7
SLen = len(data)
targets = "ABC"
array = [[0 for i in range(SLen + 1)] for _ in range(4)]
array[0][0] = 1
for i in range(SLen):
    for j in range(4):
        if data[i] == '?':
            if j < 3:
                array[j + 1][i + 1] = (array[j + 1][i + 1] + array[j][i]) % MOD
            array[j][i + 1] = (array[j][i + 1] + array[j][i] * 3) % MOD
        else:
            if j < 3 and data[i] == targets[j]:
                array[j + 1][i + 1] = (array[j + 1][i + 1] + array[j][i]) % MOD
            array[j][i + 1] = (array[j][i + 1] + array[j][i]) % MOD

print((array[3][SLen]))


S = input()
MOD = 10**9+7
A = 0
AB = 0
ABC = 0
cnt = 1
for c in S:
  if c=='A':
    A += cnt
    A %= MOD
  elif c=='B':
    AB += A
    AB %= MOD
  elif c=='C':
    ABC += AB
    ABC %= MOD
  else:
    nA = 3*A+cnt
    nAB = 3*AB+A
    nABC = 3*ABC+AB
    cnt *= 3
    A,AB,ABC = nA%MOD,nAB%MOD,nABC%MOD
    cnt %= MOD
print(ABC)

MOD = 10**9+7

S = input()
N = len(S)
dp = [[0]*4 for i in range(N+1)]
dp[0][0] = 1
for i in range(N):
    s = S[i]
    for j in range(4):
        if s == "?":
            dp[i+1][j] += dp[i][j]*3%MOD
        else:
            dp[i+1][j] += dp[i][j]%MOD
        if j < 3 and (s == "?" or s == "ABC"[j]):
            dp[i+1][j+1] += dp[i][j]%MOD
print((dp[N][3]%MOD))


S=input()
mod=10**9+7
La,Lq,Rc,Rq=0,0,S.count("C"),S.count("?")
ans=0
f=lambda x,y:pow(x,y,mod) if y>=0 else 0
for s in S:
	Rc-=s=="C";Rq-=s=="?"
	if s=="B" or s=="?":
		ans+=(La*f(3,Lq)+Lq*f(3,Lq-1))*(Rc*f(3,Rq)+Rq*f(3,Rq-1))
		ans%=mod
	La+=s=="A";Lq+=s=="?"
print(ans)

#we love abc
s=input()
mod=10**9+7
dpa=[[0,0] for i in range(len(s)+1)]
dpc=[[0,0] for i in range(len(s)+1)]
power3=[1 for i in range(10**5+100)]
for i in range(10**5+3):
    power3[i+1]=(power3[i]*3)%mod
for i in range(len(s)):
    if s[i]=="A":
        dpa[i+1][0]=(dpa[i][0]+power3[dpa[i][1]])%mod
        dpa[i+1][1]=dpa[i][1]  
    elif s[i]=="?":
        dpa[i+1][0]=(3*dpa[i][0]+power3[dpa[i][1]])%mod
        dpa[i+1][1]=dpa[i][1]+1   
    else:
        dpa[i+1]=dpa[i]
for i in range(len(s)):
    if s[len(s)-1-i]=="C":
        dpc[i+1][0]=(dpc[i][0]+power3[dpc[i][1]])%mod
        dpc[i+1][1]=dpc[i][1]  
    elif s[len(s)-1-i]=="?":
        dpc[i+1][0]=(3*dpc[i][0]+power3[dpc[i][1]])%mod
        dpc[i+1][1]=dpc[i][1]+1   
    else:
        dpc[i+1]=dpc[i]    
ans=0
for i in range(1,len(s)-1):
    if s[i]=="B" or s[i]=="?":
        ans+=dpa[i][0]*dpc[len(s)-1-i][0]
        ans=ans%mod
print(ans)

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

dp=[[0]*4 for i in range(N+1)]

dp[0][0]=1

for i in range(N):
    dp[i+1][0]=dp[i][0] if (S[i]!='?') else dp[i][0]*3%MOD
    dp[i+1][1]=dp[i][1] if (S[i]!='A' and S[i]!='?') else (dp[i][1]+dp[i][0])%MOD if (S[i]=='A') else (dp[i][0]+dp[i][1]*3)%MOD
    dp[i+1][2]=dp[i][2] if (S[i]!='B' and S[i]!='?') else (dp[i][2]+dp[i][1])%MOD if (S[i]=='B') else (dp[i][1]+dp[i][2]*3)%MOD
    dp[i+1][3]=dp[i][3] if (S[i]!='C' and S[i]!='?') else (dp[i][3]+dp[i][2])%MOD if (S[i]=='C') else (dp[i][2]+dp[i][3]*3)%MOD

print(dp[N][3])

# dp[i][j] := sのi文字目まで見たときに、ABCのj文字目までを部分列として取り出す方法の数。

s = input()

dp = [[0 for _ in range(4)]for _ in range(len(s))]
mod = 10 ** 9 + 7

power_3 = 1
for idx, letter in enumerate(s):
    dp[idx] = dp[idx-1].copy()

    if letter == 'A':
        dp[idx][1] += power_3
    elif letter == 'B':
        dp[idx][2] += dp[idx-1][1]
    elif letter == 'C':
        dp[idx][3] += dp[idx-1][2]
    elif letter == '?':
        dp[idx][1] *= 3
        dp[idx][2] *= 3
        dp[idx][3] *= 3
        dp[idx][1] += power_3 # 3**(この?を含まない、今までの?の個数)だけ、Aの手前の場合が考えられる。
        power_3 *= 3
        power_3 %= mod
        dp[idx][2] += dp[idx-1][1]
        dp[idx][3] += dp[idx-1][2]
        dp[idx][1] %= mod
        dp[idx][2] %= mod
        dp[idx][3] %= mod


print((dp[len(s)-1][3] % mod)) 
# print(dp)


s = input()
MOD = 10 ** 9 + 7
dp = [1, 0, 0, 0]

for x in s:
    emp, a, b, c = dp
    if x == 'A':
        dp[1] += emp
    if x == 'B':
        dp[2] += a
    if x == 'C':
        dp[3] += b
    if x == '?':
        dp = [v * 3 for v in dp]
        dp[1] += emp
        dp[2] += a
        dp[3] += b

    dp = [v % MOD for v in dp]

print(dp[3])

# def C(n, r ,mod=10**9+7):
#     if n-r<r: r=n-r
#     if r == 0: return 1
#     if r == 1: return n
# 
#     numerator = [n - r + k + 1 for k in range(r)]
#     denominator = [k + 1 for k in range(r)]
# 
#     for p in range(2,r+1):
#         pivot = denominator[p - 1]
#         if pivot > 1:
#             offset = (n - r) % p
#             for k in range(p-1,r,p):
#                 numerator[k - offset] /= pivot
#                 denominator[k] /= pivot
# 
#     result = 1
#     for k in range(r):
#         if numerator[k] > 1:
#             result *= int(numerator[k]) %mod
# 
#     return result % mod

A=list(input())
n=len(A)
mod=10**9+7
ans=0
numa= A[0]=="A" 
numa_= A[0]=="?"
numc=A[2:].count("C")
numc_= A[2:].count("?")

for i in range(1,n-1):
    #print(numa,numa_,numc,numc_)
    apro=cpro=0
    if A[i]=="B" or A[i]=="?":
        # for k in range(numa_+1):
        #     apro+= (((C(numa_,k)*pow(2,numa_-k,mod))%mod)*(numa+k))%mod
        # for k in range(numc_+1):
        #     cpro+= (((C(numc_,k)*pow(2,numc_-k,mod))%mod)*(numc+k))%mod
        #print(apro,cpro)
        apro= ((3*numa+numa_)*pow(3,(numa_-1),mod))%mod
        cpro= ((3*numc+numc_)*pow(3,(numc_-1),mod))%mod
        ans+= (apro*cpro)%mod
        ans%=mod
    if A[i] == "A":
        numa+=1
    if A[i]=="?":
        numa_+=1
    if A[i+1] =="C":
        numc-=1
    if A[i+1]=="?":
        numc_-=1
print(ans)


def main():
    MOD = 10 ** 9 + 7

    s = input()

    x, a, b, c = 1, 0, 0, 0

    for char in s:
        if char == 'A':
            a = (a + x) % MOD
        elif char == 'B':
            b = (b + a) % MOD
        elif char == 'C':
            c = (c + b) % MOD
        else:
            x, a, b, c = 3 * x % MOD, (3 * a + x) % MOD, (3 * b + a) % MOD, (3 * c + b) % MOD

    print(c)


def __starting_point():
    main()

__starting_point()

import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

S = sr()[::-1]
MOD = 10 ** 9 + 7
answer = 0
dp = [0, 0, 1] #Cの数, BC数, 総数
for i in range(len(S)):
    s = S[i]
    if s == 'A':
        answer += dp[1]
    elif s == 'B':
        dp[1] += dp[0]
    elif s == 'C':
        dp[0] += dp[2]
    elif s == '?':
        answer *= 3
        answer += dp[1]
        dp[1] *= 3
        dp[1] += dp[0]
        dp[0] *= 3
        dp[0] += dp[2]
        dp[2] *= 3
    answer %= MOD
    dp[0] %= MOD; dp[1] %= MOD; dp[2] %= MOD
print(answer)


s = input()
S = len(s)

#i文字目まで見たときj文字目まで確定しているときの組み合わせ
dp = [[0 for i in range(4)]for j in range(S+1)]
mod = 10**9+7

dp[0][0] = 1

for j in range(4):
    for i in range(S):
        dp[i+1][j] = dp[i][j]%mod
        if s[i] == "?":
            dp[i+1][j] = dp[i][j]*3%mod
            if j > 0:
                dp[i+1][j] += dp[i][j-1]%mod
        else:
            if "ABC".index(s[i])+1 == j:
                dp[i+1][j] += dp[i][j-1]%mod

print(dp[S][3]%mod)

s = input()
n = len(s)
mod = 10**9+7
dp = [[0]*4 for i in range(n+1)]
dp[0][0] = 1
for i in range(n):
  l = s[i]
  for j in range(4):
    if l == "?":
      dp[i+1][j] = (dp[i][j]*3)%mod
    else:
      dp[i+1][j] = dp[i][j] % mod
  if l == "A" or l == "?":
    dp[i+1][1] += dp[i][0] % mod
  if l == "B" or l == "?":
    dp[i+1][2] += dp[i][1] % mod
  if l == "C" or l == "?":
    dp[i+1][3] += dp[i][2] % mod
print(dp[n][3]%mod)

mod=10**9+7
s=list(input())
s=['-']+s
#print(s)
l=len(s)
dp=[[0 for j in range(4)] for i in range(l)]
dp[0][0]=1
for i in range(1,l):
    for j in range(4):
        dp[i][j]=dp[i-1][j]
        if s[i]=='?':
            dp[i][j]*=3;
        if (j  > 0) and (s[i]=='?' or 'ABC'[j-1]==s[i]):
            dp[i][j] += dp[i-1][j-1]
        dp[i][j] %= mod
        
print((dp[-1][3]))
#print(dp)


import sys
#input = sys.stdin.buffer.readline

def main():
    S = input()
    l = len(S)
    MOD = 10**9+7
    dp = [[0 for _ in range(3)] for _ in range(2)]
    cq = 1
    for st in S:
        if st == "A":
            dp[1][0] = dp[0][0]+cq
            dp[1][1] = dp[0][1]
            dp[1][2] = dp[0][2]
        elif st == "B":
            dp[1][0] = dp[0][0]
            dp[1][1] = dp[0][0]+dp[0][1]
            dp[1][2] = dp[0][2]
        elif st == "C":
            dp[1][0] = dp[0][0]
            dp[1][1] = dp[0][1]
            dp[1][2] = dp[0][1]+dp[0][2]
        else:
            dp[1][0] = dp[0][0]*3+cq
            dp[1][1] = dp[0][1]*3+dp[0][0]
            dp[1][2] = dp[0][2]*3+dp[0][1]
            cq *= 3
            cq %= MOD
        for i in range(3):
            dp[0][i] = dp[1][i]%MOD
    
    print((dp[0][-1]))

def __starting_point():
    main()

__starting_point()

MOD = 10**9 + 7
S = input()
res = 0
dp0 = 1 # ''
dp1 = 0 # 'a'
dp2 = 0 # 'ab'
dp3 = 0 # 'abc'

for c in S:
    if c == 'A':
        dp1 += dp0
    elif c == 'B':
        dp2 += dp1
    elif c == 'C':
        dp3 += dp2
    else:
        dp0,dp1,dp2,dp3 = dp0*3,dp1*3+dp0,dp2*3+dp1,dp3*3+dp2
    dp0 %= MOD
    dp1 %= MOD
    dp2 %= MOD
    dp3 %= MOD
print(dp3)


S = input(); N = len(S)
a,b,c,d = 0,0,0,1
mod = 10**9+7
for x in reversed(S):
  if x == "?":
    a,b,c,d = (3*a+b)%mod, (3*b+c)%mod, (3*c+d)%mod, 3*d%mod
  elif x == "A": a = (a+b)%mod
  elif x == "B": b = (b+c)%mod
  elif x == "C": c = (c+d)%mod
print(a)

s=input()
mod=pow(10,9)+7
dp=[0]*4
dp[0]=1
for si in s:
  if si=='A':
    dp[1]+=dp[0]
  elif si=='B':
    dp[2]+=dp[1]
  elif si=='C':
    dp[3]+=dp[2]
  else:
    dp[3]*=3
    dp[3]+=dp[2]
    dp[2]*=3
    dp[2]+=dp[1]
    dp[1]*=3
    dp[1]+=dp[0]
    dp[0]*=3
  dp[3]%=mod
  dp[2]%=mod
  dp[1]%=mod
  dp[0]%=mod
print((dp[3]))


S = input()

def solve(S):
    mod = 10**9+7
    N = len(S)
    Aquest = []
    Cquest = []
    cntA,cntquest = 0,0
    for i in range(N):
        if S[i] in 'B?':
            Aquest.append([cntA,cntquest])
        if S[i]=='A':
            cntA += 1
        if S[i]=='?':
            cntquest += 1
    cntC,cntquest = 0,0
    for i in range(N-1,-1,-1):
        if S[i] in 'B?':
            Cquest.append([cntC,cntquest])
        if S[i]=='C':
            cntC += 1
        if S[i]=='?':
            cntquest += 1
    Cquest = Cquest[::-1]
    ans = 0
    for aquest,cquest in zip(Aquest,Cquest):
        a = aquest[0]*pow(3,aquest[1],mod)
        if aquest[1]>0:
            a += aquest[1]*pow(3,aquest[1]-1,mod)
        c = cquest[0]*pow(3,cquest[1],mod)
        if cquest[1]>0:
            c += cquest[1]*pow(3,cquest[1]-1,mod)
        ans += a*c%mod
    ans %= mod
    return ans
print(solve(S))

s = input().rstrip()
n = len(s)
mod = 10**9 + 7
dp = [0] * 4
dp[0] = 1

for i in range(n):
    next = [0] * 4
    if s[i] == 'A':
        next[1] += dp[0]
    elif s[i] == 'B':
        next[2] += dp[1]
    elif s[i] == 'C':
        next[3] += dp[2]
    else:
        next[1] += dp[0]
        next[2] += dp[1]
        next[3] += dp[2]
        next[0] += dp[0] * 2
        next[1] += dp[1] * 2
        next[2] += dp[2] * 2
        next[3] += dp[3] * 2
    next[0] += dp[0]
    next[1] += dp[1]
    next[2] += dp[2]
    next[3] += dp[3]

    for j in range(4):
        next[j] %= mod
    dp = next
print((dp[3]))


import sys
sys.setrecursionlimit(100000000)
input = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = 10 ** 15

def main():
    S = input()
    N = len(S)
    C = [0] * (N + 1)
    QL = [0] * (N + 1)
    A = [0] * (N + 1)
    QR = [0] * (N + 1)
    for i in range(N):
        if S[i] == 'A':
            A[i + 1] = A[i] + 1
        else:
            A[i + 1] = A[i]
        if S[i] == '?':
            QL[i + 1] = QL[i] + 1
        else:
            QL[i + 1] = QL[i]
    
    for i in range(N - 1,-1,-1):
        if S[i] == 'C':
            C[i] = C[i + 1] + 1
        else:
            C[i] = C[i + 1]
        if S[i] == '?':
            QR[i] = QR[i + 1] + 1
        else:
            QR[i] = QR[i + 1]
    
    power3 = [1]
    for i in range(N):
        power3.append(power3[-1]*3%MOD)

    ans = 0
    for i in range(N):
        if S[i] in 'AC':
            continue
        choose_A = (A[i]*power3[QL[i]] + (QL[i] > 0)*QL[i]*power3[QL[i] - 1])%MOD
        choose_B = (C[i + 1]*power3[QR[i + 1]] + (QR[i + 1] > 0)*QR[i + 1]*power3[QR[i + 1] - 1])%MOD
        ans += choose_A*choose_B%MOD
        ans %= MOD
    print(ans) 

def __starting_point():
    main()
    

__starting_point()

s = input()
n_a = [0]
n_l = [0]
n_c = [0]
n_r = [0]

mod = 10 ** 9 + 7
n = len(s)

pow3 = [1]
for i in range(n):
    pow3.append(pow3[-1] * 3 % mod)

for i in range(n):
    if s[i] == 'A':
        n_a.append(n_a[-1]+1)
    else:
        n_a.append(n_a[-1])

    if s[i] == '?':
        n_l.append(n_l[-1]+1)
    else:
        n_l.append(n_l[-1])

    if s[-i-1] == 'C':
        n_c.append(n_c[-1]+1)
    else:
        n_c.append(n_c[-1])

    if s[-i-1] == '?':
        n_r.append(n_r[-1]+1)
    else:
        n_r.append(n_r[-1])

ans = 0

for i in range(1, n - 1):
    if s[i] in ['B', '?']:
        # ABC
        ans += n_a[i] * n_c[n -  1 - i] * pow3[n_l[i]] * pow3[n_r[n - 1 - i]] % mod
        ans %= mod
        # ?BC   
        ans += n_l[i] * n_c[n -  1 - i] * pow3[n_l[i] - 1] * pow3[n_r[n - 1 - i]] % mod
        ans %= mod
        # AB?
        ans += n_a[i] * n_r[n -  1 - i] * pow3[n_l[i]] * pow3[n_r[n - 1 - i] - 1] % mod
        ans %= mod
        # ?B?
        ans += n_l[i] * n_r[n -  1 - i] * pow3[n_l[i]-1] * pow3[n_r[n - 1 - i] - 1] % mod
        ans %= mod

print(ans)


#i文字目を見て，それより前のAの個数，ABの個数，ABCの個数を持っておく

S=input()
N=len(S)
dp=[0,0,0]

mod=10**9+7

p=[1]*(N+1)
for i in range(N):
    p[i+1]=(p[i]*3)%mod


count=0#?の数
for i in range(N):
    if S[i]=="A":
        dp[0]=(dp[0]+p[count]) %mod
    elif S[i]=="B":
        dp[1]=(dp[1]+dp[0])%mod
    elif S[i]=="C":
        dp[2]=(dp[2]+dp[1])%mod
    else:
        dp[2]=(dp[2]*3+dp[1])%mod
        dp[1]=(dp[1]*3+dp[0])%mod
        dp[0]=(dp[0]*3+p[count])%mod
        count+=1
        
print((dp[2]%mod))   







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

dp=[]
for i in range(len(S)+1):
  dp.append([0,0,0,0])
  
dp[-1][3]=1
for i in reversed(range(len(S))):
  if S[i]=="?":
    m1=3
  else:
    m1=1        
  dp[i][3]=m1*dp[i+1][3]
  dp[i][3]%=MOD
  
  for j in range(3):
    if S[i]=="?":
      m2=1
    else:
      if S[i]==["A","B","C"][j]:
        m2=1
      else:
        m2=0    
    dp[i][j]=m1*dp[i+1][j]+m2*dp[i+1][j+1]
    dp[i][j]%=MOD
    
print(dp[0][0])

#!/usr/bin/env python3


def main():
    S = input()
    N = len(S)
    m = 10**9 + 7
    # dp[i][j]:= 先頭からi-1文字目までみてABCのうちj文字目まで選んでいた時の残りの処理の個数
    dp = [[0]*4 for _ in range(N+1)]
    for i in range(N,-1,-1):
        for j in range(3,-1,-1):
            # print(i,j)
            if i == N:
                if j == 3:
                    # print(i,j)
                    dp[i][j] = 1
                else:
                    dp[i][j] = 0
            else:
                if S[i] == '?':
                    dp[i][j] = dp[i+1][j] * 3 % m
                else:
                    dp[i][j] = dp[i+1][j]
                
                if j < 3:# S[i]文字を選択する場合
                    if S[i] == '?' or S[i] == 'ABC'[j]:
                        dp[i][j] += dp[i+1][j+1]
                        dp[i][j] %= m

    print((dp[0][0]))


def __starting_point():
    main()

__starting_point()

D=[0,0,0,1,0]
for s in input():D=[(D[j]*((s=="?")*2+1)+D[j+1]*(s in t+"?"))%(10**9+7) for j,t in enumerate("CBA.")]+[0]
print(D[0])

def main():
    MOD = 10 ** 9 + 7

    s = input()
    n = len(s)

    acc_a = [0] * (n + 1)
    acc_c = [0] * (n + 1)
    acc_q = [0] * (n + 1)

    a = 0
    c = 0
    q = 0
    for i, char in enumerate(s, 1):
        if char == 'A':
            a += 1
        elif char == 'C':
            c += 1
        elif char == '?':
            q += 1
        acc_a[i] = a
        acc_c[i] = c
        acc_q[i] = q

    sq = [1]
    for _ in range(acc_q[n]):
        sq.append(sq[-1] * 3 % MOD)

    ans = 0
    qn = acc_q[n]
    for i, char in enumerate(s, 1):
        if char == 'B' or char == '?':
            is_q = int(char == '?')
            rq = acc_q[n] - acc_q[i]
            rc = acc_c[n] - acc_c[i]
            t = 0
            if qn - is_q >= 0:
                t += acc_a[i - 1] * rc * sq[acc_q[n] - is_q]
            if qn - 1 - is_q >= 0:
                t += acc_a[i - 1] * rq * sq[acc_q[n] - 1 - is_q]
                t += acc_q[i - 1] * rc * sq[acc_q[n] - 1 - is_q]
            if qn - 2 - is_q >= 0:
                t += acc_q[i - 1] * rq * sq[acc_q[n] - 2 - is_q]
            t %= MOD
            ans = (ans + t) % MOD
    print(ans)


def __starting_point():
    main()

__starting_point()

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

dp = [[0] * 4 for _ in range(n)]
dp[-1][0] = 1
# dp[i文字目までの?を確定させた][i文字目までで文字をn個選んだ]

for i, s in enumerate(S):
    if s == '?':
        dp[i][0] = dp[i - 1][0] * 3 % mod
        dp[i][1] = (dp[i - 1][0] + dp[i - 1][1] * 3) % mod
        dp[i][2] = (dp[i - 1][1] + dp[i - 1][2] * 3) % mod
        dp[i][3] = (dp[i - 1][2] + dp[i - 1][3] * 3) % mod
    elif s == 'A':
        dp[i][0] = dp[i - 1][0]
        dp[i][1] = (dp[i - 1][1] + dp[i - 1][0]) % mod
        dp[i][2] = dp[i - 1][2]
        dp[i][3] = dp[i - 1][3]
    elif s == 'B':
        dp[i][0] = dp[i - 1][0]
        dp[i][1] = dp[i - 1][1]
        dp[i][2] = (dp[i - 1][1] + dp[i - 1][2]) % mod
        dp[i][3] = dp[i - 1][3]
    else:
        dp[i][0] = dp[i - 1][0]
        dp[i][1] = dp[i - 1][1]
        dp[i][2] = dp[i - 1][2]
        dp[i][3] = (dp[i - 1][3] + dp[i - 1][2]) % mod

print((dp[-1][-1]))


S = input()
a = [1,0,0,0]

for s in S:
  if s=="A":
    a[1]+=a[0]
  elif s=="B":
    a[2]+=a[1]
  elif s=="C":
    a[3]+=a[2]
  else:
    a=[3*a[0]]+[3*a[n+1]+a[n] for n in range(3)]
  a=[a[n]%1000000007 for n in range(4)]

print(a[3])

md=10**9+7
s=input()
dp=[[0]*4 for _ in range(3)]
for c in s:
    if c=="A":dp[0][0]=(dp[0][0]+1)%md
    if c=="B":
        for j in range(2):dp[1][j]=(dp[1][j]+dp[0][j])%md
    if c=="C":
        for j in range(3):dp[2][j]=(dp[2][j]+dp[1][j])%md
    if c=="?":
        for j in range(3):dp[2][j+1]=(dp[2][j+1]+dp[1][j])%md
        for j in range(2):dp[1][j+1]=(dp[1][j+1]+dp[0][j])%md
        dp[0][1] = (dp[0][1] + 1) % md
ans=0
q=s.count("?")
for j in range(4):
    if q-j<0:break
    ans+=dp[2][j]*pow(3,q-j,md)
    ans%=md
print(ans)


MOD = 10**9 + 7


def main():
    S = input()
    N = len(S)
    pre_hatena = S[:1].count("?")
    a = S[:1].count("A")
    post_hatena = S[2:].count("?")
    c = S[2:].count("C")

    ans = 0
    for i in range(1, N-1):
        if S[i] == "?" or S[i] == "B":
            pre_pow = pow(3, pre_hatena-1, MOD)
            pre = ((pre_pow * 3) % MOD) * a + pre_pow * pre_hatena
            post_pow = pow(3, post_hatena-1, MOD)
            post = ((post_pow * 3) % MOD) * c + post_pow * post_hatena
            ans += pre * post
            ans %= MOD
        if S[i] == "?":
            pre_hatena += 1
        if S[i] == "A":
            a += 1
        if S[i+1] == "?":
            post_hatena -= 1
        if S[i+1] == "C":
            c -= 1
    print(ans)


def __starting_point():
    main()

__starting_point()

N=input()
DP=[[0]*(len(N)+1) for i in range(4)]
DP[0][0]=1#後側が位置
mod=10**9+7
for i in range(len(N)):
   if N[i]=="A":
      DP[0][i+1]=DP[0][i]%mod
      DP[1][i+1]=(DP[1][i]+DP[0][i])%mod
      DP[2][i+1]=DP[2][i]%mod
      DP[3][i+1]=DP[3][i]%mod
   elif N[i]=="B":
      DP[0][i+1]=DP[0][i]%mod
      DP[1][i+1]=DP[1][i]%mod
      DP[2][i+1]=(DP[2][i]+DP[1][i])%mod
      DP[3][i+1]=DP[3][i]%mod
   elif N[i]=="C":
      DP[0][i+1]=DP[0][i]%mod
      DP[1][i+1]=DP[1][i]%mod
      DP[2][i+1]=DP[2][i]%mod
      DP[3][i+1]=(DP[3][i]+DP[2][i])%mod
   else:
      DP[3][i+1]=(3*DP[3][i]+DP[2][i])%mod
      DP[0][i+1]=(DP[0][i]*3)%mod
      DP[1][i+1]=(DP[1][i]*3+DP[0][i])%mod
      DP[2][i+1]=(DP[2][i]*3+DP[1][i])%mod
print(DP[3][-1]%mod)