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:
S = input()
mod = 10 ** 9 + 7
count = 0
leftA = (1 if S[0] == "A" else 0)
leftQ = (1 if S[0] == "?" else 0)
rightC = S[1:].count("C")
rightQ = S[1:].count("?")

def mult(a, b, mod):
    if b == 0:
        return a
    else:
        return ((3*a + b) * pow(3, b-1)) % mod

for i in range(1,len(S)-1):
    if S[i] == "B" or S[i] == "?":
        rightQ -= (1 if S[i] == "?" else 0)
        leftpatt, rightpatt = mult(leftA, leftQ, mod), mult(rightC, rightQ, mod)
        leftQ += (1 if S[i] == "?" else 0)
        count += leftpatt * rightpatt
        count %= mod
    else:
        leftA += (1 if S[i] == "A" else 0)
        rightC -= (1 if S[i] == "C" else 0)
print(count)

Submission status: Time Limit Exceeded

Solution code:
S = input()
mod = 10 ** 9 + 7
count = 0
leftA = (1 if S[0] == "A" else 0)
leftQ = (1 if S[0] == "?" else 0)
rightC = S[1:].count("C")
rightQ = S[1:].count("?")

for i in range(1,len(S)-1):
    if S[i] == "B" or S[i] == "?":
        rightQ -= (1 if S[i] == "?" else 0)
        if leftQ >= 1:
            leftpatt = leftA * (3 ** leftQ) + leftQ * (3 ** (leftQ - 1))
        else:
            leftpatt = leftA
        if rightQ >= 1:
            rightpatt = rightC * (3 ** rightQ) + rightQ * (3 ** (rightQ - 1))
        else:
            rightpatt = rightC
        leftQ += (1 if S[i] == "?" else 0)
        count += (leftpatt * rightpatt) % mod
        count %= mod
    else:
        leftA += (1 if S[i] == "A" else 0)
        rightC -= (1 if S[i] == "C" else 0)
print(int(count))

Submission status: Time Limit Exceeded

Solution code:
S = input()
mod = 10 ** 9 + 7
count = 0
leftA = (1 if S[0] == "A" else 0)
leftQ = (1 if S[0] == "?" else 0)
rightC = S[1:].count("C")
rightQ = S[1:].count("?")

for i in range(1,len(S)-1):
    if S[i] == "A":
        leftA += 1
    elif S[i] == "C":
        rightC -= 1
    elif S[i] == "B":
        if leftQ >= 1:
            leftpatt = leftA * (3 ** leftQ) + leftQ * (3 ** (leftQ - 1))
        else:
            leftpatt = leftA
        if rightQ >= 1:
            rightpatt = rightC * (3 ** rightQ) + rightQ * (3 ** (rightQ - 1))
        else:
            rightpatt = rightC
        count += (leftpatt * rightpatt) % mod
        count %= mod
    else:
        rightQ -= 1
        if leftQ >= 1:
            leftpatt = leftA * (3 ** leftQ) + leftQ * (3 ** (leftQ - 1))
        else:
            leftpatt = leftA
        if rightQ >= 1:
            rightpatt = rightC * (3 ** rightQ) + rightQ * (3 ** (rightQ - 1))
        else:
            rightpatt = rightC
        leftQ += 1
        count += (leftpatt * rightpatt) % mod
        count %= mod
print(int(count))

Submission status: Time Limit Exceeded

Solution code:

dp = [0, 0, 0, 1]
for s in input()[::-1]:
    tmp = dp[:]

    dp[3] = tmp[3] * 3 if s == '?' else tmp[3]

    for j in range(2, -1, -1):
        dp[j] = tmp[j] * 3 + tmp[j + 1] if s == '?' else \
                tmp[j] + tmp[j + 1] if s == 'ABC'[j] else \
                tmp[j]

print(dp[0] % (10**9 + 7))

Submission status: Time Limit Exceeded

Solution code:

S = input()

dp = [0, 0, 0, 1]
for i in range(len(S) - 1, -1, -1):
    tmp = dp[:]

    dp[3] = tmp[3] * 3 if S[i] == '?' else tmp[3]

    for j in range(2, -1, -1):
        dp[j] = tmp[j] * 3 + tmp[j + 1] if S[i] == '?' else \
                tmp[j] + tmp[j + 1] if S[i] == 'ABC'[j] else \
                tmp[j]

print(dp[0] % (10**9 + 7))

Submission status: Time Limit Exceeded

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

# dp = [[0] * 4 for i in range(len(S) + 1)]
# dp[len(S)][3] = 1
# for i in range(len(S) - 1, -1, -1):
#     dp[i][3] += dp[i + 1][3] * 3 if S[i] == '?' else dp[i + 1][3]

#     for j in range(2, -1, -1):
#         dp[i][j] += dp[i + 1][j] * 3 if S[i] == '?' else dp[i + 1][j]
#         dp[i][j] += dp[i + 1][j + 1] if S[i] == 'ABC' [j] or S[i] == '?' else 0

# print(dp[0][0] % (10**9 + 7))

dp = [0, 0, 0, 1]
for i in range(len(S) - 1, -1, -1):
    tmp = dp[:]

    dp[3] = tmp[3] * 3 if S[i] == '?' else tmp[3]

    for j in range(2, -1, -1):
        dp[j] = tmp[j] * 3 + tmp[j + 1] if S[i] == '?' else tmp[j]
        dp[j] += tmp[j + 1] if S[i] == 'ABC' [j] else 0

print(dp[0] % (10**9 + 7))

Submission status: Time Limit Exceeded

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

# dp = [[0] * 4 for i in range(len(S) + 1)]
# dp[len(S)][3] = 1
# for i in range(len(S) - 1, -1, -1):
#     dp[i][3] += dp[i + 1][3] * 3 if S[i] == '?' else dp[i + 1][3]

#     for j in range(2, -1, -1):
#         dp[i][j] += dp[i + 1][j] * 3 if S[i] == '?' else dp[i + 1][j]
#         dp[i][j] += dp[i + 1][j + 1] if S[i] == 'ABC' [j] or S[i] == '?' else 0

# print(dp[0][0] % (10**9 + 7))

dp = [0, 0, 0, 1]
for i in range(len(S) - 1, -1, -1):
    tmp = dp[:]

    dp[3] = tmp[3] * 3 if S[i] == '?' else tmp[3]

    for j in range(2, -1, -1):
        dp[j] = tmp[j] * 3 if S[i] == '?' else tmp[j]
        dp[j] += tmp[j + 1] if S[i] == 'ABC' [j] or S[i] == '?' else 0

print(dp[0] % (10**9 + 7))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
S = input()
dp = [[0] * 4 for i in range(len(S) + 1)]

dp[len(S)][3] = 1
for i in range(len(S) - 1, -1, -1):
    dp[i][3] += dp[i + 1][3] * 3 if S[i] == '?' else dp[i + 1][3]

    for j in range(2, -1, -1):
        dp[i][j] += dp[i + 1][j] * 3 if S[i] == '?' else dp[i + 1][j]
        dp[i][j] += dp[i + 1][j + 1] if S[i] == 'ABC' [j] or S[i] == '?' else 0

print(dp[0][0] % (10**9 + 7))

Submission status: Time Limit Exceeded

Solution code:
S = input()
a = 0
b = 0
c = 0
p = 1
mod = 1000000000+7
for C in S:
    if C == "?":
        c = 3*c+b
        b = 3*b+a
        a = 3*a+p
        p *= 3
        a %= mod
        b %= mod
        c %= mod
    elif C == "A":
        a += p
        a %= mod
    elif C == "B":
        b += a
        b %= mod
    elif C == "C":
        c += b
        c %= mod
print(c)

Submission status: Time Limit Exceeded

Solution code:
S = input()
a = 0
b = 0
c = 0
p = 1
mod = 1000000000+7
for C in S:
    if C == "?":
        c = 3*c+b
        b = 3*b+a
        a = 3*a+p
        p *= 3
    elif C == "A":
        a += p
    elif C == "B":
        b += a
    elif C == "C":
        c += b
    a %= mod
    b %= mod
    c %= mod
print(c)

Submission status: Time Limit Exceeded

Solution code:
S = input()
a = 0
b = 0
c = 0
p = 1
mod = 1000000000+7
for C in S:
    if C == "?":
        c = 3*c+b
        b = 3*b+a
        a = 3*a+p
        p *= 3
    if C == "A":
        a += p
    if C == "B":
        b += a
    if C == "C":
        c += b
    a %= mod
    b %= mod
    c %= mod
print(c)

Submission status: Time Limit Exceeded

Solution code:
s = input()
mod = 1000000007
a = 0
mae = 0
usi = s.count("?")
c = s.count("C")
ans = 0
for i in range(len(s)):
  if s[i] == "B":
    ans += (a*c*(3**(usi+mae)))%mod+(mae*c*(3**(mae-1+usi)))%mod+(usi*a*(3**(mae-1+usi)))%mod+(usi*mae*(3**(mae-2+usi)))%mod
  if s[i] == "?":
    usi -= 1
    ans += (a*c*(3**(usi+mae)))%mod+(mae*c*(3**(mae-1+usi)))%mod+(usi*a*(3**(mae-1+usi)))%mod+(usi*mae*(3**(mae-2+usi)))%mod
    mae +=1
  if s[i] == "A":
    a +=1
  if s[i] == "C":
    c -=1
print(int(ans%mod))

Submission status: Time Limit Exceeded

Solution code:
S = input()
L = len(S)
Q = 10**9 + 7
anum = [ 0 for _ in range(L+1)]
#bnum = [ 0 for _ in range(L+1)]
cnum = [ 0 for _ in range(L+1)]
hnum = [ 0 for _ in range(L+1)]
for i in range(1,L+1):
    if S[i-1] == 'A':
        anum[i] = anum[i-1] + 1
#        bnum[i] = bnum[i-1]
        cnum[i] = cnum[i-1]
        hnum[i] = hnum[i-1]
    elif S[i-1] == 'B':
        anum[i] = anum[i-1]
#        bnum[i] = bnum[i-1] + 1
        cnum[i] = cnum[i-1]
        hnum[i] = hnum[i-1]
    elif S[i-1] == 'C':
        anum[i] = anum[i-1]
#        bnum[i] = bnum[i-1]
        cnum[i] = cnum[i-1] + 1
        hnum[i] = hnum[i-1]
    else:
        anum[i] = anum[i-1]
#        bnum[i] = bnum[i-1]
        cnum[i] = cnum[i-1]
        hnum[i] = hnum[i-1] + 1

ans = 0
czen = cnum[L]
hzen = hnum[L] 
for i in range(1,L+1):
    if S[i-1] == 'B' or S[i-1] == '?':
        A = ((anum[i-1]*(3**hnum[i-1]))%Q + (hnum[i-1]*(3**(hnum[i-1]-1)))%Q)%Q
        C = (((czen - cnum[i])*(3**(hzen - hnum[i])))%Q + ((hzen - hnum[i])*(3**(hzen - hnum[i]-1)))%Q)%Q
        K = (A*C)%Q
        ans = (ans + K)%Q
print(int(ans))

Submission status: Time Limit Exceeded

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

mod = 10 ** 9 + 7
A, AB, ABC, ALL = 0, 0, 0, 1
for s in S:
    if s == "A":
        A += ALL

    if s == "B":
        AB += A

    if s == "C":
        ABC += AB

    if s == "?":
        ABC = ABC * 3 + AB
        AB = AB * 3 + A
        A = A * 3 + ALL
        ALL *= 3

print(ABC % mod)

Submission status: Time Limit Exceeded

Solution code:
S = input()
L = len(S)
Q = 10**9 + 7
anum = [ 0 for _ in range(L+1)]
#bnum = [ 0 for _ in range(L+1)]
cnum = [ 0 for _ in range(L+1)]
hnum = [ 0 for _ in range(L+1)]
for i in range(1,L+1):
    if S[i-1] == 'A':
        anum[i] = anum[i-1] + 1
#        bnum[i] = bnum[i-1]
        cnum[i] = cnum[i-1]
        hnum[i] = hnum[i-1]
    elif S[i-1] == 'B':
        anum[i] = anum[i-1]
#        bnum[i] = bnum[i-1] + 1
        cnum[i] = cnum[i-1]
        hnum[i] = hnum[i-1]
    elif S[i-1] == 'C':
        anum[i] = anum[i-1]
#        bnum[i] = bnum[i-1]
        cnum[i] = cnum[i-1] + 1
        hnum[i] = hnum[i-1]
    else:
        anum[i] = anum[i-1]
#        bnum[i] = bnum[i-1]
        cnum[i] = cnum[i-1]
        hnum[i] = hnum[i-1] + 1

ans = 0
czen = cnum[L]
hzen = hnum[L] 
for i in range(1,L+1):
    if S[i-1] == 'B' or S[i-1] == '?':
        A = (anum[i-1]*(3**hnum[i-1]) + hnum[i-1]*(3**(hnum[i-1]-1)))%Q
        C = ((czen - cnum[i])*(3**(hzen - hnum[i])) + (hzen - hnum[i])*(3**(hzen - hnum[i]-1)))%Q
        K = (A*C)%Q
        ans = (ans + K)%Q
print(int(ans))

Submission status: Time Limit Exceeded

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

num_q = [0]
res = 0
for i in range(N):
    if S[i] == "?":
        res += 1
    num_q.append(res)

# それぞれi番目までのa,a-b,a-b-cの数
dp_a = [0]*(N+1)
dp_ab = [0]*(N+1)
dp_abc = [0]*(N+1)

for i in range(1,N+1):
    if S[i-1] == "A":
        dp_a[i] = dp_a[i-1] + 3**num_q[i-1]
        dp_ab[i] = dp_ab[i-1]
        dp_abc[i] = dp_abc[i-1]
        
    elif S[i-1] == "B":
        dp_a[i] = dp_a[i-1]
        dp_ab[i] = dp_ab[i-1] + dp_a[i-1]
        dp_abc[i] = dp_abc[i-1]
        
    elif S[i-1] == "C":
        dp_a[i] = dp_a[i-1]
        dp_ab[i] = dp_ab[i-1]
        dp_abc[i] = dp_abc[i-1] + dp_ab[i-1]
        
    elif S[i-1] == "?":
        dp_a[i] = dp_a[i-1] * 3 + 3**num_q[i-1]
        dp_ab[i] = dp_ab[i-1] * 3 + dp_a[i-1] 
        dp_abc[i] = dp_abc[i-1] * 3 + dp_ab[i-1]
        
    dp_a[i] %= mod
    dp_ab[i] %= mod
    dp_abc[i] %= mod
        
print(dp_abc[N])

Submission status: Time Limit Exceeded

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

mod=10**9+7


Asum=[0]*lens
#Bsum=[0]*lens
Csum=[0]*lens
qsum=[0]*lens

for i in range(lens):
    if S[i]=="A":
        Asum[i]=Asum[i-1]+1
        Csum[i]=Csum[i-1]
        qsum[i]=qsum[i-1]
    elif S[i]=="C":
        Asum[i]=Asum[i-1]
        Csum[i]=Csum[i-1]+1
        qsum[i]=qsum[i-1]
    elif S[i]=="?":
        Asum[i]=Asum[i-1]
        Csum[i]=Csum[i-1]
        qsum[i]=qsum[i-1]+1
    else:
        Asum[i]=Asum[i-1]
        Csum[i]=Csum[i-1]
        qsum[i]=qsum[i-1]        

CSUM=Csum[lens-1]
QSUM=qsum[lens-1]


count=0
for i in range(1,lens-1):
    if S[i]=="B":
        count+=Asum[i-1]*(CSUM-Csum[i])*(3**max(0,QSUM))%mod
        count+=Asum[i-1]*(QSUM-qsum[i])*(3**max(0,(QSUM-1)))%mod
        count+=qsum[i-1]*(CSUM-Csum[i])*(3**max(0,(QSUM-1)))%mod
        count+=qsum[i-1]*(QSUM-qsum[i])*(3**max(0,(QSUM-2)))%mod


    elif S[i]=="?":
        count+=Asum[i-1]*(CSUM-Csum[i])*(3**max(0,(QSUM-1)))%mod
        count+=Asum[i-1]*(QSUM-qsum[i])*(3**max(0,(QSUM-2)))%mod
        count+=qsum[i-1]*(CSUM-Csum[i])*(3**max(0,(QSUM-2)))%mod
        count+=qsum[i-1]*(QSUM-qsum[i])*(3**max(0,(QSUM-3)))%mod

print(count%mod)

Submission status: Time Limit Exceeded

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

mod=10**9+7


Asum=[0]*lens
#Bsum=[0]*lens
Csum=[0]*lens
qsum=[0]*lens

for i in range(lens):
    if S[i]=="A":
        Asum[i]=Asum[i-1]+1
        Csum[i]=Csum[i-1]
        qsum[i]=qsum[i-1]
    elif S[i]=="C":
        Asum[i]=Asum[i-1]
        Csum[i]=Csum[i-1]+1
        qsum[i]=qsum[i-1]
    elif S[i]=="?":
        Asum[i]=Asum[i-1]
        Csum[i]=Csum[i-1]
        qsum[i]=qsum[i-1]+1
    else:
        Asum[i]=Asum[i-1]
        Csum[i]=Csum[i-1]
        qsum[i]=qsum[i-1]        

CSUM=Csum[lens-1]
QSUM=qsum[lens-1]


count=0
for i in range(1,lens-1):
    if S[i]=="B":
        count+=Asum[i-1]*(CSUM-Csum[i])*(3**max(0,QSUM))%mod
        count+=Asum[i-1]*(QSUM-qsum[i])*(3**max(0,(QSUM-1)))%mod
        count+=qsum[i-1]*(CSUM-Csum[i])*(3**max(0,(QSUM-1)))%mod
        count+=qsum[i-1]*(QSUM-qsum[i])*(3**max(0,(QSUM-2)))%mod


    elif S[i]=="?":
        count+=Asum[i-1]*(CSUM-Csum[i])*(3**max(0,(QSUM-1)))%mod
        count+=Asum[i-1]*(QSUM-qsum[i])*(3**max(0,(QSUM-2)))%mod
        count+=qsum[i-1]*(CSUM-Csum[i])*(3**max(0,(QSUM-2)))%mod
        count+=qsum[i-1]*(QSUM-qsum[i])*(3**max(0,(QSUM-3)))%mod

        
    



#count=0
#for a in range(lens-2):
#    if S[a]=="A" or S[a]=="?":
#        for b in range(a+1,lens-1):
#            if S[b]=="B" or S[b]=="?":
#                for c in range(b+1,lens):
#                    if S[c]=="C" or S[c]=="?":
#                        count+=1
print(count%mod)

Submission status: Time Limit Exceeded

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

mod=10**9+7

Alist=[0]*lens
#Blist=[0]*lens
Clist=[0]*lens
qlist=[0]*lens

Asum=[0]*lens
#Bsum=[0]*lens
Csum=[0]*lens
qsum=[0]*lens

for i in range(lens):
    if S[i]=="A":
        Alist[i]=1
    #elif S[i]=="B":
    #    Blist[i]=1
    elif S[i]=="C":
        Clist[i]=1
    elif S[i]=="?":
        qlist[i]=1

    Asum[i]=Asum[i-1]+Alist[i]
    #Bsum[i]=Bsum[i-1]+Blist[i]
    Csum[i]=Csum[i-1]+Clist[i]
    qsum[i]=qsum[i-1]+qlist[i]

#ASUM=Asum[lens-1]
CSUM=Csum[lens-1]
QSUM=qsum[lens-1]


count=0
for i in range(1,lens-1):
    if S[i]=="B":
        count+=Asum[i-1]*(CSUM-Csum[i])*(3**max(0,QSUM))%mod
        count+=Asum[i-1]*(QSUM-qsum[i])*(3**max(0,(QSUM-1)))%mod
        count+=qsum[i-1]*(CSUM-Csum[i])*(3**max(0,(QSUM-1)))%mod
        count+=qsum[i-1]*(QSUM-qsum[i])*(3**max(0,(QSUM-2)))%mod


    elif S[i]=="?":
        count+=Asum[i-1]*(CSUM-Csum[i])*(3**max(0,(QSUM-1)))%mod
        count+=Asum[i-1]*(QSUM-qsum[i])*(3**max(0,(QSUM-2)))%mod
        count+=qsum[i-1]*(CSUM-Csum[i])*(3**max(0,(QSUM-2)))%mod
        count+=qsum[i-1]*(QSUM-qsum[i])*(3**max(0,(QSUM-3)))%mod

        
    



#count=0
#for a in range(lens-2):
#    if S[a]=="A" or S[a]=="?":
#        for b in range(a+1,lens-1):
#            if S[b]=="B" or S[b]=="?":
#                for c in range(b+1,lens):
#                    if S[c]=="C" or S[c]=="?":
#                        count+=1
print(count%mod)

Submission status: Time Limit Exceeded

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

mod=10**9+7

Alist=[0]*lens
Blist=[0]*lens
Clist=[0]*lens
qlist=[0]*lens

Asum=[0]*lens
Bsum=[0]*lens
Csum=[0]*lens
qsum=[0]*lens

for i in range(lens):
    if S[i]=="A":
        Alist[i]=1
    elif S[i]=="B":
        Blist[i]=1
    elif S[i]=="C":
        Clist[i]=1
    elif S[i]=="?":
        qlist[i]=1

    Asum[i]=Asum[i-1]+Alist[i]
    Bsum[i]=Bsum[i-1]+Blist[i]
    Csum[i]=Csum[i-1]+Clist[i]
    qsum[i]=qsum[i-1]+qlist[i]

ASUM=Asum[lens-1]
CSUM=Csum[lens-1]
QSUM=qsum[lens-1]


count=0
for i in range(1,lens-1):
    if S[i]=="B":
        count+=Asum[i-1]*(CSUM-Csum[i])*(3**max(0,QSUM))%mod
        count+=Asum[i-1]*(QSUM-qsum[i])*(3**max(0,(QSUM-1)))%mod
        count+=qsum[i-1]*(CSUM-Csum[i])*(3**max(0,(QSUM-1)))%mod
        count+=qsum[i-1]*(QSUM-qsum[i])*(3**max(0,(QSUM-2)))%mod


    elif S[i]=="?":
        count+=Asum[i-1]*(CSUM-Csum[i])*(3**max(0,(QSUM-1)))%mod
        count+=Asum[i-1]*(QSUM-qsum[i])*(3**max(0,(QSUM-2)))%mod
        count+=qsum[i-1]*(CSUM-Csum[i])*(3**max(0,(QSUM-2)))%mod
        count+=qsum[i-1]*(QSUM-qsum[i])*(3**max(0,(QSUM-3)))%mod

print(count%mod)

Submission status: Time Limit Exceeded

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

mod=10**9+7

Alist=[0]*lens
Blist=[0]*lens
Clist=[0]*lens
qlist=[0]*lens

for i in range(lens):
    if S[i]=="A":
        Alist[i]=1
    elif S[i]=="B":
        Blist[i]=1
    elif S[i]=="C":
        Clist[i]=1
    elif S[i]=="?":
        qlist[i]=1


Asum=[0]*lens
Bsum=[0]*lens
Csum=[0]*lens
qsum=[0]*lens

for i in range(lens):
    Asum[i]=Asum[i-1]+Alist[i]
    Bsum[i]=Bsum[i-1]+Blist[i]
    Csum[i]=Csum[i-1]+Clist[i]
    qsum[i]=qsum[i-1]+qlist[i]

ASUM=Asum[lens-1]
CSUM=Csum[lens-1]
QSUM=qsum[lens-1]


count=0
for i in range(1,lens-1):
    if S[i]=="B":
        count+=Asum[i-1]*(CSUM-Csum[i])*(3**max(0,QSUM))%mod
        count+=Asum[i-1]*(QSUM-qsum[i])*(3**max(0,(QSUM-1)))%mod
        count+=qsum[i-1]*(CSUM-Csum[i])*(3**max(0,(QSUM-1)))%mod
        count+=qsum[i-1]*(QSUM-qsum[i])*(3**max(0,(QSUM-2)))%mod


    if S[i]=="?":
        count+=Asum[i-1]*(CSUM-Csum[i])*(3**max(0,(QSUM-1)))%mod
        count+=Asum[i-1]*(QSUM-qsum[i])*(3**max(0,(QSUM-2)))%mod
        count+=qsum[i-1]*(CSUM-Csum[i])*(3**max(0,(QSUM-2)))%mod
        count+=qsum[i-1]*(QSUM-qsum[i])*(3**max(0,(QSUM-3)))%mod

        
    



#count=0
#for a in range(lens-2):
#    if S[a]=="A" or S[a]=="?":
#        for b in range(a+1,lens-1):
#            if S[b]=="B" or S[b]=="?":
#                for c in range(b+1,lens):
#                    if S[c]=="C" or S[c]=="?":
#                        count+=1
print(count%mod)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7
s = input()

cumsum = {}
for key in ['A', 'B', 'C', '?']:
    cumsum[key] = [0]*(len(s)+1)
for i, ss in enumerate(s):
    for key in cumsum.keys():
        if key == ss:
            cumsum[key][i+1] = cumsum[key][i]+1
        else:
            cumsum[key][i+1] = cumsum[key][i]

ans = 0
for i in range(1, len(s)-1):
    if s[i] == 'A' or s[i] == 'C':
        continue
    
    n_a = cumsum['A'][i]
    n_c = cumsum['C'][-1] - cumsum['C'][i+1]
    n_q_left = cumsum['?'][i]
    n_q_right = cumsum['?'][-1] - cumsum['?'][i+1]

    n_left = n_a*pow(3, n_q_left) + n_q_left*pow(3, max(n_q_left-1, 0))
    n_right = n_c*pow(3, n_q_right) + n_q_right*pow(3, max(n_q_right-1, 0))
    ans += n_left*n_right

print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
S = input()


MOD = 10**9 + 7

# time complexity: O(|S|)
def focus_on_B():
    cuml = [[0] * 3 for _ in range(len(S))]
    num_A = num_C = num_q = 0
    for i, char in enumerate(S):
        if char == "A":
            num_A += 1
        elif char == "C":
            num_C += 1
        elif char == "?":
            num_q += 1
        cuml[i][0] = num_A
        cuml[i][1] = num_C
        cuml[i][2] = num_q

    num_combinations = 0
    for i in range(1, len(S) - 1):
        if S[i] in {"B", "?"}:
            A_L = cuml[i-1][0]
            Q_L = cuml[i-1][2]
            C_R = cuml[-1][1] - cuml[i][1]
            Q_R = cuml[-1][2] - cuml[i][2]
            left_pow = 3**Q_L
            right_pow = 3**Q_R
            num_combinations += (A_L * left_pow + Q_L * left_pow//3) * (C_R * right_pow + Q_R * right_pow//3)
            if num_combinations >= MOD:
                num_combinations %= MOD
    print(num_combinations)

focus_on_B()

Submission status: Time Limit Exceeded

Solution code:
S = input()


MOD = 10**9 + 7



# time complexity: O(|S|)
def focus_on_B():
    cuml = [[0] * 3 for _ in range(len(S))]
    num_A = num_C = num_q = 0
    for i, char in enumerate(S):
        if char == "A":
            num_A += 1
        elif char == "C":
            num_C += 1
        elif char == "?":
            num_q += 1
        cuml[i][0] = num_A
        cuml[i][1] = num_C
        cuml[i][2] = num_q

    num_combinations = 0
    for i in range(1, len(S) - 1):
        if S[i] in {"B", "?"}:
            A_L = cuml[i-1][0]
            Q_L = cuml[i-1][2]
            C_R = cuml[-1][1] - cuml[i][1]
            Q_R = cuml[-1][2] - cuml[i][2]
            left_pow = 3**Q_L
            right_pow = 3**Q_R
            num_combinations += (A_L * left_pow + Q_L * left_pow//3) * (C_R * right_pow + Q_R * right_pow//3)
            num_combinations %= MOD
        else:
            continue
    print(num_combinations)

focus_on_B()

Submission status: Time Limit Exceeded

Solution code:
S = input()


MOD = 10**9 + 7

# time complexity: O(|S|)
def focus_on_B():
    char_to_idx = {"A": 0,
                     "C": 1,
                     "?": 2}

    cuml = [[0] * 3 for _ in range(len(S))]
    num_A = num_C = num_q = 0
    for i, char in enumerate(S):
        if char == "A":
            num_A += 1
        elif char == "C":
            num_C += 1
        elif char == "?":
            num_q += 1
        cuml[i][0] = num_A
        cuml[i][1] = num_C
        cuml[i][2] = num_q

    num_combinations = 0
    for i in range(1, len(S) - 1):
        if S[i] in {"B", "?"}:
            A_L = cuml[i-1][0]
            Q_L = cuml[i-1][2]
            C_R = cuml[-1][1] - cuml[i][1]
            Q_R = cuml[-1][2] - cuml[i][2]
            left_pow = 3**Q_L
            right_pow = 3**Q_R
            num_combinations += (A_L * left_pow + Q_L * left_pow//3) * (C_R * right_pow + Q_R * right_pow//3)
            num_combinations %= MOD
        else:
            continue
    print(num_combinations)


focus_on_B()

Submission status: Time Limit Exceeded

Solution code:
S = input()


MOD = 10**9 + 7

# time complexity: O(|S|)
def focus_on_B(S):
    cuml = {"A": [], 
            "C": [],
            "?": []}
    current_nums = {"A": 0,
                    "C": 0,
                    "?": 0}
    for char in S:
        if char in cuml.keys():
            current_nums[char] += 1
        for key in cuml.keys():
            cuml[key].append(current_nums[key])
    assert len(cuml['A']) == len(S)

    # num_combinations[i]: i番目をBとした時に、可能な組み合わせの数
    num_combinations = [0] * len(S)
    for i in range(1, len(S) - 1):
        if S[i] in {"B", "?"}:
            A_L = cuml["A"][i-1]
            Q_L = cuml["?"][i-1]
            C_R = cuml["C"][-1] - cuml["C"][i]
            Q_R = cuml["?"][-1] - cuml["?"][i]
            num_combinations[i] = (A_L * 3**Q_L + Q_L * int(3**(Q_L - 1)))\
                                * (C_R * 3**Q_R + Q_R * int(3**(Q_R - 1)))
            num_combinations[i] %= MOD
        else:
            continue
    print(sum(num_combinations) % MOD)

focus_on_B(S)

Submission status: Time Limit Exceeded

Solution code:
S = input()


MOD = 10**9 + 7

# time complexity: O(|S|)
def dp(S):
    dp = [[0] * 4 for _ in range(len(S) + 1)]
    dp[len(S)][3] = 1
    for i in range(len(S))[::-1]:
        dp[i][3] = 3 * dp[i + 1][3] if S[i] == "?" else dp[i + 1][3]
        dp[i][3] %= MOD
        if S[i] == "?":
            dp[i][0] = (3 * dp[i + 1][0] + dp[i + 1][1]) % MOD
            dp[i][1] = (3 * dp[i + 1][1] + dp[i + 1][2]) % MOD
            dp[i][2] = (3 * dp[i + 1][2] + dp[i + 1][3]) % MOD
        else:
            dp[i][0] = (dp[i + 1][0] + int(S[i] == "A") * dp[i + 1][1]) % MOD
            dp[i][1] = (dp[i + 1][1] + int(S[i] == "B") * dp[i + 1][2]) % MOD
            dp[i][2] = (dp[i + 1][2] + int(S[i] == "C") * dp[i + 1][3]) % MOD
    print(dp[0][0])


# time complexity: O(|S|)
def focus_on_B(S):
    cuml = {"A": [], 
            "C": [],
            "?": []}
    current_nums = {"A": 0,
                    "C": 0,
                    "?": 0}
    for char in S:
        if char in cuml.keys():
            current_nums[char] += 1
        for key in cuml.keys():
            cuml[key].append(current_nums[key])
    assert len(cuml['A']) == len(S)

    # num_combinations[i]: i番目をBとした時に、可能な組み合わせの数
    num_combinations = [0] * len(S)
    for i in range(1, len(S) - 1):
        if S[i] in {"B", "?"}:
            A_L = cuml["A"][i-1]
            Q_L = cuml["?"][i-1]
            C_R = cuml["C"][-1] - cuml["C"][i]
            Q_R = cuml["?"][-1] - cuml["?"][i]
            num_combinations[i] = (A_L * 3**Q_L + Q_L * int(3**(Q_L - 1)))\
                                * (C_R * 3**Q_R + Q_R * int(3**(Q_R - 1)))
            num_combinations[i] %= MOD
        else:
            continue
    print(sum(num_combinations) % MOD)

focus_on_B(S)

Submission status: Time Limit Exceeded

Solution code:
S = input()
n = len(S)
mod = (10**9 + 7)

A = [0] * n
C = [0] * n
Q = [0] * n
Bi = []
Qi = []

for i, s in enumerate(S):
    if s == 'A':
        A[i] = 1
    elif s == 'B':
        Bi.append(i)
    elif s == 'C':
        C[i] = 1
    else:
        Q[i] = 1
        Qi.append(i)

for i in range(1, n):
    A[i] += A[i - 1]
    C[i] += C[i - 1]
    Q[i] += Q[i - 1]

def mod_pow(x, n, mod):
    if n == 0: return 1
    d, m = n >> 1, n & 1
    p = mod_pow(x, d, mod)
    return (p * p * (x if m else 1)) % mod

from itertools import chain
ans = 0
for b in chain(Bi, Qi):
    if b == 0 or n - 1 <= b: continue
    ai = A[b - 1]
    qa = Q[b - 1]
    a = (ai * mod_pow(3, qa, mod))
    if qa > 0:
        a += (mod_pow(3, qa - 1, mod) * qa)

    lc = C[n - 1] - C[b]
    lqc = Q[n - 1] - Q[b]
    c = (lc * mod_pow(3, lqc, mod))
    if lqc > 0:
        c += (mod_pow(3, lqc - 1, mod) * lqc)
    
    ans = (ans + (a * c)) % mod

print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
S = input()
n = len(S)
mod = (10**9 + 7)

A = [0] * n
C = [0] * n
Q = [0] * n
Bi = []
Qi = []

for i, s in enumerate(S):
    if s == 'A':
        A[i] = 1
    elif s == 'B':
        Bi.append(i)
    elif s == 'C':
        C[i] = 1
    else:
        Q[i] = 1
        Qi.append(i)

for i in range(1, n):
    A[i] += A[i - 1]
    C[i] += C[i - 1]
    Q[i] += Q[i - 1]

def mod_pow(x, n, mod):
    if n == 0: return 1
    d, m = n >> 1, n & 1
    p = mod_pow(x, d, mod)
    return (p * p * (x if m else 1))

from itertools import chain
ans = 0
for b in chain(Bi, Qi):
    if b == 0 or n - 1 <= b: continue
    ai = A[b - 1]
    qa = Q[b - 1]
    a = (ai * mod_pow(3, qa, mod))
    if qa > 0:
        a += (mod_pow(3, qa - 1, mod) * qa)

    lc = C[n - 1] - C[b]
    lqc = Q[n - 1] - Q[b]
    c = (lc * mod_pow(3, lqc, mod))
    if lqc > 0:
        c += (mod_pow(3, lqc - 1, mod) * lqc)
    
    ans += (a * c) % mod

print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
S = input()
n = len(S)
mod = (10**9 + 7)

A = [0] * n
C = [0] * n
Q = [0] * n
Bi = []
Qi = []

for i, s in enumerate(S):
    if s == 'A':
        A[i] = 1
    elif s == 'B':
        Bi.append(i)
    elif s == 'C':
        C[i] = 1
    else:
        Q[i] = 1
        Qi.append(i)

for i in range(1, n):
    A[i] += A[i - 1]
    C[i] += C[i - 1]
    Q[i] += Q[i - 1]

def mod_pow(x, n, mod):
    if n == 0: return 1
    d, m = n >> 1, n & 1
    p = mod_pow(x, d, mod)
    return (p * p * (x if m else 1)) % mod

from itertools import chain
ans = 0
for b in chain(Bi, Qi):
    if b == 0 or n - 1 <= b: continue
    ai = A[b - 1]
    qa = Q[b - 1]
    a = (ai * mod_pow(3, qa, mod))
    if qa > 0:
        a += (mod_pow(3, qa - 1, mod) * qa)

    lc = C[n - 1] - C[b]
    lqc = Q[n - 1] - Q[b]
    c = (lc * mod_pow(3, lqc, mod))
    if lqc > 0:
        c += (mod_pow(3, lqc - 1, mod) * lqc)
    
    ans += (a * c) % mod

print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
S = input()
n = len(S)
mod = (10**9 + 7)

A = [0] * n
C = [0] * n
Q = [0] * n
Bi = []
Qi = []

for i, s in enumerate(S):
    if s == 'A':
        A[i] = 1
    elif s == 'B':
        Bi.append(i)
    elif s == 'C':
        C[i] = 1
    else:
        Q[i] = 1
        Qi.append(i)

for i in range(1, n):
    A[i] += A[i - 1]
    C[i] += C[i - 1]
    Q[i] += Q[i - 1]

def mod_pow(x, n, mod):
    if n == 0: return 1
    d, m = divmod(n, 2)
    p = mod_pow(x, d, mod)
    return (p * p * (x if m else 1)) % mod

from itertools import chain
ans = 0
for b in chain(Bi, Qi):
    if b == 0 or n - 1 <= b: continue
    ai = A[b - 1]
    qa = Q[b - 1]
    a = (ai * mod_pow(3, qa, mod)) % mod
    if qa > 0:
        a += (mod_pow(3, qa - 1, mod) * qa) % mod

    ci = C[b]
    qc = Q[b]
    lc = C[n - 1] - ci
    lqc = Q[n - 1] - qc
    c = (lc * mod_pow(3, lqc, mod)) % mod
    if lqc > 0:
        c += (mod_pow(3, lqc - 1, mod) * lqc) % mod
    
    ans += (a * c) % mod

print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:

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

A = [0] * len(S)
C = [0] * len(S)
Q = [0] * len(S)
Bi = []
Qi = []

for i, s in enumerate(S):
    if s == 'A':
        A[i] = 1
    elif s == 'B':
        Bi.append(i)
    elif s == 'C':
        C[i] = 1
    else:
        Q[i] = 1
        Qi.append(i)

def acc(l):
    for i in range(1, len(l)):
        l[i] += l[i - 1]
acc(A)
acc(C)
acc(Q)

def pow(x, n, mod):
    if n == 0: return 1
    d, m = divmod(n, 2)
    p = pow(x, d, mod)
    return (p * p * (x if m else 1)) % mod

from itertools import chain
ans = 0
for b in chain(Bi, Qi):
    if b == 0 or n - 1 <= b: continue
    ai = A[b - 1]
    qa = Q[b - 1]
    a = (ai * (3 ** qa)) % mod
    if qa > 0:
        a += (pow(3, qa - 1, mod) * qa) % mod

    ci = C[b]
    qc = Q[b]
    lc = C[n - 1] - ci
    lqc = Q[n - 1] - qc
    c = (lc * (3 ** lqc)) % mod
    if lqc > 0:
        c += (pow(3, lqc - 1, mod) * lqc) % mod
    
    ans += (a * c) % mod

print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
S = input()
p = 10 ** 9 + 7
DP = [0, 0, 0, 1]
dp = [0] * 4
for i in range(len(S) - 1, -1, -1):
  for j in range(3, -1, -1):
    if j == 3:
      dp[j] = DP[3] * (3 if S[i] == '?' else 1) % p
    else:
      dp[j] = DP[j + 1] * (1 if S[i] == chr(65 + j) or S[i] == '?' else 0)
      dp[j] += DP[j] * (3 if S[i] == '?' else 1)
      dp[j] % p
  DP = [x for x in dp]
print(DP[0] % p)