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 = list(str(input()))
n = len(s)

dl = {'A':0, 'C':0, '?':0}
dr = {'A':0, 'C':0, '?':0}

dls = []
drs = []

import copy

for i in range(n):
    if s[i] == 'A' or s[i] == 'C':
        dl[s[i]] += 1
    elif s[i] == 'B':
        dl_ = copy.copy(dl)
        dls.append(dl_)
    else:
        dl_ = copy.copy(dl)
        dls.append(dl_)
        dl[s[i]] += 1
    j = n - 1- i
    if s[j] == 'A' or s[j] == 'C':
        dr[s[j]] += 1
    elif s[j] == 'B':
        dr_ = copy.copy(dr)
        drs.append(dr_)
    else:
        dr_ = copy.copy(dr)
        drs.append(dr_)
        dr[s[j]] += 1

drs = list(reversed(drs))
#print(dls)
#print(drs)

ans = 0
mod = 10**9+7

def power(a, n, mod):
  bi=str(format(n,"b")) #2進数
  res=1
  for i in range(len(bi)):
    res=(res*res) %mod
    if bi[i]=="1":
      res=(res*a) %mod
  return res

for i in range(len(dls)):
    a = (dls[i]['A']*power(3, dls[i]['?'], mod) + dls[i]['?']*power(3, max(0, dls[i]['?']-1), mod))
    b = (drs[i]['C']*power(3, drs[i]['?'], mod) + drs[i]['?']*power(3, max(0, drs[i]['?']-1), mod))
    ans += (a*b)
    #print(ans)
ans %=mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = list(str(input()))
n = len(s)

dl = {'A':0, 'C':0, '?':0}
dr = {'A':0, 'C':0, '?':0}

dls = []
drs = []

import copy

for i in range(n):
    if s[i] == 'A' or s[i] == 'C':
        dl[s[i]] += 1
    elif s[i] == 'B':
        dl_ = copy.copy(dl)
        dls.append(dl_)
    else:
        dl_ = copy.copy(dl)
        dls.append(dl_)
        dl[s[i]] += 1
    j = n - 1- i
    if s[j] == 'A' or s[j] == 'C':
        dr[s[j]] += 1
    elif s[j] == 'B':
        dr_ = copy.copy(dr)
        drs.append(dr_)
    else:
        dr_ = copy.copy(dr)
        drs.append(dr_)
        dr[s[j]] += 1

drs = list(reversed(drs))
#print(dls)
#print(drs)

ans = 0
mod = 10**9+7

def power(a, n, mod):
  bi=str(format(n,"b")) #2進数
  res=1
  for i in range(len(bi)):
    res=(res*res) %mod
    if bi[i]=="1":
      res=(res*a) %mod
  return res

for i in range(len(dls)):
    a = (dls[i]['A']*power(3, dls[i]['?'], mod) + dls[i]['?']*power(3, max(0, dls[i]['?']-1), mod))%mod
    b = (drs[i]['C']*power(3, drs[i]['?'], mod) + drs[i]['?']*power(3, max(0, drs[i]['?']-1), mod))%mod
    ans += (a*b)%mod
    #print(ans)
ans %=mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#i文字目を見て，それより前のAの個数，ABの個数，ABCの個数を持っておく

S=input()
N=len(S)
dp=[0,0,0]

mod=10**9+7


count=0#?の数
for i in range(N):
    if S[i]=="A":
        dp[0]=(dp[0]+pow(3,count)) %mod
    elif S[i]=="B":
        dp[1]=(dp[1]+dp[0])%mod
    elif S[i]=="C":
        dp[2]=(dp[2]+dp[1])%mod
    else:
        dp[2]=(dp[2]*3+dp[1])%mod
        dp[1]=(dp[1]*3+dp[0])%mod
        dp[0]=(dp[0]*3+pow(3,count))%mod
        count+=1
        
print(dp[2]%mod)

Submission status: Time Limit Exceeded

Solution code:
#i文字目を見て，それより前のAの個数，ABの個数，ABCの個数を持っておく

S=input()
N=len(S)
dp=[0,0,0]

mod=10**9+7

p=[1]*(N+1)
for i in range(N):
    p[i+1]=p[i]*3


count=0#?の数
for i in range(N):
    if S[i]=="A":
        dp[0]=(dp[0]+p[count]) %mod
    elif S[i]=="B":
        dp[1]=(dp[1]+dp[0])%mod
    elif S[i]=="C":
        dp[2]=(dp[2]+dp[1])%mod
    else:
        dp[2]=(dp[2]*3+dp[1])%mod
        dp[1]=(dp[1]*3+dp[0])%mod
        dp[0]=(dp[0]*3+p[count])%mod
        count+=1
        
print(dp[2]%mod)

Submission status: Time Limit Exceeded

Solution code:
#i文字目を見て，それより前のAの個数，ABの個数，ABCの個数を持っておく

S=input()
N=len(S)
dp=[0,0,0]

mod=10**9+7

p=[1]*(N+1)
for i in range(N):
    p[i+1]=p[i]*3


count=0#?の数
for i in range(N):
    if S[i]=="A":
        dp[0]+=p[count]
    elif S[i]=="B":
        dp[1]+=dp[0]
    elif S[i]=="C":
        dp[2]+=dp[1]
    else:
        dp[2]=dp[2]*3+dp[1]
        dp[1]=dp[1]*3+dp[0]
        dp[0]=dp[0]*3+p[count]
        count+=1
        
print(dp[-1]%mod)

Submission status: Time Limit Exceeded

Solution code:
#i文字目を見て，それより前のAの個数，ABの個数，ABCの個数を持っておく

S=input()
N=len(S)
dp=[[0,0,0] for _ in range(N+1)]

mod=10**9+7

p=[1]*(N+1)
for i in range(N):
    p[i+1]=p[i]*3


count=0#?の数
for i in range(N):
    for j in range(3):
        dp[i+1][j]=dp[i][j]
    if S[i]=="A":
        dp[i+1][0]+=p[count]
    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][2]=dp[i][2]*3+dp[i][1]
        dp[i+1][1]=dp[i][1]*3+dp[i][0]
        dp[i+1][0]=dp[i][0]*3+p[count]
        count+=1
    for j in range(3):
        dp[i+1][j]%=mod
        
print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
S = input()

mod = 10**9+7
A = 0
AB = 0
ABC = 0
cnt = 0
for i in range(len(S)):
    if S[i] == "A":
        A += 3**cnt
        A %= mod
    elif S[i] == "B":
        AB += A
        AB %= mod
    elif S[i] == "C":
        ABC += AB
        ABC %= mod
    else:
        ABC = (3*ABC + AB) % mod
        AB = (3*AB + A) % mod
        A = (3*A + 3**cnt) % mod
        cnt += 1
        
        
print(ABC)

Submission status: Time Limit Exceeded

Solution code:
S = input()

mod = 10**9+7
A = 0
AB = 0
ABC = 0
cnt = 0
for i in range(len(S)):
    if S[i] == "A":
        A += 3**cnt
    elif S[i] == "B":
        AB += A
    elif S[i] == "C":
        ABC += AB
    else:
        ABC = (3*ABC + AB) % mod
        AB = (3*AB + A) % mod
        A = (3*A + 3**cnt) % mod
        cnt += 1
        
        
print(ABC%mod)

Submission status: Time Limit Exceeded

Solution code:
S = input()
N = len(S)
mod = 10**9+7
numofA = 0
numofAB = 0
numofABC = 0
numofquestion = 1
for i in range(N):
    if S[i] == "?":
        numofABC = (numofABC*3+numofAB) % mod
        numofAB = (numofAB*3+numofA) % mod
        numofA = (numofquestion + numofA*3) % mod
        numofquestion *= 3
    elif S[i] == "C":
        numofABC = (numofAB+numofABC) % mod
    elif S[i] == "B":
        numofAB = (numofAB + numofA) % mod
    else:
        numofA = (numofquestion + numofA) % mod
print(numofABC)

Submission status: Time Limit Exceeded

Solution code:
s=input()
l=len(s)

dp=[4*[0]for _ in range(l+1)]
dp[0][0]=1

for i in range(1,l+1):
  si = s[i-1]
  if si == "?":
    dp[i][0] = dp[i-1][0] * 3
    dp[i][1] = dp[i-1][1] * 3
    dp[i][2] = dp[i-1][2] * 3
    dp[i][3] = dp[i-1][3] * 3
  else:
    dp[i][0] = dp[i-1][0]
    dp[i][1] = dp[i-1][1]
    dp[i][2] = dp[i-1][2]
    dp[i][3] = dp[i-1][3]
    
  if si == "A":
    dp[i][1] = dp[i-1][0] + dp[i][1]
  elif si == "B":
    dp[i][2] = dp[i-1][1] + dp[i][2]
  elif si == "C":
    dp[i][3] = dp[i-1][2] + dp[i][3]
  else:
    dp[i][1] = dp[i-1][0] + dp[i][1]
    dp[i][2] = dp[i-1][1] + dp[i][2]
    dp[i][3] = dp[i-1][2] + dp[i][3]
  
print(int(dp[-1][-1] % 1000000007))

Submission status: Time Limit Exceeded

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

l = len(S)
nAB = [0]*(l+1)
nA = [0]*(l+1)
nB = [0]*(l+1)
nC = [0]*(l+1)
nABC = [0]*(l+1)

q = 0
for i,s in enumerate(S):
    if s == '?':
        nA[i+1] = 3*nA[i] + (3**q % MOD)
        nB[i+1] = 3*nB[i] + (3**q & MOD)
        nC[i+1] = 3*nC[i] + (3**q & MOD)
        nAB[i+1] = 3*nAB[i] + nA[i]
        nABC[i+1] = 3*nABC[i] + nAB[i]
        q += 1
    if s == 'A':
        nA[i+1] = nA[i] + (3**q % MOD)
        nB[i+1] = nB[i]
        nC[i+1] = nC[i]
        nAB[i+1] = nAB[i]
        nABC[i+1] = nABC[i]
    if s == 'B':
        nA[i+1] = nA[i]
        nB[i+1] = nB[i] + (3**q % MOD)
        nC[i+1] = nC[i]
        nAB[i+1] = nAB[i] + nA[i]
        nABC[i+1] = nABC[i]
    if s == 'C':
        nA[i+1] = nA[i]
        nB[i+1] = nB[i]
        nC[i+1] = nC[i] + (3**q % MOD)
        nAB[i+1] = nAB[i]
        nABC[i+1] = nABC[i] + nAB[i]
    nA[i+1] = nA[i+1] % MOD
    nB[i+1] = nB[i+1] % MOD
    nC[i+1] = nC[i+1] % MOD
    nAB[i+1] = nAB[i+1] % MOD
    nABC[i+1] = nABC[i+1] % MOD

print(nABC[l] % MOD)

Submission status: Time Limit Exceeded

Solution code:
S = input()

suma,sumc,sumq=0,0,0
maxC=S.count("C")
maxQ=S.count("?")
mod=10**9+7  
ans=0

for i,s in enumerate(S):
  if s=="A":
    suma+=1
  elif s=="C":
    sumc+=1
  elif s=="?":
    sumq+=1
  
  if i==0 or i==len(S):
    continue
    
  if s=="?":
    k=maxQ-1
    ans+=suma*(maxC-sumc)*(3**k)%mod
    ans+=(sumq-1)*(maxC-sumc)*(3**(k-1))%mod
    ans+=suma*(maxQ-sumq)*(3**(k-1))%mod
    ans+=(sumq-1)*(maxQ-sumq)*(3**(k-2))%mod
  elif s=="B":
    k=maxQ
    ans+=suma*(maxC-sumc)*(3**k)%mod
    ans+=sumq*(maxC-sumc)*(3**(k-1))%mod
    ans+=suma*(maxQ-sumq)*(3**(k-1))%mod
    ans+=sumq*(maxQ-sumq)*(3**(k-2))%mod
  
print(int(ans%mod))

Submission status: Time Limit Exceeded

Solution code:
S = input()
A,B_i,C,Q=[],[],[],[]

suma,sumc,sumq=0,0,0
for i,s in enumerate(S):
  if s=="A":
    suma+=1
  elif s=="C":
    sumc+=1
  elif s=="?":
    sumq+=1
    B_i.append(i)
  elif s=="B":
    B_i.append(i)
    
  A.append(suma)
  C.append(sumc)
  Q.append(sumq)
  
mod=10**9+7  
ans=0
for i in B_i:
  if i==0 or i==len(S):
    continue
  k=Q[-1]-Q[i]+Q[i-1]
  ans+=A[i-1]*(C[-1]-C[i])*(3**k)%mod
  ans+=Q[i-1]*(C[-1]-C[i])*(3**(k-1))%mod
  ans+=A[i-1]*(Q[-1]-Q[i])*(3**(k-1))%mod
  ans+=Q[i-1]*(Q[-1]-Q[i])*(3**(k-2))%mod
  
print(int(ans%mod))

Submission status: Time Limit Exceeded

Solution code:
class ModWorld:
    def __init__(self, mod):
        self.mod = mod

    def prepare_factorial(self, N):
        self.f = [1] # f[n] := n!
        p = 1
        for i in range(1,N+1):
            p = (p*i) % self.mod
            self.f.append(p)

    def modpow(self, x, k):
        x %= self.mod
        k %= self.mod-1 # a^(p-1) = 1
        retval = 1
        while k:
            if k&1: retval = retval * x % self.mod
            k>>=1
            x = x*x % self.mod
        return retval % self.mod

    def modcomb(self, n, k):
        return self.f[n] * self.modpow(self.f[n-k], -1) * self.modpow(self.f[k], -1) % self.mod

mw = ModWorld(mod=10**9+7)

S = input()
nQ_r = S.count('?')
nC_r = S.count('C')
nQ_l = 0
nA_l = 0
N = len(S)
ans = 0
for n, c in enumerate(S):
    if c=='C': nC_r-=1
    if c=='?': nQ_r-=1
    
    if n>0 and n<N-1 and (c=='B' or c=='?'):
        p = ( nQ_l*mw.modpow(3, max(0, nQ_l-1)) + nA_l*mw.modpow(3, nQ_l) ) % mw.mod
        q = ( nQ_r*mw.modpow(3, max(0, nQ_r-1)) + nC_r*mw.modpow(3, nQ_r) ) % mw.mod
        ans += p * q
        ans %= mw.mod

    if c=='A': nA_l+=1
    if c=='?': nQ_l+=1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()
nQ_r = S.count('?')
nC_r = S.count('C')
nQ_l = 0
nA_l = 0
N = len(S)
mod = 10**9+7
ans = 0
for n, c in enumerate(S):
    if c=='C': nC_r-=1
    if c=='?': nQ_r-=1
    
    if n>0 and n<N-1 and (c=='B' or c=='?'):
        p = ( nQ_l*(3**max(0, nQ_l-1) % mod) + nA_l*(3**nQ_l % mod) ) % mod
        q = ( nQ_r*(3**max(0, nQ_r-1) % mod) + nC_r*(3**nQ_r % mod) ) % mod
        ans += p * q
        ans %= mod

    if c=='A': nA_l+=1
    if c=='?': nQ_l+=1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()
nQ_r = S.count('?')
nC_r = S.count('C')
nQ_l = 0
nA_l = 0
N = len(S)
mod = 10**9+7
ans = 0
for n, c in enumerate(S):
    if c=='C': nC_r-=1
    if c=='?': nQ_r-=1
    
    if n>0 and n<N-1 and (c=='B' or c=='?'):
        p = nQ_l*(3**(max(0, nQ_l-1) % (mod-1))) + nA_l*(3**(nQ_l % mod))
        q = nQ_r*(3**(max(0, nQ_r-1) % (mod-1))) + nC_r*(3**(nQ_r % mod))
        ans += p * q
        ans %= mod

    if c=='A': nA_l+=1
    if c=='?': nQ_l+=1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()
nQ_r = S.count('?')
nC_r = S.count('C')
nQ_l = 0
nA_l = 0
N = len(S)
mod = 10**9+7
ans = 0
for n, c in enumerate(S):
    if c=='C': nC_r-=1
    if c=='?': nQ_r-=1
    
    if n>0 and n<N-1 and (c=='B' or c=='?'):
        p = nQ_l*(3**(max(0, nQ_l-1))) + nA_l*(3**nQ_l)
        q = nQ_r*(3**(max(0, nQ_r-1))) + nC_r*(3**nQ_r)
        ans += p * q
        ans %= mod

    if c=='A': nA_l+=1
    if c=='?': nQ_l+=1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()

dp_prev = [1, 0, 0, 0]

for c in s:
    dp_new = [dp_prev[i] for i in range(0, 4)]
    for i in range(0, 4):
        if c == "A":
            dp_new[1] = dp_prev[0] + dp_prev[1]

        elif c == "B":
            dp_new[2] = dp_prev[1] + dp_prev[2]

        elif c == "C":
            dp_new[3] = dp_prev[2] + dp_prev[3]

        else:
            dp_new[0] = dp_prev[0] * 3
            dp_new[1] = dp_prev[0] + dp_prev[1] * 3
            dp_new[2] = dp_prev[1] + dp_prev[2] * 3
            dp_new[3] = dp_prev[2] + dp_prev[3] * 3

    dp_prev = dp_new

ans = dp_prev[3] % 1000000007
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import cmath
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


S = sys.stdin.buffer.readline().decode().rstrip()

a = 0
ab = 0
abc = 0
q = 0
for i, s in enumerate(S):
    if s == 'C':
        abc += ab
    if s == 'B':
        ab += a
    if s == 'A':
        a += 3 ** q
    if s == '?':
        abc = abc * 3 + ab
        ab = ab * 3 + a
        a = a * 3 + 3 ** q
        q += 1
    a %= MOD
    ab %= MOD
    abc %= MOD
    # print(s, a, ab, abc)
print(abc)

Submission status: Time Limit Exceeded

Solution code:
S = input()
mod = 10**9 + 7
dic = {'': 1, 'A': 0, 'B': 0, 'C': 0}
for s in S:
    if s == 'A':
        dic[s] += dic['']

    elif s == 'B':
        dic[s] += dic['A']

    elif s == 'C':
        dic[s] += dic['B']

    elif s == '?':
        dic['C'] = dic['C'] * 3 + dic['B']
        dic['B'] = dic['B'] * 3 + dic['A']
        dic['A'] = dic['A'] * 3 + dic['']
        dic[''] *= 3

print(dic['C']%mod)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7
def solve(s):
    n = len(s)
    dp = [[0,0,0,0] for i in range(n+1)]
    dp[0][0] = 1
    for i in range(n):
        t = 2 * int(s[i] == "?") + 1
        for j in range(4):
            dp[i+1][j] = t * dp[i][j]
        if s[i] == "A":
            dp[i+1][1] = (dp[i+1][1] + dp[i][0]) % MOD
        elif s[i] == "B":
            dp[i+1][2] = (dp[i+1][2] + dp[i][1]) % MOD
        elif s[i] == "C":
            dp[i+1][3] = (dp[i+1][3] + dp[i][2]) % MOD
        else:
            dp[i+1][1] = (dp[i+1][1] + dp[i][0]) % MOD
            dp[i+1][2] = (dp[i+1][2] + dp[i][1]) % MOD
            dp[i+1][3] = (dp[i+1][3] + dp[i][2]) % MOD
    return dp[n][3] % MOD

s = input()
print(solve(s))

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7
def solve(s):
    n = len(s)
    dp = [[0,0,0,0] for i in range(n+1)]
    dp[0][0] = 1
    for i in range(n):
        t = 2 * int(s[i] == "?") + 1
        for j in range(4):
            dp[i+1][j] = t * dp[i][j]
        if (s[i] == "A") or (s[i] == "?"):
            dp[i+1][1] = (dp[i+1][1] + dp[i][0]) % MOD
        if (s[i] == "B") or (s[i] == "?"):
            dp[i+1][2] = (dp[i+1][2] + dp[i][1]) % MOD
        if (s[i] == "C") or (s[i] == "?"):
            dp[i+1][3] = (dp[i+1][3] + dp[i][2]) % MOD
    return dp[n][3] % MOD

s = input()
print(solve(s))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
limit = 100000
mod = 10**9+7
lpow = [False] * (limit+1)
lpow[0] = 1
def pow(n,p):
    if p<0:return 0
    if lpow[p]:
        return lpow[p]
    else:
        if p % 2 == 0:
            return pow(n,p//2)**2
        else:
            return (pow(n,p//2)**2)*n

def main():
    s=input()
    res = 0
    ca = 0
    cc = s.count("C")
    cw = 0
    aw = s.count("?")
    for c in s:
        if c == "A":
            ca += 1
        elif c == "C":
            cc -= 1
        elif c == "B":
            res += ca*cc*pow(3,aw)+ca*(aw-cw)*pow(3,aw-1)+cw*cc*pow(3,aw-1)+cw*(aw-cw)*pow(3,aw-2)
            res %= mod
        elif c == "?":
            res += ca*cc*pow(3,aw-1)+ca*(aw-cw-1)*pow(3,aw-2)+cw*cc*pow(3,aw-2)+cw*(aw-cw-1)*pow(3,aw-3)
            res %= mod
            cw += 1

    print(res)

main()

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9+7
def pow(n,p):
    res=1
    while p >0:
        if p%2==0:
            n = n**2 % mod
            p //= 2
        else:
            res = res * n % mod
            p -= 1
    return res % mod

def main():
    s=input()
    res = 0
    ca = 0
    cc = s.count("C")
    cw = 0
    aw = s.count("?")
    for c in s:
        if c == "A":
            ca += 1
        elif c == "C":
            cc -= 1
        elif c == "B":
            res += ca*cc*pow(3,aw)+ca*(aw-cw)*pow(3,aw-1)+cw*cc*pow(3,aw-1)+cw*(aw-cw)*pow(3,aw-2)
            res %= mod
        elif c == "?":
            res += ca*cc*pow(3,aw-1)+ca*(aw-cw-1)*pow(3,aw-2)+cw*cc*pow(3,aw-2)+cw*(aw-cw-1)*pow(3,aw-3)
            res %= mod
            cw += 1

    print(res)

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

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

# dp[i][0] -> A
# dp[i][1] -> AB
# dp[i][2] -> ABC
dp = [0, 0, 0]
k = 0
for i in range(N):
    if S[i] == "A":
        dp[0] += (3**k)%mod
    elif S[i] == "B":
        dp[1] += dp[0]
    elif S[i] == "C":
        dp[2] += dp[1]
    else:
        dp[2] = 3*dp[2] + dp[1]
        dp[1] = 3*dp[1] + dp[0]
        dp[0] = 3*dp[0] + (3**k)%mod
        k += 1
    
    dp[0] %= mod
    dp[1] %= mod
    dp[2] %= mod

print(dp[2])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

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

# dp[i][0] -> A
# dp[i][1] -> AB
# dp[i][2] -> ABC
dp = [[0, 0, 0] for _ in range(N+1)]
k = 0
for i in range(N):
    if S[i] == "A":
        dp[i+1][0] = dp[i][0] + (3**k)%mod
        dp[i+1][1] = dp[i][1]
        dp[i+1][2] = dp[i][2]
    elif S[i] == "B":
        dp[i+1][0] = dp[i][0]
        dp[i+1][1] = dp[i][1] + dp[i][0]
        dp[i+1][2] = dp[i][2]
    elif S[i] == "C":
        dp[i+1][0] = dp[i][0]
        dp[i+1][1] = dp[i][1]
        dp[i+1][2] = dp[i][2] + dp[i][1]
    else:
        dp[i+1][0] = 3*dp[i][0] + (3**k)%mod
        dp[i+1][1] = 3*dp[i][1] + dp[i][0]
        dp[i+1][2] = 3*dp[i][2] + dp[i][1]
        k += 1
    
    dp[i+1][0] %= mod
    dp[i+1][1] %= mod
    dp[i+1][2] %= mod

print(dp[N][2])

Submission status: Time Limit Exceeded

Solution code:
S = input()
INF = 10**9+7
dp = [0,0,0]
N = 1
for i in range(len(S)):
  if S[i]=='A':
    dp[0] += N%INF
    dp[0] %= INF
  elif S[i]=='B':
    dp[1] += (dp[0]%INF)
  elif S[i]=='C':
    dp[2] += (dp[1]%INF)
  else:
    a = dp[0]
    b = dp[1]
    dp[0] = N + dp[0]*3
    dp[1] = a + dp[1]*3
    dp[2] = b + dp[2]*3
    dp[0] %= INF
    dp[1] %= INF
    dp[2] %= INF
    N *= 3
print(dp[2]%INF)

Submission status: Time Limit Exceeded

Solution code:
S = input()
INF = 10**9+7
dp = [0,0,0]
Q = 0
N = 1
for i in range(len(S)):
  if S[i]=='A':
    dp[0] += N%INF
    dp[0] %= INF
  elif S[i]=='B':
    dp[1] += (dp[0]%INF)
  elif S[i]=='C':
    dp[2] += (dp[1]%INF)
  else:
    a = dp[0]
    b = dp[1]
    dp[0] = N + dp[0]*3
    dp[1] = a + dp[1]*3
    dp[2] = b + dp[2]*3
    dp[0] %= INF
    dp[1] %= INF
    dp[2] %= INF
    N *= 3
print(dp[2]%INF)

Submission status: Time Limit Exceeded

Solution code:
S = input()
INF = 10**9+7
dp = [0,0,0]
Q = 0
for i in range(len(S)):
  if S[i]=='A':
    dp[0] += (3**Q)%INF
    dp[0] %= INF
  elif S[i]=='B':
    dp[1] += (dp[0]%INF)
  elif S[i]=='C':
    dp[2] += (dp[1]%INF)
  else:
    a = dp[0]
    b = dp[1]
    dp[0] = 3**Q + dp[0]*3
    dp[1] = a + dp[1]*3
    dp[2] = b + dp[2]*3
    dp[0] %= INF
    dp[1] %= INF
    dp[2] %= INF
    Q += 1
print(dp[2]%INF)

Submission status: Time Limit Exceeded

Solution code:
S = input()
INF = 10**9+7
dp = [0,0,0]
Q = 0
for i in range(len(S)):
  if S[i]=='A':
    dp[0] += 3**Q
    dp[0] %= INF
  elif S[i]=='B':
    dp[1] += dp[0]
    dp[1] %= INF
  elif S[i]=='C':
    dp[2] += dp[1]
    dp[2] %= INF
  else:
    a = dp[0] + 3**Q
    b = dp[1] + dp[0]
    c = dp[2] + dp[1]
    dp[0] = a + dp[0]*2
    dp[1] = b + dp[1]*2
    dp[2] = c + dp[2]*2
    dp[0] %= INF
    dp[1] %= INF
    dp[2] %= INF
    Q += 1
print(dp[2])

Submission status: Time Limit Exceeded

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

MOD = 1000000007  # type: int


def solve(S: str):
    N = len(S)
    # 0:文字列の総数 1:Aの数  2:ABの数 3:ABCの数
    ## dp[i][j] = i文字目まで見たときに状態jの数

    ## answer: dp[N][3]

    dp = [[0]*4 for _ in range(N+1)]
    dp[0][0] = 1
    for i in range(N):
        for j in (0,1,2,3):
            if S[i] == "?":
                dp[i+1][j] += dp[i][j]*3
            else:
                dp[i+1][j] += dp[i][j]
            
        ## カウント進める場合
        if S[i] == "A" or S[i] == "?":
            dp[i+1][1] += dp[i][0]
            # dp[i+1][1] %= MOD
        
        if S[i] == "B" or S[i] == "?":
            dp[i+1][2] += dp[i][1]
            # dp[i+1][2] %= MOD

        if S[i] == "C" or S[i] == "?":
            dp[i+1][3] += dp[i][2]
            # dp[i+1][3] %= MOD

    print(dp[N][3]%MOD)
    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:
#0:09
"""
ABC数
遷移を考える問題
dp[どこまでみたか][その時の状態] = になりうる場合の数
"""
S = input()
n = len(S)

dp = [[0]*3 for i in range(n+1)]
cnt = 0 #はてなの数
#初期は後で構築
mod = 10**9 + 7 

for i in range(n):
    if S[i] == "A":
        dp[i+1][0] = (dp[i][0] + int(3**(cnt))) % mod
        dp[i+1][1] = dp[i][1]
        dp[i+1][2] = dp[i][2]
    elif S[i] == "B":
        dp[i+1][0] = dp[i][0]
        dp[i+1][1] = (dp[i][0] + dp[i][1]) % mod
        dp[i+1][2] = dp[i][2]
    elif S[i] == "C":
        dp[i+1][0] = dp[i][0]
        dp[i+1][1] = dp[i][1]
        dp[i+1][2] = (dp[i][1] + dp[i][2]) % mod
    elif S[i] == "?":
        dp[i+1][0] = (dp[i][0] * 3 + int(3**(cnt))) % mod
        dp[i+1][1] = (dp[i][1] * 3 + dp[i][0]) % mod
        dp[i+1][2] = (dp[i][2] * 3 + dp[i][1]) % mod        
        cnt += 1

print(dp[n][2]%mod)

Submission status: Time Limit Exceeded

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

dp = [[0]*3 for i in range(n+1)]
cnt = 0 #はてなの数
#初期は後で構築
mod = 10**9 + 7 

for i in range(n):
    if S[i] == "A":
        dp[i+1][0] = dp[i][0] + int(3**(cnt))
        dp[i+1][1] = dp[i][1]
        dp[i+1][2] = dp[i][2]
    elif S[i] == "B":
        dp[i+1][0] = dp[i][0]
        dp[i+1][1] = dp[i][0] + dp[i][1]
        dp[i+1][2] = dp[i][2]
    elif S[i] == "C":
        dp[i+1][0] = dp[i][0]
        dp[i+1][1] = dp[i][1]
        dp[i+1][2] = dp[i][1] + dp[i][2]
    elif S[i] == "?":
        dp[i+1][0] = dp[i][0] * 3 + int(3**(cnt))
        dp[i+1][1] = dp[i][1] * 3 + dp[i][0]
        dp[i+1][2] = dp[i][2] * 3 + dp[i][1]        
        cnt += 1

print(dp[n][2]%mod)

Submission status: Time Limit Exceeded

Solution code:
# D - We Love ABC

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

def find_cumsum(X):
    output = [1] if S[0] == X else [0]    
    for idx in range(1,N):
        if S[idx] == X:
            output.append(output[-1]+1)
        else:
            output.append(output[-1])
    return output

q_count = S.count("?")
A_cumsum = find_cumsum("A")
q_cumsum = find_cumsum("?")
        
# last_b[i][j] : S[j]を末尾の"B"とするABのインデックスのパターンの中で、i個の?を"AB"のために使用したもの
last_b = [[0] for _ in range(3)]
for idx in range(1,N):
    if S[idx] == "B":
        last_b[0].append(A_cumsum[idx-1]) # AB
        last_b[1].append(q_cumsum[idx-1]) # ?B
        last_b[2].append(0)
    elif S[idx] == "?":
        last_b[0].append(0)
        last_b[1].append(A_cumsum[idx-1]) # A?
        last_b[2].append(q_cumsum[idx-1]) # ??
    else:
        for i in [0,1,2]:
            last_b[i].append(0)

last_b_cumsum = [[last_b[0][0]], [last_b[1][0]], [last_b[2][0]]]
for i in range(3):
    for idx in range(1,N):
        last_b_cumsum[i].append((last_b[i][idx] + last_b_cumsum[i][-1]) % MOD)

ans = 0
for idx in range(2,N):
    ans %= MOD
    if S[idx] == "C":
        for n_q in range(min(q_count,2)+1):
            ans += last_b_cumsum[n_q][idx-1] * 3**(q_count-n_q)
    elif S[idx] == "?":
        for n_q in range(1, min(q_count,3)+1):
            ans += last_b_cumsum[n_q-1][idx-1] * 3**(q_count-n_q)
        
print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
# D - We Love ABC

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

def find_cumsum(X):
    output = [1] if S[0] == X else [0]    
    for idx in range(1,N):
        if S[idx] == X:
            output.append(output[-1]+1)
        else:
            output.append(output[-1])
    return output

q_count = S.count("?")
A_cumsum = find_cumsum("A")
q_cumsum = find_cumsum("?")
        
# last_b[i][j] : S[j]を末尾の"B"とするABのインデックスのパターンの中で、i個の?を"AB"のために使用したもの
last_b = [[0] for _ in range(3)]
for idx in range(1,N):
    if S[idx] == "B":
        last_b[0].append(A_cumsum[idx-1]) # AB
        last_b[1].append(q_cumsum[idx-1]) # ?B
        last_b[2].append(0)
    elif S[idx] == "?":
        last_b[0].append(0)
        last_b[1].append(A_cumsum[idx-1]) # A?
        last_b[2].append(q_cumsum[idx-1]) # ??
    else:
        for i in [0,1,2]:
            last_b[i].append(0)

last_b_cumsum = [[last_b[0][0]], [last_b[1][0]], [last_b[2][0]]]
for i in range(3):
    for idx in range(1,N):
        last_b_cumsum[i].append((last_b[i][idx] + last_b_cumsum[i][-1]) % MOD)

# last_c[i] : S[i]を末尾の"C"とするABCのパターン数で、しかも?の置き換えも考慮したもの
last_c = [0]*2
for idx in range(2,N):
    n_ABC = 0
    if S[idx] == "C":
        for n_q in range(min(q_count,2)+1):
            n_ABC += last_b_cumsum[n_q][idx-1] * 3**(q_count-n_q)
    elif S[idx] == "?":
        for n_q in range(1, min(q_count,3)+1):
            n_ABC += last_b_cumsum[n_q-1][idx-1] * 3**(q_count-n_q)
    last_c.append(n_ABC % MOD)
        
print(sum(last_c) % MOD)

Submission status: Time Limit Exceeded

Solution code:
s = input()

dp = [[0 for j in range(4)] for i in range(len(s)+1)]
dp[0][0] = 1
mod = 10**9+7
for i in range(len(s)):
    for j in range(4):
        dp[i+1][j] = dp[i][j]
        dp[i+1][j] %= mod
    if s[i] == "A":
        dp[i+1][1] += dp[i][0]
    elif s[i] == "B":
        dp[i+1][2] += dp[i][1]
    elif s[i] == "C":
        dp[i+1][3] += dp[i][2]
    else:
        dp[i+1][0] += dp[i][0] * 2
        dp[i+1][1] += dp[i][1] * 2 + dp[i][0]
        dp[i+1][2] += dp[i][2] * 2 + dp[i][1]
        dp[i+1][3] += dp[i][3] * 2 + dp[i][2]

print(dp[-1][3]%mod)

Submission status: Time Limit Exceeded

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

ret = 0
la, rc = 0, S.count('C')
lq, rq = 0, S.count('?')

fac = [1]
inv = [1]
for i in range(1, len(S) + 1) :
    fac.append(fac[-1] * i % mod)
    inv.append(pow(fac[-1], mod - 2, mod))

def comb(ac, q) :
    ret = 0
    for i in range(q + 1) :
        ret += pow(2, q - i, mod) * (ac + i) * fac[q] * inv[q-i] * inv[i] % mod
        
    return ret

for s in S :
    if s == '?' :
        rq -= 1
        ret += comb(la, lq) * comb(rc, rq)
        ret %= mod
        lq += 1
    elif s == 'A' :
        la += 1
    elif s == 'B' :
        ret += comb(la, lq) * comb(rc, rq)
        ret %= mod
    elif s == 'C' :
        rc -= 1
    
print(ret)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

S = str(input())
N = len(S)

h_all = 0
for i in range(N):
    if S[i]=='?':
        h_all += 1

a = 0
b = 0
h = 0
numAB = 0
numAH = 0
numHB = 0
numHH = 0
dp = [0]*N

for i in range(N):
    if S[i]=='A':
        if i>=1:
            dp[i] = dp[i-1]
        a += 1
    elif S[i]=='B':
        if i>=1:
            dp[i] = dp[i-1]
        numAB += a
        numHB += h
        b += 1
    elif S[i]=='?':
        if i>=1:
            if h_all>=1:
                dp[i] = (dp[i-1]+numAB*3**(h_all-1)) %mod
            if h_all>=2:
                dp[i] = (dp[i]+numAH*3**(h_all-2)) %mod
                dp[i] = (dp[i]+numHB*3**(h_all-2)) %mod
            if h_all>=3:
                dp[i] = (dp[i]+numHH*3**(h_all-3))%mod
        numAH += a
        numHH += h
        h += 1
    else:
        if i>=1:
            dp[i] = (dp[i-1]+numAB*3**h_all) %mod
            if h_all>=1:
                dp[i] = (dp[i]+numAH*3**(h_all-1)) %mod
                dp[i] = (dp[i]+numHB*3**(h_all-1)) %mod
            if h_all>=2:
                dp[i] = (dp[i]+numHH*3**(h_all-2))%mod

print(dp[N-1])

Submission status: Time Limit Exceeded

Solution code:
def main():
    MOD = 10**9+7
    S = input()
    
    dp = [0] * 4
    dp_next = [0] * 4
    dp[0] = 1
    
    for s in S:
        if s == '?':
            m = 3
        else:
            m = 1
        dp_next[0] = m * dp[0]
        dp_next[1] = m * dp[1]
        dp_next[2] = m * dp[2]
        dp_next[3] = m * dp[3]
        
        if s == '?' or s == 'A':
            dp_next[1] = (dp_next[1]+dp[0]) % MOD
        if s == '?' or s == 'B':
            dp_next[2] = (dp_next[2]+dp[1]) % MOD
        if s == '?' or s == 'C':
            dp_next[3] = (dp_next[3]+dp[2]) % MOD
            
        dp[0] = dp_next[0]
        dp[1] = dp_next[1]
        dp[2] = dp_next[2]
        dp[3] = dp_next[3]
            
    print(dp[3])

if __name__ == '__main__':
    main()