Buggy python submission (verdict: Time Limit Exceeded):
S = input()
n = len(S)
mod = (10**9 + 7)

A = [0] * n
C = [0] * n
Q = [0] * n
Bi = []
Qi = []

for i, s in enumerate(S):
    if s == 'A':
        A[i] = 1
    elif s == 'B':
        Bi.append(i)
    elif s == 'C':
        C[i] = 1
    else:
        Q[i] = 1
        Qi.append(i)

for i in range(1, n):
    A[i] += A[i - 1]
    C[i] += C[i - 1]
    Q[i] += Q[i - 1]

def mod_pow(x, n, mod):
    if n == 0: return 1
    d, m = n >> 1, n & 1
    p = mod_pow(x, d, mod)
    return (p * p * (x if m else 1)) % mod

from itertools import chain
ans = 0
for b in chain(Bi, Qi):
    if b == 0 or n - 1 <= b: continue
    ai = A[b - 1]
    qa = Q[b - 1]
    a = (ai * mod_pow(3, qa, mod))
    if qa > 0:
        a += (mod_pow(3, qa - 1, mod) * qa)

    lc = C[n - 1] - C[b]
    lqc = Q[n - 1] - Q[b]
    c = (lc * mod_pow(3, lqc, mod))
    if lqc > 0:
        c += (mod_pow(3, lqc - 1, mod) * lqc)
    
    ans = (ans + (a * c)) % mod

print(ans % mod)

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

Buggy python submission (verdict: Time Limit Exceeded):
S = input()
n = len(S)
mod = (10**9 + 7)

A = [0] * n
C = [0] * n
Q = [0] * n
Bi = []
Qi = []

for i, s in enumerate(S):
    if s == 'A':
        A[i] = 1
    elif s == 'B':
        Bi.append(i)
    elif s == 'C':
        C[i] = 1
    else:
        Q[i] = 1
        Qi.append(i)

for i in range(1, n):
    A[i] += A[i - 1]
    C[i] += C[i - 1]
    Q[i] += Q[i - 1]

def mod_pow(x, n, mod):
    if n == 0: return 1
    d, m = n >> 1, n & 1
    p = mod_pow(x, d, mod)
    return (p * p * (x if m else 1))

from itertools import chain
ans = 0
for b in chain(Bi, Qi):
    if b == 0 or n - 1 <= b: continue
    ai = A[b - 1]
    qa = Q[b - 1]
    a = (ai * mod_pow(3, qa, mod))
    if qa > 0:
        a += (mod_pow(3, qa - 1, mod) * qa)

    lc = C[n - 1] - C[b]
    lqc = Q[n - 1] - Q[b]
    c = (lc * mod_pow(3, lqc, mod))
    if lqc > 0:
        c += (mod_pow(3, lqc - 1, mod) * lqc)
    
    ans += (a * c) % mod

print(ans % mod)

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

Buggy python submission (verdict: Runtime Error):
init_input()

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

A = [0] * n
C = [0] * n
Q = [0] * n
Bi = []
Qi = []

for i, s in enumerate(S):
    if s == 'A':
        A[i] = 1
    elif s == 'B':
        Bi.append(i)
    elif s == 'C':
        C[i] = 1
    else:
        Q[i] = 1
        Qi.append(i)

for i in range(1, n):
    A[i] += A[i - 1]
    C[i] += C[i - 1]
    Q[i] += Q[i - 1]

def mod_pow(x, n, mod):
    if n == 0: return 1
    d, m = n >> 1, n & 1
    p = mod_pow(x, d, mod)
    return (p * p * (x if m else 1))

from itertools import chain
ans = 0
for b in chain(Bi, Qi):
    if b == 0 or n - 1 <= b: continue
    ai = A[b - 1]
    qa = Q[b - 1]
    a = (ai * mod_pow(3, qa, mod))
    if qa > 0:
        a += (mod_pow(3, qa - 1, mod) * qa)

    lc = C[n - 1] - C[b]
    lqc = Q[n - 1] - Q[b]
    c = (lc * mod_pow(3, lqc, mod))
    if lqc > 0:
        c += (mod_pow(3, lqc - 1, mod) * lqc)
    
    ans += (a * c) % mod

print(ans % mod)

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

Buggy python submission (verdict: Time Limit Exceeded):
S = input()
n = len(S)
mod = (10**9 + 7)

A = [0] * n
C = [0] * n
Q = [0] * n
Bi = []
Qi = []

for i, s in enumerate(S):
    if s == 'A':
        A[i] = 1
    elif s == 'B':
        Bi.append(i)
    elif s == 'C':
        C[i] = 1
    else:
        Q[i] = 1
        Qi.append(i)

for i in range(1, n):
    A[i] += A[i - 1]
    C[i] += C[i - 1]
    Q[i] += Q[i - 1]

def mod_pow(x, n, mod):
    if n == 0: return 1
    d, m = n >> 1, n & 1
    p = mod_pow(x, d, mod)
    return (p * p * (x if m else 1)) % mod

from itertools import chain
ans = 0
for b in chain(Bi, Qi):
    if b == 0 or n - 1 <= b: continue
    ai = A[b - 1]
    qa = Q[b - 1]
    a = (ai * mod_pow(3, qa, mod))
    if qa > 0:
        a += (mod_pow(3, qa - 1, mod) * qa)

    lc = C[n - 1] - C[b]
    lqc = Q[n - 1] - Q[b]
    c = (lc * mod_pow(3, lqc, mod))
    if lqc > 0:
        c += (mod_pow(3, lqc - 1, mod) * lqc)
    
    ans += (a * c) % mod

print(ans % mod)

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

Buggy python submission (verdict: Time Limit Exceeded):
S = input()
n = len(S)
mod = (10**9 + 7)

A = [0] * n
C = [0] * n
Q = [0] * n
Bi = []
Qi = []

for i, s in enumerate(S):
    if s == 'A':
        A[i] = 1
    elif s == 'B':
        Bi.append(i)
    elif s == 'C':
        C[i] = 1
    else:
        Q[i] = 1
        Qi.append(i)

for i in range(1, n):
    A[i] += A[i - 1]
    C[i] += C[i - 1]
    Q[i] += Q[i - 1]

def mod_pow(x, n, mod):
    if n == 0: return 1
    d, m = divmod(n, 2)
    p = mod_pow(x, d, mod)
    return (p * p * (x if m else 1)) % mod

from itertools import chain
ans = 0
for b in chain(Bi, Qi):
    if b == 0 or n - 1 <= b: continue
    ai = A[b - 1]
    qa = Q[b - 1]
    a = (ai * mod_pow(3, qa, mod)) % mod
    if qa > 0:
        a += (mod_pow(3, qa - 1, mod) * qa) % mod

    ci = C[b]
    qc = Q[b]
    lc = C[n - 1] - ci
    lqc = Q[n - 1] - qc
    c = (lc * mod_pow(3, lqc, mod)) % mod
    if lqc > 0:
        c += (mod_pow(3, lqc - 1, mod) * lqc) % mod
    
    ans += (a * c) % mod

print(ans % mod)

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

Buggy python submission (verdict: Time Limit Exceeded):

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

A = [0] * len(S)
C = [0] * len(S)
Q = [0] * len(S)
Bi = []
Qi = []

for i, s in enumerate(S):
    if s == 'A':
        A[i] = 1
    elif s == 'B':
        Bi.append(i)
    elif s == 'C':
        C[i] = 1
    else:
        Q[i] = 1
        Qi.append(i)

def acc(l):
    for i in range(1, len(l)):
        l[i] += l[i - 1]
acc(A)
acc(C)
acc(Q)

def pow(x, n, mod):
    if n == 0: return 1
    d, m = divmod(n, 2)
    p = pow(x, d, mod)
    return (p * p * (x if m else 1)) % mod

from itertools import chain
ans = 0
for b in chain(Bi, Qi):
    if b == 0 or n - 1 <= b: continue
    ai = A[b - 1]
    qa = Q[b - 1]
    a = (ai * (3 ** qa)) % mod
    if qa > 0:
        a += (pow(3, qa - 1, mod) * qa) % mod

    ci = C[b]
    qc = Q[b]
    lc = C[n - 1] - ci
    lqc = Q[n - 1] - qc
    c = (lc * (3 ** lqc)) % mod
    if lqc > 0:
        c += (pow(3, lqc - 1, mod) * lqc) % mod
    
    ans += (a * c) % mod

print(ans % mod)

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

Buggy python submission (verdict: Time Limit Exceeded):
S = input()
n = len(S)
mod = (10**9 + 7)

A = [0] * len(S)
C = [0] * len(S)
Q = [0] * len(S)
Bi = []
Qi = []

for i, s in enumerate(S):
    if s == 'A':
        A[i] = 1
    elif s == 'B':
        Bi.append(i)
    elif s == 'C':
        C[i] = 1
    else:
        Q[i] = 1
        Qi.append(i)

def acc(l):
    for i in range(1, len(l)):
        l[i] += l[i - 1]
acc(A)
acc(C)
acc(Q)

from itertools import chain
ans = 0
for b in chain(Bi, Qi):
    if b == 0 or n - 1 <= b: continue
    ai = A[b - 1]
    qa = Q[b - 1]
    a = (ai * (3 ** qa)) % mod
    if qa > 0:
        a += (3 ** (qa - 1) * qa) % mod

    ci = C[b]
    qc = Q[b]
    lc = C[n - 1] - ci
    lqc = Q[n - 1] - qc
    c = (lc * (3 ** lqc)) % mod
    if lqc > 0:
        c += (3 ** (lqc - 1) * lqc) % mod
    
    ans += (a * c) % mod

print(ans % mod)

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

Buggy python submission (verdict: Time Limit Exceeded):
S = input()
mod = (10**9 + 7)

A,B,C,Q = [], [], [], []
for i, s in enumerate(S):
    if s == 'A':
        A.append(i)
    elif s == 'B':
        B.append(i)
    elif s == 'C':
        C.append(i)
    else:
        Q.append(i)

import bisect
ans = 0
for b in B + Q:
    ai = bisect.bisect_left(A, b)
    qa = bisect.bisect_left(Q, b)
    a = (ai * (3 ** qa)) % mod
    if qa > 0:
        a += (3 ** (qa - 1) * qa) % mod

    ci = bisect.bisect_right(C, b)
    qc = bisect.bisect_right(Q, b)
    lc = len(C) - ci
    lqc = len(Q) - qc
    c = (lc * (3 ** lqc)) % mod
    if lqc > 0:
        c += (3 ** (lqc - 1) * lqc) % mod
    
    ans += (a * c) % mod

print(ans % mod)

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

Buggy python submission (verdict: Time Limit Exceeded):
S = input()
A,B,C,Q = [], [], [], []
for i, s in enumerate(S):
    if s == 'A':
        A.append(i)
    elif s == 'B':
        B.append(i)
    elif s == 'C':
        C.append(i)
    else:
        Q.append(i)

import bisect
ans = 0
for b in B + Q:
    ai = bisect.bisect_left(A, b)
    qa = bisect.bisect_left(Q, b)
    a = ai * (3 ** qa)
    if qa > 0:
        a += 3 ** (qa - 1) * qa

    ci = bisect.bisect_right(C, b)
    qc = bisect.bisect_right(Q, b)
    lc = len(C) - ci
    lqc = len(Q) - qc
    c = lc * (3 ** lqc)
    if lqc > 0:
        c += 3 ** (lqc - 1) * lqc
    
    ans += a * c

print(ans % (10**9 + 7))

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