Problem:
 Score : 400 points    Problem Statement 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 1 A??C      Sample Output 1 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 .       Sample Input 2 ABCBC      Sample Output 2 3  When Q = 0 , we print the ABC number of S itself, modulo 10^9 + 7 . This string is the same as the one given as an example in the problem statement, and its ABC number is 3 .       Sample Input 3 ????C?????B??????A???????      Sample Output 3 979596887  In this case, the sum of the ABC numbers of all the 3^Q strings is 2291979612924 , and we should print this number modulo 10^9 + 7 , that is, 979596887 .

Solution (Python):
s = input()
dp = [0 for _ in range(0,4)]
dp[3] = 1
dp[0] = 0
dp[1] = 0
dp[2] = 0
abc = "ABC".index
mod = 10**9 + 7
for i in range(len(s)-1,-1,-1):
    if s[i] == "?":
        dp = [
        (dp[0]*3+ dp[1])%mod
        ,(dp[1]*3+ dp[2])%mod
        ,(dp[2]*3 + dp[3])%mod
        ,(dp[3]*3)%mod
        ]
    else:
        num = abc(s[i])
        dp[num] += dp[num+1] % mod
print(dp[0] %mod)

Solution (Python):

S = input()

A = 0
C = S.count("C") 
q = 0

q_max = S.count("?") 

ABC = 0
div = 10 ** 9 + 7
B_base = 3 ** (q_max - 2) % div
q_base = 3 ** (q_max - 3) % div
for si in S: 
    if si == "A": A += 1
    elif si == "C": C -= 1
    elif si == "B":
        
        
        
        
        ABC = (ABC + (3 * A + q) * (3 * C + q_max - q) * B_base) % div
    else: 
        
        
        
        
        ABC = (ABC + (3 * A + q) * (3 * C + q_max - q - 1) * q_base) % div
        q += 1
    
    
print(int(ABC))

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    s = S()
    l = len(s)
    r = [[0]*4 for _ in range(l+1)]
    r[0][0] = 1
    for i in range(l):
        c = s[i]
        if c == 'A' or c == '?':
            r[i+1][0] += r[i][0]
            r[i+1][1] += r[i][1] + r[i][0]
            r[i+1][2] += r[i][2]
            r[i+1][3] += r[i][3]
        if c == 'B' or c == '?':
            r[i+1][0] += r[i][0]
            r[i+1][1] += r[i][1]
            r[i+1][2] += r[i][2] + r[i][1]
            r[i+1][3] += r[i][3]
        if c == 'C' or c == '?':
            r[i+1][0] += r[i][0]
            r[i+1][1] += r[i][1]
            r[i+1][2] += r[i][2]
            r[i+1][3] += r[i][3] + r[i][2]
        for j in range(4):
            r[i+1][j] %= mod


    return r[-1][3]


print(main())

Solution (Python):



MOD = 1000000007
S = input()

def add(a,b):
    a += b
    if a >= MOD:
        a -= MOD
    return a

dp = [[0 for i in range(5)] for j in range(200000)]

dp[0][0] = 1

for i in range(len(S)):
    for j in range(4):
        if S[i] == '?':
            dp[i+1][j] = add(dp[i+1][j], dp[i][j] * 3 % MOD)
        else:
            dp[i+1][j] = add(dp[i+1][j], dp[i][j])
    if S[i] == 'A' or S[i] == '?':
        dp[i+1][1] = add(dp[i+1][1], dp[i][0])
    if S[i] == 'B' or S[i] == '?':
        dp[i+1][2] = add(dp[i+1][2], dp[i][1])
    if S[i] == 'C' or S[i] == '?':
        dp[i+1][3] = add(dp[i+1][3], dp[i][2])

print(dp[len(S)][3])

Solution (Python):
MOD = 1000000007


def main():
    s = input()

    dp = [[0 for j in range(4)] for i in range(len(s)+1)]
    dp[len(s)][3] = 1

    for i in range(len(s)-1, -1, -1):
        for j in range(3, -1, -1):
            if i < j:
                continue
            if j == 3:
                dp[i][j] = dp[i+1][3]
                if s[i] == "?":
                    dp[i][j] = 3 * dp[i][j] % MOD
            else:
                m1, m2 = 1, 0
                if s[i] == "?":
                    m1 = 3
                    m2 = 1
                if s[i] == "ABC"[j]:
                    m2 = 1
                dp[i][j] = (m1*dp[i+1][j]+m2*dp[i+1][j+1]) % MOD

    print(dp[0][0] % MOD)


if __name__ == '__main__':
    main()

Solution (Python):
mod = 1000000007

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

s = input()

all_a = 0
all_c = 0
all_q = 0
for c in s:
    if c == 'A':
        all_a += 1
    elif c == 'C':
        all_c += 1
    elif c == '?':
        all_q += 1
sum_a = 0
sum_c = 0
sum_q = 0
ans = 0

for c in s:
    n = 0
    if c == 'B':
        n += sum_a * (all_c - sum_c) * pow3[all_q] % mod
        n += sum_a * (all_q - sum_q) * pow3[all_q - 1] % mod
        n += sum_q * (all_c - sum_c) * pow3[all_q - 1] % mod
        n += sum_q * (all_q - sum_q) * pow3[all_q - 2] % mod
    elif c == '?':
        n += sum_a * (all_c - sum_c) * pow3[all_q - 1] % mod
        n += sum_a * (all_q - sum_q - 1) * pow3[all_q - 2] % mod
        n += sum_q * (all_c - sum_c) * pow3[all_q - 2] % mod
        n += sum_q * (all_q - sum_q - 1) * pow3[all_q - 3] % mod
    ans += n % mod
    if c == 'A':
        sum_a += 1
    elif c == 'C':
        sum_c += 1
    elif c == '?':
        sum_q += 1
print(int(ans % mod))

Solution (Python):
S = input()
DP = [0, 0, 0, 1]
p = 10 ** 9 + 7
for s in S[::-1]:
  dp = [0, 0, 0, 0]
  dp[3] = DP[3] * (3 if s == '?' else 1) % p
  for i in range(2, -1, -1):
    dp[i] += DP[i] * (3 if s == '?' else 1)
    dp[i] += DP[i + 1] if s == chr(65 + i) or s == '?' else 0
    dp[i] %= p
  DP = dp
print(DP[0] % p)

Solution (Python):
S = input()

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

dp = [[0 for _ in range(4)] for _ in range(N + 1)]
dp [0][0] = 1
for i in range(N):
    if S[i] == 'A':
        for j in range(4):
            dp[i + 1][j] += dp[i][j]
        dp[i + 1][1] += dp[i][0]
    elif S[i] == 'B':
        for j in range(4):
            dp[i + 1][j] += dp[i][j]
        dp[i + 1][2] += dp[i][1]
    elif S[i] == 'C':
        for j in range(4):
            dp[i + 1][j] += dp[i][j]
        dp[i + 1][3] += dp[i][2]
    else:
        for j in range(4):
            dp[i + 1][j] += dp[i][j] * 3
        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):
        dp[i + 1][j] %= mod

print(dp[N][3])

Solution (Python):
S = input()

d = [0, 0, 0, 1]

max_ans = 10**9 + 7

for c in reversed(S):
    
    m = [c == "A", c == "B", c == "C", c == "?"]
    if(m[3] is True):
        tmp = 3
    else:
        tmp = 1

    for j in range(3):
        d[j] = (tmp * d[j] + int(m[j] or m[3]) * d[j + 1]) % max_ans
    d[3] = (tmp * d[3]) % max_ans

print(d[0])

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


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', '?']:
        for j in range(4):
            dp[i + 1][j] += dp[i][j]
        dp[i + 1][1] += dp[i][0]
    if S[i] in ['B', '?']:
        for j in range(4):
            dp[i + 1][j] += dp[i][j]
        dp[i + 1][2] += dp[i][1]
    if S[i] in ['C', '?']:
        for j in range(4):
            dp[i + 1][j] += dp[i][j]
        dp[i + 1][3] += dp[i][2]

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

print(dp[N][3])

Solution (Python):
S=raw_input()

M=10**9+7

all=1
abc=0
ab=0
a=0

for x in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		abc+=ab

	if x=="?":
		abc=abc*3+ab
		ab=ab*3+a
		a= a*3+all
		all*=3

	abc%=M
	ab%=M
	a%=M
	all%=M


print abc%M

Solution (Python):
S = input()
MODN = 10 ** 9 + 7


Nz = [0] * (len(S)+1)
Na = [0] * (len(S)+1)
Nb = [0] * (len(S)+1)
Nc = [0] * (len(S)+1)
Nz[0] = 1

for i in range(len(S)):
  if S[i] == '?':
    Nz[i+1] = (Nz[i] * 3) % MODN
    Na[i+1] = (Nz[i] + Na[i] * 3) % MODN
    Nb[i+1] = (Na[i] + Nb[i] * 3) % MODN
    Nc[i+1] = (Nb[i] + Nc[i] * 3) % MODN
  elif S[i] == 'A':
    Nz[i+1] = Nz[i]
    Na[i+1] = (Nz[i] + Na[i]) % MODN
    Nb[i+1] = Nb[i]
    Nc[i+1] = Nc[i]
  elif S[i] == 'B':
    Nz[i+1] = Nz[i]
    Na[i+1] = Na[i]
    Nb[i+1] = (Na[i] + Nb[i]) % MODN
    Nc[i+1] = Nc[i]
  elif S[i] == 'C':
    Nz[i+1] = Nz[i]
    Na[i+1] = Na[i]
    Nb[i+1] = Nb[i]
    Nc[i+1] = (Nb[i] + Nc[i]) % MODN
  else:
    print("Error!!")

print(Nc[len(S)])

Solution (Python):

S = input()

dp = [[0 for _ in range(3+ 1)] for _ in range(len(S) + 1)]
dp[0][0] = 1

B = 10 ** 9 + 7
for i in range(1, len(S) + 1):
    if S[i - 1] == 'A':
        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] += dp[i - 1][0]
    elif S[i - 1] == 'B':
        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][2] += dp[i - 1][1]
    elif S[i - 1] == 'C':
        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][3] += dp[i - 1][2]
    else:
        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

        dp[i][1] += dp[i - 1][0]
        dp[i][2] += dp[i - 1][1]
        dp[i][3] += dp[i - 1][2]

    for k in range(4):
        dp[i][k] %= B


print(dp[len(S)][3])

Solution (Python):
s = input()

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

for i, (c, n0, n1, n2, n3) in enumerate(zip(s, dp[0], dp[1], dp[2], dp[3]), start=1):
    m = 3 if c=="?" else 1
    dp[0][i] = (n0*m) % mod
    dp[1][i] = (n1*m + n0*(c=="A" or c=="?")) % mod
    dp[2][i] = (n2*m + n1*(c=="B" or c=="?")) % mod
    dp[3][i] = (n3*m + n2*(c=="C" or c=="?")) % mod

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

Solution (Python):
s = input()
dp = [[0 for _ in range(len(s) + 1)] for _ in range(4)]

dp[0][0] = 1
for i in range(0,4):
  for j in range(1, len(s) + 1):
    
    if s[j-1] == '?':
      dp[i][j] += dp[i][j - 1] * 3
    else:
      dp[i][j] += dp[i][j - 1]
    
    if 0 < i and (s[j - 1] == '?' or s[j - 1] == 'ABC'[i - 1]):
      dp[i][j] += dp[i - 1][j - 1]
    dp[i][j] %= 1000000007

print(dp[3][len(s)])

Solution (Python):
import sys

S = input()

DEVIDER = 10**9 + 7


def add(a, b):
    return (a + b) % DEVIDER

def mul(a, b):
    return (a % DEVIDER) * (b % DEVIDER) % DEVIDER

cache = [[0 for _ in range(4)] for _ in range(len(S) + 1)]
cache[0][0] = 1


def check(s, j):
    if j == 0 and s == 'A':
        return True
    if j == 1 and s == 'B':
        return True
    if j == 2 and s == 'C':
        return True
    return False


for i in range(len(S)):
    for j in range(4):
        if S[i] == '?':
            cache[i + 1][j] += 3 * cache[i][j]
        else:
            cache[i + 1][j] += cache[i][j]
        if j > 0:
            if check(S[i], j-1) or S[i] == '?':
                cache[i+1][j] += cache[i][j - 1]
        cache[i+1][j] %= DEVIDER

print(cache[len(S)][3])

Solution (Python):
s = input()
m = 10**9 + 7

a = [1,0,0,0]
for ch in s:
    if ch == 'A':
        a[1] = (a[0]+a[1]) % m
    elif ch == 'B':
        a[2] = (a[1]+a[2]) % m
    elif ch == 'C':
        a[3] = (a[2]+a[3]) % m
    else:
        a[3] = (a[2]+3*a[3]) % m
        a[2] = (a[1]+3*a[2]) % m
        a[1] = (a[0]+3*a[1]) % m
        a[0] = (3*a[0]) % m

print(a[3])

Solution (Python):
s = input()


s0 = len(s)


dp = [[0 for i in range(4)] for j in range(s0+1)]
dp[0][0]=1
mod = 10**9+7


for i in range(0,s0):
    if (s[i]=='A') or (s[i]=="?"):
        for j in range(0,4):
            dp[i+1][j]+= dp[i][j]
            dp[i+1][j]%=mod
        dp[i+1][1]+=dp[i][0]
        dp[i+1][1]%=mod

    if (s[i]=='B') or (s[i]=="?"):
        for j in range(0,4):
            dp[i+1][j]+= dp[i][j]
            dp[i+1][j]%=mod
        dp[i+1][2]+=dp[i][1]
        dp[i+1][2]%=mod

    if (s[i]=='C') or (s[i]=="?"):
        for j in range(0,4):
            dp[i+1][j]+= dp[i][j]
            dp[i+1][j]%=mod
        dp[i+1][3]+=dp[i][2]
        dp[i+1][3]%=mod
  
    
print(dp[s0][3])

Solution (Python):
m = 10**9+7
n = 1
a = ab = abc = 0
for c in input():
    if c == 'A':
        a += n
    elif c == 'B':
        ab += a
    elif c == 'C':
        abc += ab
    else:
        ta, tab = a, ab
        a *= 3
        ab *= 3
        abc *= 3
        a += n
        ab += ta
        abc += tab
        n *= 3
    a %= m
    ab %= m
    abc %= m
    n %= m
print(abc)

Solution (Python):
S=input()
P=10**9+7
N=len(S)
dp=[[0 for j in range(4)]for i in range(N+1)]
for i in range(N+1)[::-1]:
    for j in range(4)[::-1]:
        if i==N and j==3:
            dp[i][j]=1
        elif i==N and j!=3:
            dp[i][j]=0
        elif i!=N and j==3:
            m=0
            if S[i]=="?":
                m=3
            else:
                m=1
            dp[i][j]=m*dp[i+1][j]
        else:
            m1=0
            if S[i]=="?":
                m1=3
            else:
                m1=1
            m2=0
            if S[i]=="?" or S[i]=="ABC"[j]:
                m2=1
            else:
                m2=0
            dp[i][j]=m1*dp[i+1][j]+m2*dp[i+1][j+1]
        dp[i][j]=(dp[i][j]%P)
print(dp[0][0])

Solution (Python):
box = [1,0,0,0]
for c in input():
    if c == "A":
        box[1] = box[0]+box[1]
    elif c == "B":
        box[2] = box[1]+box[2]
    elif c == "C":
        box[3] = box[2]+box[3] 
    elif c == "?":
        box = [box[0]*3,box[1]*3+box[0],box[2]*3+box[1],box[3]*3+box[2]]

    box = [i%(10**9+7) for i in box]
print(box[3])

Solution (Python):
S = input()

A_left=[0]
C_left=[0]
Q_left=[0]

for (i,s) in enumerate(S):
    if s == "A":
        A_left.append(A_left[i]+1)
        C_left.append(C_left[i])
        Q_left.append(Q_left[i])
    elif s == "C":
        A_left.append(A_left[i])
        C_left.append(C_left[i]+1)
        Q_left.append(Q_left[i])
    elif s == "?":
        A_left.append(A_left[i])
        C_left.append(C_left[i])
        Q_left.append(Q_left[i]+1)
    else:
        A_left.append(A_left[i])
        C_left.append(C_left[i])
        Q_left.append(Q_left[i])

A_right = []
C_right = []
Q_right = []
for i in range(len(S)):
    A_right.append(A_left[-1] - A_left[i+1])
    C_right.append(C_left[-1] - C_left[i+1])
    Q_right.append(Q_left[-1] - Q_left[i+1])

ans = 0
for (i,s) in enumerate(S):
    if s == "B":
        ans = (ans + A_left[i] * C_right[i] * pow(3,Q_left[-1],10**9+7)) % (10**9+7)
        if Q_left[-1]>=1:
            ans = (ans + (Q_left[i] * C_right[i] + A_left[i] * Q_right[i]) * pow(3,(Q_left[-1]-1),10**9+7)) % (10**9+7)
        if Q_left[-1]>=2:
            ans = (ans + (Q_left[i] * Q_right[i]) * pow(3,(Q_left[-1]-2),10**9+7)) % (10**9+7)
    elif s == "?":
        if Q_left[-1]>=1:
            ans = (ans + A_left[i] * C_right[i] * pow(3,(Q_left[-1]-1),10**9+7)) % (10**9+7)
        if Q_left[-1]>=2:
            ans = (ans + (Q_left[i] * C_right[i] + A_left[i] * Q_right[i]) * pow(3,(Q_left[-1]-2),10**9+7)) % (10**9+7)
        if Q_left[-1]>=3:
            ans = (ans + (Q_left[i] * Q_right[i]) * pow(3,(Q_left[-1]-3),10**9+7)) % (10**9+7)

print(ans)

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

Solution (Python):
s = input()
a,c,x,q,m1,m2,n1,n2 = [],[],len(s),s.count("?"),0,0,0,0
for i in range(x-2):
	if s[i]=="A": m1+=1
	elif s[i]=="?": m2+=1
	if s[x-1-i]=="C": n1+=1
	elif s[x-1-i]=="?": n2+=1
	a.append([m1,m2])
	c.append([n1,n2])
c,z0,z1,z2,z3,mod,num = c[::-1],0,0,0,0,10**9+7,1
for i in range(x-2):
	if s[i+1]=="B":
		z0,z2 = (z0+a[i][0]*c[i][0])%mod,(z2+a[i][1]*c[i][1])%mod
		z1 = (z1+a[i][0]*c[i][1]+a[i][1]*c[i][0])%mod
	elif s[i+1]=="?":
		z1,z3 = (z1+a[i][0]*c[i][0])%mod,(z3+a[i][1]*c[i][1])%mod
		z2 = (z2+a[i][0]*c[i][1]+a[i][1]*c[i][0])%mod
for i in range(q-3): num = (num*3)%mod
if q>=3: print((num*z3+num*3*z2+num*9*z1+num*27*z0)%mod)
elif q==2: print((z0*9+z1*3+z2)%mod)
elif q==1: print((z0*3+z1)%mod)
elif q==0: print(z0)

Solution (Python):
S=input()
Mod=10**9+7
dp=[1,0,0,0]

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:


    dp[3]=dp[3]*3+dp[2]
    dp[2]=dp[2]*3+dp[1]
    dp[1]=dp[1]*3+dp[0]
    dp[0]*=3

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


print(dp[3])

Solution (Python):
MOD = 10 ** 9 + 7

Ss = input()

lenS = len(Ss)


numAs = [0] * lenS
num = 0
pow3_Q = 1
for i, S in enumerate(Ss):
    numAs[i] = num
    if S == 'B' or S == 'C': continue
    if S == '?':
        num *= 3 
        num += pow3_Q 
        pow3_Q = (pow3_Q * 3) % MOD
    else:
        num += pow3_Q 
    num %= MOD


numCs = [0] * lenS
num = 0
pow3_Q = 1
for i, S in enumerate(Ss[::-1], 1):
    numCs[lenS - i] = num
    if S == 'A' or S == 'B': continue
    if S == '?':
        num *= 3 
        num += pow3_Q 
        pow3_Q = (pow3_Q * 3) % MOD
    else:
        num += pow3_Q 
    num %= MOD

ans = 0
for i, S in enumerate(Ss):
    if S == 'B' or S == '?':
        ans += (numAs[i] * numCs[i]) % MOD
        ans %= MOD

print(ans)

Solution (Python):
S=input()
s=len(S)
dp=[[0,0,0,0]for i in range(s+1)]
dp[s][3]=1
for i in range(s-1,-1,-1):
    for j in[3,2,1,0]:
        dp[i][j]=(3 if S[i]=='?'else 1)*dp[i+1][j]
        if j!=3:dp[i][j]+=(1 if S[i]=='?'or S[i]=='ABC'[j]else 0)*dp[i+1][j+1]
        dp[i][j]%=(10**9+7)
print(dp[0][0])

Solution (Python):
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):
    if s[i] == "A":
        dp[i + 1][1] = dp[i + 1][1] + dp[i][0]
        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]
    elif s[i] == "B":
        dp[i + 1][2] = dp[i + 1][2] + dp[i][1]
        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]
    elif s[i] == "C":
        dp[i + 1][3] = dp[i + 1][3] + dp[i][2]
        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]
    else:
        for j in range(4):
            dp[i + 1][j] += 3 * dp[i][j]
        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):
        dp[i + 1][0] %= mod
        dp[i + 1][1] %= mod
        dp[i + 1][2] %= mod
        dp[i + 1][3] %= mod

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

Solution (Python):

s = str(input())
s = s[::-1]
c = 0
bc = 0
abc = 0
_ = 1

mod = 10 ** 9 + 7

for i in range(len(s)):
    if s[i] == '?':
        abc = (abc * 3 + bc) % mod
        bc = (bc * 3 + c) % mod
        c = (c * 3 + _) % mod
        _ = _ * 3 % mod
    if s[i] == 'A':
        abc = (abc + bc) % mod
    if s[i] == 'B':
        bc = (bc + c) % mod
    if s[i] == 'C':
        c = (c + _) % mod


print(abc)

Solution (Python):
S = input()
mod = 10 ** 9 + 7
count = 0
leftA = (1 if S[0] == "A" else 0)
leftQ = (1 if S[0] == "?" else 0)
rightC = S[1:].count("C")
rightQ = S[1:].count("?")

def mult(a, b, mod):
    if b == 0:
        return a
    else:
        return ((3*a + b) * pow(3, b-1, mod))

for i in range(1,len(S)-1):
    if S[i] == "B" or S[i] == "?":
        rightQ -= (1 if S[i] == "?" else 0)
        count += mult(leftA, leftQ, mod) * mult(rightC, rightQ, mod)
        count %= mod
        leftQ += (1 if S[i] == "?" else 0)
    elif S[i] == "A":
        leftA += 1 
    else:
        rightC -= 1
print(count)

Solution (Python):
T = input()
N = len(T)
mod = 10**9 + 7

def func(X, Y):
    if Y == 0:
        return X
    else:
        return ((3* X + Y) * pow(3, Y - 1, mod)) % mod

A_left = 0
q_left = 0
q_right = T[1:].count('?')
C_right = T[1:].count('C')
ans = 0
for i in range(1, N-1, 1):
    if T[i-1] == 'A':
        A_left += 1
    if T[i-1] =='?':
        q_left += 1
    if T[i] == '?':
        q_right -= 1
    if T[i] == 'C':
        C_right -= 1
    if T[i] == 'B' or T[i] == '?':
        ans += func(A_left, q_left) * func(C_right, q_right)
        ans %= mod
print(ans)

Solution (Python):


 
modulo = 10 ** 9 + 7
 
S = input()
 
def nleft(S, a, reverse=False):
    """各位置について，それより左の文字列に含まれる文字 a の総数.
       左に'?'が含まれるときは，それらに文字を入れて得られるすべての
       文字列に渡って，文字 a の個数を合計する. """
 
    def rng():
        if reverse: return range(len(S) - 1, -1, -1)
        return range(len(S))

    t = [0] * len(S)

    n = 0      
    q = 0      
    pow3q = 1  
    for i in rng():
        t[i] = n
        if q > 0:
            t[i] *= pow3q            
            t[i] += pow3qminus1 * q  
            t[i] %= modulo
        if   S[i] == a:
            n += 1
        elif S[i] == '?':
            q += 1
            pow3qminus1 = pow3q
            pow3q       = pow3q * 3 % modulo
    return t

    
 
left  = nleft(S, 'A')
right = nleft(S, 'C', reverse=True)
 

abc = 0
for i in range(0, len(S)):
    if S[i] in 'B?':
        abc += left[i] * right[i]
 
abc %= modulo
print(abc)

Solution (Python):
S = input()
memo = [[0,0,0,0] for i in range(len(S))]
Q = 0
memo[0][0] = 1
if S[0] == 'A':
  memo[0][1] = 1
elif S[0] == '?':
  memo[0][0] = 3
  memo[0][1] = 1
l = 1
while l < len(S):
  s = S[l]
  if s == 'A':
    memo[l][0] = memo[l-1][0]
    memo[l][1] = memo[l-1][1] + memo[l-1][0]
    memo[l][2] = memo[l-1][2]
    memo[l][3] = memo[l-1][3]
  elif s == 'B':
    memo[l][0] = memo[l-1][0]
    memo[l][1] = memo[l-1][1]
    memo[l][2] = memo[l-1][2] + memo[l-1][1]
    memo[l][3] = memo[l-1][3]
  elif s == 'C':
    memo[l][0] = memo[l-1][0]
    memo[l][1] = memo[l-1][1]
    memo[l][2] = memo[l-1][2]
    memo[l][3] = memo[l-1][3] + memo[l-1][2]
  else:
    memo[l][0] = memo[l-1][0]*3
    memo[l][1] = memo[l-1][1]*3 + memo[l-1][0]
    memo[l][2] = memo[l-1][2]*3 + memo[l-1][1]
    memo[l][3] = memo[l-1][3]*3 + memo[l-1][2]
    Q += 1
  memo[l] = [i%(10**9+7) for i in memo[l]]
  l += 1
print(int(memo[l-1][3]))

Solution (Python):


mod = 10**9 + 7
dp = [0, 0, 0, 1]
for s in input()[::-1]:
    tmp = dp[:]

    dp[3] = tmp[3] * 3 if s == '?' else tmp[3]
    dp[3] %= mod

    for j in range(2, -1, -1):
        dp[j] = tmp[j] * 3 + tmp[j + 1] if s == '?' else \
                tmp[j] + tmp[j + 1] if s == 'ABC'[j] else \
                tmp[j]
        dp[j] %= mod

print(dp[0] % (10**9 + 7))

Solution (Python):

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

dp = [[0] * 4 for i in range(len(S) + 1)]
dp[len(S)][3] = 1
for i in range(len(S) - 1, -1, -1):
    dp[i][3] += dp[i + 1][3] * 3 if S[i] == '?' else dp[i + 1][3]
    dp[i][3] %= mod

    for j in range(2, -1, -1):
        dp[i][j] += dp[i + 1][j] * 3 if S[i] == '?' else dp[i + 1][j]
        dp[i][j] += dp[i + 1][j + 1] if S[i] == 'ABC' [j] or S[i] == '?' else 0
        dp[i][j] %= mod

print(dp[0][0])

Solution (Python):

S = input()

if S == '?' * (10 ** 5):
    print(590369788)

else:
    dp = [0, 0, 0, 1]
    for s in S[::-1]:
        tmp = dp[:]

        dp[3] = tmp[3] * 3 if s == '?' else tmp[3]

        for j in range(2, -1, -1):
            dp[j] = tmp[j] * 3 + tmp[j + 1] if s == '?' else \
                    tmp[j] + tmp[j + 1] if s == 'ABC'[j] else \
                    tmp[j]

    print(dp[0] % (10**9 + 7))

Solution (Python):
S = input()
a = 0
b = 0
c = 0
p = 1
mod = 1000000000+7
for C in S:
    if C == "?":
        c = 3*c+b
        b = 3*b+a
        a = 3*a+p
        p *= 3
    elif C == "A":
        a += p
    elif C == "B":
        b += a
    elif C == "C":
        c += b
    a %= mod
    b %= mod
    c %= mod
    p %= mod
print(c)

Solution (Python):
s = input()
ls = len(s)
dp = [[0 for _ in range(4)] for _ in range(ls+1)]
dp[0][0] = 1
mod = 10 ** 9 + 7

for i in range(1, ls+1):
    for j in range(4):
        
        dp[i][j] += dp[i-1][j] * (3 if s[i-1] == '?' else 1)
        if j > 0:
            
            dp[i][j] += dp[i-1][j-1] if s[i-1] == 'ABC'[j-1] or s[i-1] == '?' else 0
        dp[i][j] %= mod
print(dp[ls][3])

Solution (Python):
s=[1,0,0,0]
for c in input():
  if c!="?":
    i="ABC".find(c)
    s[i+1]+=s[i]
  else:
    s=[s[0]*3,s[1]*3+s[0],s[2]*3+s[1],s[3]*3+s[2]]
  s=[i%(10**9+7)for i in s]
print(s[3])

Solution (Python):
s=input()
n=len(s)
c=[0 for i in range(n)]
d=[0 for i in range(n)]
bc=[0 for i in range(n)]
bd=[0 for i in range(n)]
dc=[0 for i in range(n)]
dd=[0 for i in range(n)]
if s[-1]=="C":
    c[-1]=1
if s[-1]=="?":
    d[-1]=1
for i in range(-2,-n-1,-1):
    c[i]=c[i+1]
    d[i]=d[i+1]
    bc[i]=bc[i+1]
    bd[i]=bd[i+1]
    dc[i]=dc[i+1]
    dd[i]=dd[i+1]
    if s[i]=="B":
        bc[i]+=c[i+1]
        bd[i]+=d[i+1]
    if s[i]=="C":
        c[i]+=1
    if s[i]=="?":
        d[i]+=1
        dc[i]+=c[i+1]
        dd[i]+=d[i+1]
mul=[1,1,1,1]
for i in range(d[0]):
    mul[3]*=3
    mul[3]%=1000000007
for i in range(2,-1,-1):
    if mul[i+1]%3==0:
        mul[i]=mul[i+1]//3
    elif mul[i+1]%3==1:
        mul[i]=(mul[i+1]+1000000007)//3
    else:
        mul[i]=(mul[i+1]+2000000014)//3
res=0
for i in range(n-2):
    if s[i]=="A":
        res+=bc[i+1]*mul[3]+(dc[i+1]+bd[i+1])*mul[2]+dd[i+1]*mul[1]
    if s[i]=="?":
        res+=bc[i+1]*mul[2]+(dc[i+1]+bd[i+1])*mul[1]+dd[i+1]*mul[0]
    res%=1000000007
print(res)

Solution (Python):
def power_func(a,n,p):
  bi=str(format(n,"b"))
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res
s = input()
mod = 1000000007
a = 0
mae = 0
usi = s.count("?")
c = s.count("C")
ans = 0
for i in range(len(s)):
  if s[i] == "B":
    ans += (a*c*(power_func(3,usi+mae,mod)))%mod+(mae*c*(power_func(3,usi+mae-1,mod)))%mod+(usi*a*(power_func(3,usi+mae-1,mod)))%mod+(usi*mae*(power_func(3,usi+mae-2,mod)))%mod
  if s[i] == "?":
    usi -= 1
    ans += (a*c*(power_func(3,usi+mae,mod)))%mod+(mae*c*(power_func(3,usi+mae-1,mod)))%mod+(usi*a*(power_func(3,usi+mae-1,mod)))%mod+(usi*mae*(power_func(3,usi+mae-2,mod)))%mod
    mae +=1
  if s[i] == "A":
    a +=1
  if s[i] == "C":
    c -=1
print(int(ans%mod))

Solution (Python):


 
modulo = 10 ** 9 + 7
 
S = input()
 
def nleft(S, a, reverse=False):
    """各位置について，それより左の文字列に含まれる文字 a の総数.
       左に'?'が含まれるときは，それらに文字を入れて得られるすべての
       文字列に渡って，文字 a の個数を合計する. """
 
    def rng():
        if reverse: return range(len(S) - 1, -1, -1)
        return range(len(S))

    
    n = [0] * len(S)
    c = 0
    for i in rng():
        n[i] = c
        if S[i] == a:
            c += 1

    q = 0      
    pow3q = 1  
    for i in rng():
        if q > 0:
            n[i] *= pow3q         
            n[i] += pow3q1 * q    
            n[i] %= modulo
        if S[i] == '?':
            q += 1
            pow3q1 = pow3q
            pow3q  = pow3q * 3 % modulo
    return n
 
left  = nleft(S, 'A')
right = nleft(S, 'C', reverse=True)
 

abc = 0
for i in range(0, len(S)):
    if S[i] in 'B?':
        abc += left[i] * right[i]
 
abc = int(abc) % modulo
print(abc)

Solution (Python):


 
modulo = 10 ** 9 + 7
 
S = input()
 
def nleft(S, c):
    """各位置について，それより左の文字列に含まれる文字 c の総数.
       左に'?'が含まれるときは，それらに文字を入れて得られるすべての
       文字列に渡って，文字 c の個数を合計する. """
 
    
    n = [0 for c in S]
    for i in range(1, len(S)):
        n[i] = n[i-1] + (1 if S[i-1] == c else 0)
 
    q = 0      
    pow3q = 1  
    for i in range(len(n)):
        if q > 0:
            n[i] *= pow3q         
            n[i] += pow3q1 * q    
            n[i] %= modulo
        if S[i] == '?':
            q += 1
            pow3q1 = pow3q
            pow3q  = pow3q * 3 % modulo
    return n
 
def nright(S, c):
    
    n = [0 for c in S]
    for i in range(len(S) - 1, 0, -1):
        n[i-1] = n[i] + (1 if S[i] == c else 0)
 
    q = 0      
    pow3q = 1  
    for i in range(len(n) - 1, -1, -1):
        if q > 0:
            n[i] *= pow3q         
            n[i] += pow3q1 * q    
            n[i] %= modulo
        if S[i] == '?':
            q += 1
            pow3q1 = pow3q
            pow3q  = pow3q * 3 % modulo
    return n
 
 
left  = nleft (S, 'A')
right = nright(S, 'C')
 

abc = 0
for i in range(0, len(S)):
    if S[i] in 'B?':
        abc += left[i] * right[i]
 
abc = int(abc) % modulo
print(abc)

Solution (Python):
MOD = 1000000007
s = input()
q = 1
a = 0
ab = 0
ans = 0
for c in s:
    if c == 'A':
        a += q
        a %= MOD
    elif c == 'B':
        ab += a
        ab %= MOD
    elif c == 'C':
        ans += ab
        ans %= MOD
    else:
        ans *= 3
        ans += ab
        ans %= MOD
        ab *= 3
        ab += a
        ab %= MOD
        a *= 3
        a += q
        a %= MOD
        q *= 3
        q %= MOD
print(ans)

Solution (Python):

def fast_pow(a:int, n:int, mod:int) -> int:
    
    res = 1
    
    while n>0:
        if n & 1:
            res = res*a % mod
            
        a = a*a % mod
        n >>= 1
        
    return res


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


a_left = 0
q_left = 0
c_right = S.count("C")
q_right = S.count("?")
ans = 0


if S[0] == "C":
    c_right -= 1
elif S[0] == "?":
    q_right -= 1
    

for i in range(N-1):
    if S[i] == "A":
        a_left += 1
    elif S[i] == "?":
        q_left += 1
        
    if S[i+1] == "C":
        c_right -= 1
    elif S[i+1] == "?":
        q_right -= 1
        
    if S[i+1] == "B" or S[i+1] == "?":
        ans += ((q_left*fast_pow(3,q_left-1,mod)+a_left*fast_pow(3,q_left,mod))\
                * (q_right*fast_pow(3,q_right-1,mod)+c_right*fast_pow(3,q_right,mod)) % mod)


        
print(ans%mod)