Problem:


Score : 400 points

Problem Statement

The ABC number of a string T is the number of triples of integers (i, j, k) that satisfy all of the following conditions:

1 ≤ i < j < k ≤ |T| (|T| is the length of T.)

T_i = A (T_i is the i-th character of T from the beginning.)

T_j = B

T_k = C

For example, when T = ABCBC, there are three triples of integers (i, j, k) that satisfy the conditions: (1, 2, 3), (1, 2, 5), (1, 4, 5). Thus, the ABC number of T is 3.

You are given a string S. Each character of S is A, B, C or ?.

Let Q be the number of occurrences of ? in S. We can make 3^Q strings by replacing each occurrence of ? in S with A, B or C. Find the sum of the ABC numbers of all these strings.

This sum can be extremely large, so print the sum modulo 10^9 + 7.

Constraints

3 ≤ |S| ≤ 10^5

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

Input

Input is given from Standard Input in the following format:

S

Output

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

Sample Input 1

A??C

Sample Output 1

8

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

AAAC: 0

AABC: 2

AACC: 0

ABAC: 1

ABBC: 2

ABCC: 2

ACAC: 0

ACBC: 1

ACCC: 0

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

Sample Input 2

ABCBC

Sample Output 2

3

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

Sample Input 3

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

Sample Output 3

979596887

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



Sample input:
A??C


Sample output:
8

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys

S=sys.stdin.readline().strip()
l=len(S)

mod=10**9+7

dp=defaultdict(lambda: 0)   #dp[ (i,j) ]	i: nan-mojime,  j=0:All mojiretsu pattern , 1:A, 2:AB, 3:ABC
dp[(0,0)]=1

n=1
for i, s in enumerate(S):
	if s in "ABC":
		dp[ (i+1,0) ]=n
	elif s=="?":
		n*=3
		dp[ (i+1,0) ]=n		

nashi=0
a=1
ab=2
abc=3

for i,s in enumerate(S):
	if s =="A":
		dp[ (i+1,a) ]+=dp[ (i,nashi) ]
		dp[ (i+1,a) ]+=dp[ (i,a) ]
		dp[ (i+1,ab) ]+=dp[ (i,ab) ]
		dp[ (i+1,abc) ]+=dp[ (i,abc) ]
	elif s=="B":
		dp[ (i+1,ab) ]+=dp[ (i,ab) ]
		dp[ (i+1,ab) ]+=dp[ (i,a) ]
		dp[ (i+1,a) ]+=dp[ (i,a) ]
		dp[ (i+1,abc) ]+=dp[ (i,abc) ]
	elif s=="C":
		dp[ (i+1,abc) ]+=dp[ (i,abc) ]
		dp[ (i+1,abc) ]+=dp[ (i,ab) ]
		dp[ (i+1,a) ]+=dp[ (i,a) ]
		dp[ (i+1,ab) ]+=dp[ (i,ab) ]
	elif s=="?":
		dp[ (i+1,a) ]+=dp[ (i,a) ]*3
		dp[ (i+1,a) ]+=dp[ (i,nashi) ]
		dp[ (i+1,a) ]%=mod

		dp[ (i+1,ab) ]+=dp[ (i,ab) ]*3
		dp[ (i+1,ab) ]+=dp[ (i,a) ]	
		dp[ (i+1,ab) ]%=mod

		dp[ (i+1,abc) ]+=dp[ (i,abc) ]*3
		dp[ (i+1,abc) ]+=dp[ (i,ab) ]
		dp[ (i+1,abc) ]%=mod


print ( dp[(l,3)]%mod )

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys

S=sys.stdin.readline().strip()
l=len(S)

mod=10**9+7

dp=defaultdict(lambda: 0)   #dp[ (i,j) ]	i: nan-mojime,  j=0:All mojiretsu pattern , 1:A, 2:AB, 3:ABC
dp[(0,0)]=1

n=1
for i, s in enumerate(S):
	if s in "ABC":
		dp[ (i+1,0) ]=n
	elif s=="?":
		n*=3
		dp[ (i+1,0) ]=n		

nashi=0
a=1
ab=2
abc=3

for i,s in enumerate(S):
	if s =="A":
		dp[ (i+1,a) ]+=dp[ (i,nashi) ]
		dp[ (i+1,a) ]+=dp[ (i,a) ]
		dp[ (i+1,ab) ]+=dp[ (i,ab) ]
		dp[ (i+1,abc) ]+=dp[ (i,abc) ]
	elif s=="B":
		dp[ (i+1,ab) ]+=dp[ (i,ab) ]
		dp[ (i+1,ab) ]+=dp[ (i,a) ]
		dp[ (i+1,a) ]+=dp[ (i,a) ]
		dp[ (i+1,abc) ]+=dp[ (i,abc) ]
	elif s=="C":
		dp[ (i+1,abc) ]+=dp[ (i,abc) ]
		dp[ (i+1,abc) ]+=dp[ (i,ab) ]
		dp[ (i+1,a) ]+=dp[ (i,a) ]
		dp[ (i+1,ab) ]+=dp[ (i,ab) ]
	elif s=="?":
		dp[ (i+1,a) ]+=dp[ (i,a) ]*3
		dp[ (i+1,a) ]+=dp[ (i,nashi) ]
		dp[ (i+1,a) ]%=mod

		dp[ (i+1,ab) ]+=dp[ (i,ab) ]*3
		dp[ (i+1,ab) ]+=dp[ (i,a) ]	
		dp[ (i+1,ab) ]%=mod

		dp[ (i+1,abc) ]+=dp[ (i,abc) ]*3
		dp[ (i+1,abc) ]+=dp[ (i,ab) ]
		dp[ (i+1,abc) ]%=mod


print dp[(l,3)]%mod

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

S=raw_input()
l=len(S)

mod=10**9+7

dp=defaultdict(lambda: 0)   #dp[ (i,j) ]	i: i-mojime,  j=0:None , 1:A, 2:AB, 3:ABC
dp[(0,0)]=1

n=1
for i, s in enumerate(S):
	if s in "ABC":
		dp[ (i+1,0) ]=n
	elif s=="?":
		n*=3
		dp[ (i+1,0) ]=n		

nashi=0
a=1
ab=2
abc=3

n=0
cnt=0	# count of "?"
for i,s in enumerate(S):
	if s =="A":
		dp[ (i+1,a) ]+=dp[ (i,nashi) ]
		dp[ (i+1,a) ]+=dp[ (i,a) ]
		dp[ (i+1,ab) ]+=dp[ (i,ab) ]
		dp[ (i+1,abc) ]+=dp[ (i,abc) ]
	elif s=="B":
		dp[ (i+1,ab) ]+=dp[ (i,ab) ]
		dp[ (i+1,ab) ]+=dp[ (i,a) ]
		dp[ (i+1,a) ]+=dp[ (i,a) ]
		dp[ (i+1,abc) ]+=dp[ (i,abc) ]
	elif s=="C":
		dp[ (i+1,abc) ]+=dp[ (i,abc) ]
		dp[ (i+1,abc) ]+=dp[ (i,ab) ]
		dp[ (i+1,a) ]+=dp[ (i,a) ]
		dp[ (i+1,ab) ]+=dp[ (i,ab) ]
	elif s=="?":
		dp[ (i+1,a) ]+=dp[ (i,a) ]*3
		dp[ (i+1,a) ]+=dp[ (i,nashi) ]
		dp[ (i+1,a) ]%=mod

		dp[ (i+1,ab) ]+=dp[ (i,ab) ]*3
		dp[ (i+1,ab) ]+=dp[ (i,a) ]	
		dp[ (i+1,ab) ]%=mod

		dp[ (i+1,abc) ]+=dp[ (i,abc) ]*3
		dp[ (i+1,abc) ]+=dp[ (i,ab) ]
		dp[ (i+1,abc) ]%=mod


print dp[(l,3)]%mod

Submission status: Time Limit Exceeded

Solution code:
mod = 1000000007

S = input()
n = 1
a = 0
ab = 0
abc = 0
for s in S:
    if s in "A":
        a += n
    if s in "B":
        ab += a
    if s == "C":
        abc += ab
    if s in "?":
        n, a, ab, abc = 3 * n, 3 * a + n, 3 * ab + a, 3 * abc + ab

print(abc % mod)

Submission status: Time Limit Exceeded

Solution code:
a=[1]+[0]*4
for s in input():
 i=ord(s)-64
 if i>0:a[i]+=a[i-1]
 else:a=[a[i]*3+a[i-1]for i in range(4)]+[0]
print(a[3]%(10**9+7))

Submission status: Time Limit Exceeded

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

dp[0][0] = 1
for i in range(len(S)):
    for j in range(4):
        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]
    if S[i] == 'B' or S[i] == '?':
        dp[i + 1][2] += dp[i][1]
    if S[i] == 'C' or S[i] == '?':
        dp[i + 1][3] += dp[i][2]
        
print(dp[len(S)][3] % mod)

Submission status: Time Limit Exceeded

Solution code:
X = list(input())

q_num = X.count("?")
a_num = 0
c_num = X.count("C")
left_q_num = 0
right_q_num = q_num
ans = 0
len_x = len(X)
q_dict = []
for i in range(q_num + 1):
    q_dict.append(3 ** i % (10 ** 9 + 7))

if X[0] == "?":
    right_q_num -= 1
elif X[0] == "C":
    c_num -= 1
for i, x in enumerate(X):
    if x == "B" or x == "?":
        ans += (a_num * c_num)  * (q_dict[(left_q_num + right_q_num)])
        if left_q_num + right_q_num >= 2:
            ans += (right_q_num * left_q_num  + 3*(left_q_num * c_num) + 3*(right_q_num * a_num)) * (q_dict[(left_q_num + right_q_num - 2)])
        elif left_q_num + right_q_num == 1:
            ans += ((left_q_num * c_num) + (right_q_num * a_num)) * (q_dict[(left_q_num + right_q_num - 1)])
        ans = ans % (10 ** 9 + 7)
    if  i == len_x - 1:
        break
    if x == "A":
        a_num += 1
    elif x == "?":
        left_q_num += 1
    if X[i + 1] == "C":
        c_num -= 1
    elif X[i + 1] == "?":
        right_q_num -= 1

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

Submission status: Time Limit Exceeded

Solution code:
X = list(input())

q_num = X.count("?")
a_num = 0
c_num = X.count("C")
left_q_num = 0
right_q_num = q_num
ans = 0
len_x = len(X)
q_dict = {}
for i in range(q_num + 1):
    q_dict[i] = 3 ** i

if X[0] == "?":
    right_q_num -= 1
elif X[0] == "C":
    c_num -= 1
for i, x in enumerate(X):
    if x == "B" or x == "?":
        ans += (a_num * c_num)  * (q_dict[(left_q_num + right_q_num)])
        if left_q_num + right_q_num >= 2:
            ans += (right_q_num * left_q_num  + 3*(left_q_num * c_num) + 3*(right_q_num * a_num)) * (q_dict[(left_q_num + right_q_num - 2)])
        elif left_q_num + right_q_num == 1:
            ans += ((left_q_num * c_num) + (right_q_num * a_num)) * (q_dict[(left_q_num + right_q_num - 1)])
        ans = ans % (10 ** 9 + 7)
    if  i == len_x - 1:
        break
    if x == "A":
        a_num += 1
    elif x == "?":
        left_q_num += 1
    if X[i + 1] == "C":
        c_num -= 1
    elif X[i + 1] == "?":
        right_q_num -= 1

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

Submission status: Time Limit Exceeded

Solution code:
X = list(input())

q_num = X.count("?")
a_num = 0
c_num = X.count("C")
left_q_num = 0
right_q_num = q_num
ans = 0
len_x = len(X)
if X[0] == "?":
    right_q_num -= 1
elif X[0] == "C":
    c_num -= 1
for i, x in enumerate(X):
    if x == "B" or x == "?":
        ans += (a_num * c_num)  * (3 ** (left_q_num + right_q_num))
        if left_q_num + right_q_num >= 2:
            ans += (right_q_num * left_q_num  + 3*(left_q_num * c_num) + 3*(right_q_num * a_num)) * (3 ** (left_q_num + right_q_num - 2))
        elif left_q_num + right_q_num == 1:
            ans += ((left_q_num * c_num) + (right_q_num * a_num)) * (3 ** (left_q_num + right_q_num - 1))
        ans = ans % (10 ** 9 + 7)
    if  i == len_x - 1:
        break
    if x == "A":
        a_num += 1
    elif x == "?":
        left_q_num += 1
    if X[i + 1] == "C":
        c_num -= 1
    elif X[i + 1] == "?":
        right_q_num -= 1

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

Submission status: Time Limit Exceeded

Solution code:
X = list(input())

q_num = X.count("?")
a_num = 0
c_num = X.count("C")
left_q_num = 0
right_q_num = q_num
ans = 0
if X[0] == "?":
    right_q_num -= 1
elif X[0] == "C":
    c_num -= 1
for i, x in enumerate(X):
    if x == "B" or x == "?":
        ans += (a_num * c_num)  * (3 ** (left_q_num + right_q_num))
        if left_q_num + right_q_num != 0:
            ans += (left_q_num * c_num ) * (3 ** (left_q_num + right_q_num - 1))
            ans += (right_q_num * a_num) * (3 ** (left_q_num + right_q_num - 1))
        if left_q_num + right_q_num >= 2:
            ans += (right_q_num * left_q_num) * (3 ** (left_q_num + right_q_num - 2))
        ans = ans % (10 ** 9 + 7)
    if  i == len(X) - 1:
        break
    if x == "A":
        a_num += 1
    elif x == "?":
        left_q_num += 1
    if X[i + 1] == "C":
        c_num -= 1
    elif X[i + 1] == "?":
        right_q_num -= 1

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

Submission status: Time Limit Exceeded

Solution code:
X = list(input())

q_num = X.count("?")
a_num = 0
c_num = X.count("C")
left_q_num = 0
right_q_num = q_num
# ある値を軸に その左にあるaの数 * (3 のはてなの数上)  + ?の数
# a_num
# left_q_num
# right_q_num
# c_num
ans = 0
if X[0] == "?":
    right_q_num -= 1
elif X[0] == "C":
    c_num -= 1
for i, x in enumerate(X):
    if x == "B" or x == "?":
        ans += (a_num * c_num)  * (3 ** (left_q_num + right_q_num))
        if left_q_num + right_q_num != 0:
            ans += (left_q_num * c_num ) * (3 ** (left_q_num + right_q_num - 1))
            ans += (right_q_num * a_num) * (3 ** (left_q_num + right_q_num - 1))
        if left_q_num + right_q_num >= 2:
            ans += (right_q_num * left_q_num) * (3 ** (left_q_num + right_q_num - 2))
    #print("i", i)
    #print(ans)    
    #print(a_num)
    if  i == len(X) - 1:
        break
    if x == "A":
        a_num += 1
    elif x == "?":
        left_q_num += 1
    if X[i + 1] == "C":
        c_num -= 1
    elif X[i + 1] == "?":
        right_q_num -= 1

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

Submission status: Time Limit Exceeded

Solution code:
#ABC104D
S=input()
A=[0 for _ in range(len(S))]
QA=[0 for _ in range(len(S))]
C=[0 for _ in range(len(S))]
QC=[0 for _ in range(len(S))]
ta=0
tqa=0
tc=0
tqc=0
for i in range(len(S))[::-1]:
    if S[i]=='C':
        tc+=1
    elif S[i]=='?':
        tqc+=1
    C[i]=tc
    QC[i]=tqc
ans=0
for i in range(len(S)):
    if S[i]=='A':
        ta+=1
    elif S[i]=='?':
        tqa+=1
    A[i]=ta
    QA[i]=tqa
    if S[i]=='B':
        ans+=A[i]*C[i]*(3**tqc)%(10**9+7)
        ans+=A[i]*QC[i]*(3**max(0,tqc-1))%(10**9+7)
        ans+=QA[i]*C[i]*(3**max(0,tqc-1))%(10**9+7)
        ans+=QA[i]*QC[i]*(3**max(0,tqc-2))%(10**9+7)
    elif S[i]=='?':
        ans+=A[i]*C[i]*(3**max(0,tqc-1))%(10**9+7)
        ans+=A[i]*max(0,QC[i]-1)*(3**max(0,tqc-2))%(10**9+7)
        ans+=max(0,QA[i]-1)*C[i]*(3**max(0,tqc-2))%(10**9+7)
        ans+=max(0,QA[i]-1)*max(0,QC[i]-1)*(3**max(0,tqc-3))%(10**9+7)
    ans%=(10**9+7)
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
#ABC104D
S=input()
A=[0 for _ in range(len(S))]
QA=[0 for _ in range(len(S))]
C=[0 for _ in range(len(S))]
QC=[0 for _ in range(len(S))]
ta=0
tqa=0
for i in range(len(S)):
    if S[i]=='A':
        ta+=1
    elif S[i]=='?':
        tqa+=1
    A[i]=ta
    QA[i]=tqa
tc=0
tqc=0
for i in range(len(S))[::-1]:
    if S[i]=='C':
        tc+=1
    elif S[i]=='?':
        tqc+=1
    C[i]=tc
    QC[i]=tqc
ans=0
for i in range(len(S)):
    if S[i]=='B':
        ans+=A[i]*C[i]*(3**tqa)
        ans+=A[i]*QC[i]*(3**max(0,tqa-1))
        ans+=QA[i]*C[i]*(3**max(0,tqa-1))
        ans+=QA[i]*QC[i]*(3**max(0,tqa-2))
    elif S[i]=='?':
        ans+=A[i]*C[i]*(3**max(0,tqa-1))
        ans+=A[i]*max(0,QC[i]-1)*(3**max(0,tqa-2))
        ans+=max(0,QA[i]-1)*C[i]*(3**max(0,tqa-2))
        ans+=max(0,QA[i]-1)*max(0,QC[i]-1)*(3**max(0,tqa-3))
    ans%=(10**9+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#ABC104D
S=input()
A=[0 for _ in range(len(S))]
QA=[0 for _ in range(len(S))]
C=[0 for _ in range(len(S))]
QC=[0 for _ in range(len(S))]
ta=0
tqa=0
for i in range(len(S)):
    if S[i]=='A':
        ta+=1
    elif S[i]=='?':
        tqa+=1
    A[i]=ta
    QA[i]=tqa
tc=0
tqc=0
for i in range(len(S))[::-1]:
    if S[i]=='C':
        tc+=1
    elif S[i]=='?':
        tqc+=1
    C[i]=tc
    QC[i]=tqc
ans=0
for i in range(len(S)):
    if S[i]=='B':
        ans+=A[i]*C[i]*(3**tqa)
        ans+=A[i]*QC[i]*(3**max(0,tqa-1))
        ans+=QA[i]*C[i]*(3**max(0,tqa-1))
        ans+=QA[i]*QC[i]*(3**max(0,tqa-2))
    elif S[i]=='?':
        ans+=A[i]*C[i]*(3**max(0,tqa-1))
        ans+=A[i]*max(0,QC[i]-1)*(3**max(0,tqa-2))
        ans+=max(0,QA[i]-1)*C[i]*(3**max(0,tqa-2))
        ans+=max(0,QA[i]-1)*max(0,QC[i]-1)*(3**max(0,tqa-3))
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
s = input()

a = [0] * len(s)
b = [0] * len(s)
c = [0] * len(s)
q = 0

if s[0] == "A":
    a[0] = 1
elif s[0] == "?":
    a[0] = 1
    q = 1

for i in range(1, len(s)):
    if s[i] == "A":
        a[i] = a[i - 1] + 3**q
        b[i] = b[i - 1]
        c[i] = c[i - 1]
    elif s[i] == "B":
        a[i] = a[i - 1]
        b[i] = b[i - 1] + a[i - 1]
        c[i] = c[i - 1]
    elif s[i] == "C":
        a[i] = a[i - 1]
        b[i] = b[i - 1]
        c[i] = c[i - 1] + b[i - 1]
    else:
        a[i] = 3 * a[i - 1] + 3**q
        b[i] = 3 * b[i - 1] + a[i - 1]
        c[i] = 3 * c[i - 1] + b[i - 1]
        q += 1
        
print(c[len(s) - 1] % (10**9 + 7))

Submission status: Time Limit Exceeded

Solution code:
s = input()

A = [1,0]
AB = 0
ABC = 0
D = 10**9 + 7
for c in s:
    if c == 'A':
        A[1] += A[0]
    elif c == 'B':
        AB += A[1]
    elif c == 'C':
        ABC += AB
    elif c == '?':
        ABC = (((ABC)%D *3)%D + (AB)%D)%D
        AB *= 3#AB + C and AB + B and AB + C
        AB += A[1] # AB + B
        A[1] = A[1]*3 + A[0]
        A[0] *= 3

print(ABC%D)

Submission status: Time Limit Exceeded

Solution code:
s = input()

A = [1,0]
AB = 0
ABC = 0
D = 10**9 + 7
for c in s:
    if c == 'A':
        A[1] += A[0]
    elif c == 'B':
        AB += A[1]
    elif c == 'C':
        ABC += AB
    elif c == '?':
        ABC = ABC*3 + AB
        AB *= 3#AB + C and AB + B and AB + C
        AB += A[1] # AB + B
        A[1] = A[1]*3 + A[0]
        A[0] *= 3

print(ABC%D)

Submission status: Time Limit Exceeded

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

dp = [0, 0, 0, 0]
dp[0] = 1

for s in S:
    factor = 3 if s == '?' else 1
    for j, c in zip([2, 1, 0], 'CBA'):
        dp[j + 1] *= factor
        if s == c or s == '?':
            dp[j + 1] += dp[j]
    if s == '?':
        dp[0] *= 3

ans = dp[-1] % MOD

print(ans)

Submission status: Time Limit Exceeded

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

dp = [0, 0, 0, 0]
dp[0] = 1

for s in S:
    factor = 3 if s == '?' else 1
    for j, c in zip([2, 1, 0], 'CBA'):
        dp[j + 1] *= factor
        if s in c + '?':
            dp[j + 1] += dp[j]
    if s == '?':
        dp[0] *= 3

ans = dp[-1] % MOD

print(ans)

Submission status: Time Limit Exceeded

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

q = 3 if S[0] == '?' else 1
a = b = c = 0
def fq():
    global a, b, c, q
    c = c * 3 + b
    b = b * 3 + a
    a = a * 3 + q
    q *= 3
def fa():
    global a
    a += q
def fb():
    global b
    b += a
def fc():
    global c
    c += b
funcs = {'A':fa, 'B': fb, 'C':fc, '?':fq}
if S[0] in 'A?':
    a = 1
for s in S[1:]:
    funcs[s]()
ans = c % MOD
print(ans)

Submission status: Time Limit Exceeded

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

q = 3 if S[0] == '?' else 1
a = b = c = 0
def fq(a, b, c, q):
    return a * 3 + q, b * 3 + a, c * 3 + b, q * 3
def fa(a, b, c, q):
    return a + q, b, c, q
def fb(a, b, c, q):
    return a, b + a, c, q
def fc(a, b, c, q):
    return a, b, c + b, q
funcs = {'A':fa, 'B': fb, 'C':fc, '?':fq}
if S[0] in 'A?':
    a = 1
from functools import reduce
ans = reduce(lambda x, y: funcs[y](*x), S[1:], (a, b, c, q))
ans = ans[2] % MOD
print(ans)

Submission status: Time Limit Exceeded

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

q = 3 if S[0] == '?' else 1
a = b = c = 0
def fq(a, b, c, q):
    return a * 3 + q, b * 3 + a, c * 3 + b, q * 3
def fa(a, b, c, q):
    return a + q, b, c, q
def fb(a, b, c, q):
    return a, b + a, c, q
def fc(a, b, c, q):
    return a, b, c + b, q
funcs = {'A':fa, 'B': fb, 'C':fc, '?':fq}
if S[0] in 'A?':
    a = 1
for s in S[1:]:
    a, b, c, q = funcs[s](a, b, c, q)

ans = c % MOD
print(ans)

Submission status: Time Limit Exceeded

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

q = 3 if S[0] == '?' else 1
a = b = c = 0
if S[0] in 'A?':
    a = 1
for s in S[1:]:
    if s == '?':
        c = c * 3 + b
        b = b * 3 + a
        a = a * 3 + q
        q *= 3
    elif s == 'A':
        a += q
    elif s == 'B':
        b += a
    elif s == 'C':
        c += b
    a, b, c = a % MOD, b % MOD, c % MOD

ans = c % MOD
print(ans)

Submission status: Time Limit Exceeded

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

q = 3 if S[0] == '?' else 1
a = b = c = 0
if S[0] in 'A?':
    a = 1
for s in S[1:]:
    if s == '?':
        c = c * 3 + b
        b = b * 3 + a
        a = a * 3 + q
        q *= 3
    elif s == 'A':
        a += q
    elif s == 'B':
        b += a
    elif s == 'C':
        c += b

ans = c % MOD
print(ans)

Submission status: Time Limit Exceeded

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

q = 3 if S[0] == '?' else 1
a = b = c = 0
if S[0] in 'A?':
    a = 1
for i, s in enumerate(S[1:], 1):
    if s == '?':
        c = c * 3 + b
        b = b * 3 + a
        a = a * 3 + q
        q *= 3
    elif s == 'A':
        a += q
    elif s == 'B':
        b += a
    elif s == 'C':
        c += b

ans = c % MOD
print(ans)

Submission status: Time Limit Exceeded

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

Qs = 3 if S[0] == '?' else 1
A = [0] * N
AB = [0] * N
ABC = [0] * N
if S[0] in 'A?':
    A[0] = 1
a, ab, abc = A[0], AB[0], ABC[0]
for i in range(1, N):
    s = S[i]
    if s == '?':
        A[i] = a * 3 + Qs
        AB[i] = ab * 3 + a
        ABC[i] = abc * 3 + ab
        Qs *= 3
    elif s == 'A':
        A[i] = a + Qs
        AB[i] = ab
        ABC[i] = abc
    elif s == 'B':
        A[i] = a
        AB[i] = ab + a
        ABC[i] = abc
    elif s == 'C':
        A[i] = a
        AB[i] = ab
        ABC[i] = abc + ab
    a, ab, abc = A[i], AB[i], ABC[i]

ans = ABC[-1] % MOD
print(ans)

Submission status: Time Limit Exceeded

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

Qs = 3 if S[0] == '?' else 1
A = [0] * N
AB = [0] * N
ABC = [0] * N
if S[0] in 'A?':
    A[0] = 1
for i in range(1, N):
    s = S[i]
    if s == '?':
        A[i] = A[i - 1] * 3 + Qs
        AB[i] = AB[i - 1] * 3 + A[i - 1]
        ABC[i] = ABC[i - 1] * 3 + AB[i - 1]
        Qs *= 3
    elif s == 'A':
        A[i] = A[i - 1] + Qs
        AB[i] = AB[i - 1]
        ABC[i] = ABC[i - 1]
    elif s == 'B':
        A[i] = A[i - 1]
        AB[i] = AB[i - 1] + A[i - 1]
        ABC[i] = ABC[i - 1]
    elif s == 'C':
        A[i] = A[i - 1]
        AB[i] = AB[i - 1]
        ABC[i] = ABC[i - 1] + AB[i - 1]

ans = ABC[-1] % MOD
print(ans)

Submission status: Time Limit Exceeded

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

Qs = 3 if S[0] == '?' else 1
A = [0] * N
AB = [0] * N
ABC = [0] * N
if S[0] in 'A?':
    A[0] = 1
for i, s in enumerate(S[1:], 1):
    if s == '?':
        A[i] = A[i - 1] * 3 + Qs
        AB[i] = AB[i - 1] * 3 + A[i - 1]
        ABC[i] = ABC[i - 1] * 3 + AB[i - 1]
        Qs *= 3
    elif s == 'A':
        A[i] = A[i - 1] + Qs
        AB[i] = AB[i - 1]
        ABC[i] = ABC[i - 1]
    elif s == 'B':
        A[i] = A[i - 1]
        AB[i] = AB[i - 1] + A[i - 1]
        ABC[i] = ABC[i - 1]
    elif s == 'C':
        A[i] = A[i - 1]
        AB[i] = AB[i - 1]
        ABC[i] = ABC[i - 1] + AB[i - 1]

ans = ABC[-1] % MOD
print(ans)

Submission status: Time Limit Exceeded

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

Qs = 3 if S[0] == '?' else 1
A = [0] * N
AB = [0] * N
ABC = [0] * N
if S[0] in 'A?':
    A[0] = 1
for i, s in enumerate(S[1:], 1):
    factor = 3 if s == '?' else 1
    A[i] = A[i - 1] * factor % MOD
    AB[i] = AB[i - 1] * factor % MOD
    ABC[i] = ABC[i - 1] * factor % MOD
    if s in 'A?':
        A[i] += Qs
    if s in 'B?':
        AB[i] += A[i - 1]
    if s in 'C?':
        ABC[i] += AB[i - 1]
    if s == '?':
        Qs *= 3

ans = ABC[-1] % MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
ABC = 'ABC'
S = list(input())

dp = [0, 0, 0, 0]
dp[3] = 1

for i in range(len(S))[::-1]:
    c = S[i]
    if c == '?':
        dp[0] = 3 * dp[0] + dp[1]
        dp[1] = 3 * dp[1] + dp[2]
        dp[2] = 3 * dp[2] + dp[3]
        dp[3] = 3 * dp[3]
    elif c == 'A':
        dp[0] = 1 * dp[0] + dp[1]
        dp[1] = 1 * dp[1]
        dp[2] = 1 * dp[2]
        dp[3] = 1 * dp[3]
    elif c == 'B':
        dp[0] = 1 * dp[0]
        dp[1] = 1 * dp[1] + dp[2]
        dp[2] = 1 * dp[2]
        dp[3] = 1 * dp[3]
    elif c == 'C':
        dp[0] = 1 * dp[0]
        dp[1] = 1 * dp[1]
        dp[2] = 1 * dp[2] + dp[3]
        dp[3] = 1 * dp[3]

print(dp[0] % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
ABC = 'ABC'
S = input()

dp = [0, 0, 0, 0]
dp[3] = 1

for i in range(len(S))[::-1]:
    c = S[i]
    if c == '?':
        dp[0] = 3 * dp[0] + dp[1]
        dp[1] = 3 * dp[1] + dp[2]
        dp[2] = 3 * dp[2] + dp[3]
        dp[3] = 3 * dp[3]
    elif c == 'A':
        dp[0] = 1 * dp[0] + dp[1]
        dp[1] = 1 * dp[1]
        dp[2] = 1 * dp[2]
        dp[3] = 1 * dp[3]
    elif c == 'B':
        dp[0] = 1 * dp[0]
        dp[1] = 1 * dp[1] + dp[2]
        dp[2] = 1 * dp[2]
        dp[3] = 1 * dp[3]
    elif c == 'C':
        dp[0] = 1 * dp[0]
        dp[1] = 1 * dp[1]
        dp[2] = 1 * dp[2] + dp[3]
        dp[3] = 1 * dp[3]

print(dp[0] % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
ABC = 'ABC'
S = input()

dp = [0, 0, 0, 0]
dp[3] = 1

for i in range(len(S)-1, -1, -1):
    c = S[i]
    if c == '?':
        m, m1 = 3, 3
    else:
        m, m1 = 1, 1

    for j in range(3):
        m2 = 1 if c == '?' or c == ABC[j] else 0
        dp[j] = m1 * dp[j] + m2 * dp[j+1]
    dp[3] = m * dp[3]

print(dp[0] % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
S = input()


ABC = 'ABC'

dp = [0, 0, 0, 0]
dp[3] = 1

for c in reversed(S):
    if c == '?':
        m, m1 = 3, 3
    else:
        m, m1 = 1, 1

    for j in range(3):
        m2 = 1 if c == '?' or c == ABC[j] else 0
        dp[j] = m1 * dp[j] + m2 * dp[j+1]
    dp[3] = m * dp[3]

print(dp[0] % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
S = ''


def we_love_abc()->int:
    global S
    ABC = 'ABC'

    dp = [0, 0, 0, 0]
    dp[3] = 1

    for c in reversed(S):
        if c == '?':
            m, m1 = 3, 3
        else:
            m, m1 = 1, 1

        for j in range(3):
            m2 = 1 if c == '?' or c == ABC[j] else 0
            dp[j] = m1 * dp[j] + m2 * dp[j+1]
        dp[3] = m * dp[3]

    return dp[0] % 1000000007


if __name__ == "__main__":
    S = input()
    ans = we_love_abc()  # S)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def we_love_abc(S: str)->int:
    ABC = 'ABC'

    dp = [0, 0, 0, 0]
    dp[3] = 1

    for c in reversed(S):
        if c == '?':
            m, m1 = 3, 3
        else:
            m, m1 = 1, 1

        for j in range(3):
            # m1 = 3 if c == '?' else 1
            m2 = 1 if c == '?' or c == ABC[j] else 0
            dp[j] = m1 * dp[j] + m2 * dp[j+1]
        # dp[3] = (3 if c == '?' else 1) * dp[3]
        dp[3] = m * dp[3]

    return dp[0] % 1000000007


if __name__ == "__main__":
    S = input()
    ans = we_love_abc(S)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def we_love_abc(S: str)->int:
    ABC = 'ABC'

    dp = [0, 0, 0, 0]
    dp[3] = 1

    for c in reversed(S):
        for j in range(3):
            m1 = 3 if c == '?' else 1
            m2 = 1 if c == '?' or c == ABC[j] else 0
            dp[j] = m1 * dp[j] + m2 * dp[j+1]
        dp[3] = (3 if c == '?' else 1) * dp[3]

    return dp[0] % 1000000007


if __name__ == "__main__":
    S = input()
    ans = we_love_abc(S)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def we_love_abc(S: str)->int:
    n = len(S)
    dp = [[0, 0, 0, 0] for _ in range(n + 1)]
    dp[n][3] = 1

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

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


if __name__ == "__main__":
    S = input()
    ans = we_love_abc(S)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))

s = input()
n = len(s)
dp = [[0 for j in range(4)] for i in range(n+1)]
dp[0][0] = 1

for i,c in enumerate(s):
    if c == "?":
        dp[i+1][0] = dp[i][0] * 3
        dp[i + 1][1] = dp[i][0] + dp[i][1] * 3
        dp[i + 1][2] = dp[i][1] + dp[i][2] * 3
        dp[i + 1][3] = dp[i][2] + dp[i][3] * 3

    elif c == "A":
        dp[i + 1][0] = dp[i][0]
        dp[i + 1][1] = dp[i][0] + dp[i][1]
        dp[i + 1][2] = dp[i][2]
        dp[i + 1][3] = dp[i][3]


    elif c == "B":
        dp[i + 1][0] = dp[i][0]
        dp[i + 1][1] = dp[i][1]
        dp[i + 1][2] = dp[i][1] + dp[i][2]
        dp[i + 1][3] = dp[i][3]

    else:
        dp[i + 1][0] = dp[i][0]
        dp[i + 1][1] = dp[i][1]
        dp[i + 1][2] = dp[i][2]
        dp[i + 1][3] = dp[i][2] + dp[i][3]

print(dp[n][3] % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9 + 7

s = input()[::-1]
n = len(s)
DP = [[0]*3 for i in range(n+1)]

htn_cnt = 0
for i, c in enumerate(list(s)):
    for j in range(3):
        if c == "?":
            DP[i+1][j] = 3*DP[i][j] % mod
        else:
            DP[i+1][j] = DP[i][j] % mod
    if c == "C" or c == "?":
        DP[i+1][0] = (DP[i+1][0] + 3**htn_cnt) % mod
    if c == "B" or c == "?":
        DP[i+1][1] = (DP[i+1][1] + DP[i][0]) % mod
    if c == "A" or c == "?":
        DP[i+1][2] = (DP[i+1][2] + DP[i][1]) % mod
    if c == "?":
        htn_cnt += 1
print(DP[n][2] % mod)

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9 + 7

s = input()[::-1]
n = len(s)
DP = [[0]*3 for i in range(n+1)]

htn_cnt = 0
for i, c in enumerate(list(s)):
    for j in range(3):
        if c == "?":
            DP[i+1][j] = 3*DP[i][j] % mod
        else:
            DP[i+1][j] = DP[i][j] % mod
    if c == "C" or c == "?":
        DP[i+1][0] += 3**htn_cnt
    if c == "B" or c == "?":
        DP[i+1][1] += DP[i][0]
    if c == "A" or c == "?":
        DP[i+1][2] += DP[i][1]
    if c == "?":
        htn_cnt += 1
print(DP[n][2] % mod)

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9 + 7

s = input()[::-1]
n = len(s)
DP = [[0]*3 for i in range(n+1)]

htn_cnt = 0
for i, c in enumerate(list(s)):
    if c == "C" or c == "?":
        DP[i+1][0] += DP[i][0] + 3**htn_cnt
        DP[i+1][1] += DP[i][1]
        DP[i+1][2] += DP[i][2]
    if c == "B" or c == "?":
        DP[i+1][0] += DP[i][0]
        DP[i+1][1] += DP[i][1] + DP[i][0]
        DP[i+1][2] += DP[i][2]
    if c == "A" or 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]
    if c == "?":
        htn_cnt += 1
    for j in range(3):
        DP[i+1][j] = DP[i+1][j] % mod
print(DP[n][2] % mod)

Submission status: Time Limit Exceeded

Solution code:
str_num, a,b,c = 1, 0, 0, 0
for i in input():
    if i == 'A':
        a += str_num
    elif i == 'B':
        b += a
    elif i == 'C':
        c += b
    else:
        str_num, a,b,c = 3*str_num, (3*a+str_num), (a+3*b), (b+3*c)
print(c % (10**9+7))

Submission status: Time Limit Exceeded

Solution code:
e,a,b,c=1,0,0,0
for i in input():
  if i == "A":
    a+=e
  elif i == "B":
    b+=a
  elif i == "C":
    c+=b
  else:
    e,a,b,c = 3*e,e+3*a,a+3*b,b+3*c
print(c%1000000007)

Submission status: Time Limit Exceeded

Solution code:
p = 1000000007
s = input()
n = len(s)
e,a,b,c = 1,0,0,0
for i in range(n):
  if s[i] == "A":
    a+=e
  elif s[i] == "B":
    b+=a
  elif s[i] == "C":
    c+=b
  else:
    e,a,b,c = 3*e,e+3*a,a+3*b,b+3*c
print(c%p)