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):
def main():
    
    S = input()
    ans3 = cumsum(S)

    print(ans3)
    

def cumsum(S):
    
    n = len(S)
    q = [0 for _ in range(n+1)]
    abc = [[0] * 3 for _ in range(n+1)]
    for i in range(n):
        is_q = S[i] == "?"
        q[i+1] += q[i] + int(is_q)

        # for j, c in enumerate("ABC"):
        #    add = int(is_q or S[i] == c)
        for j, c in enumerate("ABC"):
            if c == "B":
                add = int(is_q or S[i] == c)
            else:
                add = int(S[i] == c)
            abc[i+1][j] += abc[i][j] + add

    ans = 0
    MOD = 10 ** 9 + 7
    for i in range(1, n-1):
        a = abc[i][0]
        b = abc[i+1][1] - abc[i][1]
        c = abc[n][2] - abc[i+1][2]
        l = q[i]
        r = q[n] - q[i+1]

        
        # ans += a * b * c

        
        
        
        
        ac = a * b * c * (3 ** (l + r))
        aq = a * b * r * (3 ** (l + r - 1))
        qc = l * b * c * (3 ** (l + r - 1))
        qq = l * b * r * (3 ** (l + r - 2))
        ans += ac + aq + qc + qq
        ans %= MOD

    return ans


if __name__ == '__main__':
    main()


def main():
    
    S = input()
    ans3 = cumsum(S)
    print(ans3)


def cumsum(S):
    
    n = len(S)
    aa = [0 for _ in range(n+1)]
    cc = [0 for _ in range(n+1)]
    q = [0 for _ in range(n+1)]
    for i in range(n):
        aa[i+1] += aa[i] + int(S[i] == "A")
        cc[i+1] += cc[i] + int(S[i] == "C")
        q[i+1] += q[i] + int(S[i] == "?")

    ans = 0
    MOD = 10 ** 9 + 7
    for i in range(1, n-1):
        a = aa[i]
        c = cc[n] - cc[i+1]
        l = q[i]
        r = q[n] - q[i+1]
        
        
        
        
        if S[i] in ("B", "?"):
            ac = a * c * pow(3, l + r, MOD)
            aq, qc, qq = (0, 0, 0)
            if l + r - 1:
                p = pow(3, l + r - 1, MOD)
                aq = a * r * p
                qc = l * c * p
            if l + r - 1:
                qq = l * r * pow(3, l + r - 2, MOD)
            
            
            
            ans += ac + aq + qc + qq
            ans %= MOD

    return ans


if __name__ == '__main__':
    main()


def main():
    
    S = input()
    ans3 = cumsum(S)

    print(ans3)

def cumsum(S):
    
    n = len(S)
    q = [0 for _ in range(n+1)]
    abc = [[0] * 3 for _ in range(n+1)]
    for i in range(n):
        is_q = S[i] == "?"
        q[i+1] += q[i] + int(is_q)

        # for j, c in enumerate("ABC"):
        #    add = int(is_q or S[i] == c)
        for j, c in enumerate("ABC"):
            if c == "B":
                add = int(is_q or S[i] == c)
            else:
                add = int(S[i] == c)
            abc[i+1][j] += abc[i][j] + add

    ans = 0
    MOD = 10 ** 9 + 7
    for i in range(1, n-1):
        a = abc[i][0]
        b = abc[i+1][1] - abc[i][1]
        c = abc[n][2] - abc[i+1][2]
        l = q[i]
        r = q[n] - q[i+1]

        
        # ans += a * b * c

        
        
        
        
        ac = a * b * c * (3 ** (l + r))
        aq = a * b * r * (3 ** (l + r - 1))
        qc = l * b * c * (3 ** (l + r - 1))
        qq = l * b * r * (3 ** (l + r - 2))
        ans += ac + aq + qc + qq
        ans %= MOD

    return ans


if __name__ == '__main__':
    main()


def main():
    
    S = input()
    ans3 = cumsum(S)
    print(ans3)


def cumsum(S):
    
    n = len(S)
    aa = [0 for _ in range(n+1)]
    cc = [0 for _ in range(n+1)]
    q = [0 for _ in range(n+1)]
    for i in range(n):
        aa[i+1] += aa[i] + int(S[i] == "A")
        cc[i+1] += cc[i] + int(S[i] == "C")
        q[i+1] += q[i] + int(S[i] == "?")

    ans = 0
    MOD = 10 ** 9 + 7
    for i in range(1, n-1):
        a = aa[i]
        c = cc[n] - cc[i+1]
        l = q[i]
        r = q[n] - q[i+1]
        
        
        
        
        if S[i] in ("B", "?"):
            ac = a * c * pow(3, l + r, MOD)
            aq, qc, qq = (0, 0, 0)
            if l + r - 1 >= 0:
                p = pow(3, l + r - 1, MOD)
                aq = a * r * p
                qc = l * c * p
            if l + r - 2 >= 0:
                qq = l * r * pow(3, l + r - 2, MOD)
            
            
            
            ans += ac + aq + qc + qq
            ans %= MOD

    return ans


if __name__ == '__main__':
    main()


Verdicts: Wrong Answer

Runtime Error

Wrong Answer

Accepted