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()
n=len(s)
mod=10**9+7
dp=[[0]*3 for i in range(n)]
data=[0]*(n)
data[0]=1
for i in range(1,n):
    data[i]=data[i-1]*3%mod
count=0
if s[0]=="A":
    dp[0][0]=1
if s[0]=="?":
    dp[0][0]=1
    count+=1
for i in range(1,n):
    if s[i]=="A":
        dp[i][0]=(dp[i-1][0]+data[count])%mod
        dp[i][1]=dp[i-1][1]
        dp[i][2]=dp[i-1][2]
    elif s[i]=="B":
        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]
    elif s[i]=="C":
        dp[i][0]=dp[i-1][0]
        dp[i][1]=dp[i-1][1]
        dp[i][2]=(dp[i-1][2]+dp[i-1][1])%mod
    else:
        dp[i][0]=(3*dp[i-1][0]+data[count])%mod
        dp[i][1]=(3*dp[i-1][1]+dp[i-1][0])%mod
        dp[i][2]=(3*dp[i-1][2]+dp[i-1][1])%mod
        count+=1
print(dp[n-1][2])

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

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

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


def add(x, y):
    ret = x + y
    if ret >= MOD:
        ret -= MOD
    return ret


S = input().strip()

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

for i in range(len(S)):
    unit = 3 if S[i] == '?' else 1
    for j in range(4):
        dp[i + 1][j] = dp[i][j] * unit % MOD

    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[-1][3])

Solution (Python):
s=input()
a=[1,0,0,0]
for i in s:
    if i=="A": a[1]+=a[0]
    elif i=="B": a[2]+=a[1]
    elif i=="C": a[3]+=a[2]
    else: a=[ a[0]*3 ] + [ a[j+1]*3+a[j] for j in range(3) ]

    a=[a[i]%1000000007 for i in range(4)]
print(a[3])

Solution (Python):
from sys import stdin

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

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

for k in range(len(S) - 1, -1, -1):
    if S[k] == '?':
        dp[k][3] = 3 * dp[k + 1][3]
    else:
        dp[k][3] = dp[k + 1][3]
    dp[k][3] %= inf

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

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

Solution (Python):
MOD = 10**9 + 7
S = input()
N = len(S)
target = 'ABC'
n = len(target)
cur = [0]*(n+1)
cur[0] = 1
for s in S:
    for w in range(n):
        if s == target[w]:
            cur[w+1] += cur[w]
            cur[w+1] %= MOD
            break
    else: 
        for w in range(n-1,-1,-1):
            cur[w+1] = (cur[w+1]*3 + cur[w]) % MOD
        cur[0] *= 3
        cur[0] %= MOD
print(cur[-1])

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

S = input()

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

for i in reversed(range(N)):
    for j in reversed(range(4)):
        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):
def main():
    MOD = 10 ** 9 + 7

    S = input()

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

    for i in reversed(range(N + 1)):
        for j in reversed(range(4)):
            if i == N:
                dp[i][j] = int(j == 3)
            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])


if __name__ == '__main__':
    main()

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

S = input()

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

for i in reversed(range(N + 1)):
    for j in reversed(range(4)):
        if i == N:
            dp[i][j] = int(j == 3)
        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()
n = len(s)
mod = 10**9+7

a = [0]*n
b = [0]*n
c = [0]*n
d = [0]*n

x = 0
y = 0
for i in range(n):
    a[i] = x
    b[i] = y
    if s[i] == 'A':
        x += 1
    elif s[i] == '?':
        y += 1

x = 0
y = 0
for i in range(n-1,-1,-1):
    c[i] = x
    d[i] = y
    if s[i] == 'C':
        x += 1
    elif s[i] == '?':
        y += 1

def f(A,B,C,D):
    if B+D == 0:
        return pow(3,B+D,mod)*A*C%mod
    if B+D == 1:
        return pow(3,B+D,mod)*A*C%mod + pow(3,B+D-1,mod)*B*C%mod + pow(3,B+D-1,mod)*A*D%mod

    return pow(3,B+D,mod)*A*C%mod + pow(3,B+D-1,mod)*B*C%mod + pow(3,B+D-1,mod)*A*D%mod + pow(3,B+D-2,mod)*B*D%mod

res = 0
for i in range(1,n-1):
    if s[i] == 'B' or s[i]=='?':
        res = (res+f(a[i],b[i],c[i],d[i]))%mod
print(res%mod)

Solution (Python):
s = input()

dp = [[0 for j in range(4)] for i in range(len(s)+1)]
dp[0][0] = 1
mod = 10**9+7
for i in range(len(s)):
    for j in range(4):
        dp[i+1][j] = dp[i][j]
        dp[i+1][j] %= mod
        dp[i][j] %= mod
    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] * 2
        dp[i+1][1] += dp[i][1] * 2 + dp[i][0]
        dp[i+1][2] += dp[i][2] * 2 + dp[i][1]
        dp[i+1][3] += dp[i][3] * 2 + dp[i][2]

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

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

ret = 0
la, rc = 0, S.count('C')
lq, rq = 0, S.count('?')

def comb(ac, q) :
    if q == 0 :
        return ac * pow(3, q, mod) % mod
    else :
        p = pow(3, q - 1, mod)
        return (q * p + ac * p * 3) % mod

for s in S :
    if s == '?' :
        rq -= 1
        ret += comb(la, lq) * comb(rc, rq)
        ret %= mod
        lq += 1
    elif s == 'A' :
        la += 1
    elif s == 'B' :
        ret += comb(la, lq) * comb(rc, rq)
        ret %= mod
    elif s == 'C' :
        rc -= 1
    
print(ret)

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007


def A():
    r = II()
    if r < 1200:
        print("ABC")
    elif r < 2800:
        print("ARC")
    else:
        print("AGC")
    return


def B():
    return


def C():
    d, g = LI()
    pc = LIR(d)
    ans = float("INF")
    tokumono = list(itertools.product((0, 1), repeat=d))
    for toku in tokumono:
        ansa = 0
        ansb = 0
        for i in range(len(toku)):
            if toku[i] == 1:
                ansa += pc[i][0]
                ansb += pc[i][0] * (i + 1) * 100 + pc[i][1]
        for k in range(len(toku) - 1, -1, -1):
            if toku[k] == 0:
                for i in range(pc[k][0] + 1):
                    if i == pc[k][0]:
                        ansb += pc[k][1]
                    if ansb >= g:
                        ans = min(ans, ansa)
                        break
                    ansa += 1
                    ansb += (k+1) * 100
                break
    print(ans)
    return


def D_():
    N, X = LI()
    def dfs(n, x):
        
        if x == 1 and n > 0:
            return 0 
        elif x < 2 ** (n + 1) - 1:
            return dfs(n - 1, x - 1)
        elif x == 2 ** (n + 1) - 1:
            return 2 ** n 
        elif x == 2 ** (n + 2) - 3:
            return 2 ** (n + 1) - 1
        else:
            return dfs(n - 1, x - 2 ** (n + 1) + 1) + 2 ** n 
    a = dfs(N, X)
    print(a)
    return

def D():
    s = S()
    dp = [0] * 3
    s = s[::-1]
    x = 1
    for i, si in enumerate(s):
        if si == "A":
            dp[0] = (dp[0] + dp[1]) % mod
        elif si == "B":
            dp[1] = (dp[1] + dp[2]) % mod
        elif si == "C":
            dp[2] = (dp[2] + x) % mod
        else:
            dp[0] = (dp[0] * 3 + dp[1]) % mod
            dp[1] = (dp[1] * 3 + dp[2]) % mod
            dp[2] = (dp[2] * 3 + x) % mod
            x *= 3
            x %= mod
    print(dp[0])


if __name__ == '__main__':
    D()

Solution (Python):

m = (10 ** 9) + 7
S = list(input())
N = len(S)
dp = [[0 for i in range(N + 2)] for j in range(3)]
three = [0 for i in range(10 ** 5 + 1)]
three[0] = 1
for i in range(1, 10 ** 5 + 1):
	three[i] = (three[i - 1] * 3) % m


que = 0
for i in range(N):
	if S[i] == "A":
		dp[0][i + 1] = dp[0][i] + three[que]
		dp[1][i + 1] = dp[1][i]
		dp[2][i + 1] = dp[2][i]
	elif S[i] == "B":
		dp[0][i + 1] = dp[0][i]
		dp[1][i + 1] = dp[0][i] + dp[1][i]
		dp[2][i + 1] = dp[2][i]
	elif S[i] == "C":
		dp[0][i + 1] = dp[0][i]
		dp[1][i + 1] = dp[1][i]
		dp[2][i + 1] = dp[1][i] + dp[2][i]
	else:
		dp[0][i + 1] = 3 * dp[0][i] + three[que]
		dp[1][i + 1] = 3 * dp[1][i] + dp[0][i]
		dp[2][i + 1] = 3 * dp[2][i] + dp[1][i]
		que += 1
	dp[0][i + 1], dp[1][i + 1], dp[2][i + 1] = dp[0][i + 1] % m, dp[1][i + 1] % m, dp[2][i + 1] % m

print(dp[2][N])

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

Solution (Python):

s = input()
mod = 10 ** 9 + 7
cum = [[0],[0],[0],[0]]
for i in range(len(s)):
  tmp = ord(s[i]) - 65
  if tmp == -2:
    tmp = 3
  for j in range(4):
    if j == tmp:
      cum[j].append(cum[j][-1]+1)
    else:
      cum[j].append(cum[j][-1])
q = cum[3][-1]
tri = [1]
for _ in range(len(s)):
  tri.append(tri[-1] * 3 % mod)
ans = 0
for i in range(len(s)):
  if s[i] == 'B':
    ans += cum[0][i] * (cum[2][-1]-cum[2][i+1]) * tri[q]
    ans += cum[0][i] * (cum[3][-1]-cum[3][i+1]) * tri[q-1]
    ans += cum[3][i] * (cum[2][-1]-cum[2][i+1]) * tri[q-1]
    ans += cum[3][i] * (cum[3][-1]-cum[3][i+1]) * tri[q-2]
  if s[i] == '?':
    ans += cum[0][i] * (cum[2][-1]-cum[2][i+1]) * tri[q-1]
    ans += cum[0][i] * (cum[3][-1]-cum[3][i+1]) * tri[q-2]
    ans += cum[3][i] * (cum[2][-1]-cum[2][i+1]) * tri[q-2]
    ans += cum[3][i] * (cum[3][-1]-cum[3][i+1]) * tri[q-3]
  ans %= mod
print(ans)

Solution (Python):
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))



S = str(input())
N = len(S)

h_all = 0
for i in range(N):
    if S[i]=='?':
        h_all += 1

a = 0
b = 0
h = 0
numAB = 0
numAH = 0
numHB = 0
numHH = 0
dp = [0]*N

beki3 = pow(3,h_all-3,mod) if h_all>=4 else 1
beki2 = beki3*3 % mod if h_all>=3 else 1
beki1 = beki2*3 %mod if h_all>=2 else 1
beki0 = beki1*3 %mod if h_all>=1 else 1

for i in range(N):
    if S[i]=='A':
        if i>=1:
            dp[i] = dp[i-1]
        a += 1
    elif S[i]=='B':
        if i>=1:
            dp[i] = dp[i-1]
        numAB += a
        numHB += h
        b += 1
    elif S[i]=='?':
        if i>=1:
            if h_all>=1:
                dp[i] = (dp[i-1]+numAB*beki1) %mod
            if h_all>=2:
                dp[i] = (dp[i]+numAH*beki2) %mod
                dp[i] = (dp[i]+numHB*beki2) %mod
            if h_all>=3:
                dp[i] = (dp[i]+numHH*beki3)%mod
        numAH += a
        numHH += h
        h += 1
    else:
        if i>=1:
            dp[i] = (dp[i-1]+numAB*beki0) %mod
            if h_all>=1:
                dp[i] = (dp[i]+numAH*beki1) %mod
                dp[i] = (dp[i]+numHB*beki1) %mod
            if h_all>=2:
                dp[i] = (dp[i]+numHH*beki2)%mod

print(dp[N-1])

Solution (Python):
def main():
    S = input()
    MOD = 10 ** 9 + 7
    a = 0
    ab = 0
    abc = 0
    
    total = 1
    for s in S:
        if s == 'A':
            a += total
        elif s == 'B':
            ab += a
        elif s == 'C':
            abc += ab
        else:
            
            abc = abc * 3 + ab
            ab = ab * 3 + a
            a = a * 3 + total
            total *= 3
        a %= MOD
        ab %= MOD
        abc %= MOD
        total %= MOD
    
    print(abc)


main()

Solution (Python):
import math


MOD = (10 ** 9) + 7
S = input()
dp = [ [ 0 for _ in range(4)]  for _ in range(len(S) + 1)]
dp[0][0] = 1
for i in range(len(S) ):
    if S[i] == "A":
        dp[i + 1][0] += dp[i][0]
        dp[i + 1][1] += (dp[i][0] + dp[i][1])
        dp[i + 1][2] += (dp[i][2])
        dp[i + 1][3] += dp[i][3]
    if S[i] == "B":
        dp[i + 1][0] += dp[i][0]
        dp[i + 1][1] +=dp[i][1]
        dp[i + 1][2] +=  (dp[i][1] + dp[i][2])
        dp[i + 1][3] +=dp[i][3]

    if S[i] == "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][2] + dp[i][3])

    if S[i] == "?":
        dp[i + 1][0] +=  (dp[i][0] * 3)
        dp[i + 1][1] += (dp[i][0] + (dp[i][1]) * 3)
        dp[i + 1][2] += (dp[i][1]+ (dp[i][2]) * 3)
        dp[i + 1][3] += (dp[i][2]+ (dp[i][3]) * 3)
    for j in range(0,4):
        dp[i + 1][j] %= MOD




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

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LIM(): return list(map(lambda x:int(x) - 1, sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def LIRM(n): return [LIM() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 1000000007


s = S()
n = 1
a = ab = abc = 0
for i in s:
    if i == 'A':
        a = (a + n) % mod
    elif i == 'B':
        ab = (ab + a) % mod
    elif i == 'C':
        abc = (abc + ab) % mod
    else:
        abc = (abc * 3 + ab) % mod
        ab = (ab * 3 + a) % mod
        a = (a * 3 + n) % mod
        n = n * 3 % mod





print(abc)

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

S = [0] + list(input())
n = len(S) - 1

yet = [0] * (n+1)
a = [0] * (n+1)
ab = [0] * (n+1)
abc = [0] * (n+1)


abc[n] = 1

for i in range(1,n+1):
    if S[n-i+1] == "A":
        yet[n-i] = (yet[n-i+1] + a[n-i+1]) % MOD
        a[n-i] = a[n-i+1]
        ab[n-i] = ab[n-i+1]
        abc[n-i] = abc[n-i+1]
    elif S[n-i+1] == "B":
        yet[n-i] = yet[n-i+1]
        a[n-i] = (ab[n-i+1] + a[n-i+1]) % MOD
        ab[n-i] = ab[n-i+1]
        abc[n-i] = abc[n-i+1]
    elif S[n-i+1] == "C":
        yet[n-i] = yet[n-i+1]
        a[n-i] = a[n-i+1]
        ab[n-i] = (ab[n-i+1] + abc[n-i+1]) % MOD
        abc[n-i] = abc[n-i+1]
    else:
        yet[n-i] = (yet[n-i+1] * 3 + a[n-i+1]) % MOD
        a[n-i] = (a[n-i+1] * 3 + ab[n-i+1]) % MOD
        ab[n-i] = (ab[n-i+1] * 3 + abc[n-i+1]) % MOD
        abc[n-i] = (abc[n-i+1] * 3) % MOD

print(yet[0])

Solution (Python):
def main():
    S = input()
    
    mod = 10**9 + 7
    Ans = [[0,0,0,0,0]]
    import copy
    q = 1
    
    S = S[::-1]
    for i in range(len(S)):
        tmp = copy.deepcopy(Ans[i])
        if S[i] == "C":
            tmp[2] += q
            Ans.append(tmp)
        elif S[i] == "B":
            tmp[1] += q
            tmp[3] += tmp[2]
            tmp[3] %= mod
            Ans.append(tmp)
        elif S[i] == "A":
            tmp[0] += q
            tmp[4] += tmp[3]
            tmp[4] %= mod
            Ans.append(tmp)
        elif S[i] == "?":
            a,b,c,bc,abc = tmp
            Ans.append([(3*a+q)%mod, (3*b+q)%mod, (3*c+q)%mod, (3*bc+c)%mod, (3*abc+bc)%mod])
            q *= 3
            q %= mod
            
    print(Ans[-1][-1])
    
    
main()

Solution (Python):
def main():
    S = input()
    mod = pow(10, 9) + 7
    n = len(S)
    
    countA, countAB, countABC = 0, 0, 0
    strA, strNonA = 0, 1
    for i in range(n):
        if S[i] == "A":
            countA += strNonA + strA
            strA += strNonA
            strNonA = 0
        elif S[i] == "B":
            countAB += countA
        elif S[i] == "C":
            countABC += countAB
        else:
            countABC = 3*countABC + countAB
            countAB = 3*countAB + countA
            countA = 3*countA + strNonA + strA
            strA = 3*strA + strNonA
            strNonA *= 2

        countA %= mod
        countAB %= mod
        countABC %= mod
        strA %= mod
        strNonA %= mod
        

    return countABC % mod

if __name__ == '__main__':
    print(main())

Solution (Python):

S = input()

lis = [1,0,0,0]
nlis = [1,0,0,0]

for s in S:

    if s == "?":

        nlis[0] += lis[0] * 2
        nlis[1] += lis[1] * 2
        nlis[2] += lis[2] * 2
        nlis[3] += lis[3] * 2

    if s == "A" or s == "?":

        nlis[1] += lis[0]

    if s == "B" or s == "?":

        nlis[2] += lis[1]

    if s == "C" or s == "?":

        nlis[3] += lis[2]

    lis = []
    for i in range(4):

        lis.append(nlis[i] % (10 ** 9 + 7))

print (lis[3]  % (10 ** 9 + 7))

Solution (Python):
def main():
    s = input()

    pre = [1, 0, 0, 0]

    MOD = int(1e9) + 7

    for i in range(len(s)):
        next_ = [pre[0], pre[1], pre[2], pre[3]]
        if s[i] == "A":
            next_[1] += pre[0]
        elif s[i] == "B":
            next_[2] += pre[1]
        elif s[i] == "C":
            next_[3] += pre[2]
        else:
            next_[0] = pre[0] * 3
            next_[1] = pre[1] * 3 + pre[0]
            next_[2] = pre[2] * 3 + pre[1]
            next_[3] = pre[3] * 3 + pre[2]
        for i in range(4):
            next_[i] %= MOD
        pre = next_
    
    print(pre[3])

if __name__ == "__main__":
    main()

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

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

for i in range(size):
  cn = dp[i][0]%mod
  a = dp[i][1]%mod
  b = dp[i][2]%mod
  c = dp[i][3]%mod
  if(S[i] == 'A'):
    dp[i+1][0] += cn
    dp[i+1][1] += (a+cn)
    dp[i+1][2] += b
    dp[i+1][3] += c
  elif(S[i] == 'B'):
    dp[i+1][0] += cn
    dp[i+1][1] += a
    dp[i+1][2] += (b+a)
    dp[i+1][3] += c
  elif(S[i] == 'C'):
    dp[i+1][0] += cn
    dp[i+1][1] += a
    dp[i+1][2] += b
    dp[i+1][3] += (c+b)
  else:
    dp[i+1][0] += (3*cn)
    dp[i+1][1] += (3*a+cn)
    dp[i+1][2] += (3*b+a)
    dp[i+1][3] += (3*c+b)

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

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

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