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()
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)

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 += (3 ** (qa - 1) * 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 += (3 ** (lqc - 1) * lqc) % mod
    
    ans += (a * c) % mod

print(ans % mod)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
S = input()
p = 10 ** 9 + 7
DP = [0, 0, 0, 1]
for i in range(len(S) - 1, -1, -1):
  dp = [0] * 4
  for j in range(3, -1, -1):
    if j == 3:
      dp[j] = DP[3] * (3 if S[i] == '?' else 1)
    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)

Submission status: Time Limit Exceeded

Solution code:
S = input()
p = 10 ** 9 + 7
C = [1 for i in range(S.count('?') + 1)]
for i in range(1, len(C)):
  C[i] = C[i - 1] * i % p
Ci = [c for c in C]
Ci[-1] = pow(C[-1], p - 2, p)
for i in range(1, len(C) - 1):
  Ci[len(C) - i - 1] = Ci[len(C) - i] * (len(C) - i) % p
def comb(*A):
  c = C[sum(A)]
  for a in A:
    c *= Ci[a]
  return c % p
posB = []
posQ = []
for i, s in enumerate(S):
  if s == 'B':
    posB.append(i)
  elif s == '?':
    posQ.append(i)
cnt = 0
for b in sorted(posB + posQ):
  cntA = S[:b].count('A')
  cntAQ = S[:b].count('?')
  cntC = S[b + 1:].count('C')
  cntCQ = S[b + 1:].count('?')
  a = 0
  for ai in range(cntAQ + 1):
    a += (cntA + ai) * comb(ai, cntAQ - ai) * (2 ** (cntAQ - ai)) % p
  c = 0
  for ci in range(cntCQ + 1):
    c += (cntC + ci) * comb(ci, cntCQ - ci) * (2 ** (cntCQ - ci)) % p
  cnt += (a * c) % p
print(cnt % p)

Submission status: Time Limit Exceeded

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

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

import bisect
ans = 0
for b in B + Q:
    ai = bisect.bisect_left(A, b)
    qa = bisect.bisect_left(Q, b)
    a = (ai * (3 ** qa)) % mod
    if qa > 0:
        a += (3 ** (qa - 1) * qa) % mod

    ci = bisect.bisect_right(C, b)
    qc = bisect.bisect_right(Q, b)
    lc = len(C) - ci
    lqc = len(Q) - qc
    c = (lc * (3 ** lqc)) % mod
    if lqc > 0:
        c += (3 ** (lqc - 1) * lqc) % mod
    
    ans += (a * c) % mod

print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
S = input()
A,B,C,Q = [], [], [], []
for i, s in enumerate(S):
    if s == 'A':
        A.append(i)
    elif s == 'B':
        B.append(i)
    elif s == 'C':
        C.append(i)
    else:
        Q.append(i)

import bisect
ans = 0
for b in B + Q:
    ai = bisect.bisect_left(A, b)
    qa = bisect.bisect_left(Q, b)
    a = ai * (3 ** qa)
    if qa > 0:
        a += 3 ** (qa - 1) * qa

    ci = bisect.bisect_right(C, b)
    qc = bisect.bisect_right(Q, b)
    lc = len(C) - ci
    lqc = len(Q) - qc
    c = lc * (3 ** lqc)
    if lqc > 0:
        c += 3 ** (lqc - 1) * lqc
    
    ans += a * c

print(ans % (10**9 + 7))

Submission status: Time Limit Exceeded

Solution code:
s = input()

dp1 = {'A': 0, 'AB': 0, 'ABC': 0}
dp2 = {'A': 0, 'AB': 0, 'ABC': 0}

c = 1000000000 + 7
n = len(s)
count = 0
for i in range(n):
    #dp2 = {'A': 0, 'AB': 0, 'ABC': 0}

    # if s[i] == '?':
    #     dp2['A'] = dp1['A']*3 + (3**count)
    # elif s[i] == 'A':
    #     dp2['A'] = dp1['A'] + (3**count)
    # else:
    #     dp2['A'] = dp1['A']
    #
    # if s[i] == '?':
    #     dp2['AB'] = dp1['AB']*3 + dp1['A']
    # elif s[i] == 'B':
    #     dp2['AB'] = dp1['AB'] + dp1['A']
    # else:
    #     dp2['AB'] = dp1['AB']
    #
    # if s[i] == '?':
    #     dp2['ABC'] = dp1['ABC']*3 + dp1['AB']
    # elif s[i] == 'C':
    #     dp2['ABC'] = dp1['ABC'] + dp1['AB']
    # else:
    #     dp2['ABC'] = dp1['ABC']
    #
    # if s[i] == '?':
    #     count += 1

    if s[i] == '?':
        dp2['A'] = dp1['A']*3 + (3**count)
        dp2['AB'] = dp1['AB']*3 + dp1['A']
        dp2['ABC'] = dp1['ABC']*3 + dp1['AB']
        count += 1
    elif s[i] == 'A':
        dp2['A'] = dp1['A'] + (3**count)
        dp2['AB'] = dp1['AB']
        dp2['ABC'] = dp1['ABC']
    elif s[i] == 'B':
        dp2['A'] = dp1['A']
        dp2['AB'] = dp1['AB'] + dp1['A']
        dp2['ABC'] = dp1['ABC']
    elif s[i] == 'C':
        dp2['A'] = dp1['A']
        dp2['AB'] = dp1['AB']
        dp2['ABC'] = dp1['ABC'] + dp1['AB']

    # for j in dp2.keys():
    #     dp2[j] = dp2[j] % c\
    # dp1 = dp2

    dp1['ABC'] = dp2['ABC'] % c
    dp1['AB'] = dp2['AB'] % c
    dp1['A'] = dp2['A'] % c

    #print(i, dp1)

print(dp1['ABC'])

Submission status: Time Limit Exceeded

Solution code:
s = input()

dp1 = {'A': 0, 'AB': 0, 'ABC': 0}
dp2 = {'A': 0, 'AB': 0, 'ABC': 0}

c = 1000000000 + 7

count = 0
for i in range(len(s)):
    #dp2 = {'A': 0, 'AB': 0, 'ABC': 0}

    # if s[i] == '?':
    #     dp2['A'] = dp1['A']*3 + (3**count)
    # elif s[i] == 'A':
    #     dp2['A'] = dp1['A'] + (3**count)
    # else:
    #     dp2['A'] = dp1['A']
    #
    # if s[i] == '?':
    #     dp2['AB'] = dp1['AB']*3 + dp1['A']
    # elif s[i] == 'B':
    #     dp2['AB'] = dp1['AB'] + dp1['A']
    # else:
    #     dp2['AB'] = dp1['AB']
    #
    # if s[i] == '?':
    #     dp2['ABC'] = dp1['ABC']*3 + dp1['AB']
    # elif s[i] == 'C':
    #     dp2['ABC'] = dp1['ABC'] + dp1['AB']
    # else:
    #     dp2['ABC'] = dp1['ABC']
    #
    # if s[i] == '?':
    #     count += 1

    if s[i] == '?':
        dp2['A'] = dp1['A']*3 + (3**count)
        dp2['AB'] = dp1['AB']*3 + dp1['A']
        dp2['ABC'] = dp1['ABC']*3 + dp1['AB']
        count += 1
    elif s[i] == 'A':
        dp2['A'] = dp1['A'] + (3**count)
        dp2['AB'] = dp1['AB']
        dp2['ABC'] = dp1['ABC']
    elif s[i] == 'B':
        dp2['A'] = dp1['A']
        dp2['AB'] = dp1['AB'] + dp1['A']
        dp2['ABC'] = dp1['ABC']
    elif s[i] == 'C':
        dp2['A'] = dp1['A']
        dp2['AB'] = dp1['AB']
        dp2['ABC'] = dp1['ABC'] + dp1['AB']

    # for j in dp2.keys():
    #     dp2[j] = dp2[j] % c\
    # dp1 = dp2

    dp1['ABC'] = dp2['ABC'] % c
    dp1['AB'] = dp2['AB'] % c
    dp1['A'] = dp2['A'] % c

    #print(i, dp1)

print(dp1['ABC'])

Submission status: Time Limit Exceeded

Solution code:
s=input()
n=len(s)
c=[0 for i in range(n)]
d=[0 for i in range(n)]
bc=[0 for i in range(n)]
bd=[0 for i in range(n)]
dc=[0 for i in range(n)]
dd=[0 for i in range(n)]
if s[-1]=="C":
    c[-1]=1
if s[-1]=="?":
    d[-1]=1
for i in range(-2,-n-1,-1):
    c[i]=c[i+1]
    d[i]=d[i+1]
    bc[i]=bc[i+1]
    bd[i]=bd[i+1]
    dc[i]=dc[i+1]
    dd[i]=dd[i+1]
    if s[i]=="B":
        bc[i]+=c[i+1]
        bd[i]+=d[i+1]
    if s[i]=="C":
        c[i]+=1
    if s[i]=="?":
        d[i]+=1
        dc[i]+=c[i+1]
        dd[i]+=d[i+1]
mul=3**d[0]
res=0
for i in range(n-2):
    if s[i]=="A":
        res+=bc[i+1]*mul+(dc[i+1]+bd[i+1])*(mul//3)+dd[i+1]*(mul//9)
    if s[i]=="?":
        res+=bc[i+1]*(mul//3)+(dc[i+1]+bd[i+1])*(mul//9)+dd[i+1]*(mul//27)
    res%=1000000007
print(res)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
s = input()
count = 0
a, qa, c, qc = 0, 0, 0, 0
def calc(x, qx, y, qy):
    return ((3*x+qx) * (3*y+qy) * pow(3, qx+qy-2))
#x*y*pow(3,qx+qy)+qx*y*pow(3,qx+qy-1)+x*qy*pow(3,qx+qy-1)+qx*qy*pow(3,qx+qy-2)
for i in range(len(s)):
    if s[i] == 'C':
        c += 1
    elif s[i] == '?':
        qc += 1
    else:
        continue
for i in range(len(s)):
    if s[i] == 'A':
        a += 1
    elif s[i] == 'C':
        c -= 1
    elif s[i] == 'B':
        count += calc(a, qa, c, qc)
    else:
        qc -= 1
        count += calc(a, qa, c, qc)
        qa += 1
print(int(count) % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
s = input()

dp1 = {'A': 0, 'AB': 0, 'ABC': 0}

c = 1000000000 + 7

count = 0
for i in range(len(s)):
    dp2 = {'A': 0, 'AB': 0, 'ABC': 0}

    if s[i] == '?':
        dp2['A'] = dp1['A']*3 + (3**count)
    elif s[i] == 'A':
        dp2['A'] = dp1['A'] + (3**count)
    else:
        dp2['A'] = dp1['A']

    if s[i] == '?':
        dp2['AB'] = dp1['AB']*3 + dp1['A']
    elif s[i] == 'B':
        dp2['AB'] = dp1['AB'] + dp1['A']
    else:
        dp2['AB'] = dp1['AB']

    if s[i] == '?':
        dp2['ABC'] = dp1['ABC']*3 + dp1['AB']
    elif s[i] == 'C':
        dp2['ABC'] = dp1['ABC'] + dp1['AB']
    else:
        dp2['ABC'] = dp1['ABC']

    if s[i] == '?':
        count += 1

    # for j in dp2.keys():
    #     dp2[j] = dp2[j] % c\
    # dp1 = dp2
    dp1['ABC'] = dp2['ABC'] % c
    dp1['AB'] = dp2['AB'] % c
    dp1['A'] = dp2['A'] % c
    #print(i, dp1)

print(dp1['ABC'])

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from collections import defaultdict

S = input()

right = Counter(S)
left = defaultdict(int)

hatena = right["?"]

mod = pow(10,9)+7

POW = []
for i in range(hatena-3,hatena+1):
    POW.append(int(pow(3,i)))

ans = 0
for s in S:
    right[s] -=1
    leftA,rightC = left["A"],right["C"]
    leftH,rightH = left["?"],right["?"]
    if s=="B":
        ans = (ans + rightC*leftA*POW[3] + rightH*leftA*POW[2] \
        + rightC*leftH*POW[2] + rightH*leftH*POW[1])%mod
    if s=="?":
        ans = (ans + rightC*leftA*POW[2] + rightH*leftA*POW[1] \
        + rightC*leftH*POW[1] + rightH*leftH*POW[0])%mod
    left[s] +=1
    #print(right,left)
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()

dp1 = {'A': 0, 'AB': 0, 'ABC': 0}

c = 1000000000 + 7

count = 0
for i in range(len(s)):
    dp2 = {'A': 0, 'AB': 0, 'ABC': 0}

    if s[i] == '?':
        dp2['A'] = dp1['A']*3 + (3**count)
    elif s[i] == 'A':
        dp2['A'] = dp1['A'] + (3**count)
    else:
        dp2['A'] = dp1['A']

    if s[i] == '?':
        dp2['AB'] = dp1['AB']*3 + dp1['A']
    elif s[i] == 'B':
        dp2['AB'] = dp1['AB'] + dp1['A']
    else:
        dp2['AB'] = dp1['AB']

    if s[i] == '?':
        dp2['ABC'] = dp1['ABC']*3 + dp1['AB']
    elif s[i] == 'C':
        dp2['ABC'] = dp1['ABC'] + dp1['AB']
    else:
        dp2['ABC'] = dp1['ABC']

    if s[i] == '?':
        count += 1

    for j in dp2.keys():
        dp2[j] = dp2[j] % c
    dp1 = dp2
    #print(i, dp1)

print(dp1['ABC'])

Submission status: Time Limit Exceeded

Solution code:
s = input()

dp1 = {'A': 0, 'AB': 0, 'ABC': 0}

c = 1000000000 + 7

count = 0
for i in range(len(s)):
    dp2 = {'A': 0, 'AB': 0, 'ABC': 0}

    if s[i] == '?':
        dp2['A'] = dp1['A']*3 + (3**count)
    elif s[i] == 'A':
        dp2['A'] = dp1['A'] + (3**count)
    else:
        dp2['A'] = dp1['A']

    if s[i] == '?':
        dp2['AB'] = dp1['AB']*3 + dp1['A']
    elif s[i] == 'B':
        dp2['AB'] = dp1['AB'] + dp1['A']
    else:
        dp2['AB'] = dp1['AB']

    if s[i] == '?':
        dp2['ABC'] = dp1['ABC']*3 + dp1['AB']
    elif s[i] == 'C':
        dp2['ABC'] = dp1['ABC'] + dp1['AB']
    else:
        dp2['ABC'] = dp1['ABC']

    if s[i] == '?':
        count += 1

    for j in dp2.keys():
        dp2[j] = dp2[j] % c
    dp1 = dp2.copy()
    #print(i, dp1)

print(dp1['ABC'])

Submission status: Time Limit Exceeded

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

N = len(S)
A1,A2,A3,C1,C2,C3 = [1]*N,[0]*N,[1]*N,[1]*N,[0]*N,[1]*N
A4,C4 = [1]*N,[1]*N
a,aa = 0,0
c,cc = 0,0
for i in range(1,N):
    if S[i-1]=="A":
        a += 1
    if S[i-1]=="?":
        aa += 1
        A3[i] = A3[i-1]*3
    else:
        A3[i] = A3[i-1]
    A1[i],A2[i] = a,aa
    A4[i] = A3[i]//3 % mod
for i in range(1,N):
    if S[N-1-i+1]=="C":
        c += 1
    if S[N-1-i+1]=="?":
        cc += 1
        C3[N-1-i] = C3[N-1-i+1]*3
    else:
        C3[N-1-i] = C3[N-1-i+1]
    C1[N-1-i] = c
    C2[N-1-i] = cc
    C4[N-1-i] = C3[N-1-i]//3 % mod

Ans = 0
for i in range(1,N-1):
    if S[i]=="B" or S[i]=="?":
        ta,tc = 0,0
        if A2[i]==0:
            ta = A1[i]
        else:
            ta = (A4[i]*(A1[i]*3 + A2[i])) % mod 
        if C2[i]==0:
            tc = C1[i]
        else:
            tc = (C4[i]*(C1[i]*3 + C2[i])) % mod
        Ans += ta*tc
        Ans

print(Ans % mod)

Submission status: Time Limit Exceeded

Solution code:
s = input()
 
m = 1000000007
dp = [0] * 4
dp[0] = 1
 
for c in s:
    if c=='A':
        dp[1] += dp[0]
    elif c=='B':
        dp[2] += dp[1]
    elif c=='C':
        dp[3] += dp[2]
    elif c=='?':
        dp = [dp[0]*3, dp[0]+dp[1]*3, dp[1]+dp[2]*3, dp[2]+dp[3]*3]
print(dp[3]%m)

Submission status: Time Limit Exceeded

Solution code:
S = input()
def ABC(S):
    N = len(S)
    dp = [[0 for j in range(4)] for i in range(N+1)]
    model = 'ABC'
    for i in range(N, -1, -1):
        for j in range(3,-1,-1):
            if i == N and j == 3:
                dp[i][j] = 1
            elif i == N and j < 3:
                dp[i][j] = 0
            elif i < N and j == 3:
                if S[i] == '?':
                    dp[i][j] = 3 * dp[i+1][j]
                else:
                    dp[i][j] = dp[i+1][j]
            else:
                if S[i] == '?':
                    m1 = 3
                else:
                    m1 = 1
                if S[i] == '?' or S[i] == model[j]:
                    m2 = 1
                else:
                    m2 = 0
                dp[i][j] = m1 * dp[i+1][j] + m2 * dp[i+1][j+1]
    return dp[0][0] % (10**9 + 7)
print(ABC(S))

Submission status: Time Limit Exceeded

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

N = len(S)
A1,A2,A3,C1,C2,C3 = [1]*N,[0]*N,[1]*N,[1]*N,[0]*N,[1]*N
a,aa = 0,0
c,cc = 0,0
for i in range(1,N):
    if S[i-1]=="A":
        a += 1
    if S[i-1]=="?":
        aa += 1
        A3[i] = A3[i-1]*3
    else:
        A3[i] = A3[i-1]
    A1[i],A2[i] = a,aa
for i in range(1,N):
    if S[N-1-i+1]=="C":
        c += 1
    if S[N-1-i+1]=="?":
        cc += 1
        C3[N-1-i] = C3[N-1-i+1]*3
    else:
        C3[N-1-i] = C3[N-1-i+1]
    C1[N-1-i] = c
    C2[N-1-i] = cc

Ans = 0
for i in range(1,N-1):
    if S[i]=="B" or S[i]=="?":
        ta,tc = 0,0
        if A2[i]==0:
            ta = A1[i]
        else:
            ta = (A3[i]//3*(A1[i]*3 + A2[i])) % mod 
        if C2[i]==0:
            tc = C1[i]
        else:
            tc = (C3[i]//3*(C1[i]*3 + C2[i])) % mod
        Ans += ta*tc

print(Ans % mod)

Submission status: Time Limit Exceeded

Solution code:
S = input()
P = 10**9+7
d = [[0 for j in range(4)] for i in range(len(S)+1)]

d[len(S)][3] = 1
#d[len(S)][0--2] = 0
for i in range(len(S)-1,-1,-1):
	d[i][3] = (3 if S[i] == "?" else 1) * d[i+1][3]
	d[i][2] = (3 if S[i] == "?" else 1) * d[i+1][2]
	d[i][2] += (1 if S[i] == "C" or S[i] == "?" else 0) * d[i+1][3]
	d[i][1] = (3 if S[i] == "?" else 1) * d[i+1][1]
	d[i][1] += (1 if S[i] == "B" or S[i] == "?" else 0) * d[i+1][2]
	d[i][0] = (3 if S[i] == "?" else 1) * d[i+1][0]
	d[i][0] += (1 if S[i] == "A" or S[i] == "?" else 0) * d[i+1][1]
print(d[0][0] % P)

Submission status: Time Limit Exceeded

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

N = len(S)
A1,A2,A3,C1,C2,C3 = [1]*N,[1]*N,[1]*N,[1]*N,[1]*N,[1]*N
a,aa = 0,0
c,cc = 0,0
for i in range(1,N):
    if S[i-1]=="A":
        a += 1
    if S[i-1]=="?":
        aa += 1
        A3[i] = A3[i-1]*3
    else:
        A3[i] = A3[i-1]
    A1[i],A2[i] = a,aa
for i in range(1,N):
    if S[N-1-i+1]=="C":
        c += 1
    if S[N-1-i+1]=="?":
        cc += 1
        C3[N-1-i] = C3[N-1-i+1]*3
    else:
        C3[N-1-i] = C3[N-1-i+1]
    C1[N-1-i] = c
    C2[N-1-i] = cc

Ans = 0
for i in range(1,N-1):
    if S[i]=="B" or S[i]=="?":
        ta,tc = 0,0
        if A2[i]==0:
            ta = A1[i]
        else:
            ta = (A3[i]//3*(A1[i]*3 + A2[i])) % mod 
        if C2[i]==0:
            tc = C1[i]
        else:
            tc = (C3[i]//3*(C1[i]*3 + C2[i])) % mod
        Ans += ta*tc

print(Ans % mod)

Submission status: Time Limit Exceeded

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

N = len(S)
A1,A2,A3,C1,C2,C3 = [1]*N,[1]*N,[1]*N,[1]*N,[1]*N,[1]*N
a,aa = 0,0
c,cc = 0,0
for i in range(1,N):
    if S[i-1]=="A":
        a += 1
    if S[i-1]=="?":
        aa += 1
        A3[i] = A3[i-1]*3
    else:
        A3[i] = A3[i-1]
    A1[i],A2[i] = a,aa
for i in range(1,N):
    if S[N-1-i+1]=="C":
        c += 1
    if S[N-1-i+1]=="?":
        cc += 1
        C3[N-1-i] = C3[N-1-i+1]*3
    else:
        C3[N-1-i] = C3[N-1-i+1]
    C1[N-1-i] = c
    C2[N-1-i] = cc

Ans = 0
for i in range(1,N-1):
    if S[i]=="B" or S[i]=="?":
        ta,tc = 0,0
        if A2[i]==0:
            ta = A1[i]
        else:
            ta = (A3[i]*(A1[i]*3 + A2[i])//3) % mod 
        if C2[i]==0:
            tc = C1[i]
        else:
            tc = (C3[i]*(C1[i]*3 + C2[i])//3) % mod
        Ans += ta*tc

print(Ans % mod)

Submission status: Time Limit Exceeded

Solution code:
a = 0
ab = 0
abc = 0
r = 1
 
s = input()
 
for c in s:
    if c == "A":
        a += r
    elif c == "B":
        ab += a
    elif c == "C":
        abc += ab
    else:
        abc = abc * 3 + ab
        ab = ab * 3 + a
        a = a * 3 + r
        r *= 3
 
print(abc % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from collections import defaultdict

S = input()

right = Counter(S)
left = defaultdict(int)

hatena = right["?"]
#print(hatena)

mod = pow(10,9)+7

POW = []
for i in range(hatena-3,hatena+1):
    POW.append(int(pow(3,i)))

ans = 0
for s in S:
    right[s] -=1
    if s=="B":
        ans = (ans + right["C"]*left["A"]*POW[3] + right["?"]*left["A"]*POW[2] \
        + right["C"]*left["?"]*POW[2] + right["?"]*left["?"]*POW[1])%mod
        #print(s,ans)
    if s=="?":
        ans = (ans + right["C"]*left["A"]*POW[2] + right["?"]*left["A"]*POW[1] \
        + right["C"]*left["?"]*POW[1] + right["?"]*left["?"]*POW[0])%mod
        #print(s,ans)
    left[s] +=1
    #print(right,left)
    
print(ans)

Submission status: Time Limit Exceeded

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

N = len(S)
A1,A2,A3,C1,C2,C3 = [1]*N,[1]*N,[1]*N,[1]*N,[1]*N,[1]*N
a,aa = 0,0
c,cc = 0,0
for i in range(1,N):
    if S[i-1]=="A":
        a += 1
    if S[i-1]=="?":
        aa += 1
        A3[i] = A3[i-1]*3
    else:
        A3[i] = A3[i-1]
    A1[i],A2[i] = a,aa
for i in range(1,N):
    if S[N-1-i+1]=="C":
        c += 1
    if S[N-1-i+1]=="?":
        cc += 1
        C3[N-1-i] = C3[N-1-i+1]*3
    else:
        C3[N-1-i] = C3[N-1-i+1]
    C1[N-1-i] = c
    C2[N-1-i] = cc

Ans = 0
for i in range(1,N-1):
    if S[i]=="B" or S[i]=="?":
        ta,tc = 0,0
        if A2[i]==0:
            ta = A1[i]
        else:
            ta = A3[i]*A1[i] + A3[i]//3*A2[i]
            ta %= mod
        if C2[i]==0:
            tc = C1[i]
        else:
            tc = C3[i]*C1[i] + C3[i]//3*C2[i]
            tc %= mod
        Ans += ta*tc
        Ans %= mod

print(Ans)

Submission status: Time Limit Exceeded

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

a = [0]*len(s)
c = [0]*len(s)
lq = [0]*len(s)
rq = [0]*len(s)

for i in range(1, len(s)):
  if s[i-1]=="A":
    a[i] = a[i-1]+1
  else:
    a[i] = a[i-1]
  if s[i-1]=="?":
    lq[i] = lq[i-1]+1
  else:
    lq[i] = lq[i-1]
for i in range(len(s)-2, -1, -1):
  if s[i+1]=="C":
    c[i] = c[i+1]+1
  else:
    c[i] = c[i+1]
  if s[i+1]=="?":
    rq[i] = rq[i+1]+1
  else:
    rq[i] = rq[i+1]

ans = 0
for i in range(1, len(s)-1):
  if s[i]=="B" or s[i]=="?":
    ans += int((3*a[i]+lq[i])*(3*c[i]+rq[i])*3**(lq[i]+rq[i]-2))%MOD
print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
s = input()

m = 1000000007
dp = [0] * 4
dp[0] = 1

for c in s:
  if c=='A':
    dp[1] += dp[0]
  elif c=='B':
    dp[2] += dp[1]
  elif c=='C':
    dp[3] += dp[2]
  elif c=='?':
    dp = [dp[0]*3, dp[0]+dp[1]*3, dp[1]+dp[2]*3, dp[2]+dp[3]*3]

print(dp[3]%m)

Submission status: Time Limit Exceeded

Solution code:
s = input()

ans = 0

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

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]=='?':
        x = z[i][1]
        a = z[i][0]
        a1 = 3*a+x
        a2 = 3**(x-1)%(10**9+7)
        y = z[i][3]
        c = z[i][2]
        c1 = 3*c+y
        c2 = 3**(y-1)%(10**9+7)
        ans += (a1*a2*c1*c2)%(10**9+7)
    ans %=(10**9+7)

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from collections import defaultdict

S = input()

right = Counter(S)
left = defaultdict(int)

hatena = right["?"]
#print(hatena)

ans = 0
mod = pow(10,9)+7
for s in S:
    right[s] -=1
    if s=="B":
        ans = int(ans + right["C"]*left["A"]*pow(3,hatena) + right["?"]*left["A"]*pow(3,hatena-1) \
        + right["C"]*left["?"]*pow(3,hatena-1) + right["?"]*left["?"]*pow(3,hatena-2))%mod
        #print(s,ans)
    if s=="?":
        ans = int(ans + right["C"]*left["A"]*pow(3,hatena-1) + right["?"]*left["A"]*pow(3,hatena-2) \
        + right["C"]*left["?"]*pow(3,hatena-2) + right["?"]*left["?"]*pow(3,hatena-3))%mod
        #print(s,ans)
    left[s] +=1
    #print(right,left)
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()

ans = 0

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

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]=='?':
        x = z[i][1]
        a = z[i][0]
        a_ = ((3*a+x)*(3 ** (x-1))) % (10 ** 9 + 7)
        y = z[i][3]
        c = z[i][2]
        c_ = ((3*c+y)*(3**(y-1)))%(10**9+7)
        ans += (a_*c_)%(10**9+7)
    ans %=(10**9+7)

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
s = input()

ans = 0

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

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]=='?':
        x = z[i][1]
        a = z[i][0]
        a_ = ((3*a+x)*(3 ** (x-1))) % (10 ** 9 + 7)
        y = z[i][3]
        c = z[i][2]
        c_ = ((3*c+y)*(3**(y-1)))%(10**9+7)
        ans += (a_*c_)%(10**9+7)

ans %=(10**9+7)
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
mod = 1000000007

S = input()
L = len(S)
i = L-1
A = [0 for _ in range(L+1)]
C = [0 for _ in range(L+1)]
Q = [0 for _ in range(L+1)]
while i >= 0:
    Q[i] = Q[i+1]
    A[i] = A[i+1]
    C[i] = C[i+1]

    if S[i] == '?':
        Q[i] = Q[i+1] + 1
    else:
        Q[i] = Q[i+1]

    if S[i] == 'A':
        A[i] = A[i+1] + 1
    else:
        A[i] = A[i+1]
    if S[i] == 'C':
        C[i] = C[i+1] + 1
    else:
        C[i] = C[i+1]
    i -= 1

ans = 0
for i in range(L):
    if S[i] in ('B','?'):
        a = A[0] - A[i]
        qleft = Q[0] - Q[i]
        c = C[i+1]
        qright = Q[i+1]
        if qleft > 0:
            LEFT = a*3**qleft + qleft*3**(qleft-1)
        else: 
            LEFT = a*3**qleft
        if qright > 0:
            RIGHT = c*3**qright + qright*3**(qright-1)
        else:
            RIGHT = c*3**qright
        number = (LEFT * RIGHT)%mod
        ans = (ans + number)%mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
l = tuple(input())
n = len(l)
ABC_n = 0
BC_n = 0
C_n = 0
ha_n = 0

def kai(num):
    c = 1
    for i in range(num):
        c *= 3
        c %= 10**9 + 7
    return c



for i in range(n-1, -1, -1):
    car = l[i]
    if car == 'A':
        ABC_n += BC_n
        ABC_n = ABC_n % (10**9 + 7)
    elif car == 'B':
        BC_n += C_n
        BC_n = BC_n % (10**9 + 7)
    elif car == 'C':
        C_n += kai(ha_n)
        C_n = C_n % (10**9 + 7)
    else:
        ABC_n = 3*ABC_n +  BC_n
        ABC_n = ABC_n % (10**9 + 7)
        BC_n = 3*BC_n + C_n
        BC_n = BC_n % (10**9 + 7)
        c = kai(ha_n)
        C_n = 3*C_n  + c
        C_n = C_n % (10**9 + 7)
        ha_n += 1


print(ABC_n)

Submission status: Time Limit Exceeded

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

N = len(S)
A1,A2,C1,C2 = [1]*N,[0]*N,[1]*N,[0]*N
a,aa = 0,0
c,cc = 0,0
for i in range(1,N):
    if S[i-1]=="A":
        a += 1
    elif S[i-1]=="?":
        aa += 1
    A1[i],A2[i] = a,aa
for i in range(1,N):
    if S[N-1-i+1]=="C":
        c += 1
    elif S[N-1-i+1]=="?":
        cc += 1
    C1[N-1-i] = c
    C2[N-1-i] = cc

Ans = 0
for i in range(1,N-1):
    if S[i]=="B" or S[i]=="?":
        ta,tc = 0,0
        if A2[i]==0:
            ta = A1[i]
        else:
            ta = (3**A2[i])*A1[i] + 3**(A2[i]-1)*A2[i]
            if ta>mod:
                ta %= mod
        if C2[i]==0:
            tc = C1[i]
        else:
            tc = (3**C2[i])*C1[i] + 3**(C2[i]-1)*C2[i]
            if tc > mod:
                tc %= mod
        Ans += ta*tc
        if Ans > mod:
            Ans %= mod

print(Ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
S = input()
MOD = 10 ** 9 + 7
ans = 0
front = [0, 0, 0, 0]
back = [0, 0, 0, 0]
m = { 'A': 0, 'B': 1, 'C': 2, '?': 3 }
for c in S:
  back[m[c]] += 1

pow3 = [1]
for i in range(max(3, back[3])):
  pow3.append(pow3[-1] * 3)

for i in range(len(S)):
  c = S[i]
  back[m[c]] -= 1
  # Bの位置を固定
  if c == 'B' or c == '?':
    fbsum = front[3] + back[3]
    # ?を使わない
    ans += front[0] * back[2] * (pow3[fbsum])
    # Aだけ?をつかう
    ans += front[3] * back[2] * (pow3[fbsum - 1])
    # Cだけ?をつかう
    ans += front[0] * back[3] * (pow3[fbsum - 1])
    # 両方?をつかう
    ans += front[3] * back[3] * (pow3[fbsum - 2])
    ans %= MOD
  front[m[c]] += 1

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
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)