Buggy python submission (verdict: Time Limit Exceeded):
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
    else:
      dp[j] = DP[j + 1] * (1 if S[i] == chr(65 + j) or S[i] == '?' else 0)
      dp[j] += DP[j] * (3 if S[i] == '?' else 1)
      dp[j] % p
  DP = [x for x in dp]
print(DP[0] % p)

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

Buggy python submission (verdict: Time Limit Exceeded):
S = input()
p = 10 ** 9 + 7
DP = [[0 for j in range(4)] for i in range(len(S) + 1)]
DP[len(S)][3] = 1
for i in range(len(S) - 1, -1, -1):
  for j in range(3, -1, -1):
    if j == 3:
      DP[i][j] = DP[i + 1][3] * (3 if S[i] == '?' else 1) % p
    else:
      DP[i][j] += DP[i + 1][j + 1] * (1 if S[i] == chr(65 + j) or S[i] == '?' else 0)
      DP[i][j] += DP[i + 1][j] * (3 if S[i] == '?' else 1)
      DP[i][j] % p
print(DP[0][0] % p)

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

Buggy python submission (verdict: Time Limit Exceeded):
S = input()
p = 10 ** 9 + 7
DP = [0, 0, 0, 1]
for i in range(len(S) - 1, -1, -1):
  dp = [0] * 4
  for j in range(3, -1, -1):
    if j == 3:
      dp[j] = DP[3] * (3 if S[i] == '?' else 1)
    else:
      dp[j] += DP[j + 1] * (1 if S[i] == chr(65 + j) or S[i] == '?' else 0)
      dp[j] += DP[j] * (3 if S[i] == '?' else 1)
      dp[j] % p
  DP = [x for x in dp]
print(DP[0] % p)

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

Buggy python submission (verdict: Time Limit Exceeded):
S = input()
p = 10 ** 9 + 7
C = [1 for i in range(S.count('?') + 1)]
for i in range(1, len(C)):
  C[i] = C[i - 1] * i % p
Ci = [c for c in C]
Ci[-1] = pow(C[-1], p - 2, p)
for i in range(1, len(C) - 1):
  Ci[len(C) - i - 1] = Ci[len(C) - i] * (len(C) - i) % p
def comb(*A):
  c = C[sum(A)]
  for a in A:
    c *= Ci[a]
  return c % p
posB = []
posQ = []
for i, s in enumerate(S):
  if s == 'B':
    posB.append(i)
  elif s == '?':
    posQ.append(i)
cnt = 0
for b in sorted(posB + posQ):
  cntA = S[:b].count('A')
  cntAQ = S[:b].count('?')
  cntC = S[b + 1:].count('C')
  cntCQ = S[b + 1:].count('?')
  a = 0
  for ai in range(cntAQ + 1):
    a += (cntA + ai) * comb(ai, cntAQ - ai) * (2 ** (cntAQ - ai)) % p
  c = 0
  for ci in range(cntCQ + 1):
    c += (cntC + ci) * comb(ci, cntCQ - ci) * (2 ** (cntCQ - ci)) % p
  cnt += (a * c) % p
print(cnt % p)

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

Buggy python submission (verdict: Time Limit Exceeded):
S = input()
p = 10 ** 9 + 7
DP = [[0 for j in range(4)] for i in range(len(S) + 1)]
DP[len(S)][3] = 1
for i in range(len(S) - 1, -1, -1):
  for j in range(3, -1, -1):
    if j == 3:
      DP[i][j] = DP[i + 1][3] * (3 if S[i] == '?' else 1)
    else:
      DP[i][j] += DP[i + 1][j + 1] * (1 if S[i] == chr(65 + j) or S[i] == '?' else 0)
      DP[i][j] += DP[i + 1][j] * (3 if S[i] == '?' else 1)
      DP[i][j] % p
print(DP[0][0] % p)

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

Buggy python submission (verdict: Time Limit Exceeded):
S = input()
p = 10 ** 9 + 7
DP = [[0 for j in range(4)] for i in range(len(S) + 1)]
DP[len(S)][3] = 1
for i in range(len(S) - 1, -1, -1):
  for j in range(3, -1, -1):
    if j == 3:
      DP[i][j] = DP[i + 1][3] * (3 if S[i] == '?' else 1)
    else:
      DP[i][j] += DP[i + 1][j + 1] * (1 if S[i] == chr(65 + j) or S[i] == '?' else 0)
      DP[i][j] += DP[i + 1][j] * (3 if S[i] == '?' else 1)
print(DP[0][0] % p)

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