Problem: 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.

Submission attempts (in order):
s = input()
n = len(s)
p = 10 ** 9 + 7






dp = [[0 for j in range(4)] for i in range(n + 1)]
dp[0][0] = 1 
for j in range(1, 4):
    dp[0][j] = 0  

for i in range(1, n + 1):
    m = 3 if s[i - 1] == '?' else 1

    for j in range(4):
        dp[i][j] = dp[i - 1][j] * m

    if s[i - 1] == 'A' or s[i - 1] == '?':
        dp[i][A] =  (dp[i][A] + dp[i - 1][0]) % p
    if s[i - 1] == 'B' or s[i - 1] == '?':
        dp[i][AB] = (dp[i][AB] + dp[i - 1][A]) % p
    if s[i - 1] == 'C' or s[i - 1] == '?':
        dp[i][ABC] = (dp[i][ABC] + dp[i - 1][AB]) % p

print(dp[n][ABC])

import sys
input = sys.stdin.readline

s = input()
n = len(s)
p = 10 ** 9 + 7

q = s.count('?')
l_a = [0] * n  
l_x = [0] * n  
r_c = [0] * n  
r_x = [0] * n  

for i in range(1, n):  
    l_a[i] = l_a[i - 1] + int(s[i - 1] == 'A')
    l_x[i] = l_x[i - 1] + int(s[i - 1] == '?')
    r_c[n - i - 1] = r_c[n - i] + int(s[n - i] == 'C')
    r_x[n - i - 1] = r_x[n - i] + int(s[n - i] == '?')

ans = 0
pow_q3 = max(1, 3 ** (q - 3) % p)
pow_q2 = max(1, pow_q3 * 3 % p)
pow_q1 = max(1, pow_q2 * 3 % p)
pow_q = max(1, pow_q1 * 3 % p)

for i in range(n):
    if s[i] == 'B':
        ans += (l_a[i] * r_c[i] % p) * pow_q % p  # ABC
        ans += (l_x[i] * r_c[i] % p) * pow_q1 % p # ?BC
        ans += (l_a[i] * r_x[i] % p) * pow_q1 % p # AB?
        ans += (l_x[i] * r_x[i] % p) * pow_q2 % p # ?B?
        ans %= p
    elif s[i] == '?':
        ans += (l_a[i] * r_c[i] % p) * pow_q1 % p # A?C
        ans += (l_x[i] * r_c[i] % p) * pow_q2 % p # ??C
        ans += (l_a[i] * r_x[i] % p) * pow_q2 % p # A??
        ans += (l_x[i] * r_x[i] % p) * pow_q3 % p # ???
        ans %= p

print(ans)


s = input()
n = len(s)
p = 10 ** 9 + 7






dp = [[0 for j in range(4)] for i in range(n + 1)]
dp[0][0] = 1 
for j in range(1, 4):
    dp[0][j] = 0  

print("dp[0] = {}".format(dp[0]))
for i in range(1, n + 1):
    m = 3 if s[i - 1] == '?' else 1

    for j in range(4):
        dp[i][j] = dp[i - 1][j] * m

    if s[i - 1] == 'A' or s[i - 1] == '?':
        dp[i][A] =  (dp[i][A] + dp[i - 1][0]) % p
    if s[i - 1] == 'B' or s[i - 1] == '?':
        dp[i][AB] = (dp[i][AB] + dp[i - 1][A]) % p
    if s[i - 1] == 'C' or s[i - 1] == '?':
        dp[i][ABC] = (dp[i][ABC] + dp[i - 1][AB]) % p

print(dp[n][ABC])

s = input()
n = len(s)
p = 10 ** 9 + 7






dp = [[0 for j in range(4)] for i in range(n + 1)]
dp[0][0] = 1 
for j in range(1, 4):
    dp[0][j] = 0  

for i in range(1, n + 1):
    m = 3 if s[i - 1] == '?' else 1

    for j in range(4):
        dp[i][j] = dp[i - 1][j] * m % p

    if s[i - 1] == 'A' or s[i - 1] == '?':
        dp[i][1] =  (dp[i][1] + dp[i - 1][0]) % p
    if s[i - 1] == 'B' or s[i - 1] == '?':
        dp[i][2] = (dp[i][2] + dp[i - 1][1]) % p
    if s[i - 1] == 'C' or s[i - 1] == '?':
        dp[i][3] = (dp[i][3] + dp[i - 1][2]) % p

print(dp[n][3])

Verdicts: Runtime Error

Wrong Answer

Runtime Error

Accepted