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):
import sys
sys.setrecursionlimit(10**7)

modulus = 10 ** 9 + 7
s = input()


def dp(i, j):
    """
    dynamic programming for abc 104
    :param i: index of the given string
    :param j: count of letters of composed string (like 'ABC')
    :return: the number of cases
    """
    if i == n:
        if j == 3:
            return 1
        else:
            return 0

    if i < n and j == 3:
        m = 3 if s[i] == '?' else 1
        return m * dp(i + 1, 3) % modulus

    if i < n and j < 3:
        m1 = 3 if s[i] == '?' else 1
        m2 = 1 if s[i] == '?' or s[i] == 'ABC'[j] else 0

        _pass = m1 * dp(i + 1, j) % modulus
        _take = m2 * dp(i + 1, j + 1) % modulus

        return _pass + _take


print(dp(0, 0))


class ABC104:
    modulus = 10 ** 9 + 7

    def __init__(self, s):
        self.s = s
        self.n = len(s)

    def dp(self, i, j):
        """
        dynamic programming for abc 104
        :param i: index of the given string
        :param j: count of letters of composed string (like 'ABC')
        :return: the number of cases
        """
        if i == self.n:
            if j == 3:
                return 1
            else:
                return 0

        if i < self.n and j == 3:
            m = 3 if self.s[i] == '?' else 1
            return m * self.dp(i + 1, 3) % self.modulus

        if i < self.n and j < 3:
            m1 = 3 if self.s[i] == '?' else 1
            m2 = 1 if self.s[i] == '?' or self.s[i] == 'ABC'[j] else 0

            _pass = m1 * self.dp(i + 1, j) % self.modulus
            _take = m2 * self.dp(i + 1, j + 1) % self.modulus

            return _pass + _take


if __name__ == '__main__':
    import sys
    sys.setrecursionlimit(10**15)

    abc = ABC104(input())
    print(abc.dp(0, 0))


if __name__ == "__main__":
    modulus = 10 ** 9 + 7
    s = input()
    n = len(s)
    dp = [[0] * 4 for _ in range(n + 1)]

    for i in range(n + 1)[::-1]:
        for j in range(4)[::-1]:
            if i == n:
                if j == 3:
                    dp[i][j] = 1
                else:
                    dp[i][j] = 0
            else:
                is_wildcard = s[i] == '?'
                if j == 3:
                    m = 3 if is_wildcard else 1
                    dp[i][j] = m * dp[i + 1][3] % modulus

                else:
                    m1 = 3 if is_wildcard else 1
                    m2 = 1 if is_wildcard or s[i] == 'ABC'[j] else 0

                    dp[i][j] = (m1 * dp[i + 1][j] + m2 * dp[i + 1][j + 1]) % modulus
            # print(i, j, dp[i][j])
    print(dp[0][0])


Verdicts: Runtime Error

Runtime Error

Accepted