Problem:


Score : 400 points

Problem Statement

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.

Constraints

3 ≤ |S| ≤ 10^5

Each character of S is A, B, C or ?.

Input

Input is given from Standard Input in the following format:

S

Output

Print the sum of the ABC numbers of all the 3^Q strings, modulo 10^9 + 7.

Sample Input 1

A??C

Sample Output 1

8

In this case, Q = 2, and we can make 3^Q = 9 strings by by replacing each occurrence of ? with A, B or C. The ABC number of each of these strings is as follows:

AAAC: 0

AABC: 2

AACC: 0

ABAC: 1

ABBC: 2

ABCC: 2

ACAC: 0

ACBC: 1

ACCC: 0

The sum of these is 0 + 2 + 0 + 1 + 2 + 2 + 0 + 1 + 0 = 8, so we print 8 modulo 10^9 + 7, that is, 8.

Sample Input 2

ABCBC

Sample Output 2

3

When Q = 0, we print the ABC number of S itself, modulo 10^9 + 7. This string is the same as the one given as an example in the problem statement, and its ABC number is 3.

Sample Input 3

????C?????B??????A???????

Sample Output 3

979596887

In this case, the sum of the ABC numbers of all the 3^Q strings is 2291979612924, and we should print this number modulo 10^9 + 7, that is, 979596887.



Sample input:
A??C


Sample output:
8

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate


def solve(string):
    s = string.replace("?", "q").lower()
    n = len(s)
    i_a = []
    i_b = []
    i_c = []
    i_q = []
    for i, _s in enumerate(s):
        exec("i_{}.append({})".format(_s, i))
    s = s[::-1]

    c_b = [1 if _s == "b" else 0 for _s in s]
    c_c = [1 if _s == "c" else 0 for _s in s]
    c_q = [1 if _s == "q" else 0 for _s in s]
    c_b = list(accumulate(c_b))[::-1]
    c_c = list(accumulate(c_c))[::-1]
    c_q = list(accumulate(c_q))[::-1]
    ans = 0
    # ABC
    ans += sum(
        sum(c_c[_b + 1] * 3**len(i_q)
            for _b in i_b
            if _a < _b < n - 1)
        for _a in i_a
        if _a < n - 2)
    # AB?
    ans += sum(
        sum(c_q[_b + 1] * 3**(len(i_q) - 1)
            for _b in i_b
            if _a < _b < n - 1)
        for _a in i_a
        if _a < n - 2)
    # A?C
    ans += sum(
        sum(c_c[_b + 1] * 3**(len(i_q) - 1)
            for _b in i_q
            if _a < _b < n - 1)
        for _a in i_a
        if _a < n - 2)
    # ?BC
    ans += sum(
        sum(c_c[_b + 1] * 3**(len(i_q) - 1)
            for _b in i_b
            if _a < _b < n - 1)
        for _a in i_q
        if _a < n - 2)
    # A??
    ans += sum(
        sum(c_q[_b + 1] * 3**(len(i_q) - 2)
            for _b in i_q
            if _a < _b < n - 1)
        for _a in i_a
        if _a < n - 2)
    # ?B?
    ans += sum(
        sum(c_q[_b + 1] * 3**(len(i_q) - 2)
            for _b in i_b
            if _a < _b < n - 1)
        for _a in i_q
        if _a < n - 2)
    # ??C
    ans += sum(
        sum(c_c[_b + 1] * 3**(len(i_q) - 2)
            for _b in i_q
            if _a < _b < n - 1)
        for _a in i_q
        if _a < n - 2)
    # ???
    ans += sum(
        sum(c_q[_b + 1] * 3**(len(i_q) - 3)
            for _b in i_q
            if _a < _b < n - 1)
        for _a in i_q
        if _a < n - 2)
    return str(int(ans % (10**9 + 7)))


if __name__ == '__main__':
    print(solve(input()))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int

def solve(S: str):
    total = 0
    for s in S:
        if s == '?':
            total += 1
    n = len(S)
    dp = [[0] * 4 for _ in range(n + 1)]
    cnt = 0
    for i in range(n):
        s = S[i]
        dp[i + 1][0] = dp[i][0]
        dp[i + 1][1] = dp[i][1]
        dp[i + 1][2] = dp[i][2]
        dp[i + 1][3] = dp[i][3]
        if s == '?':
            dp[i + 1][1] = dp[i][1] + 1
            dp[i + 1][2] = (dp[i][2] * 3 + (dp[i][0] * int(3 ** cnt)) + (dp[i][1] * int(3 ** (cnt - 1)))) % MOD
            dp[i + 1][3] = (dp[i][3] + dp[i][2] * (3 ** (total - cnt - 1))) % MOD
            cnt += 1
        elif s == 'A':
            dp[i + 1][0] = dp[i][0] + 1
        elif s == 'B':
            dp[i + 1][2] = (dp[i][2] + (dp[i][0] * int(3 ** cnt)) + (dp[i][1] * int(3 ** (cnt - 1)))) % MOD
        elif s == 'C':
            dp[i + 1][3] = (dp[i][3] + dp[i][2] * (3 ** (total - cnt))) % MOD
    #print(dp)
    ret = dp[n][3] % MOD
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
 
MOD = 1000000007  # type: int
 
def solve(S: str):
    total = 0
    for s in S:
        if s == '?':
            total += 1
    n = len(S)
    dp = [[0] * 4 for _ in range(n + 1)]
    cnt = 0
    for i in range(n):
        s = S[i]
        dp[i + 1][0] = dp[i][0]
        dp[i + 1][1] = dp[i][1]
        dp[i + 1][2] = dp[i][2]
        dp[i + 1][3] = dp[i][3]
        if s == '?':
            dp[i + 1][1] = dp[i][1] + 1
            dp[i + 1][2] = dp[i][2] * 3 + (dp[i][0] * int(3 ** cnt)) + (dp[i][1] * int(3 ** (cnt - 1)))
            dp[i + 1][3] = dp[i][3] + dp[i][2] * (3 ** (total - cnt - 1))
            cnt += 1
        elif s == 'A':
            dp[i + 1][0] = dp[i][0] + 1
        elif s == 'B':
            dp[i + 1][2] = dp[i][2] + (dp[i][0] * int(3 ** cnt)) + (dp[i][1] * int(3 ** (cnt - 1)))
        elif s == 'C':
            dp[i + 1][3] = dp[i][3] + dp[i][2] * (3 ** (total - cnt))
    #print(dp)
    ret = dp[n][3] % MOD
    print(ret)
    return
 
 
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)
 
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int

def solve(S: str):
    total = 0
    for s in S:
        if s == '?':
            total += 1
    n = len(S)
    dp = [[0] * 4 for _ in range(n + 1)]
    cnt = 0
    for i in range(n):
        s = S[i]
        dp[i + 1][0] = dp[i][0]
        dp[i + 1][1] = dp[i][1]
        dp[i + 1][2] = dp[i][2]
        dp[i + 1][3] = dp[i][3]
        if s == '?':
            dp[i + 1][1] = dp[i][1] + 1
            dp[i + 1][2] = dp[i][2] * 3 + (dp[i][0] * int(3 ** cnt)) + (dp[i][1] * int(3 ** (cnt - 1)))
            dp[i + 1][3] = dp[i][3] + dp[i][2] * (3 ** (total - cnt - 1))
            cnt += 1
        elif s == 'A':
            dp[i + 1][0] = dp[i][0] + 1
        elif s == 'B':
            dp[i + 1][2] = dp[i][2] + (dp[i][0] * int(3 ** cnt)) + (dp[i][1] * int(3 ** (cnt - 1)))
        elif s == 'C':
            dp[i + 1][3] = dp[i][3] + dp[i][2] * (3 ** (total - cnt))
    #print(dp)
    ret = dp[n][3] % MOD
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
s=input()
a_count=[0]
c_count=[0]
q_lcount=[0]
q_rcount=[0]
n=len(s)
for i in range(n):
    if s[i]=='A':
        a_count.append(a_count[i]+1)
        q_lcount.append(q_lcount[i])
    elif s[i]=='?':
        a_count.append(a_count[i])
        q_lcount.append(q_lcount[i]+1)
    else:
        a_count.append(a_count[i])
        q_lcount.append(q_lcount[i])
for i in range(n):
    if s[n-1-i]=='C':
        c_count.append(c_count[i]+1)
        q_rcount.append(q_rcount[i])
    elif s[n-1-i]=='?':
        c_count.append(c_count[i])
        q_rcount.append(q_rcount[i]+1)
    else:
        c_count.append(c_count[i])
        q_rcount.append(q_rcount[i])
q=q_lcount[n]
ans=0
INF=10**9+7
a=3**q
b=a//3
c=b//3
d=c//3
for i in range(n):
    if s[i]=='B':
        x=a_count[i]*c_count[n-1-i]*a
        y=a_count[i]*q_rcount[n-1-i]*b
        z=q_lcount[i]*c_count[n-1-i]*b
        w=q_lcount[i]*q_rcount[n-1-i]*c
        ans=(ans+x+y+z+w)%INF
    elif s[i]=='?':
        x=a_count[i]*c_count[n-1-i]*b
        y=a_count[i]*q_rcount[n-1-i]*c
        z=q_lcount[i]*c_count[n-1-i]*c
        w=q_lcount[i]*q_rcount[n-1-i]*d
        ans=(ans+x+y+z+w)%INF
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
s=input()
a_count=[0]
c_count=[0]
q_lcount=[0]
q_rcount=[0]
n=len(s)
for i in range(n):
    if s[i]=='A':
        a_count.append(a_count[i]+1)
        q_lcount.append(q_lcount[i])
    elif s[i]=='?':
        a_count.append(a_count[i])
        q_lcount.append(q_lcount[i]+1)
    else:
        a_count.append(a_count[i])
        q_lcount.append(q_lcount[i])
for i in range(n):
    if s[n-1-i]=='C':
        c_count.append(c_count[i]+1)
        q_rcount.append(q_rcount[i])
    elif s[n-1-i]=='?':
        c_count.append(c_count[i])
        q_rcount.append(q_rcount[i]+1)
    else:
        c_count.append(c_count[i])
        q_rcount.append(q_rcount[i])
q=q_lcount[n]
ans=0
INF=10**9+7
for i in range(n):
    if s[i]=='B':
        x=a_count[i]*c_count[n-1-i]*3**q
        y=a_count[i]*q_rcount[n-1-i]*3**(q-1)
        z=q_lcount[i]*c_count[n-1-i]*3**(q-1)
        w=q_lcount[i]*q_rcount[n-1-i]*3**(q-2)
        ans=(ans+x+y+z+w)%INF
    elif s[i]=='?':
        x=a_count[i]*c_count[n-1-i]*3**(q-1)
        y=a_count[i]*q_rcount[n-1-i]*3**(q-2)
        z=q_lcount[i]*c_count[n-1-i]*3**(q-2)
        w=q_lcount[i]*q_rcount[n-1-i]*3**(q-3)
        ans=(ans+x+y+z+w)%INF
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
#D問題
S=str(input())
Slist=list(S)
Slen=len(S)
mod=1000000007
dp=[[0 for i in range(4)] for j in range(Slen+1)]
for i in range(4):
    I=3-i
    for j in range(Slen+1):
        J=Slen-j
        if J == Slen and I == 3:
            dp[J][I]=1
        elif J == Slen and I < 3:
            dp[J][I]=0
        elif J < Slen and I == 3:
            if Slist[J] == "?":
                dp[J][I]=3*dp[J+1][I]
            else:
                dp[J][I]=dp[J+1][I]
        else:
            if Slist[J] == "?":
                dp[J][I]=3*dp[J+1][I]+dp[J+1][I+1]
            else:
                if Slist[J] == "A":
                    if I == 0:
                        dp[J][I]=dp[J+1][I]+dp[J+1][I+1]
                    else:
                        dp[J][I]=dp[J+1][I]
                elif Slist[J] == "B":
                    if I == 1:
                        dp[J][I]=dp[J+1][I]+dp[J+1][I+1]
                    else:
                        dp[J][I]=dp[J+1][I]
                elif Slist[J] == "C":
                    if I == 2:
                        dp[J][I]=dp[J+1][I]+dp[J+1][I+1]
                    else:
                        dp[J][I]=dp[J+1][I]
                
ans=dp[0][0]%1000000007
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#D問題
S=str(input())
Slist=list(S)
Slen=len(S)
mod=1000000007
dp=[[0 for i in range(4)] for j in range(Slen+1)]
for i in range(4):
    I=3-i
    for j in range(Slen+1):
        J=Slen-j
        if J == Slen and I == 3:
            dp[J][I]=1
        elif J == Slen and I < 3:
            dp[J][I]=0
        elif J < Slen and I == 3:
            if Slist[J] == "?":
                dp[J][I]=3*dp[J+1][I]
            else:
                dp[J][I]=dp[J+1][I]
        elif J < Slen and I < 3:
            if Slist[J] == "?":
                dp[J][I]=3*dp[J+1][I]+dp[J+1][I+1]
            else:
                if Slist[J] == "A":
                    if I == 0:
                        dp[J][I]=dp[J+1][I]+dp[J+1][I+1]
                    else:
                        dp[J][I]=dp[J+1][I]
                elif Slist[J] == "B":
                    if I == 1:
                        dp[J][I]=dp[J+1][I]+dp[J+1][I+1]
                    else:
                        dp[J][I]=dp[J+1][I]
                elif Slist[J] == "C":
                    if I == 2:
                        dp[J][I]=dp[J+1][I]+dp[J+1][I+1]
                    else:
                        dp[J][I]=dp[J+1][I]
                
print(dp[0][0]%mod)

Submission status: Time Limit Exceeded

Solution code:
S = input()
dp = [[0 for i in range(4)] for i in range(len(S)+1)]
MOD = 10**9+7
dp[0][3] = 1
for i in range(len(S)):
    x = S[i]
    if x == '?': k = 3
    else: k = 1
    for _ in range(k):
        dp[i+1][0] += dp[i][0] 
        dp[i+1][1] += dp[i][1] 
        dp[i+1][2] += dp[i][2] 
        dp[i+1][3] += dp[i][3] 
    if x == 'A':
        dp[i+1][0] +=  dp[i][3]
    elif x == 'B':
        dp[i+1][1] +=  dp[i][0]
    elif x == 'C':
        dp[i+1][2] += dp[i][1]
    else:
        dp[i+1][0] += dp[i][3]
        dp[i+1][1] += dp[i][0]
        dp[i+1][2] += dp[i][1]
    for j in range(3):
        if dp[1+i][j] > MOD: dp[i+1][j] %= MOD
print(dp[len(S)][2]%MOD)

Submission status: Time Limit Exceeded

Solution code:
S = input()
dp = [[0 for i in range(4)] for i in range(len(S)+1)]
MOD = 10**9+7
dp[0][3] = 1
for i in range(len(S)):
    if S[i] == '?': k = 3
    else: k = 1
    for _ in range(k):
      for l in range(4):
        dp[i+1][l] += dp[i][l] 
    if S[i] == 'A':
        dp[i+1][0] +=  dp[i][3]
    elif S[i] == 'B':
        dp[i+1][1] +=  dp[i][0]
    elif S[i] == 'C':
        dp[i+1][2] += dp[i][1]
    else:
        dp[i+1][0] += dp[i][3]
        dp[i+1][1] += dp[i][0]
        dp[i+1][2] += dp[i][1]
    for j in range(4):
        if dp[i][j] > MOD: dp[i][j] %= MOD
print(dp[len(S)][2]%MOD)

Submission status: Time Limit Exceeded

Solution code:
S = input()
dp = [[0 for i in range(4)] for i in range(len(S)+1)]
MOD = 10**9+7
dp[0][3] = 1
for i in range(len(S)):
    x = S[i]
    if x == '?': k = 3
    else: k = 1
    for _ in range(k):
        dp[i+1][0] += dp[i][0] 
        dp[i+1][1] += dp[i][1] 
        dp[i+1][2] += dp[i][2] 
        dp[i+1][3] += dp[i][3] 
    if x == 'A':
        dp[i+1][0] +=  dp[i][3]
    elif x == 'B':
        dp[i+1][1] +=  dp[i][0]
    elif x == 'C':
        dp[i+1][2] += dp[i][1]
    else:
        dp[i+1][0] += dp[i][3]
        dp[i+1][1] += dp[i][0]
        dp[i+1][2] += dp[i][1]
    for j in range(3):
        if dp[i][j] > MOD: dp[i][j] %= MOD
print(dp[len(S)][2]%MOD)

Submission status: Time Limit Exceeded

Solution code:
s=input()
dp=[[0]*4 for i in range(len(s)+1)]
dp[0][0]=1
mod=10**9+7
from copy import deepcopy
def dp_next(dp,i,j,mod):
    dp[i+1][j+1]=(dp[i+1][j+1]+dp[i][j])%mod
for i in range(len(s)):
    if s[i]=='?':
        for j in range(4):
            dp[i+1][j]=dp[i][j]*3
        for j in range(3):
            dp_next(dp,i,j,mod)
        continue
    dp[i+1]=deepcopy(dp[i])
    if s[i]=='A':
        dp_next(dp,i,0,mod)
    elif s[i]=='B':
        dp_next(dp,i,1,mod)
    elif s[i]=='C':
        dp_next(dp,i,2,mod)
print(dp[-1][3])

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8
S=raw_input()

all=1
a=ab=abc=0

for _ in range(len(S)):
    i=_+1
    c=S[_]
    if c=="A":
        a+=all
    if c=="B":
        ab+=a
    if c=="C":
        abc+=ab
    if c=="?":
        abc=abc*3+ab
        ab=ab*3+a
        a=a*3+all
        all*=3
print(abc%((10**9)+7))

Submission status: Time Limit Exceeded

Solution code:
s = input()

ans = 0

q = s.count('?')

rc = [0]
rq = [0]
la = [0]
lq = [0]

for i in range(len(s)-1):
    if s[len(s)-i-1]=='C':
        rc.append(rc[-1]+1)
    else:
        rc.append(rc[-1])
    if s[len(s)-i-1]=='?':
        rq.append(rq[-1] + 1)
    else:
        rq.append(rq[-1])
    if s[i]=='A':
        la.append(la[-1]+1)
    else:
        la.append(la[-1])
    if s[i]=='?':
        lq.append(lq[-1]+1)
    else:
        lq.append(lq[-1])
rc.reverse()
rq.reverse()

t = 10**9+7

for i in range(len(s)):
    if s[i]=='B' or s[i]=='?':
        l = 3**(lq[i]-1)%t
        r = 3**(rq[i]-1)%t
        ans += la[i]*3*l*rc[i]*3*r % t
        ans += lq[i]*l*rc[i]*3*r % t
        ans += la[i]*3*l*rq[i]*r % t
        ans += lq[i]*l*rq[i]*r % t

print(int(ans%t))

Submission status: Time Limit Exceeded

Solution code:
s = input()

ans = 0

z = [[0]*4 for i in range(len(s))]

t = 10**9+7

for i in range(1,len(s)-1):
    z[i][0] = z[i - 1][0]
    z[i][1] = z[i - 1][1]
    if s[i-1]=='A':
        z[i][0] +=1
    elif s[i-1]=='?':
        z[i][1] += 1

    z[-i-1][2] = z[-i][2]
    z[-i-1][3] = z[-i][3]
    if s[-i]=='C':
        z[-i-1][2] += 1
    elif s[-i] =='?':
        z[-i-1][3] += 1

for i in range(1, len(s) - 1):
    if s[i]=='B' or s[i]=='?':
        a1 = 3*z[i][0]+z[i][1]
        a2 = 3**(z[i][1]-1)%t
        c1 = 3*z[i][2]+z[i][3]
        c2 = 3**(z[i][3]-1)%t
        ans += (a1*a2*c1*c2)%t
    ans %=t

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
s = input()

ans = 0

z = [[0]*4 for i in range(len(s))]

t = (10**9+7)

for i in range(1,len(s)-1):
    z[i][0] = z[i - 1][0]
    z[i][1] = z[i - 1][1]
    if s[i-1]=='A':
        z[i][0] +=1
    elif s[i-1]=='?':
        z[i][1] += 1

for i in range(1,len(s)-1):
    z[-i-1][2] = z[-i][2]
    z[-i-1][3] = z[-i][3]
    if s[-i]=='C':
        z[-i-1][2] += 1
    elif s[-i] =='?':
        z[-i-1][3] += 1


for i in range(1,len(s)-1):
    if s[i]=='B' or s[i]=='?':
        a1 = 3*z[i][0]+z[i][1]
        a2 = 3**(z[i][1]-1)%t
        c1 = 3*z[i][2]+z[i][3]
        c2 = 3**(z[i][3]-1)%t
        ans += (a1*a2*c1*c2)%t
    ans %=t

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
s = input()

ans = 0

q = s.count('?')

rc = [0]
rq = [0]
for i in range(len(s)-1):
    if s[len(s)-i-1]=='C':
        rc.append(rc[-1]+1)
    else:
        rc.append(rc[-1])
    if s[len(s)-i-1]=='?':
        rq.append(rq[-1] + 1)
    else:
        rq.append(rq[-1])
rc.reverse()
rq.reverse()

for i in range(len(s)):
    if s[i]=='A' or s[i]=='?':
        if s[i]=='?':
            qq = q-1
        else:
            qq = q
        for j in range(i+1,len(s)):
            if s[j]=='B' or s[j]=='?':
                if s[j] == '?':
                    qqq = qq-1
                else:
                    qqq = qq
                ans += rc[j]*(3**qqq)
                if qq>0:
                    ans += rq[j]*(3**(qqq-1))
                ans %= 10**9+7

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
def main():
    """
    1 <= i < j < k <= |T|
    Ti = A
    Tj = B
    Tk = C
    """
    S = input()
    #ans = editorial(S)
    #ans2 = dp_simple(S)
    ans3 = cumsum(S)

    #assert ans == ans2 == ans3
    #if len(S) <= 5:
    #    ans4 = TLE(S)
    #    assert ans == ans4

    print(ans3)


def TLE(S):
    """文字列全列挙
    ?をすべて置き換えるパターンを作成し
    それについてABC数を算出
    """
    s = list(S)
    qi = [i for i, c in enumerate(S) if c == "?"]
    nq = len(qi)
    mod = 10 ** 9 + 7
    import sys
    sys.setrecursionlimit(mod)

    def rec(i):
        if i == nq:
            return n_ABC(s)

        ans = 0
        for x in list("ABC"):
            s[qi[i]] = x
            ans += rec(i+1)

        return ans

    ans = rec(0) % mod
    return ans


def n_ABC(S):
    """3^Q を考えていないパターン がABCを求めるパターンになっていた
    """
    ans = 0
    n = len(S)
    for i in range(n):
        for j in range(i+1, n):
            for k in range(j+1, n):
                # print(i, j, k, S[i] + S[j] + S[k])
                if S[i] in ("A", "?") and S[j] in ("B", "?") and S[k] in ("C", "?"):
                    ans += 1

    return ans


def editorial(S):
    MOD = 10 ** 9 + 7
    n = len(S)
    dp = [[0] * (3+1) for _ in range(n+1)]

    for i in range(n, -1, -1):
        for j in range(3, -1, -1):
            if i == n:
                x = int(j == 3)
                # ≠3: 丸を3個つける前に最後の文字まで見終わってしまい、手遅れ
                # =3: 処理が正常終了
                dp[i][j] = x
            else:
                m1 = 1
                if S[i] == "?":
                    m1 = 3

                if j == 3:
                    # 丸は3個つけ終わったので、あとは?を置換するのみ
                    dp[i][j] = m1 * dp[i+1][j]
                else:
                    m2 = int(S[i] == "?" or S[i] == "ABC"[j])
                    # 前半:i文字目に丸をつけない場合, 後半:丸をつける場合に対応
                    dp[i][j] = m1 * dp[i+1][j] + m2 * dp[i+1][j+1]

                dp[i][j] %= MOD

    ans = dp[0][0]
    return ans


def dp_simple(S):
    n = len(S)
    MOD = 10 ** 9 + 7
    dp = [[0] * (3+1) for _ in range(n+1)]
    # 組合せ列挙なので掛け算としての単位元
    dp[0][0] = 1

    for i in range(n):
        # i文字目まで
        for j in range(3+1):
            # 0-3文字揃ってる
            m = 1
            if S[i] == "?":
                # 置換できるので3パターン
                m = 3
            dp[i+1][j] += dp[i][j] * m
            dp[i+1][j] %= MOD

            # 3文字揃ってないとき, 対応する文字になるか？
            if j < 3 and (S[i] == "?" or S[i] == "ABC"[j]):
                dp[i+1][j+1] += dp[i][j]
                dp[i+1][j+1] %= MOD

    ans = dp[n][3]
    return ans


def cumsum(S):
    """
    考えたときに累積和が浮かんだ
    ABCとあるので
    i文字目までのA相当の数、つまり?も含んだ数
    これをBとCにも適用する
    Aを決め打ちで進めるとBも走査することになる
    Cは定数倍で求められるが、|S|^2: TLE で意味がない

    ここで断念していろいろ調べると
    Bを決め打ちすれば
    A: 0-(B-1)
    C: (B+1)-N
    なのでNでおｋ

    と、思ったがWAと同じ間違いをしている
    3^q パターンをきちんと考える
    """
    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]
        # ABC の作り方
        # AB?: ? 1つをCに割り当てる
        # ?BC: ? 1つをAに割り当てる
        # ?B?: ? 2つをACに割り当てる
        if S[i] in ("B", "?"):
            ac = a * c * (3 ** (l + r))
            aq = a * r * (3 ** (l + r - 1))
            qc = l * c * (3 ** (l + r - 1))
            qq = l * r * (3 ** (l + r - 2))
            # print(a, c, l, r, ((l+r, l+r-1, l+r-2)), (ac, aq, qc, qq))
            # 3^x: xが負になるときに少数になってしまう
            ans += int(ac + aq + qc + qq)
            ans %= MOD

    return ans


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    """
    1 <= i < j < k <= |T|
    Ti = A
    Tj = B
    Tk = C
    """
    S = input()
    ans = editorial(S)
    ans2 = dp_simple(S)
    ans3 = cumsum(S)
    assert ans == ans2 == ans3
    if len(S) <= 5:
        ans4 = TLE(S)
        assert ans == ans4

    print(ans)


def TLE(S):
    """文字列全列挙
    ?をすべて置き換えるパターンを作成し
    それについてABC数を算出
    """
    s = list(S)
    qi = [i for i, c in enumerate(S) if c == "?"]
    nq = len(qi)
    mod = 10 ** 9 + 7
    import sys
    sys.setrecursionlimit(mod)

    def rec(i):
        if i == nq:
            return n_ABC(s)

        ans = 0
        for x in list("ABC"):
            s[qi[i]] = x
            ans += rec(i+1)

        return ans

    ans = rec(0) % mod
    return ans


def n_ABC(S):
    """3^Q を考えていないパターン がABCを求めるパターンになっていた
    """
    ans = 0
    n = len(S)
    for i in range(n):
        for j in range(i+1, n):
            for k in range(j+1, n):
                # print(i, j, k, S[i] + S[j] + S[k])
                if S[i] in ("A", "?") and S[j] in ("B", "?") and S[k] in ("C", "?"):
                    ans += 1

    return ans


def editorial(S):
    MOD = 10 ** 9 + 7
    n = len(S)
    dp = [[0] * (3+1) for _ in range(n+1)]

    for i in range(n, -1, -1):
        for j in range(3, -1, -1):
            if i == n:
                x = int(j == 3)
                # ≠3: 丸を3個つける前に最後の文字まで見終わってしまい、手遅れ
                # =3: 処理が正常終了
                dp[i][j] = x
            else:
                m1 = 1
                if S[i] == "?":
                    m1 = 3

                if j == 3:
                    # 丸は3個つけ終わったので、あとは?を置換するのみ
                    dp[i][j] = m1 * dp[i+1][j]
                else:
                    m2 = int(S[i] == "?" or S[i] == "ABC"[j])
                    # 前半:i文字目に丸をつけない場合, 後半:丸をつける場合に対応
                    dp[i][j] = m1 * dp[i+1][j] + m2 * dp[i+1][j+1]

                dp[i][j] %= MOD

    ans = dp[0][0]
    return ans


def dp_simple(S):
    n = len(S)
    MOD = 10 ** 9 + 7
    dp = [[0] * (3+1) for _ in range(n+1)]
    # 組合せ列挙なので掛け算としての単位元
    dp[0][0] = 1

    for i in range(n):
        # i文字目まで
        for j in range(3+1):
            # 0-3文字揃ってる
            m = 1
            if S[i] == "?":
                # 置換できるので3パターン
                m = 3
            dp[i+1][j] += dp[i][j] * m
            dp[i+1][j] %= MOD

            # 3文字揃ってないとき, 対応する文字になるか？
            if j < 3 and (S[i] == "?" or S[i] == "ABC"[j]):
                dp[i+1][j+1] += dp[i][j]
                dp[i+1][j+1] %= MOD

    ans = dp[n][3]
    return ans


def cumsum(S):
    """
    考えたときに累積和が浮かんだ
    ABCとあるので
    i文字目までのA相当の数、つまり?も含んだ数
    これをBとCにも適用する
    Aを決め打ちで進めるとBも走査することになる
    Cは定数倍で求められるが、|S|^2: TLE で意味がない

    ここで断念していろいろ調べると
    Bを決め打ちすれば
    A: 0-(B-1)
    C: (B+1)-N
    なのでNでおｋ

    と、思ったがWAと同じ間違いをしている
    3^q パターンをきちんと考える
    """
    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]

        # WA: ? を無視している
        # ans += a * b * c

        # ABC の作り方
        # AB?: ? 1つをCに割り当てる
        # ?BC: ? 1つをCに割り当てる
        # ?B?: ? 2つをACに割り当てる
        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()

Submission status: Time Limit Exceeded

Solution code:
def main():
    """
    1 <= i < j < k <= |T|
    Ti = A
    Tj = B
    Tk = C
    """
    S = input()
    #ans = editorial(S)
    ans = TLE(S)

    print(ans)


def TLE(S):
    """文字列全列挙
    ?をすべて置き換えるパターンを作成し
    それについてABC数を算出
    """
    s = list(S)
    qi = [i for i, c in enumerate(S) if c == "?"]
    nq = len(qi)
    mod = 10 ** 9 + 7
    import sys
    sys.setrecursionlimit(mod)

    def rec(i):
        if i == nq:
            return n_ABC(s)

        ans = 0
        for x in list("ABC"):
            s[qi[i]] = x
            ans += rec(i+1)

        return ans

    ans = rec(0) % mod
    return ans


def n_ABC(S):
    """3^Q を考えていないパターン がABCを求めるパターンになっていた
    """
    ans = 0
    n = len(S)
    for i in range(n):
        for j in range(i+1, n):
            for k in range(j+1, n):
                # print(i, j, k, S[i] + S[j] + S[k])
                if S[i] in ("A", "?") and S[j] in ("B", "?") and S[k] in ("C", "?"):
                    ans += 1

    return ans


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
S = input()
N = len(S)

MOD = 10 ** 9 + 7

def nLeftA(S, A):
    """(S[:i]の'A'の選び方, S[:i]の'?'の埋め方)"""
    l = [(0, 1)]
    for s in S:
        a, q = l[-1]
        if s == A:
            a = q + a      # S[i-1]を選ぶ + S[:i]のどれかを選ぶ
        elif s == '?':
            a = q + a * 3  # S[i-1]を選ぶ + S[:i]のどれかを選ぶ(?に3通り)
            q = q * 3
        l.append((a, q))
    return l

l = nLeftA(S, 'A')
r = nLeftA(reversed(S), 'C')
r.reverse()
r = r[1:]

n = 0
for i in range(N):
    if S[i] in 'B?':
        n += l[i][0] * r[i][0] % MOD

print(n % MOD)

Submission status: Time Limit Exceeded

Solution code:
mod=10**9+7
s=input()
n=len(s)
Sum_A=[0]*(n+1)
Sum_B=[0]*(n+1)
Sum_C=[0]*(n+1)
Sum_q=[0]*(n+1)
for i in range(1, n+1):
    Sum_A[i]=Sum_A[i-1]
    Sum_C[i]=Sum_C[i-1]
    Sum_q[i]=Sum_q[i-1]
    if s[i-1]=='A':
        Sum_A[i]+=1
    elif s[i-1]=='C':
        Sum_C[i]+=1
    elif s[i-1]=='?':
        Sum_q[i]+=1
ans=0
def count(x, q):
    return int(x*3**q+q*3**(q-1))
for i in range(n):
    if s[i]=='B' or s[i]=='?':
        ans+=count(Sum_A[i], Sum_q[i])*count(Sum_C[n]-Sum_C[i+1], Sum_q[n]-Sum_q[i+1])
        ans%=mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000)
mod=10**9+7
s=input()
n=len(s)
Sum_A=[0]*(n+1)
Sum_B=[0]*(n+1)
Sum_C=[0]*(n+1)
Sum_q=[0]*(n+1)
for i in range(1, n+1):
    Sum_A[i]=Sum_A[i-1]
    Sum_C[i]=Sum_C[i-1]
    Sum_q[i]=Sum_q[i-1]
    if s[i-1]=='A':
        Sum_A[i]+=1
    elif s[i-1]=='C':
        Sum_C[i]+=1
    elif s[i-1]=='?':
        Sum_q[i]+=1
ans=0

def pow1(x, n):
    """
    O(log n)
    """
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2

    return K * x

def count(x, q):
    return int(x*pow1(3, q)+q*pow1(3, q-1))

for i in range(n):
    if s[i]=='B' or s[i]=='?':
        ans+=count(Sum_A[i], Sum_q[i])*count(Sum_C[n]-Sum_C[i+1], Sum_q[n]-Sum_q[i+1])
        ans%=mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
mod=10**9+7
s=input()
n=len(s)
Sum_A=[0]*(n+1)
Sum_B=[0]*(n+1)
Sum_C=[0]*(n+1)
Sum_q=[0]*(n+1)
for i in range(1, n+1):
    Sum_A[i]=Sum_A[i-1]
    Sum_C[i]=Sum_C[i-1]
    Sum_q[i]=Sum_q[i-1]
    if s[i-1]=='A':
        Sum_A[i]+=1
    elif s[i-1]=='C':
        Sum_C[i]+=1
    elif s[i-1]=='?':
        Sum_q[i]+=1
ans=0
def count(x, q):
    return int(x*3**q+q*3**(q-1))
for i in range(n):
    if s[i]=='B' or s[i]=='?':
        ans+=count(Sum_A[i], Sum_q[i])*count(Sum_C[n]-Sum_C[i+1], Sum_q[n]-Sum_q[i+1])
        ans%=mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
mod=10**9+7
s=input()
n=len(s)
Sum_A=[0]*(n+1)
Sum_B=[0]*(n+1)
Sum_C=[0]*(n+1)
Sum_q=[0]*(n+1)
for i in range(1, n+1):
    Sum_A[i]=Sum_A[i-1]
    Sum_B[i]=Sum_B[i-1]
    Sum_C[i]=Sum_C[i-1]
    Sum_q[i]=Sum_q[i-1]
    if s[i-1]=='A':
        Sum_A[i]+=1
    elif s[i-1]=='B':
        Sum_B[i]+=1
    elif s[i-1]=='C':
        Sum_C[i]+=1
    else:
        Sum_q[i]+=1
ans=0
def count(x, q):
    return int(x*3**q+q*3**(q-1))
for i in range(n):
    if s[i]=='B' or s[i]=='?':
        ans+=count(Sum_A[i], Sum_q[i])*count(Sum_C[n]-Sum_C[i+1], Sum_q[n]-Sum_q[i+1])
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
s=input()

a=[1,0,0,0]

for i in range(len(s)):
    c=s[i]
    if c=="A":
        a[1]+=a[0]
    elif c=="B":
        a[2]+=a[1]
    elif c=="C":
        a[3]+=a[2]
    elif c=="?":
        tmp=[a[i] for i in range(4)]
        a[0]=tmp[0]*3
        for j in range(3):
            a[j+1]=tmp[j+1]*3+tmp[j]

print(a[3]%1000000007)