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: Wrong Answer

Solution code:
import itertools
s = input()

a,b,c,x = [],[],[],[]
index = -1
while True:
    index = s.find("A", index + 1)
    if index == -1:
        break
    a.append(index)
index = -1
while True:
    index = s.find("B", index + 1)
    if index == -1:
        break
    b.append(index)
index = -1
while True:
    index = s.find("C", index + 1)
    if index == -1:
        break
    c.append(index)
index = -1
while True:
    index = s.find("?", index + 1)
    if index == -1:
        break
    x.append(index)
a += x
b += x
c += x
a = sorted(a)
b = sorted(b)
c = sorted(c)
l = list(itertools.product(a,b,c))
d = sum(1 if s[0]<s[1] and s[1]<s[2] else 0 for s in l)
print(d%(10**9+7))

Submission status: Wrong Answer

Solution code:
S = raw_input()
M = 10**9+7

def count(W):
  N = len(S)
  T1 = [0]*N
  for i in range(N):
    T1[i] = (0 if i==0 else T1[i-1]) + int(S[i]==W[0])
  T2 = [0]*N
  for i in range(N)[::-1]:
    T2[i] = (0 if i==N-1 else T2[i+1]) + int(S[i]==W[2])
  ans = 0
  for i in range(1,N-1):
    if S[i]==W[1]:
      ans += T1[i-1]*T2[i+1]
      ans %= M
  return ans

Q = S.count("?")
print (
  count("ABC")*pow(3,Q,M) +
  count("AB?")*pow(3,max(Q-1,0),M) +
  count("A?C")*pow(3,max(Q-1,0),M) +
  count("A??")*pow(3,max(Q-2,0),M) +
  count("?BC")*pow(3,max(Q-2,0),M) +
  count("?B?")*pow(3,max(Q-2,0),M) +
  count("??C")*pow(3,max(Q-2,0),M) +
  count("???")*pow(3,max(Q-3,0),M))%M

Submission status: Wrong Answer

Solution code:
#a,b=map(int,input().split())
import numpy as np

s=input()
n=len(s)
wayA=np.array([0,0,0,0],dtype=np.int64)
wayB=np.array([0,0,0,0],dtype=np.int64)
wayC=np.array([0,0,0,0],dtype=np.int64)
hatena=0
MOD=1000000007
for c in s:
	if c=="A":
		wayA[0]=wayA[0]+1
	if c=="B":
		wayB[0]=wayB[0]+wayA[0]
		wayB[1]=wayB[1]+wayA[1]
	if c=='C':
		wayC=wayC+wayB
		wayC[0]=wayC[0]+wayB[0]
		wayC[1]=wayC[1]+wayB[1]
		wayC[2]=wayC[2]+wayB[2]
	if c=='?':
		wayC[1]=wayC[1]+wayB[0]
		wayC[2]=wayC[2]+wayB[1]
		wayC[3]=wayC[3]+wayB[2]
		wayB[1]=wayB[1]+wayA[0]
		wayB[2]=wayB[2]+wayA[1]
		wayA[1]=wayA[1]+1
		hatena=hatena+1
	for z in range(0,4):
		wayA[z]=wayA[z]%MOD
		wayB[z]=wayB[z]%MOD
		wayC[z]=wayC[z]%MOD
ans=0
for i in range(0,4):
	p3=1
	wayC[i]=wayC[i]%MOD
	if wayC[i]<=0:
		continue
	for k in range(0,hatena-i):
		p3=p3*3
		p3=p3%MOD
	ans=ans+p3*wayC[i]
ans = ans%1000000007
print(int(ans))

Submission status: Wrong Answer

Solution code:

import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

mod = 1000000007

s = ns()

nums = [0]*4
nums[0] = 1
for c in s:
    if c == 'A':
        nums[1] += nums[0]
        nums[1] %= mod
    elif c == "B":
        nums[2] += nums[1]
        nums[2] %= mod
    elif c == "C":
        nums[3] += nums[2]
        nums[3] %= mod
    else:
        nums[3] = nums[3]*3+nums[2]
        nums[2] = nums[2]*3+nums[1]
        nums[1] = nums[1]*3+nums[0]
        nums[0] = nums[0]*3
        for k in range(4):
            nums[k] %= mod
print(nums[3])

Submission status: Wrong Answer

Solution code:
#a,b=map(int,input().split())
s=input()
n=len(s)
wayA=[0,0,0,0]
wayB=[0,0,0,0]
wayC=[0,0,0,0]
hatena=0
for c in s:
	if c=="A":
		wayA[0]=wayA[0]+1
	if c=="B":
		wayB[0]=wayB[0]+wayA[0]
		wayB[1]=wayB[1]+wayA[1]
	if c=='C':
		wayC=wayC+wayB
		wayC[0]=wayC[0]+wayB[0]
		wayC[1]=wayC[1]+wayB[1]
		wayC[2]=wayC[2]+wayB[2]
	if c=='?':
		wayC[1]=wayC[1]+wayB[0]
		wayC[2]=wayC[2]+wayB[1]
		wayC[3]=wayC[3]+wayB[2]
		wayB[1]=wayB[1]+wayA[0]
		wayB[2]=wayB[2]+wayA[1]
		wayA[1]=wayA[1]+1
		hatena=hatena+1
ans=0
for i in range(0,4):
	ans=ans+pow(3,hatena-i)*wayC[i]
ans = ans%1000000007
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def getval():
    s = input()
    return s
    
def main(s):
    #dp for "a","ab","abc"
    dp = [0,0,0,0]
    mod = 10**9 + 7
    for i in s:
        if i=="A":
            dp[0] += 3**(dp[3])
            dp[0] %= mod
        elif i=="B":
            dp[1] += dp[0]
            dp[1] %= mod
        elif i=="C":
            dp[2] += dp[1]
            dp[2] %= mod
        else:
            temp1 = dp[0]*2
            temp2 = dp[1]*2
            temp3 = dp[2]*2
            dp[2] += dp[1]
            dp[1] += dp[0]
            dp[0] += 3**(dp[3]) 
            dp[2] += temp3
            dp[1] += temp2
            dp[0] += temp1
            dp[3] += 1
            for j in range(3):
                dp[j] %= mod
            #print(dp)
    print(dp[2])

if __name__=="__main__":
    s = getval()
    main(s)

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9+7
S = input()
l = len(S)
dp = [0,0,1]
ans = 0
for i in range(l):
    if S[i] == 'A':
        dp[0] += dp[2]
        dp[0] %= mod
    if S[i] == 'B':
        dp[1] += dp[0]
        dp[1] %= mod
    if S[i] == 'C':
        ans += dp[1]
        ans %= mod
    if S[i] == '?':
        dp1 = dp[:]
        dp2 = dp[:]
        dp3 = dp[:]
        dp1[0] += dp1[2]
        dp2[1] += dp2[0]
        ans *= 3
        ans += dp3[1]
        ans %= mod
        dp[0] = (dp1[0]+dp2[0]+dp3[0]) % mod
        dp[1] = (dp1[1]+dp2[1]+dp3[1]) % mod
        dp[2]*= 3
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def C(n, r ,mod=10**9+7):
    if n-r<r: r=n-r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k]) %mod

    return result % mod

A=list(input())
n=len(A)
mod=10**9+7
ans=0
numa= A[0]=="A" 
numa_= A[0]=="?"
numc=A[2:].count("C")
numc_= A[2:].count("?")

for i in range(1,n-1):
    #print(numa,numa_,numc,numc_)
    apro=cpro=0
    if A[i]=="B" or A[i]=="?":
        for k in range(numa_+1):
            apro+= (((C(numa_,k)*pow(2,numa_-k,mod))%mod)*(numa+k))%mod
        for k in range(numc_+1):
            cpro+= (((C(numc_,k)*pow(2,numc_-k,mod))%mod)*(numc+k))%mod
        #print(apro,cpro)
        ans+= (apro*cpro)%mod
        ans%=mod
    if A[i] == "A":
        numa+=1
    if A[i]=="?":
        numa_+=1
    if A[i+1] =="C":
        numc-=1
    if A[i+1]=="?":
        numc_-=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7
S = input()
res = 0
dpn = 1
dp0 = 0 # a
dp1 = 0 # ab

for c in S:
    if c == 'A':
        dp0 += dpn
    elif c == 'B':
        dp1 += dp0
    elif c == 'C':
        res += dp1
    else:
        dp0,dp1,res = dp0*3+dpn,dp1*3+dp0,res*3+dp1
        dpn *= 3

    dp1 %= MOD
    res %= MOD
print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))


def main():
    S=["D"] + list(input())
    N=len(S)
    MOD=10**9+7

    A = [0] * (N+1)
    C = [0] * (N+1)
    Q = [0] * (N+1)

    for i in range(1,N+1):
        s = S[i-1]
        A[i] = A[i-1]
        C[i] = C[i-1]
        Q[i] = Q[i-1]
        if s == "A":
            A[i] += 1
        elif s == "C":
            C[i] += 1
        elif s == "?":
            Q[i] += 1
    
    # print(A,C,Q)
    ans = 0
    for i in range(1,N+1):
        s = S[i-1]
        if s == "?" or s == "B":
            l_A = A[i-1]
            l_Q = Q[i-1]
            r_Q = Q[-1] - Q[i]
            r_C = C[-1] - C[i]

    
            left = pow(2,l_Q,MOD) * l_A % MOD # 一個も使わないとき
            if l_Q > 0:
                left += l_Q * pow((1+pow(2,MOD-2,MOD)), l_Q-1,MOD) * pow(2,l_Q-1,MOD) % MOD # 1個以上使うとき
                left %= MOD
                left += l_A * (pow(3,l_Q,MOD)-pow(2,l_Q,MOD)) % MOD 


            right = pow(2,r_Q,MOD) * r_C % MOD # 一個も使わないとき
            if r_Q > 0:
                right += r_Q * pow((1+pow(2,MOD-2,MOD)), r_Q-1,MOD) * pow(2,r_Q-1,MOD) % MOD # 1個以上使うとき
                right %= MOD
                right += r_C * (pow(3,r_Q,MOD)-pow(2,r_Q,MOD)) % MOD 

            ans += left * right % MOD
            ans %= MOD


            
    ans %= MOD
    print(ans)






if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# D - We Love ABC

S = list(str(input()))
MOD = 10**9 + 7
a = 0
ab = 0
abc = 0
pat = 1
for s in S:
    if s == 'A':
        a = (a + pat) % MOD
    elif s == 'B':
        ab = (ab + a) % MOD
    elif s == 'C':
        abc = (abc + ab) % MOD
    else: # s == '?'
        tmpa = a
        tmpab = ab
        a = (3*a + pat) % MOD
        ab = (3*ab + tmpa) % MOD
        abc = (3*abc + tmpab) % MOD
        pat *= 3

print(abc)

Submission status: Time Limit Exceeded

Solution code:
# D - We Love ABC

S = list(str(input()))
MOD = 10**9 + 7
a = 0
ab = 0
abc = 0
pat = 1
for s in S:
    if s == 'A':
        a += pat
    elif s == 'B':
        ab += a
    elif s == 'C':
        abc += ab
    else: # s == '?'
        tmpa = a
        tmpab = ab
        a += 2*a + pat
        ab += 2*ab + tmpa
        abc += 2*abc + tmpab
        pat *= 3

print(abc%MOD)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# DP[0, 0], Aの数、ABの数、ABCの数
MOD = 10 ** 9 + 7
S = sr()
dp = [0, 0, 0]
total = 1
for s in S:
    if s == 'A':
        dp[0] += total
    elif s == 'B':
        dp[1] += dp[0]
    elif s == 'C':
        dp[2] += dp[1]
    elif s == '?':
        dp[2] = dp[2]*3 + dp[1]
        dp[1] = dp[1]*3 + dp[0]
        dp[0] = dp[0]*3 + total
        total *= 3
    #print(dp, total)

print(dp[2]%MOD)

Submission status: Time Limit Exceeded

Solution code:
S = input()
#dp[i][four] =: i + 1番目まで見たとき,照合したケツがfourとなるものの総数
dp = [[0 for _ in range(4)] for _ in range(len(S)+1 )]
dp[0][0] = 1
mod = 10**9 + 7
for i in range(len(S)):
    if S[i] == '?':
        dp[i+1][1] += dp[i][0] 
        dp[i+1][1] %= mod
        dp[i+1][2] += dp[i][1] 
        dp[i+1][2] %= mod
        dp[i+1][3] += dp[i][2] 
        dp[i+1][3] %= mod
    if S[i] == 'A':
        dp[i+1][1] += dp[i][0] 
        dp[i+1][1] %= mod
    if S[i] == 'B':
        dp[i+1][2] += dp[i][1]
        dp[i+1][2] %= mod
    if S[i] == 'C':
        dp[i+1][3] += dp[i][2]
        dp[i+1][3] %= mod
    for f in range(4):
        if S[i] != '?':
            dp[i+1][f] += dp[i][f]
        else:
            dp[i+1][f] += dp[i][f] * 3
print(dp[len(S)][3]%mod)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7

S = input()
N = len(S)
dp = [[0]*4 for i in range(N+1)]
dp[0][0] = 1
for i in range(N):
    s = S[i]
    for j in range(4):
        if s == "?":
            dp[i+1][j] += dp[i][j]*3
        else:
            dp[i+1][j] += dp[i][j]
        if j < 3 and (s == "?" or s == "ABC"[j]):
            dp[i+1][j+1] += dp[i][j]
print(dp[N][3]%MOD)

Submission status: Time Limit Exceeded

Solution code:
def main():
    MOD = 10 ** 9 + 7

    s = input()
    n = len(s)

    acc_a = [0] * (n + 1)
    acc_c = [0] * (n + 1)
    acc_q = [0] * (n + 1)

    a = 0
    c = 0
    q = 0
    for i, char in enumerate(s, 1):
        if char == 'A':
            a += 1
        elif char == 'C':
            c += 1
        elif char == '?':
            q += 1
        acc_a[i] = a
        acc_c[i] = c
        acc_q[i] = q

    ans = 0
    for i, char in enumerate(s, 1):
        if char == 'B' or char == '?':
            t = 0
            t += acc_a[i - 1] * (acc_c[n] - acc_c[i]) * pow(3, acc_q[n] - int(char == '?'))
            t += acc_a[i - 1] * (acc_q[n] - acc_q[i]) * pow(3, acc_q[n] - 1 - int(char == '?'))
            t += acc_q[i - 1] * (acc_c[n] - acc_c[i]) * pow(3, acc_q[n] - 1 - int(char == '?'))
            t += acc_q[i - 1] * (acc_q[n] - acc_q[i]) * pow(3, acc_q[n] - 2 - int(char == '?'))
            t %= MOD
            ans = (ans + t) % MOD
    print(int(ans))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

for i, s in enumerate(S, start=1):
    if s == "?":
        s = "ABC"
    for j in s:
        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 j == "A":
            dp[i][1] += dp[i-1][0]
            dp[i][1] %= mod
        elif j == "B":
            dp[i][2] += dp[i-1][1]
            dp[i][2] %= mod
        elif j == "C":
            dp[i][3] += dp[i-1][2]
            dp[i][3] %= mod

print(dp[N][3] % mod)

Submission status: Time Limit Exceeded

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

dp = [1, 0, 0, 0]
for s in S:
    newDP = [0, 0, 0, 0]
    if s == "?":
        s = "ABC"
    for i in s:
        newDP[0] += dp[0]
        newDP[1] += dp[1]
        newDP[2] += dp[2]
        newDP[3] += dp[3]
        if i == "A":
            newDP[1] += dp[0]
            newDP[1] %= mod
        elif i == "B":
            newDP[2] += dp[1]
            newDP[2] %= mod
        elif i == "C":
            newDP[3] += dp[2]
            newDP[3] %= mod
    dp = newDP

print(dp[3] % mod)

Submission status: Time Limit Exceeded

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

dp = {"": 0, "A": 0, "AB": 0, "ABC": 0}
dp[""] = 1

for s in S:
    newDP = {"": 0, "A": 0, "AB": 0, "ABC": 0}
    if s == "?":
        s = "ABC"

    for i in s:
        # 入れない
        newDP[""] += dp[""]
        newDP["A"] += dp["A"]
        newDP["AB"] += dp["AB"]
        newDP["ABC"] += dp["ABC"]
        if i == "A":
            newDP["A"] += dp[""]
            newDP["A"] %= mod
        elif i == "B":
            newDP["AB"] += dp["A"]
            newDP["AB"] %= mod
        else:
            newDP["ABC"] += dp["AB"]
            newDP["ABC"] %= mod
    dp = newDP


print(dp["ABC"])

Submission status: Time Limit Exceeded

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

dp = defaultdict(int)
dp[""] = 1

for s in S:
    newDP = defaultdict(int)
    if s == "?":
        s = "ABC"

    for i in s:
        # 入れない
        newDP[""] += dp[""]
        newDP["A"] += dp["A"]
        newDP["AB"] += dp["AB"]
        newDP["ABC"] += dp["ABC"]
        if i == "A":
            newDP["A"] += dp[""]
            newDP["A"] %= mod
        elif i == "B":
            newDP["AB"] += dp["A"]
            newDP["AB"] %= mod
        else:
            newDP["ABC"] += dp["AB"]
            newDP["ABC"] %= mod
    dp = newDP


print(dp["ABC"])

Submission status: Time Limit Exceeded

Solution code:
S=input()
A=0 #Aの数
B=0 #ABの数
C=0 #ABCの数
n=1 #通り数
mod=10**9+7
for s in S:
    if s=="?":
        C=3*C+B
        B=3*B+A
        A=3*A+n
        n*=3
    elif s=="A":
        A+=n
    elif s=="B":
        B+=A
    else:
        C+=B
    A%=mod
    B%=mod
    C%=mod
print(C)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
# from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

s=input()
dp=[[0]*(len(s)+1) for i in range(4)]
dp[0][0]=1
lst="ABC"
for i in range(len(s)):
    for j in range(3):
        m1=1
        m2=0
        if s[i]=="?":
            m1=3
            m2=1
        
        if lst[j]==s[i]:
            m2=1
        
        dp[j][i+1]+=m1*dp[j][i]
        dp[j+1][i+1]+=m2*dp[j][i]
        dp[j][i]%=mod
        
    if s[i]=="?":
        dp[3][i+1]+=3*dp[3][i]
    else:
        dp[3][i+1]+=dp[3][i]
    dp[3][i]%=mod

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

Submission status: Time Limit Exceeded

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
# from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

s=input()
ab=[0,0]
ans=0
cnt=0
for i in range(len(s)):
    if s[i]=="A":
        ab[0]+=pow(3,cnt)
    elif s[i]=="B":
        ab[1]+=ab[0]
    elif s[i]=="C":
        ans+=ab[1]
    else:
        ans=ab[1]+3*ans
        ab[1]=ab[0]+3*ab[1]
        ab[0]=pow(3,cnt,mod)+3*ab[0]
        cnt+=1
    ab[0]%=mod
    ab[1]%=mod
    ans%=mod
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
# from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

s=input()
ab=[0,0]
ans=0
cnt=0
for i in range(len(s)):
    if s[i]=="A":
        ab[0]+=pow(3,cnt)
    elif s[i]=="B":
        ab[1]+=ab[0]
    elif s[i]=="C":
        ans+=ab[1]
    else:
        ans=ab[1]+3*ans
        ab[1]=ab[0]+3*ab[1]
        ab[0]=pow(3,cnt)+3*ab[0]
        cnt+=1
    ab[0]%=mod
    ab[1]%=mod
    ans%=mod
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
s=input()
mod=10**9+7
retnum={"?":0,"A":1,"B":2,"C":3}
count=[[0 for i in range(len(s))] for j in range(4)]
for i in range(len(s)):
    for j in range(4):
        if retnum[s[i]] == j:
            count[j][i]=count[j][i-1]+1
        else:
            count[j][i]=count[j][i-1]
ans=0
for i in range(1,len(s)-1):
    if s[i]=="B" or s[i]=="?":
        ans+=((3**(max(0,count[0][i-1]-1)))*count[0][i-1]+(3**count[0][i-1])*count[1][i-1])*(3**(max(0,count[0][-1]-count[0][i]-1))*(count[0][-1]-count[0][i])+(3**(count[0][-1]-count[0][i]))*(count[3][-1]-count[3][i]))
        ans%=mod
print(ans)

Submission status: Time Limit Exceeded

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

S = input().rstrip()
N = len(S)
mod = 10**9 + 7
cnt = 0
A = B = C = 0
for c in S:
    if c == 'A':
        A += 3**cnt
    if c == 'B':
        B += A
    if c == 'C':
        C += B
    if c == '?':
        C = C * 3 + B
        B = B * 3 + A
        A = A * 3 + pow(3, cnt, mod)
        cnt += 1
    A %= mod
    B %= mod
    C %= mod
print(C)

Submission status: Time Limit Exceeded

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

S = input().rstrip()
N = len(S)
mod = 10**9 + 7
cnt = 0
A = B = C = 0
for c in S:
    if c == 'A':
        A += 3**cnt
    if c == 'B':
        B += A
    if c == 'C':
        C += B
    if c == '?':
        C = C * 3 + B
        B = B * 3 + A
        A = A * 3 + 3**cnt
        cnt += 1
    A %= mod
    B %= mod
    C %= mod
print(C)

Submission status: Time Limit Exceeded

Solution code:
s = input()
n = len(s)
p = 10 ** 9 + 7

# i = 0, ..., nについて
# dp[i][0] = i文字目まででありうる文字列の数（ABCなら1、AB?なら3）
# dp[i][1] = i文字目までに含まれるAの数
# dp[i][2] = i文字目までに含まれるABのパターン数
# dp[i][3] = i文字目までに含まれるABCのパターン数
dp = [[0 for j in range(4)] for i in range(n + 1)]
dp[0][0] = 1 # ''空の文字列は1パターン
for j in range(1, 4):
    dp[0][j] = 0  # 空の文字列にはAもABもABCも入っていない

for i in range(1, n + 1):
    m = 3 if s[i - 1] == '?' else 1

    for j in range(4):
        dp[i][j] = dp[i - 1][j] * m

    if s[i - 1] == 'A' or s[i - 1] == '?':
        dp[i][1] =  (dp[i][1] + dp[i - 1][0]) % p
    if s[i - 1] == 'B' or s[i - 1] == '?':
        dp[i][2] = (dp[i][2] + dp[i - 1][1]) % p
    if s[i - 1] == 'C' or s[i - 1] == '?':
        dp[i][3] = (dp[i][3] + dp[i - 1][2]) % p

print(dp[n][3])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
s = input()
n = len(s)
p = 10 ** 9 + 7

q = s.count('?')
l_a = [0] * n  # l_a[i] := s[i]より左にあるAの数
l_x = [0] * n  # l_x[i] := s[i]より左にある?の数
r_c = [0] * n  # r_c[i] := s[i]より右にあるCの数
r_x = [0] * n  # r_x[i] := s[i]より右にある?の数

for i in range(1, n):  # 1〜n-1
    l_a[i] = l_a[i - 1] + int(s[i - 1] == 'A')
    l_x[i] = l_x[i - 1] + int(s[i - 1] == '?')
    r_c[n - i - 1] = r_c[n - i] + int(s[n - i] == 'C')
    r_x[n - i - 1] = r_x[n - i] + int(s[n - i] == '?')

ans = 0
for i in range(n):
    if s[i] == 'B':
        ans += (l_a[i] * r_c[i] % p) * (3 ** q % p) % p       # ABC
        if q >= 1:
            ans += (l_x[i] * r_c[i] % p) * (3 ** (q - 1) % p) % p # ?BC
            ans += (l_a[i] * r_x[i] % p) * (3 ** (q - 1) % p) % p # AB?
        if q >= 2:
            ans += (l_x[i] * r_x[i] % p) * (3 ** (q - 2) % p) % p # ?B?
        ans %= p
    elif s[i] == '?':
        if q >= 1:
            ans += (l_a[i] * r_c[i] % p) * (3 ** (q - 1) % p) % p # A?C
        if q >= 2:
            ans += (l_x[i] * r_c[i] % p) * (3 ** (q - 2) % p) % p # ??C
            ans += (l_a[i] * r_x[i] % p) * (3 ** (q - 2) % p) % p # A??
        if q >= 3:
            ans += (l_x[i] * r_x[i] % p) * (3 ** (q - 3) % p) % p # ???
        ans %= p

print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
n = len(s)
p = 10 ** 9 + 7
 
q = s.count('?')
l_a = [0] * n  # l_a[i] := s[i]より左にあるAの数
l_x = [0] * n  # l_x[i] := s[i]より左にある?の数
r_c = [0] * n  # r_c[i] := s[i]より右にあるCの数
r_x = [0] * n  # r_x[i] := s[i]より右にある?の数
 
for i in range(1, n):  # 1〜n-1
    l_a[i] = l_a[i - 1] + int(s[i - 1] == 'A')
    l_x[i] = l_x[i - 1] + int(s[i - 1] == '?')
    r_c[n - i - 1] = r_c[n - i] + int(s[n - i] == 'C')
    r_x[n - i - 1] = r_x[n - i] + int(s[n - i] == '?')
 
ans = 0
for i in range(n):
    if s[i] == 'B':
        ans += (l_a[i] * r_c[i] % p) * (3 ** q % p) % p       # ABC
        if q >= 1:
            ans += (l_x[i] * r_c[i] % p) * (3 ** (q - 1) % p) % p # ?BC
            ans += (l_a[i] * r_x[i] % p) * (3 ** (q - 1) % p) % p # AB?
        if q >= 2:
            ans += (l_x[i] * r_x[i] % p) * (3 ** (q - 2) % p) % p # ?B?
        ans %= p
    elif s[i] == '?':
        if q >= 1:
            ans += (l_a[i] * r_c[i] % p) * (3 ** (q - 1) % p) % p # A?C
        if q >= 2:
            ans += (l_x[i] * r_c[i] % p) * (3 ** (q - 2) % p) % p # ??C
            ans += (l_a[i] * r_x[i] % p) * (3 ** (q - 2) % p) % p # A??
        if q >= 3:
            ans += (l_x[i] * r_x[i] % p) * (3 ** (q - 3) % p) % p # ???
        ans %= p
 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
n = len(s)
p = 10 ** 9 + 7

q = s.count('?')
l_a = [0] * n  # l_a[i] := s[i]より左にあるAの数
l_x = [0] * n  # l_x[i] := s[i]より左にある?の数
r_c = [0] * n  # r_c[i] := s[i]より右にあるCの数
r_x = [0] * n  # r_x[i] := s[i]より右にある?の数

for i in range(1, n):  # 1〜n-1
    l_a[i] = l_a[i - 1] + int(s[i - 1] == 'A')
    l_x[i] = l_x[i - 1] + int(s[i - 1] == '?')
    r_c[n - i - 1] = r_c[n - i] + int(s[n - i] == 'C')
    r_x[n - i - 1] = r_x[n - i] + int(s[n - i] == '?')

ans = 0
for i in range(n):
    if s[i] == 'B':
        ans += (l_a[i] * r_c[i] % p) * (3 ** q % p) % p       # ABC
        if q >= 1:
            ans += (l_x[i] * r_c[i] % p) * (3 ** (q - 1) % p) % p # ?BC
            ans += (l_a[i] * r_x[i] % p) * (3 ** (q - 1) % p) % p # AB?
        if q >= 2:
            ans += (l_x[i] * r_x[i] % p) * (3 ** (q - 2) % p) % p # ?B?
        ans %= p
    elif s[i] == '?':
        if q >= 1:
            ans += (l_a[i] * r_c[i] % p) * (3 ** (q - 1) % p) % p # A?C
        if q >= 2:
            ans += (l_x[i] * r_c[i] % p) * (3 ** (q - 2) % p) % p # ??C
            ans += (l_a[i] * r_x[i] % p) * (3 ** (q - 2) % p) % p # A??
        if q >= 3:
            ans += (l_x[i] * r_x[i] % p) * (3 ** (q - 3) % p) % p # ???
        ans %= p

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
class cmbs(object):
    def __init__(self, mod):
        self.mod = mod
        self.g1 = [1, 1]
        self.g2 = [1, 1]
        inverse = [0, 1]
        for i in range(2, 10 ** 6 + 1):
            self.g1.append((self.g1[-1] * i) % mod)
            inverse.append((-inverse[mod % i] * (mod // i)) % mod)
            self.g2.append((self.g2[-1] * inverse[-1]) % mod)
    @lru_cache(maxsize=None)
    def cmb(self, n, r):
        if n > 10 ** 6:
            return self.cmbl(n, r)
        return self.cmbr(n, r)

    def cmbr(self, n, r):
        if r < 0 or r > n:
            return 0
        r = min(r, n - r)
        return self.g1[n] * self.g2[r] * self.g2[n-r] % self.mod

    def cmbl(self, n, r):
        t = 1
        r = min(r, n-r)
        for i in range(n - r + 1, n + 1):
            t = t * i % self.mod
        return t * self.g2[r] % self.mod
def main():
    S = input()
    mod = 10**9 + 7
    n = len(S)
    A = [0] * n
    B = [0] * n
    C = [0] * n
    Q = [0] * n
    d = {'A':0, 'B':0, 'C':0, '?':0}
    for i, v in enumerate(S):
        d[v] += 1
        A[i] = d['A']
        B[i] = d['B']
        C[i] = d['C']
        Q[i] = d['?']
    r = 0
    c = cmbs(mod)
    t = d['?']
    # ???
    if t >= 3:
        r += c.cmb(t, 3) * pow(3, t - 3)
        r %= mod
    if t >= 2:
        for i in range(n):
            p = t - Q[i]
            # A??
            if S[i] == 'A' and p >= 2:
                r += c.cmb(p, 2) * pow(3, t-2)
                r %= mod
            # ?B?
            if S[i] == 'B' and Q[i] >= 1 and p >= 1:
                r += Q[i] * p * pow(3, t-2)
                r %= mod
            # ??C
            if S[i] == 'C' and Q[i] >= 2:
                r += c.cmb(Q[i], 2) * pow(3, t-2)
                r %= mod
    if t >= 1:
        for i in range(n):
            if S[i] == 'B':
                #AB?
                r += A[i] * (t - Q[i]) * pow(3, t-1)
                r %= mod
                #?BC
                r += Q[i] * (d['C']-C[i]) * pow(3, t-1)
                r %= mod
            if S[i] == '?':
                #A?C
                r += A[i] * (d['C']-C[i]) * pow(3, t-1)
                r %= mod
    for i in range(n):
        if S[i] == 'B':
            r += A[i] * (d['C'] - C[i]) * pow(3, t)
    r %= mod
    return r
print(main())

Submission status: Time Limit Exceeded

Solution code:
s=input()
n=len(s)
mod=10**9+7
dp=[ [0]*3 for _ in range(n)]
#dp[i][0] count of A's in all possible strings u generate till i
#dp[i][1] count of AB's ''
#dp[i][2] count of ABC's ''
cnt=1
for i in range(n):
    if s[i]=='?':
        if i>0:
            dp[i][2]=dp[i-1][1]+3*dp[i-1][2]
            dp[i][1]=dp[i-1][0]+3*dp[i-1][1]
            dp[i][0]=3*dp[i-1][0]+1*cnt
        else:
            dp[i][0]=1
        cnt*=3
        cnt%=mod
    elif s[i]=='C':
        if i>0:
            dp[i][2]=dp[i-1][1]+dp[i-1][2]
            dp[i][1]=dp[i-1][1]
            dp[i][0]=dp[i-1][0]
    elif s[i]=='B':
        if i>0:
            dp[i][2]=dp[i-1][2]
            dp[i][1]=dp[i-1][0]+dp[i-1][1]
            dp[i][0]=dp[i-1][0]
    elif s[i]=='A':
        if i>0:
            dp[i][2]=dp[i-1][2]
            dp[i][1]=dp[i-1][1]
            dp[i][0]=dp[i-1][0]+1*cnt
        else:
            dp[0][0]=1

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

Submission status: Time Limit Exceeded

Solution code:
s=input()
mod=10**9+7
nagasa=len(s)
dp=[[0 for _ in range(4)] for _ in range(nagasa+1)]
dp[0][0]=1
for i in range(nagasa):
    moji=s[i]
    for j in range(4):
        ni=i+1
        nj=j    
        if moji == '?':
            dp[ni][nj]+=3*dp[i][j]
            if j==0:
                nj=1
                dp[ni][nj]+=dp[i][j]
                dp[ni][nj]%=mod
            elif j==1:
                nj=2
                dp[ni][nj]+=dp[i][j]
                dp[ni][nj]%=mod
            elif j==2:
                nj=3
                dp[ni][nj]+=dp[i][j]
                dp[ni][nj]%=mod
        else:
            dp[ni][nj]+=dp[i][j]        
            if moji=='A' and j==0:
                nj=1
                dp[ni][nj]+=dp[i][j]
            elif moji=='B' and j==1:
                nj=2
                dp[ni][nj]+=dp[i][j]
            elif moji=='C' and j==2:
                nj=3
                dp[ni][nj]+=dp[i][j]
            dp[ni][nj]%=mod
print(dp[nagasa][3]%mod)

Submission status: Time Limit Exceeded

Solution code:
s=input()
mod=10**9+7
nagasa=len(s)
dp=[[0 for _ in range(4)] for _ in range(nagasa+1)]
dp[0][0]=1
for i in range(nagasa):
    moji=s[i]
    for j in range(4):
        ni=i+1
        nj=j    
        if moji == '?':
            dp[ni][nj]+=3*dp[i][j]
            if j==0:
                nj=1
                dp[ni][nj]+=dp[i][j]
                dp[ni][nj]%=mod
            elif j==1:
                nj=2
                dp[ni][nj]+=dp[i][j]
                dp[ni][nj]%=mod
            elif j==2:
                nj=3
                dp[ni][nj]+=dp[i][j]
                dp[ni][nj]%=mod
        else:
            dp[ni][nj]+=dp[i][j]        
            if moji=='A' and j==0:
                nj=1
                dp[ni][nj]+=dp[i][j]
            if moji=='B' and j==1:
                nj=2
                dp[ni][nj]+=dp[i][j]
            if moji=='C' and j==2:
                nj=3
                dp[ni][nj]+=dp[i][j]
            dp[ni][nj]%=mod
print(dp[nagasa][3]%mod)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7

s=input()
Anum = 0
ABnum = 0
ABCnum = 0
q = 0
for c in s:
    if c == 'A':
        Anum = (Anum+3**q)%MOD
    elif c == 'B':
        ABnum = (ABnum+Anum)%MOD
    elif c == 'C':
        ABCnum = (ABCnum+ABnum)%MOD
    else:
        Anum,ABnum,ABCnum = 3*Anum+3**q,3*ABnum+Anum,3*ABCnum+ABnum
        Anum,ABnum,ABCnum = Anum%MOD,ABnum%MOD,ABCnum%MOD
        q += 1
print(ABCnum)