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):
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])

Solution (Python):
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)

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 10**9 + 7
    SI = lambda : sys.stdin.readline().rstrip()
    S = SI()

    dp = [[0] * 4 for _ in range(len(S)+1)]
    dp[0] = [1,0,0,0]
    ans = 0
    for i in range(len(S)):
        rg = [0,1,2] if S[i] == '?' else [ord(S[i])-ord('A')]
        for a in rg:
            for b in range(4):
                if a == b:
                    c = b + 1
                    dp[i + 1][c] = (dp[i + 1][c] + dp[i][b]) % MOD
                dp[i + 1][b] = (dp[i + 1][b] + dp[i][b]) % MOD

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

if __name__ == '__main__':
    main()

Solution (Python):
MOD = 1000000007

S = input()
N = len(S)

dp = [[0, 0, 0, 0] for _ in range(N + 1)]
dp[0][0] = 1

for i in range(N):
    if S[i] == '?':
        for j in range(4):
            dp[i + 1][j] += dp[i][j] * 3
            dp[i + 1][j] %= MOD
    else:
        for j in range(4):
            dp[i + 1][j] += dp[i][j]
            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[N][3])

Solution (Python):




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

Solution (Python):

import sys

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


MOD = 10 ** 9 + 7
S = sr()
dp = [0, 0, 0]
total = 1
for s in S:
    if s == 'A':
        dp[0] += total
    elif s == 'B':
        dp[1] += dp[0]
    elif s == 'C':
        dp[2] += dp[1]
    elif s == '?':
        dp[2] = dp[2]*3 + dp[1]
        dp[1] = dp[1]*3 + dp[0]
        dp[0] = dp[0]*3 + total
        total *= 3
    total %= MOD; dp[0] %= MOD; dp[1] %= MOD; dp[2] %= MOD
    

answer = dp[2] % MOD
print(answer)

Solution (Python):
S = input()

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])

Solution (Python):
S = input()

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])

Solution (Python):
S = input()

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] == '?':
        dp[i+1][1] += dp[i][0] 
        dp[i+1][1] %= mod
        dp[i+1][2] += dp[i][1] 
        dp[i+1][2] %= mod
        dp[i+1][3] += dp[i][2] 
        dp[i+1][3] %= mod
    if S[i] == 'A':
        dp[i+1][1] += dp[i][0] 
        dp[i+1][1] %= mod
    if S[i] == 'B':
        dp[i+1][2] += dp[i][1]
        dp[i+1][2] %= mod
    if S[i] == 'C':
        dp[i+1][3] += dp[i][2]
        dp[i+1][3] %= mod
    for f in range(4):
        if S[i] != '?':
            dp[i+1][f] += dp[i][f]
        else:
            dp[i+1][f] += dp[i][f] * 3
        dp[i+1][f] %= mod
print(dp[len(S)][3]%mod)

Solution (Python):
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])


if __name__ == '__main__':
    main()

Solution (Python):
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)

Solution (Python):


import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))

M = 10**9+7
s = input()
n = len(s)
anum = [None] * n 
cnum = [None] * n 
hnum1 = [None] * n
hnum2 = [None] * n
acount = 0
ccount = 0
hcount1 = 0
hcount2 = 0
for i,(c,cc) in enumerate(zip(s, s[::-1])):
    if c in "A":
        acount += 1
    if c=="?":
        hcount1 += 1
    anum[i] = acount
    hnum1[i] = hcount1
    if cc in "C":
        ccount += 1
    if cc=="?":
        hcount2 += 1
    cnum[-(i+1)] = ccount
    hnum2[-(i+1)] = hcount2
ans = 0
hn = hnum1[-1]
for i,c in enumerate(s):
    if i in (0, n-1):
        continue
    if c=="B":
        ans += (anum[i-1]*cnum[i+1]*pow(3, hn, M))
        if hn>=1:
            ans += (anum[i-1]*hnum2[i+1]*pow(3, hn-1, M))
            ans += (hnum1[i-1]*cnum[i+1]*pow(3, hn-1, M))
        if hn>=2:
            ans += (hnum1[i-1]*hnum2[i+1]*pow(3, hn-2, M))
    if c=="?":
        ans += (anum[i-1]*cnum[i+1]*pow(3, hn-1, M))
        if hn>=2:
            ans += (anum[i-1]*(hnum2[i+1])*pow(3, hn-2, M))
            ans += (hnum1[i-1]*cnum[i+1]*pow(3, hn-2, M))
        if hn>=3:
            ans += (hnum1[i-1]*hnum2[i+1]*pow(3, hn-3, M))
    ans %= M

print(ans)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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) 

if __name__ == '__main__':
    main()

Solution (Python):
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)


if __name__ == '__main__':
    main()

Solution (Python):
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])


if __name__ == '__main__':
    main()

Solution (Python):
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)


if __name__ == '__main__':
    main()

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

    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]

            dp[i][0] += pre[0] + tmp
            dp[i][1] += pre[1]
            dp[i][2] += pre[2]

            dp[i][0] += pre[0]
            dp[i][1] += pre[0] + pre[1]
            dp[i][2] += pre[2]

            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[len(s)][2] % MOD)

if __name__ == "__main__":
    main()

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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))

Solution (Python):
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))

Solution (Python):
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)

Solution (Python):
s = input()
n = len(s)
mod = 10**9+7
qcnt = [[0,0]for i in range(n)]
Acnt = [0]*n
Ccnt = [0]*n
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)

Solution (Python):
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):
        
        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

        
        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])
if __name__=="__main__":
    main()

Solution (Python):
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):
        
        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

        
        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])
if __name__=="__main__":
    main()

Solution (Python):
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])

Solution (Python):
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)

Solution (Python):

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])

if __name__ == '__main__':
    main()

Solution (Python):
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])

Solution (Python):
from bisect import *
S = input()
mod = 10**9 + 7
A = []
B = []
C = []
X = []
q = 0
for i,s in enumerate(S):
    if s == 'A':
        A.append(i)
    elif s == 'B':
        B.append((i,0))
    elif s == 'C':
        C.append(i)
    else:
        X.append(i)
        B.append((i,1))
        q += 1

pow3 = [pow(3,q,mod),pow(3,max(0,q-1),mod),pow(3,max(0,q-2),mod),pow(3,max(0,q-3),mod)]
ans = 0
for b,flag in B:
    Al = bisect_left(A,b)
    Cr = (len(C) - bisect_right(C,b))
    Xl = bisect_left(X,b)
    Xr = (len(X) - bisect_right(X,b))
    ans += (Al*Cr%mod)*pow3[flag]%mod
    ans %= mod
    ans += (Al*Xr%mod + Xl*Cr%mod)*pow3[flag+1]%mod
    ans %= mod
    ans += (Xl*Xr%mod)*pow3[flag+2]%mod
print(ans)

Solution (Python):
S=input()
A=0 
B=0 
C=0 
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)

Solution (Python):
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', '?']:
        
        ans += n_a[i] * n_c[n -  1 - i] * pow3[n_l[i]] * pow3[n_r[n - 1 - i]] % mod
        ans %= mod
        
        ans += n_l[i] * n_c[n -  1 - i] * pow3[n_l[i] - 1] * pow3[n_r[n - 1 - i]] % mod
        ans %= mod
        
        ans += n_a[i] * n_r[n -  1 - i] * pow3[n_l[i]] * pow3[n_r[n - 1 - i] - 1] % mod
        ans %= mod
        
        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)

Solution (Python):
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product

def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

s=input()
dp=[[0]*(len(s)+1) for i in range(4)]
dp[0][0]=1
lst="ABC"
for i in range(len(s)):
    for j in range(3):
        m1=1
        m2=0
        if s[i]=="?":
            m1=3
            m2=1
        
        if lst[j]==s[i]:
            m2=1
        
        dp[j][i+1]+=m1*dp[j][i]
        dp[j+1][i+1]+=m2*dp[j][i]
        dp[j][i+1]%=mod
        
    if s[i]=="?":
        dp[3][i+1]+=3*dp[3][i]
    else:
        dp[3][i+1]+=dp[3][i]
    dp[3][i+1]%=mod

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

Solution (Python):
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product

def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

s=input()
ab=[0,0]
ans=0
cnt=0
for i in range(len(s)):
    if s[i]=="A":
        ab[0]+=pow(3,cnt,mod)
    elif s[i]=="B":
        ab[1]+=ab[0]
    elif s[i]=="C":
        ans+=ab[1]
    else:
        ans=ab[1]+3*ans
        ab[1]=ab[0]+3*ab[1]
        ab[0]=pow(3,cnt,mod)+3*ab[0]
        cnt+=1
    ab[0]%=mod
    ab[1]%=mod
    ans%=mod
print(ans%mod)

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

    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]
    if s[i] == "C" or s[i] == "?":
        dp[i+1][3] += dp[i][2]

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

Solution (Python):
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)