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):
from scipy.misc import comb

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


ca = [0] * N
cq1 = [0] * N
if S[0] == 'A':
    ca[0] = 1
if S[0] == '?':
    cq1[0] = 1
for i in range(1, N):
    if S[i] == 'A':
        ca[i] = ca[i - 1] + 1
    else:
        ca[i] = ca[i - 1]
    if S[i] == '?':
        cq1[i] = cq1[i - 1] + 1
    else:
        cq1[i] = cq1[i - 1]

cc = [0] * N
cq2 = [0] * N
if S[-1] == 'C':
    cc[0] = 1
if S[-1] == '?':
    cq2[0] = 1
for i in range(1, N):
    if S[N - 1 - i] == 'C':
        cc[i] = cc[i - 1] + 1
    else:
        cc[i] = cc[i - 1]
    if S[N - 1 - i] == '?':
        cq2[i] = cq2[i - 1] + 1
    else:
        cq2[i] = cq2[i - 1]
cc = cc[::-1]
cq2 = cq2[::-1]

memo = {}
def f(q):
    if q in memo:
        return memo[q]
    x = [0] * (q + 1)
    for i in range(q + 1):
        x[i] = 2 ** (q - i) * comb(q, i, exact=True)
    memo[q] = x
    return x


memo2 = {}
def g(x, q):
    if (x, q) in memo2:
        return memo2[(x, q)]
    t = f(q)
    c = 0
    for i in range(q + 1):
        c += t[i] * (i + x)
    memo2[(x, q)] = c
    return c


ans = 0
for i in range(1, N - 1):
    if S[i] in ['B', '?']:
        ans += g(ca[i - 1], cq1[i - 1]) * g(cc[i + 1], cq2[i + 1])
print(ans % mod)


from scipy.misc import comb

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


ca = [0] * N
cq1 = [0] * N
if S[0] == 'A':
    ca[0] = 1
if S[0] == '?':
    cq1[0] = 1
for i in range(1, N):
    if S[i] == 'A':
        ca[i] = ca[i - 1] + 1
    else:
        ca[i] = ca[i - 1]
    if S[i] == '?':
        cq1[i] = cq1[i - 1] + 1
    else:
        cq1[i] = cq1[i - 1]

cc = [0] * N
cq2 = [0] * N
if S[-1] == 'C':
    cc[0] = 1
if S[-1] == '?':
    cq2[0] = 1
for i in range(1, N):
    if S[N - 1 - i] == 'C':
        cc[i] = cc[i - 1] + 1
    else:
        cc[i] = cc[i - 1]
    if S[N - 1 - i] == '?':
        cq2[i] = cq2[i - 1] + 1
    else:
        cq2[i] = cq2[i - 1]
cc = cc[::-1]
cq2 = cq2[::-1]

memo = {}
def f(q):
    if q in memo:
        return memo[q]
    x = [0] * (q + 1)
    for i in range(q + 1):
        x[i] = 2 ** (q - i) * comb(q, i, exact=True)
    memo[q] = x
    return x


def g(x, q):
    t = f(q)
    c = 0
    for i in range(q + 1):
        c += t[i] * (i + x)
    return c


ans = 0
for i in range(1, N - 1):
    if S[i] in ['B', '?']:
        ans += g(ca[i - 1], cq1[i - 1]) * g(cc[i + 1], cq2[i + 1])
print(ans % mod)


S = input()

N = len(S)
mod = 10 ** 9 + 7

dp = [[0 for _ in range(4)] for _ in range(N + 1)]
dp [0][0] = 1
for i in range(N):
    if S[i] == 'A':
        for j in range(4):
            dp[i + 1][j] += dp[i][j]
        dp[i + 1][1] += dp[i][0]
    elif S[i] == 'B':
        for j in range(4):
            dp[i + 1][j] += dp[i][j]
        dp[i + 1][2] += dp[i][1]
    elif S[i] == 'C':
        for j in range(4):
            dp[i + 1][j] += dp[i][j]
        dp[i + 1][3] += dp[i][2]
    else:
        for j in range(4):
            dp[i + 1][j] += dp[i][j] * 3
        dp[i + 1][1] += dp[i][0]
        dp[i + 1][2] += dp[i][1]
        dp[i + 1][3] += dp[i][2]

    for j in range(4):
        dp[i + 1][j] %= mod

print(dp[N][3])

Verdicts: Time Limit Exceeded

Time Limit Exceeded

Accepted