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()
L = len(S)
Q = 10**9 + 7
anum = [ 0 for _ in range(L+1)]

cnum = [ 0 for _ in range(L+1)]
hnum = [ 0 for _ in range(L+1)]
for i in range(1,L+1):
    if S[i-1] == 'A':
        anum[i] = anum[i-1] + 1

        cnum[i] = cnum[i-1]
        hnum[i] = hnum[i-1]
    elif S[i-1] == 'B':
        anum[i] = anum[i-1]

        cnum[i] = cnum[i-1]
        hnum[i] = hnum[i-1]
    elif S[i-1] == 'C':
        anum[i] = anum[i-1]

        cnum[i] = cnum[i-1] + 1
        hnum[i] = hnum[i-1]
    else:
        anum[i] = anum[i-1]

        cnum[i] = cnum[i-1]
        hnum[i] = hnum[i-1] + 1

ans = 0
czen = cnum[L]
hzen = hnum[L] 
for i in range(1,L+1):
    if S[i-1] == 'B' or S[i-1] == '?':


        A = ((anum[i-1]*pow(3,hnum[i-1],Q))%Q + (hnum[i-1]*pow(3,max(0,hnum[i-1]-1),Q))%Q)%Q
        C = (((czen - cnum[i])*pow(3,hzen - hnum[i],Q))%Q + ((hzen - hnum[i])*pow(3,max(0,hzen - hnum[i]-1),Q))%Q)%Q
        K = (A*C)%Q
        ans = (ans + K)%Q
print(int(ans))

Solution (Python):
S = input()
L = len(S)
Q = 10**9 + 7
anum = [ 0 for _ in range(L+1)]

cnum = [ 0 for _ in range(L+1)]
hnum = [ 0 for _ in range(L+1)]
for i in range(1,L+1):
    if S[i-1] == 'A':
        anum[i] = anum[i-1] + 1

        cnum[i] = cnum[i-1]
        hnum[i] = hnum[i-1]
    elif S[i-1] == 'B':
        anum[i] = anum[i-1]

        cnum[i] = cnum[i-1]
        hnum[i] = hnum[i-1]
    elif S[i-1] == 'C':
        anum[i] = anum[i-1]

        cnum[i] = cnum[i-1] + 1
        hnum[i] = hnum[i-1]
    else:
        anum[i] = anum[i-1]

        cnum[i] = cnum[i-1]
        hnum[i] = hnum[i-1] + 1

ans = 0
czen = cnum[L]
hzen = hnum[L] 
for i in range(1,L+1):
    if S[i-1] == 'B' or S[i-1] == '?':


        A = ((anum[i-1]*pow(3,hnum[i-1],Q))%Q + (hnum[i-1]*pow(3,max(0,hnum[i-1]-1),Q))%Q)%Q
        C = (((czen - cnum[i])*pow(3,hzen - hnum[i],Q))%Q + ((hzen - hnum[i])*pow(3,max(0,hzen - hnum[i]-1),Q))%Q)%Q
        K = (A*C)%Q
        ans = (ans + K)%Q
print(int(ans))

Solution (Python):
S = input()
N = len(S)

mod = 10 ** 9 + 7
A, AB, ABC, ALL = 0, 0, 0, 1
for s in S:
    if s == "A":
        A += ALL

    if s == "B":
        AB += A

    if s == "C":
        ABC += AB

    if s == "?":
        ABC = (ABC * 3 + AB) % mod
        AB = (AB * 3 + A) % mod
        A = (A * 3 + ALL) % mod
        ALL = (ALL * 3) % mod

print(ABC % mod)

Solution (Python):
S = input()
MOD = 10**9+7
dp = [[0 for i in range(3)] for q in range(4)]
for c in S:
    if c == 'A':
        dp[0][0] += 1
    elif c == 'B':
        dp[0][1] += dp[0][0]
        dp[1][1] += dp[1][0]
    elif c == 'C':
        dp[0][2] += dp[0][1]
        dp[1][2] += dp[1][1]
        dp[2][2] += dp[2][1]
    else:
        
        dp[1][2] += dp[0][1]
        dp[2][2] += dp[1][1]
        dp[3][2] += dp[2][1]
        
        dp[1][1] += dp[0][0]
        dp[2][1] += dp[1][0]
        
        dp[1][0] += 1

q = S.count('?')
ans = 0
for use_q in range(4):
    if use_q > q: break
    ans += (dp[use_q][-1] % MOD) * pow(3, q - use_q, MOD)
    ans %= MOD
print(ans)

Solution (Python):
s = list(input())

div = 10 ** 9 + 7

n = len(s)

all_q = s.count('?')

a0 = 0
a1 = 0
b0 = 0
b1 = 0
b2 = 0
c0 = 0
c1 = 0
c2 = 0
c3 = 0
for x in s:
    if x == 'A':
        a0 += 1
    elif x == 'B':
        b0 += a0
        b1 += a1
    elif x == 'C':
        c0 += b0
        c1 += b1
        c2 += b2
    else:
        c1 += b0
        c2 += b1
        c3 += b2
        b1 += a0
        b2 += a1
        a1 += 1

c = 0
temp = 3 ** all_q
if c3 > 0:
    c += c3 * (temp // 27)
if c2 > 0:
    c += c2 * (temp // 9)
if c1 > 0:
    c += c1 * (temp // 3)
c += c0 * temp

print(c % div)

Solution (Python):
S = input()

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

num_q = [1]
res = 1
for i in range(N):
    if S[i] == "?":
        res = res*3 % mod
    num_q.append(res)
    


dp_a = [0]*(N+1)
dp_ab = [0]*(N+1)
dp_abc = [0]*(N+1)

for i in range(1,N+1):
    if S[i-1] == "A":
        dp_a[i] = dp_a[i-1] + num_q[i-1]
        dp_ab[i] = dp_ab[i-1]
        dp_abc[i] = dp_abc[i-1]
        
    elif S[i-1] == "B":
        dp_a[i] = dp_a[i-1]
        dp_ab[i] = dp_ab[i-1] + dp_a[i-1]
        dp_abc[i] = dp_abc[i-1]
        
    elif S[i-1] == "C":
        dp_a[i] = dp_a[i-1]
        dp_ab[i] = dp_ab[i-1]
        dp_abc[i] = dp_abc[i-1] + dp_ab[i-1]
        
    elif S[i-1] == "?":
        dp_a[i] = dp_a[i-1] * 3 + num_q[i-1]
        dp_ab[i] = dp_ab[i-1] * 3 + dp_a[i-1] 
        dp_abc[i] = dp_abc[i-1] * 3 + dp_ab[i-1]
        
    dp_a[i] %= mod
    dp_ab[i] %= mod
    dp_abc[i] %= mod
        
print(dp_abc[N])

Solution (Python):
from collections import defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
AtoZ = [chr(i) for i in range(65,65+26)]
atoz = [chr(i) for i in range(97,97+26)]

def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())


def ex_square(n,k): 
	if k <= 0:
		return 1
	elif k % 2 == 0:
		ans = ex_square(n, k//2) ** 2
	else:
		ans = ex_square(n,k-1) * n
	return ans%mod

S = list(input())

aa = [0]
bb = [0]
cc = [0]
qq = [0]
Sa = Sb =Sc = Sq = 0
for s in S:
	if s == 'A':
		Sa += 1
	elif s == 'B':
		Sb += 1
	elif s == 'C':
		Sc += 1
	elif s == '?':
		Sq += 1
	aa.append(Sa)
	bb.append(Sb)
	cc.append(Sc)
	qq.append(Sq)

ans = 0
ex = [ex_square(3,Sq),ex_square(3,Sq-1),ex_square(3,Sq-2),ex_square(3,Sq-3)]

for i,s in enumerate(S):
	if s == 'B':
		k = 0
	elif s == '?':
		k = 1
	elif s == 'A' or s == 'C':
		continue

	Lq = qq[i]
	Rq = Sq-Lq-k
	La = aa[i]
	Rc = Sc - cc[i]

	ans1 = (ex[0 + k] * (La*Rc)%mod)%mod
	ans2 = (ex[1 + k] * (Lq*Rc)%mod)%mod
	ans3 = (ex[1 + k] * (La*Rq)%mod)%mod
	ans4 = (ex[2 + k] * (Lq*Rq)%mod)%mod
	ans += (ans1+ans2+ans3+ans4)%mod
	ans %= mod

print(ans)

Solution (Python):


from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(10000000)

S = raw_input()
sz = len(S)

A = [0 for i in range(sz)]
C = [0 for i in range(sz)]

cnt = 0
for i in range(sz):
    if S[i] == 'A':
        cnt += 3
    if S[i] == '?':
        cnt += 1
    A[i] = cnt

cnt = 0
for i in range(sz - 1, -1, -1):
    if S[i] == 'C':
        cnt += 3
    if S[i] == '?':
        cnt += 1
    C[i] = cnt

ans = 0
MOD = 10 ** 9 + 7
for i in range(1, sz - 1):
    if S[i] == 'B':
        ans += A[i - 1] * C[i + 1] * 3
        ans %= MOD
    if S[i] == '?':
        ans += A[i - 1] * C[i + 1]
        ans %= MOD

def inv(n):
    POW = MOD - 2
    mul = n
    ret = 1
    while POW > 0:
        if POW % 2 == 1:
            ret *= mul
            ret %= MOD
        mul *= mul
        mul %= MOD
        POW /= 2
    return ret

q_num = S.count('?')
if q_num < 3:
    ans *= inv(3 ** (3 - q_num))
    ans %= MOD
else:
    for i in range(q_num - 3):
        ans *= 3
        ans %= MOD
print ans

Solution (Python):
a = dict()
a['A'] = []
a['B'] = []
a['C'] = []
a['?'] = []

string = input()

for i in range(0, len(string)):
    temp = string[i]
    a[temp].append(i)
    
result = 0
dp = [0] * 4
MOD = 10**9 + 7
dp[0] = 1

for c in string:
    if c == '?':
        for i in range(3, 0, -1):
            dp[i] = dp[i]*3 + dp[i-1]
            dp[i] %= MOD
        dp[0] = dp[0]*3
        dp[0] %= MOD
    elif c == 'A':
        dp[1] += dp[0] % MOD
    elif c == 'B':
        dp[2] += dp[1] % MOD
    elif c == 'C':
        dp[3] += dp[2] % MOD
print (dp[3] % MOD)

Solution (Python):
S=input()
lens=len(S)

mod=10**9+7


Asum=[0]*lens

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

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

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


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


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











print(count%mod)

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

cumsum = {}
for key in ['A', 'B', 'C', '?']:
    cumsum[key] = [0]*(len(s)+1)
for i, ss in enumerate(s):
    for key in cumsum.keys():
        if key == ss:
            cumsum[key][i+1] = cumsum[key][i]+1
        else:
            cumsum[key][i+1] = cumsum[key][i]

ans = 0
for i in range(1, len(s)-1):
    if s[i] == 'A' or s[i] == 'C':
        continue
    
    n_a = cumsum['A'][i]
    n_c = cumsum['C'][-1] - cumsum['C'][i+1]
    n_q_left = cumsum['?'][i]
    n_q_right = cumsum['?'][-1] - cumsum['?'][i+1]

    n_left = (n_a*pow(3, n_q_left, MOD))%MOD + (n_q_left*pow(3, max(n_q_left-1, 0), MOD))%MOD
    n_left %= MOD
    n_right = (n_c*pow(3, n_q_right, MOD))%MOD + (n_q_right*pow(3, max(n_q_right-1, 0), MOD))%MOD
    n_right %= MOD
    ans += (n_left*n_right)%MOD
    ans %= MOD

print(ans)

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

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

dp[n] = [0, 0, 0, 1, 0]
for i in range(n-1, -1, -1):
    m1 = 3 if S[i] == '?' else 1
    for j in range(4):
        m2 = 1 if S[i] == '?' or j == 'ABC'.find(S[i]) else 0
        dp[i][j] = (dp[i+1][j] * m1 + dp[i+1][j+1] * m2) % mod
print(dp[0][0])

Solution (Python):
def d_we_love_abc(S):
    MOD = 10**9 + 7
    dp = [[0] * 4 for _ in range(len(S)+1)]
    dp[len(S)][3] = 1  

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

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

    ans = dp[0][0]
    return ans

S = input().strip()
print(d_we_love_abc(S))

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

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

dp[n] = [0, 0, 0, 1]
for i in range(n-1, -1, -1):
    if S[i] == '?':
        dp[i][3] =  dp[i+1][3] * 3 % mod
        dp[i][2] = (dp[i+1][2] * 3 + dp[i+1][3]) % mod
        dp[i][1] = (dp[i+1][1] * 3 + dp[i+1][2]) % mod
        dp[i][0] = (dp[i+1][0] * 3 + dp[i+1][1]) % mod
    elif S[i] == 'C':
        dp[i][3] =  dp[i+1][3] % mod
        dp[i][2] = (dp[i+1][2] + dp[i+1][3]) % mod
        dp[i][1] =  dp[i+1][1] % mod
        dp[i][0] =  dp[i+1][0] % mod
    elif S[i] == 'B':
        dp[i][3] =  dp[i+1][3] % mod
        dp[i][2] =  dp[i+1][2] % mod
        dp[i][1] = (dp[i+1][1] + dp[i+1][2]) % mod
        dp[i][0] =  dp[i+1][0] % mod
    elif S[i] == 'A':
        dp[i][3] =  dp[i+1][3]
        dp[i][2] =  dp[i+1][2]
        dp[i][1] =  dp[i+1][1]
        dp[i][0] = (dp[i+1][0] + dp[i+1][1]) % mod
print(dp[0][0])

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(S):
    dp = [0] * 4
    MOD = 10**9 + 7
    dp[0] = 1
    for c in S:
        if c == '?':
            for i in range(3, 0, -1):
                dp[i] = dp[i]*3 + dp[i-1]
                dp[i] %= MOD
            dp[0] = dp[0]*3
            dp[0] %= MOD
        elif c == 'A':
            dp[1] += dp[0] % MOD
        elif c == 'B':
            dp[2] += dp[1] % MOD
        elif c == 'C':
            dp[3] += dp[2] % MOD
    return dp[3] % MOD


def main():
    S = read_str().strip()
    print(slv(S))


if __name__ == '__main__':
    main()

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(S):
    dp = [0] * 4
    MOD = 10**9 + 7
    dp[0] = 1
    for c in S:
        if c == '?':
            for i in range(3, 0, -1):
                dp[i] = dp[i]*3 + dp[i-1]
                dp[i] %= MOD
            dp[0] = dp[0]*3
            dp[0] %= MOD
        elif c == 'A':
            dp[1] += dp[0] % MOD
        elif c == 'B':
            dp[2] += dp[1] % MOD
        elif c == 'C':
            dp[3] += dp[2] % MOD
    return dp[3] % MOD


def main():
    S = read_str().strip()
    print(slv(S))


if __name__ == '__main__':
    main()

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

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

dp = [[0]*4 for _ in range(len(s)+1)]
dp[0][0] = 1
for i, ss in enumerate(s):
    if ss == 'A':
        dp[i+1][0] = dp[i][0]
        dp[i+1][1] = (dp[i][1] + dp[i][0])%MOD
        dp[i+1][2] = dp[i][2]
        dp[i+1][3] = dp[i][3]
    elif ss == '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])%MOD
        dp[i+1][3] = dp[i][3]
    elif ss == '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])%MOD
    else:
        dp[i+1][0] = dp[i][0]*3%MOD
        dp[i+1][1] = (dp[i][1]*3%MOD + dp[i][0])%MOD
        dp[i+1][2] = (dp[i][2]*3%MOD + dp[i][1])%MOD
        dp[i+1][3] = (dp[i][3]*3%MOD + dp[i][2])%MOD


print(dp[-1][3])

Solution (Python):
s = input()
count = 0
a = 0
q = s.count('?')
c = 3 * s.count('C') + q
p = pow(3, q-3)
for i in range(len(s)):
    if s[i] == 'A':
        a += 3
    elif s[i] == 'C':
        c -= 3
    elif s[i] == 'B':
        count += 3*a*c
    else:
        c -= 1
        count += a*c
        a += 1
print(int(count*p) % 1000000007)

Solution (Python):
s = input()
count = 0
a, c, q = 0, 0, 0
n = len(s)
for i in range(n):
    if s[i] == 'C':
        c += 1
    elif s[i] == '?':
        q += 1
    else:
        continue
c = 3 * c + q
p = pow(3, q-3)
for i in range(n):
    if s[i] == 'A':
        a += 3
    elif s[i] == 'C':
        c -= 3
    elif s[i] == 'B':
        count += 3*a*c
    else:
        c -= 1
        count += a*c
        a += 1
print(int(count*p) % 1000000007)

Solution (Python):
s = input()
count = 0
a, c, q = 0, 0, 0
n = len(s)
for i in range(n):
    if s[i] == 'C':
        c += 1
    elif s[i] == '?':
        q += 1
    else:
        continue
c = 3 * c + q
p = pow(3, q-3)
for i in range(n):
    if s[i] == 'A':
        a += 3
    elif s[i] == 'C':
        c -= 3
    elif s[i] == 'B':
        count += 3*a*c
    else:
        c -= 1
        count += a*c
        a += 1
print(int(count*p) % 1000000007)

Solution (Python):
s = input()
count = 0
a, c, q = 0, 0, 0
for i in range(len(s)):
    if s[i] == 'C':
        c += 1
    elif s[i] == '?':
        q += 1
    else:
        continue
c = 3 * c + q
p = pow(3, q-3)
for i in range(len(s)):
    if s[i] == 'A':
        a += 3
    elif s[i] == 'C':
        c -= 3
    elif s[i] == 'B':
        count += 3*a*c
    else:
        c -= 1
        count += a*c
        a += 1
print(int(count*p) % 1000000007)

Solution (Python):
S = input()

MOD = 10**9 + 7
dp = [[0] * 4 for _ in range(len(S) + 1)]
dp[len(S)][3] = 1
for i in range(len(S))[::-1]:
    dp[i][3] = 3 * dp[i + 1][3] if S[i] == "?" else dp[i + 1][3]
    dp[i][3] %= MOD
    if S[i] == "?":
        dp[i][0] = (3 * dp[i + 1][0] + dp[i + 1][1]) % MOD
        dp[i][1] = (3 * dp[i + 1][1] + dp[i + 1][2]) % MOD
        dp[i][2] = (3 * dp[i + 1][2] + dp[i + 1][3]) % MOD
    else:
        dp[i][0] = (dp[i + 1][0] + int(S[i] == "A") * dp[i + 1][1]) % MOD
        dp[i][1] = (dp[i + 1][1] + int(S[i] == "B") * dp[i + 1][2]) % MOD
        dp[i][2] = (dp[i + 1][2] + int(S[i] == "C") * dp[i + 1][3]) % MOD
print(dp[0][0])

Solution (Python):
s = input()

dp1 = {'A': 0, 'AB': 0, 'ABC': 0}
dp2 = {'A': 0, 'AB': 0, 'ABC': 0}

c = 1000000000 + 7
n = len(s)
tmp = [1]*n
for i in range(1, n):
    tmp[i] = (tmp[i-1] * 3)%c

count = 0
for i in range(n):
    if s[i] == '?':
        dp2['A'] = dp1['A']*3 + tmp[count]
        dp2['AB'] = dp1['AB']*3 + dp1['A']
        dp2['ABC'] = dp1['ABC']*3 + dp1['AB']
        count += 1
    elif s[i] == 'A':
        dp2['A'] = dp1['A'] + tmp[count]
        dp2['AB'] = dp1['AB']
        dp2['ABC'] = dp1['ABC']
    elif s[i] == 'B':
        dp2['A'] = dp1['A']
        dp2['AB'] = dp1['AB'] + dp1['A']
        dp2['ABC'] = dp1['ABC']
    elif s[i] == 'C':
        dp2['A'] = dp1['A']
        dp2['AB'] = dp1['AB']
        dp2['ABC'] = dp1['ABC'] + dp1['AB']

    dp1['ABC'] = dp2['ABC'] % c
    dp1['AB'] = dp2['AB'] % c
    dp1['A'] = dp2['A'] % c

    

print(dp1['ABC'])

Solution (Python):
s = input()

dp1 = {'A': 0, 'AB': 0, 'ABC': 0}
dp2 = {'A': 0, 'AB': 0, 'ABC': 0}

c = 1000000000 + 7
n = len(s)
tmp = [1]*n
for i in range(1, n):
    tmp[i] = (tmp[i-1] * 3)%c


count = 0
for i in range(n):
    

    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    

    if s[i] == '?':
        dp2['A'] = dp1['A']*3 + tmp[count]
        dp2['AB'] = dp1['AB']*3 + dp1['A']
        dp2['ABC'] = dp1['ABC']*3 + dp1['AB']
        count += 1
    elif s[i] == 'A':
        dp2['A'] = dp1['A'] + tmp[count]
        dp2['AB'] = dp1['AB']
        dp2['ABC'] = dp1['ABC']
    elif s[i] == 'B':
        dp2['A'] = dp1['A']
        dp2['AB'] = dp1['AB'] + dp1['A']
        dp2['ABC'] = dp1['ABC']
    elif s[i] == 'C':
        dp2['A'] = dp1['A']
        dp2['AB'] = dp1['AB']
        dp2['ABC'] = dp1['ABC'] + dp1['AB']

    
    
    

    dp1['ABC'] = dp2['ABC'] % c
    dp1['AB'] = dp2['AB'] % c
    dp1['A'] = dp2['A'] % c

    

print(dp1['ABC'])

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

A1, A2, C1, C2 = [1]*N, [1]*N, [1]*N, [1]*N
a, aa = 0, 0
c, cc = 0, 0
for i in range(1,N):
    if S[i-1] == "A":
        a += 1
    elif S[i-1] == "?":
        aa += 1
    A1[i] = a
    A2[i] = aa

for i in range(1,N):
    if S[N-1-i+1] == "C":
        c += 1
    elif S[N-1-i+1] == "?":
        cc +=1
    C1[N-1-i] = c
    C2[N-1-i] = cc

answer = 0
for i in range(1,N-1):
    if S[i] in ("B", "?"):
        ta = 0
        tc = 0
        if A2[i] == 0:
            ta = A1[i]
        else:
            ta = pow(3, A2[i], mod)*A1[i] +  pow(3,A2[i]-1,mod)*A2[i]
        if C2[i]==0:
            tc = C1[i]
        else:
            tc = pow(3,C2[i],mod)*C1[i] + pow(3,C2[i]-1,mod)*C2[i]
        answer += ta*tc
        answer %= mod


print(answer)

Solution (Python):
s = input()
count = 0
a, qa, c, qc = 0, 0, 0, 0
def calc(x, qx, y, qy):
    return ((3*x+qx) * (3*y+qy) * pow3q)

for i in range(len(s)):
    if s[i] == 'C':
        c += 1
    elif s[i] == '?':
        qc += 1
    else:
        continue
pow3q = pow(3, qc-3)
for i in range(len(s)):
    if s[i] == 'A':
        a += 1
    elif s[i] == 'C':
        c -= 1
    elif s[i] == 'B':
        count += 3*calc(a, qa, c, qc)
    else:
        qc -= 1
        count += calc(a, qa, c, qc)
        qa += 1
print(int(count) % 1000000007)

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

N = len(S)
A1,A2,C1,C2 = [1]*N,[1]*N,[1]*N,[1]*N
a,aa = 0,0
c,cc = 0,0
for i in range(1,N):
    if S[i-1]=="A":
        a += 1
    elif S[i-1]=="?":
        aa += 1
    A1[i],A2[i] = a,aa
for i in range(1,N):
    if S[N-1-i+1]=="C":
        c += 1
    elif S[N-1-i+1]=="?":
        cc += 1
    C1[N-1-i] = c
    C2[N-1-i] = cc

Ans = 0
for i in range(1,N-1):
    if S[i] in ("B","?"):
        ta,tc = 0,0
        if A2[i]==0:
            ta = A1[i]
        else:
            ta = pow(3,A2[i],mod)*A1[i] + pow(3,A2[i]-1,mod)*A2[i]
        if C2[i]==0:
            tc = C1[i]
        else:
            tc = pow(3,C2[i],mod)*C1[i] + pow(3,C2[i]-1,mod)*C2[i]
        Ans += ta*tc
        Ans %= mod

print(Ans)

Solution (Python):
S = input()

mod = 1000000007

dp = [[0, 0, 0] for _ in range(len(S))]

mul = 1

if S[0] == "A":
    dp[0][0] = 1
elif S[0] == "?":
    dp[0][0] = 1
    mul *= 3

for i in range(1, len(S)):
    if S[i] == "A":
        dp[i][0] = dp[i - 1][0] + mul
        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][0] + dp[i - 1][1]
        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][1] + dp[i - 1][2]
    elif S[i] == "?":
        dp[i][0] = ((dp[i - 1][0] * 3) % mod + mul) % mod
        dp[i][1] = ((dp[i - 1][1] * 3) % mod + dp[i - 1][0]) % mod
        dp[i][2] = ((dp[i - 1][2] * 3) % mod + dp[i - 1][1]) % mod
        mul = (mul * 3) % mod

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

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

s = input()
n = len(s)

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

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

for i in range(n, 0, -1):
  sr[i-1] = sr[i][:]
  if s[i-1] == 'A': sr[i-1][0] += 1
  elif s[i-1] == 'B': sr[i-1][1] += 1
  elif s[i-1] == 'C': sr[i-1][2] += 1
  else: sr[i-1][3] += 1

ans = 0
for i in range(n):
  if s[i] == 'B' or s[i] == '?':
    a = c = 0
    a += sl[i][0] * pow(3, sl[i][3], MOD)
    if sl[i][3] > 0: a += sl[i][3] * pow(3, sl[i][3]-1, MOD)
    c += sr[i+1][2] * pow(3, sr[i+1][3], MOD)
    if sr[i+1][3] > 0: c += sr[i+1][3] * pow(3, sr[i+1][3]-1, MOD)
    ans = (ans + a*c) % MOD

print(ans)

Solution (Python):
S=input()
N=len(S)
mod=pow(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" 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]
    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]
    for j in range(4):
        dp[i+1][j]=(dp[i+1][j])%mod
print(dp[N][3])

Solution (Python):
mod = 1000000007

S = input()
L = len(S)
i = L-1
A = [0 for _ in range(L+1)]
C = [0 for _ in range(L+1)]
Q = [0 for _ in range(L+1)]
while i >= 0:
    Q[i] = Q[i+1]
    A[i] = A[i+1]
    C[i] = C[i+1]

    if S[i] == '?':
        Q[i] = Q[i+1] + 1
    else:
        Q[i] = Q[i+1]

    if S[i] == 'A':
        A[i] = A[i+1] + 1
    else:
        A[i] = A[i+1]
    if S[i] == 'C':
        C[i] = C[i+1] + 1
    else:
        C[i] = C[i+1]
    i -= 1

ans = 0
for i in range(L):
    if S[i] in ('B','?'):
        a = A[0] - A[i]
        qleft = Q[0] - Q[i]
        c = C[i+1]
        qright = Q[i+1]
        if qleft > 0:
            LEFT = a*pow(3,qleft,mod) + qleft*pow(3,qleft-1,mod)
        else: 
            LEFT = a*pow(3,qleft,mod)
        if qright > 0:
            RIGHT = c*pow(3,qright,mod) + qright*pow(3,qright-1,mod)
        else:
            RIGHT = c*pow(3,qright,mod)
        number = (LEFT * RIGHT)%mod
        ans = (ans + number)%mod
print(ans)

Solution (Python):
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect
 
def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

P = 10**9 + 7

S = input()
N = len(S)

psumA = [0] + list(accumulate(c == 'A' for c in S))
psumC = [0] + list(accumulate(c == 'C' for c in S))
psumX = [0] + list(accumulate(c == '?' for c in S))
Q = psumX[N]

ans = 0
for i in range(1, N-1):
  if S[i] == 'B':
    ans += psumA[i] * (psumC[N] - psumC[i+1]) % P * pow(3, Q, P) % P
    if Q >= 1:
      ans += psumX[i] * (psumC[N] - psumC[i+1]) % P * pow(3, Q-1, P) % P
      ans += psumA[i] * (psumX[N] - psumX[i+1]) % P * pow(3, Q-1, P) % P
    if Q >= 2:
      ans += psumX[i] * (psumX[N] - psumX[i+1]) % P * pow(3, Q-2, P) % P
  if S[i] == '?':
    ans += psumA[i] * (psumC[N] - psumC[i+1]) % P * pow(3, Q-1, P) % P
    if Q >= 2:
      ans += psumX[i] * (psumC[N] - psumC[i+1]) % P * pow(3, Q-2, P) % P
      ans += psumA[i] * (psumX[N] - psumX[i+1]) % P * pow(3, Q-2, P) % P
    if Q >= 3:
      ans += psumX[i] * (psumX[N] - psumX[i+1]) % P * pow(3, Q-3, P) % P

print(ans % P)

Solution (Python):
S = input()
def ABC(S):
    N = len(S)
    dp = [[0 for j in range(4)] for i in range(N+1)]
    model = 'ABC'
    p = 10**9 + 7
    for i in range(N, -1, -1):
        for j in range(3,-1,-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:
                if S[i] == '?':
                    dp[i][j] = 3 * dp[i+1][j] % p
                else:
                    dp[i][j] = dp[i+1][j] % p
            else:
                if S[i] == '?':
                    m1 = 3
                else:
                    m1 = 1
                if S[i] == '?' or S[i] == model[j]:
                    m2 = 1
                else:
                    m2 = 0
                dp[i][j] = (m1 * dp[i+1][j])%p + m2 * (dp[i+1][j+1])%p
    return dp[0][0] % p
print(ABC(S))

Solution (Python):
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect
 
def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

P = 10**9 + 7

S = input()
N = len(S)

psumA = [0] + list(accumulate(c == 'A' for c in S))
psumC = [0] + list(accumulate(c == 'C' for c in S))
psumX = [0] + list(accumulate(c == '?' for c in S))
Q = psumX[N]

ans = 0
for i in range(1, N-1):
  if S[i] == 'B':
    ans += psumA[i] * (psumC[N] - psumC[i+1]) % P * pow(3, Q, P) % P
    if Q >= 1:
      ans += psumX[i] * (psumC[N] - psumC[i+1]) % P * pow(3, Q-1, P) % P
      ans += psumA[i] * (psumX[N] - psumX[i+1]) % P * pow(3, Q-1, P) % P
    if Q >= 2:
      ans += psumX[i] * (psumX[N] - psumX[i+1]) % P * pow(3, Q-2, P) % P
  if S[i] == '?':
    ans += psumA[i] * (psumC[N] - psumC[i+1]) % P * pow(3, Q-1, P) % P
    if Q >= 2:
      ans += psumX[i] * (psumC[N] - psumC[i+1]) % P * pow(3, Q-2, P) % P
      ans += psumA[i] * (psumX[N] - psumX[i+1]) % P * pow(3, Q-2, P) % P
    if Q >= 3:
      ans += psumX[i] * (psumX[N] - psumX[i+1]) % P * pow(3, Q-3, P) % P

print(ans % P)

Solution (Python):
S = input()
P = 10**9+7
d = [[0 for j in range(4)] for i in range(len(S)+1)]

d[len(S)][3] = 1

for i in range(len(S)-1,-1,-1):
	d[i][3] = ((3 if S[i] == "?" else 1) * d[i+1][3])%P
	d[i][2] = ((3 if S[i] == "?" else 1) * d[i+1][2])%P
	d[i][2] += (1 if S[i] == "C" or S[i] == "?" else 0) * d[i+1][3]
	d[i][1] = ((3 if S[i] == "?" else 1) * d[i+1][1])%P
	d[i][1] += (1 if S[i] == "B" or S[i] == "?" else 0) * d[i+1][2]
	d[i][0] = ((3 if S[i] == "?" else 1) * d[i+1][0])%P
	d[i][0] += (1 if S[i] == "A" or S[i] == "?" else 0) * d[i+1][1]
print(d[0][0] % P)

Solution (Python):

a = 0
_ = 0
ab = 0
a_ = 0
_b = 0
__ = 0
abc = 0
ab_ = 0
a_c = 0
_bc = 0
a__ = 0
_b_ = 0
__c = 0
___ = 0

T = input()

for c in T:
    if c == "A":
        a += 1
    if c == "B":
        ab += a
        _b += _
    if c == "C":
        abc += ab
        a_c += a_
        _bc += _b
        __c += __
    if c == "?":
        ___ += __
        __ += _
        _ += 1
        a__ += a_
        a_ += a
        _b_ += _b
        ab_ += ab

print(sum([
    abc * 3**(max(_ - 0, 0)),
    ab_ * 3**(max(_ - 1, 0)),
    a_c * 3**(max(_ - 1, 0)),
    _bc * 3**(max(_ - 1, 0)),
    a__ * 3**(max(_ - 2, 0)),
    _b_ * 3**(max(_ - 2, 0)),
    __c * 3**(max(_ - 2, 0)),
    ___ * 3**(max(_ - 3, 0)),
]) % (10**9 + 7))