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:
import sys
finput = sys.stdin.readline

S = finput()

MOD = 10**9 + 7

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


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

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

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

focus_on_B()

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7
dp = [0] * 4
dp[0] = 1
idx = {'A': 1, 'B': 2, 'C': 3}
for c in input():
    if c == '?':
        N, A, AB, ABC = dp
        dp = [N * 3, A * 3 + N, AB * 3 + A, ABC * 3 + AB]
    else:
        dp[idx[c]] += dp[idx[c] - 1]
print(dp[3] % MOD)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7
S = input()
dp = [[0] * 4 for _ in [0] * (len(S) + 1)]
dp[0][0] = 1
for i, c in enumerate(S):
    for j in range(4):
        dp[i + 1][j] += dp[i][j] * (1 + (c == '?') * 2)
    if c in 'A?':
        dp[i + 1][1] += dp[i][0]
    if c in 'B?':
        dp[i + 1][2] += dp[i][1]
    if c in 'C?':
        dp[i + 1][3] += dp[i][2]
print(dp[-1][3] % MOD)

Submission status: Time Limit Exceeded

Solution code:
s=input()[-1::-1]
n=len(s)
dp=[[0,0,0,0] for i in range(n+1)]
dp[0][0]=1
for i in range(n):
    for j in range(4):
        dp[i+1][j]=dp[i][j]%1000000007
    if s[i]=="?":
        dp[i+1][0]+=2*dp[i][0]
        for j in range(1,4):
            dp[i+1][j]+=2*dp[i][j]+dp[i][j-1]
    else:
        index=" CBA".find(s[i])
        dp[i+1][index]+=dp[i][index-1]
print(dp[n][3]%1000000007)

Submission status: Time Limit Exceeded

Solution code:
S = input()
dp0 = 1
dp1 = 0
dp2 = 0
dp3 = 0

for s in S:
    tmp0 = 0
    tmp1 = 0
    tmp2 = 0
    tmp3 = 0
    
    if s == 'A' or s == '?':
        tmp0 += dp0
        tmp1 += dp1
        tmp2 += dp2
        tmp3 += dp3
        tmp1 += dp0
    if s == 'B' or s == '?':
        tmp0 += dp0
        tmp1 += dp1
        tmp2 += dp2
        tmp3 += dp3
        tmp2 += dp1
    if s == 'C' or s == '?':
        tmp0 += dp0
        tmp1 += dp1
        tmp2 += dp2
        tmp3 += dp3
        tmp3 += dp2
    dp0 = tmp0
    dp1 = tmp1
    dp2 = tmp2
    dp3 = tmp3
    
print(dp3%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
S = input()
dp = [1, 0, 0, 0]
for s in S:
    tmp = [0, 0, 0, 0]
    if s == 'A' or s == '?':
        tmp[0] += dp[0]
        tmp[1] += dp[1]
        tmp[2] += dp[2]
        tmp[3] += dp[3]
        tmp[1] += dp[0]
    if s == 'B' or s == '?':
        tmp[0] += dp[0]
        tmp[1] += dp[1]
        tmp[2] += dp[2]
        tmp[3] += dp[3]
        tmp[2] += dp[1]
    if s == 'C' or s == '?':
        tmp[0] += dp[0]
        tmp[1] += dp[1]
        tmp[2] += dp[2]
        tmp[3] += dp[3]
        tmp[3] += dp[2]
    dp = tmp
print(dp[-1]%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
S = input()
dp = [[1, 0, 0, 0]]
for s in S:
    tmp = [0, 0, 0, 0]
    if s == 'A' or s == '?':
        tmp[0] += dp[-1][0]
        tmp[1] += dp[-1][1]
        tmp[2] += dp[-1][2]
        tmp[3] += dp[-1][3]
        tmp[1] += dp[-1][0]
    if s == 'B' or s == '?':
        tmp[0] += dp[-1][0]
        tmp[1] += dp[-1][1]
        tmp[2] += dp[-1][2]
        tmp[3] += dp[-1][3]
        tmp[2] += dp[-1][1]
    if s == 'C' or s == '?':
        tmp[0] += dp[-1][0]
        tmp[1] += dp[-1][1]
        tmp[2] += dp[-1][2]
        tmp[3] += dp[-1][3]
        tmp[3] += dp[-1][2]
    dp.append(tmp)
print(dp[-1][-1]%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
S = input()
l = len(S)
A,B,C,q = [0]*l,[0]*l,[0]*l,[0]*l
inf = 1000000007
for i in range(l):
    if S[i] == 'A':
        A[i] = 1
    elif S[i] == 'B':
        B[i] = 1
    elif S[i] == 'C':
        C[i] = 1
    else:
        q[i] = 1

for i in range(l-1):
    A[i+1] += A[i]
    B[i+1] += B[i]
    C[i+1] += C[i]
    q[i+1] += q[i]

ans = 0
for i in range(1,l-1):
    if S[i] == 'B':
        ans += (A[i-1]) * (C[-1]-C[i]) * (3**q[-1])
        ans %= inf
        if q[-1] >= 1:
            ans += (q[i-1]) * (C[-1] - C[i]) * (3**(q[-1]-1))
            ans %= inf
            ans += (A[i-1]) * (q[-1] - q[i]) * (3**(q[-1]-1))
            ans %= inf
        if q[-1] >= 2:
            ans += (q[i-1]) * (q[-1] - q[i]) * (3**(q[-1]-2))
            ans %= inf

    elif S[i] == '?':
        ans += (A[i-1]) * (C[-1]-C[i]) * (3**(q[-1]-1))
        ans %= inf
        if q[-1] >= 2:
            ans += (q[i-1]) * (C[-1] - C[i]) * (3**(q[-1]-2))
            ans %= inf
            ans += (A[i-1]) * (q[-1] - q[i]) * (3**(q[-1]-2))
            ans %= inf
        if q[-1] >= 3:
            ans += (q[i-1]) * (q[-1] - q[i]) * (3**(q[-1]-3))
            ans %= inf

print(ans%inf)

Submission status: Time Limit Exceeded

Solution code:
s = input()
q = s.count('?')
res = 0
mod = 10**9+7

# 前処理
# ある地点(pivot)まで(から)のA(C),?の数
bp_A,bp_Q,ap_C,ap_Q = [0],[0],[0],[0]
for c in s:
    bp_A.append(bp_A[-1]+(c=='A'))
    bp_Q.append(bp_Q[-1]+(c=='?'))
for c in s[::-1]:
    ap_C.append(ap_C[-1]+(c=='C'))
    ap_Q.append(ap_Q[-1]+(c=='?'))
ap_C,ap_Q = ap_C[::-1][1:],ap_Q[::-1][1:]

def add(num):
    global res
    res += num
    res %= mod

for pivot in range(1,len(s)-1):
    if s[pivot]=='B' or s[pivot]=='?':
        tmp = q - (s[pivot]=='?')
        s1_a,s1_q = bp_A[pivot],bp_Q[pivot]
        s2_c,s2_q = ap_C[pivot],ap_Q[pivot]
        add(s1_a * s2_c * 3**tmp)           # A,C
        add(s1_a * s2_q * 3**(tmp-1))       # A,?
        add(s1_q * s2_c * 3**(tmp-1))       # ?,C
        add(s1_q * s2_q * 3**(tmp-2))       # ?,?

print(int(res))

Submission status: Time Limit Exceeded

Solution code:
s = input()
q = s.count('?')
res = 0
mod = 10**9+7

def add(num):
    global res
    res += num
    res %= mod

for pivot in range(1,len(s)-1):
    # s[:pivot]とs[pivot+1:]に分割
    if s[pivot]=='B' or s[pivot]=='?':
        tmp = q - (s[pivot]=='?')
        s1,s2 = s[:pivot],s[pivot+1:]
        s1_a,s1_q = s1.count('A'),s1.count('?')
        s2_c,s2_q = s2.count('C'),s2.count('?')
        add(s1_a * s2_c * 3**tmp)           # A,C
        add(s1_a * s2_q * 3**(tmp-1))       # A,?
        add(s1_q * s2_c * 3**(tmp-1))       # ?,C
        add(s1_q * s2_q * 3**(tmp-2))       # ?,?

print(int(res))

Submission status: Time Limit Exceeded

Solution code:
s = input()
dp = [[0 for _ in range(0,4)] for _ in range(0,len(s)+1)]
dp[len(s)][3] = 1
dp[len(s)][0] = 0
dp[len(s)][1] = 0
dp[len(s)][2] = 0
abc = "ABC".index
for i in range(len(s)-1,-1,-1):
    m = 1
    if s[i] ==  "?":
        m=3
    dp[i][3] += m * dp[i+1][3]
for i in range(len(s)-1,-1,-1):
    if s[i] == "?":
        dp[i] = [
        dp[i+1][0]*3+ dp[i+1][1]
        ,dp[i+1][1]*3+ dp[i+1][2]
        ,dp[i+1][2]*3 + dp[i+1][3]
        ,dp[i+1][3]*3
        ]
    else:
        dp[i] = [
        dp[i+1][0]
        ,dp[i+1][1]
        ,dp[i+1][2]
        ,dp[i+1][3]
        ]
        num = abc(s[i])
        dp[i][num] += dp[i+1][num+1]
# for i in range(len(s),-1,-1):
#     print(dp[i])
print(dp[0][0] % (10**9 + 7))

Submission status: Time Limit Exceeded

Solution code:
s = input()
dp = [[0 for _ in range(0,4)] for _ in range(0,len(s)+1)]
dp[len(s)][3] = 1
dp[len(s)][0] = 0
dp[len(s)][1] = 0
dp[len(s)][2] = 0
abc = ["A","B","C"]
for i in range(len(s)-1,-1,-1):
    m = 1
    if s[i] ==  "?":
        m=3
    dp[i][3] += m * dp[i+1][3]

for i in range(len(s)-1,-1,-1):
    for j in range(0,3):
        m1,m2 = 1,0
        if s[i] == "?":
            m1,m2 = 3,1
        if s[i] == abc[j]:
            m1,m2 = 1,1
        dp[i][j] += m1 * dp[i+1][j] + m2 * dp[i+1][j+1]
        dp[i][j] %= (10**9 + 7)
# for i in range(len(s),-1,-1):
#     print(dp[i])
print(dp[0][0] % (10**9 + 7))

Submission status: Time Limit Exceeded

Solution code:
s = input()
dp = [[0 for _ in range(0,4)] for _ in range(0,len(s)+1)]
dp[len(s)][3] = 1
dp[len(s)][0] = 0
dp[len(s)][1] = 0
dp[len(s)][2] = 0
abc = ["A","B","C"]
for i in range(len(s)-1,-1,-1):
    m = 1
    if s[i] ==  "?":
        m=3
    dp[i][3] += m * dp[i+1][3]

for i in range(len(s)-1,-1,-1):
    for j in range(0,3):
        m1,m2 = 1,0
        if s[i] == "?":
            m1,m2 = 3,1
        if s[i] == abc[j]:
            m1,m2 = 1,1
        dp[i][j] += m1 * dp[i+1][j] + m2 * dp[i+1][j+1]
# for i in range(len(s),-1,-1):
#     print(dp[i])
print(dp[0][0] % (10**9 + 7))

Submission status: Time Limit Exceeded

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

A = 0
C = S.count("C") # N
q = 0

q_max = S.count("?") # N

ABC = 0
div = 10 ** 9 + 7
for si in S: # N
    if si == "A": A += 1
    elif si == "C": C -= 1
    elif si == "B":
        # ABC = (ABC + (A * C) * (3 ** q_max)) % div
        # ABC = (ABC + (q * C) * (3 ** (q_max - 1))) % div
        # ABC = (ABC + (A * (q_max - q)) * (3 ** (q_max - 1))) % div
        # ABC = (ABC + (q * (q_max - q)) * (3 ** (q_max - 2))) % div
        ABC = (ABC + (3 * A + q) * (3 * C + q_max - q) * (3 ** (q_max - 2))) % div
    else: # "?"
        # ABC = (ABC + (A * C) * (3 ** (q_max - 1))) % div
        # ABC = (ABC + (q * C) * (3 ** (q_max - 2))) % div
        # ABC = (ABC + (A * (q_max - q - 1)) * (3 ** (q_max - 2))) % div
        # ABC = (ABC + (q * (q_max - q - 1)) * (3 ** (q_max - 3))) % div        
        ABC = (ABC + (3 * A + q) * (3 * C + q_max - q - 1) * (3 ** (q_max - 3))) % div
        q += 1
    # print(si, ABC)
    
print(int(ABC))

Submission status: Time Limit Exceeded

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

A = 0
C = S.count("C") # N
q = 0

q_max = S.count("?") # N

ABC = 0
div = 10 ** 9 + 7
for si in S: # N
    if si == "A": A += 1
    elif si == "C": C -= 1
    elif si == "B":
        ABC = (ABC + (A * C) * (3 ** q_max)) % div
        ABC = (ABC + (q * C) * (3 ** (q_max - 1))) % div
        ABC = (ABC + (A * (q_max - q)) * (3 ** (q_max - 1))) % div
        ABC = (ABC + (q * (q_max - q)) * (3 ** (q_max - 2))) % div
    else: # "?"
        ABC = (ABC + (A * C) * (3 ** (q_max - 1))) % div
        ABC = (ABC + (q * C) * (3 ** (q_max - 2))) % div
        ABC = (ABC + (A * (q_max - q - 1)) * (3 ** (q_max - 2))) % div
        ABC = (ABC + (q * (q_max - q - 1)) * (3 ** (q_max - 3))) % div        
        q += 1
    # print(si, ABC)
    
print(int(ABC))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!

MOD = 1000000007
S = input()

def add(a,b):
    a += b
    if a >= MOD:
        a -= MOD
    return a

dp = [[0 for i in range(5)] for j in range(2000000)]

dp[0][0] = 1

for i in range(len(S)):
    for j in range(4):
        if S[i] == '?':
            dp[i+1][j] = add(dp[i+1][j], dp[i][j] * 3 % MOD)
        else:
            dp[i+1][j] = add(dp[i+1][j], dp[i][j])
    if S[i] == 'A' or S[i] == '?':
        dp[i+1][1] = add(dp[i+1][1], dp[i][0])
    if S[i] == 'B' or S[i] == '?':
        dp[i+1][2] = add(dp[i+1][2], dp[i][1])
    if S[i] == 'C' or S[i] == '?':
        dp[i+1][3] = add(dp[i+1][3], dp[i][2])

print(dp[len(S)][3])

Submission status: Time Limit Exceeded

Solution code:
mod = 1000000007

pow3 = [1] * 100001
for i in range(1, 100001):
    pow3[i] = pow3[i - 1] * 3

s = input()

all_a = 0
all_c = 0
all_q = 0
for c in s:
    if c == 'A':
        all_a += 1
    elif c == 'C':
        all_c += 1
    elif c == '?':
        all_q += 1
sum_a = 0
sum_c = 0
sum_q = 0
ans = 0

for c in s:
    n = 0
    if c == 'B':
        n += sum_a * (all_c - sum_c) * pow3[all_q] % mod
        n += sum_a * (all_q - sum_q) * pow3[all_q - 1] % mod
        n += sum_q * (all_c - sum_c) * pow3[all_q - 1] % mod
        n += sum_q * (all_q - sum_q) * pow3[all_q - 2] % mod
    elif c == '?':
        n += sum_a * (all_c - sum_c) * pow3[all_q - 1] % mod
        n += sum_a * (all_q - sum_q - 1) * pow3[all_q - 2] % mod
        n += sum_q * (all_c - sum_c) * pow3[all_q - 2] % mod
        n += sum_q * (all_q - sum_q - 1) * pow3[all_q - 3] % mod
    ans += n % mod
    if c == 'A':
        sum_a += 1
    elif c == 'C':
        sum_c += 1
    elif c == '?':
        sum_q += 1
print(int(ans % mod))

Submission status: Time Limit Exceeded

Solution code:
mod = 1000000007

s = input()

all_a = s.count('A')
all_c = s.count('C')
all_q = s.count('?')
sum_a = 0
sum_c = 0
sum_q = 0
ans = 0

for c in s:
    n = 0
    if c == 'B':
        n += sum_a * (all_c - sum_c) * 3 ** all_q % mod
        n += sum_a * (all_q - sum_q) * 3 ** (all_q - 1) % mod
        n += sum_q * (all_c - sum_c) * 3 ** (all_q - 1) % mod
        n += sum_q * (all_q - sum_q) * 3 ** (all_q - 2) % mod
    elif c == '?':
        n += sum_a * (all_c - sum_c) * 3 ** (all_q - 1) % mod
        n += sum_a * (all_q - sum_q - 1) * 3 ** (all_q - 2) % mod
        n += sum_q * (all_c - sum_c) * 3 ** (all_q - 2) % mod
        n += sum_q * (all_q - sum_q - 1) * 3 ** (all_q - 3) % mod
    ans += n % mod
    if c == 'A':
        sum_a += 1
    elif c == 'C':
        sum_c += 1
    elif c == '?':
        sum_q += 1
print(int(ans % mod))

Submission status: Time Limit Exceeded

Solution code:
S=raw_input()
L=len(S)

M=10**9+7

dp=[ [ 0 for i in range(4) ] for k in range(L+1) ]
all=1

for i in range(L):
	if S[i]=="A":
		dp[i+1][1]=dp[i][1]+all
		dp[i+1][2]=dp[i][2]
		dp[i+1][3]=dp[i][3]
	if S[i]=="B":
		dp[i+1][2]=dp[i][2]+dp[i][1]
		dp[i+1][3]=dp[i][3]
		dp[i+1][1]=dp[i][1]
	if S[i]=="C":
		dp[i+1][3]+=dp[i][3]+dp[i][2]
		dp[i+1][2]=dp[i][2]
		dp[i+1][1]=dp[i][1]

	if S[i]=="?":
		dp[i+1][1]=dp[i][1]*3+all
		dp[i+1][2]=dp[i][2]*3+dp[i][1]
		dp[i+1][3]=dp[i][3]*3+dp[i][2]
		all*=3

	dp[i+1][1]%=M
	dp[i+1][2]%=M
	dp[i+1][3]%=M
	all%M

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

Submission status: Time Limit Exceeded

Solution code:
S=raw_input()

M=10**9+7

all=1
abc=0
ab=0
a=0

for x in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		abc+=ab

	if x=="?":
		abc=abc*3+ab
		ab=ab*3+a
		a= a*3+all
		all*=3

	abc%=M
	ab%=M
	a%=M


print abc%M

Submission status: Time Limit Exceeded

Solution code:
S=raw_input()

M=10**9+7

all=1
abc=0
ab=0
a=0

for x in S:
	if x=="A":
		a=( a+all ) %M
	if x=="B":
		ab=( ab+a )%M
	if x=="C":
		abc=( abc+ab )%M

	if x=="?":
		abc=( abc*3+ab )%M
		ab=( ab*3+a)%M
		a=( a*3+all )%M
		all*=3

print abc%M

Submission status: Time Limit Exceeded

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

M=10**9+7

dp=[ [ 0 for i in range(4) ] for k in range(L+1) ]
all=1

abc=0
ab=0
a=0

for i in range(L):
	if S[i]=="A":
		a=( a+all ) %M
	if S[i]=="B":
		ab=( ab+a )%M
	if S[i]=="C":
		abc=( abc+ab )%M

	if S[i]=="?":
		abc=( abc*3+ab )%M
		ab=( ab*3+a)%M
		a=( a*3+all )%M
		all*=3

print (abc%M)

Submission status: Time Limit Exceeded

Solution code:
S=raw_input()
L=len(S)

M=10**9+7

dp=[ [ 0 for i in range(4) ] for k in range(L+1) ]
all=1

abc=0
ab=0
a=0

for i in range(L):
	if S[i]=="A":
		a=( a+all ) %M
	if S[i]=="B":
		ab=( ab+a )%M
	if S[i]=="C":
		abc=( abc+ab )%M

	if S[i]=="?":
		abc=( abc*3+ab )%M
		ab=( ab*3+a)%M
		a=( a*3+all )%M
		all*=3

print abc%M

Submission status: Time Limit Exceeded

Solution code:
S=raw_input()
L=len(S)

M=10**9+7

dp=[ [ 0 for i in range(4) ] for k in range(L+1)]
all=1

for i in range(L):
	if S[i]=="A":
		dp[i+1][1]=( dp[i][1]+all ) %M
		dp[i+1][2]=dp[i][2]
		dp[i+1][3]=dp[i][3]
	if S[i]=="B":
		dp[i+1][2]=( dp[i][2]+dp[i][1] )%M
		dp[i+1][3]=dp[i][3]
		dp[i+1][1]=dp[i][1]
	if S[i]=="C":
		dp[i+1][3]=( dp[i][3]+dp[i][2] )%M
		dp[i+1][2]=dp[i][2]
		dp[i+1][1]=dp[i][1]

	if S[i]=="?":
		dp[i+1][1]=( dp[i][1]*3+all )%M
		dp[i+1][2]=( dp[i][2]*3+dp[i][1] )%M
		dp[i+1][3]=( dp[i][3]*3+dp[i][2] )%M
		all*=3	

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

Submission status: Time Limit Exceeded

Solution code:
S = input()

dp = [[0 for _ in range(3 + 1)] for _ in range(len(S) + 1)]

dp[0][0] = 1
for i in range(1, len(S) + 1):
    if S[i - 1] == 'A':
        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]

        dp[i][1] += dp[i - 1][0]
    elif S[i - 1] == 'B':
        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]

        dp[i][2] += dp[i - 1][1]
    elif S[i - 1] == 'C':
        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]

        dp[i][3] += dp[i - 1][2]
    else:
        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

        dp[i][1] += dp[i - 1][0]
        dp[i][2] += dp[i - 1][1]
        dp[i][3] += dp[i - 1][2]

B = 10 ** 9 + 7
print(dp[len(S)][3] % B)

Submission status: Time Limit Exceeded

Solution code:
s = input()
dp = [[0 for _ in range(len(s) + 1)] for _ in range(4)]
# 0文字目までで0個の照合が住んだ数
dp[0][0] = 1
for i in range(0,4):
  for j in range(1, len(s) + 1):
    # ABCを進めない道
    if s[j-1] == '?':
      dp[i][j] += dp[i][j - 1] * 3
    else:
      dp[i][j] += dp[i][j - 1]
    # ABCを進める道
    if 0 < i and (s[j - 1] == '?' or s[j - 1] == 'ABC'[i - 1]):
      dp[i][j] += dp[i - 1][j - 1]

print(dp[3][len(s)] % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
s = input()
s = list(s)
s.reverse()
abc = 0
bc = 0
c = 0
q = 1
for i in s:
  if i == "C":
    c = c + q
  elif i == "B":
    bc = bc + c
  elif i == "A":
    abc = abc + bc
  else:
    abc = abc * 3 + bc
    bc = bc * 3 + c
    c = c * 3 + q
    q = q * 3
  abc = abc % 1000000007
print(abc % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
s = input()
s = list(s)
s.reverse()
abc = 0
bc = 0
c = 0
q = 1
for i in s:
  if i == "C":
    c = c + q
  elif i == "B":
    bc = bc + c
  elif i == "A":
    abc = abc + bc
  else:
    abc = abc * 3 + bc
    bc = bc * 3 + c
    c = c * 3 + q
    q = q * 3
print(abc % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000000)
from functools import lru_cache

S = input()

DEVIDER = 10**9 + 7


def add(a, b):
    return (a + b) % DEVIDER

def mul(a, b):
    return (a % DEVIDER) * (b % DEVIDER) % DEVIDER

cache_size = len(S) * 4

@lru_cache(maxsize=32)
def check(s, j):
    if j == 0 and s == 'A':
        return True
    if j == 1 and s == 'B':
        return True
    if j == 2 and s == 'C':
        return True
    return False

@lru_cache(maxsize=cache_size)
def dp(i, j):
    if i == len(S) and j == 3:
        # end of task
        return 1
    elif i == len(S) and j < 3:
        # fail
        return 0
    elif i < len(S) and j == 3:
        # next
        if S[i] == "?":
            return mul(3,  dp(i + 1, 3))
        else:
            return dp(i + 1, 3)
    else:
        # i < len(S) and j < 3
        if S[i] == "?":
            return add(mul(3, dp(i + 1, j)),  dp(i + 1, j + 1))
        if check(S[i], j):
            return add(dp(i + 1, j), dp( i + 1, j + 1))
        return dp(i + 1, j)


ret = dp(0, 0)
print(ret)

Submission status: Time Limit Exceeded

Solution code:
m = 10**9+7
n = 1
a = ab = abc = 0
for c in input():
    if c == 'A':
        a += n
    elif c == 'B':
        ab += a
    elif c == 'C':
        abc += ab
    else:
        ta, tab = a, ab
        a *= 3
        ab *= 3
        abc *= 3
        a += n
        ab += ta
        abc += tab
        n *= 3
    a %= m
    ab %= m
    abc %= m
print(abc)

Submission status: Time Limit Exceeded

Solution code:
S = input()

max_S = 10**9 + 7

N_Q = 0
N_C = 0
for c in S:
    if(c == "?"):
        N_Q += 1
    elif(c == "C"):
        N_C += 1

AQ_0 = int(3**N_Q)
AQ_1 = AQ_0 // 3
AQ_2 = AQ_1 // 3

BQ_0 = AQ_0 // 3
BQ_1 = AQ_1 // 3
BQ_2 = AQ_2 // 3


t_A = 0
t_Q = 0
if(S[0:1] == "C"):
    t_C = N_C - 1
else:
    t_C = N_C

ans = 0
baac = 0
bqaq = 0
aqqc = 0
for i in range(1, len(S)):
    if(S[i - 1:i] == "A"):
        t_A += 1
    elif(S[i - 1:i] == "?"):
        t_Q += 1

    bA = t_A
    bQ = t_Q
    if(S[i:i + 1] == "?"):
        aQ = N_Q - t_Q - 1
    else:
        aQ = N_Q - t_Q
    if(S[i:i + 1] == "C"):
        t_C -= 1
    aC = t_C

    if(S[i:i + 1] == "A" or S[i:i + 1] == "C"):
        continue
    elif(S[i:i + 1] == "?"):
        Q_0 = BQ_0
        Q_1 = BQ_1
        Q_2 = BQ_2
    else:
        Q_0 = AQ_0
        Q_1 = AQ_1
        Q_2 = AQ_2

    # q_0
    baac += bA * aC * Q_0
    # q_2
    bqaq += bQ * aQ * Q_2
    # Q_1
    aqqc += (bA * aQ + bQ * aC) * Q_1

ans = (ans + baac) % max_S
ans = (ans + bqaq) % max_S
ans = (ans + aqqc) % max_S


print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()

max_S = 10**9 + 7

N_Q = 0
N_C = 0
for c in S:
    if(c == "?"):
        N_Q += 1
    elif(c == "C"):
        N_C += 1

AQ_0 = int(3**N_Q)
AQ_1 = AQ_0 // 3
AQ_2 = AQ_1 // 3

BQ_0 = AQ_0 // 3
BQ_1 = AQ_1 // 3
BQ_2 = AQ_2 // 3


t_A = 0
t_Q = 0
if(S[0:1] == "C"):
    t_C = N_C - 1
else:
    t_C = N_C

ans = 0
for i in range(1, len(S)):
    if(S[i - 1:i] == "A"):
        t_A += 1
    elif(S[i - 1:i] == "?"):
        t_Q += 1

    bA = t_A
    bQ = t_Q
    if(S[i:i + 1] == "?"):
        aQ = N_Q - t_Q - 1
    else:
        aQ = N_Q - t_Q
    if(S[i:i + 1] == "C"):
        t_C -= 1
    aC = t_C

    if(S[i:i + 1] == "A" or S[i:i + 1] == "C"):
        continue
    elif(S[i:i + 1] == "?"):
        Q_0 = BQ_0
        Q_1 = BQ_1
        Q_2 = BQ_2
    else:
        Q_0 = AQ_0
        Q_1 = AQ_1
        Q_2 = AQ_2

    ans += Q_0 * bA * aC + bQ * aQ * Q_2 + Q_1 * (bA * aQ + bQ * aC)

ans = ans % max_S

print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()

max_S = 10**9 + 7

N_Q = S.count("?")
N_C = S.count("C")

AQ_0 = int(3**N_Q)
AQ_1 = AQ_0 // 3
AQ_2 = AQ_1 // 3

BQ_0 = AQ_0//3
BQ_1 = AQ_1//3
BQ_2 = AQ_2//3


t_A = 0
t_Q = 0
if(S[0:1] == "C"):
    t_C = N_C - 1
else:
    t_C = N_C

ans = 0
for i in range(1, len(S)):
    if(S[i - 1:i] == "A"):
        t_A += 1
    elif(S[i - 1:i] == "?"):
        t_Q += 1

    bA = t_A
    bQ = t_Q
    if(S[i:i + 1] == "?"):
        aQ = N_Q - t_Q - 1
    else:
        aQ = N_Q - t_Q
    if(S[i:i + 1] == "C"):
        t_C -= 1
    aC = t_C

    if(S[i:i + 1] == "A" or S[i:i + 1] == "C"):
        continue
    elif(S[i:i+1] == "?"):
        Q_0 = BQ_0
        Q_1 = BQ_1
        Q_2 = BQ_2
    else:
        Q_0 = AQ_0
        Q_1 = AQ_1
        Q_2 = AQ_2

    ans += Q_0 * bA * aC + bQ * aQ * Q_2 + Q_1 * (bA * aQ + bQ * aC)
    ans = ans % max_S

print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()

max_S = 10**9 + 7

N_Q = S.count("?")
N_C = S.count("C")

t_A = 0
t_Q = 0
if(S[0:1] == "C"):
    t_C = N_C - 1
else:
    t_C = N_C

ans = 0
for i in range(1, len(S)):
    if(S[i - 1:i] == "A"):
        t_A += 1
    elif(S[i - 1:i] == "?"):
        t_Q += 1

    bA = t_A
    bQ = t_Q
    if(S[i:i + 1] == "?"):
        aQ = N_Q - t_Q - 1
    else:
        aQ = N_Q - t_Q
    if(S[i:i + 1] == "C"):
        t_C -= 1
    aC = t_C

    if(S[i:i + 1] == "A" or S[i:i + 1] == "C"):
        continue

    Q_0 = int(3**(bQ + aQ))
    if(Q_0 == 1):
        Q_1 = 0
        Q_2 = 0
    elif(Q_0 == 3):
        Q_1 = 1
        Q_2 = 0
    else:
        Q_1 = Q_0 // 3
        Q_2 = Q_1 // 3
    ans += Q_0 * bA * aC + bQ * aQ * Q_2 + Q_1 * (bA * aQ + bQ * aC)
    ans = ans % max_S

print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()

max_S = 10**9 + 7

N_Q = S.count("?")
N_C = S.count("C")

t_A = 0
t_Q = 0
if(S[0:1] == "C"):
    t_C = N_C - 1
else:
    t_C = N_C

S_list = [{"bA": t_A, "bQ": t_Q, "aC": t_C, "aQ": N_Q - t_Q}]
for i in range(1, len(S)):
    if(S[i - 1:i] == "A"):
        t_A += 1
    elif(S[i - 1:i] == "?"):
        t_Q += 1

    ba_dic = {}
    ba_dic["bA"] = t_A
    ba_dic["bQ"] = t_Q
    if(S[i:i + 1] == "?"):
        ba_dic["aQ"] = N_Q - t_Q - 1
    else:
        ba_dic["aQ"] = N_Q - t_Q
    if(S[i:i + 1] == "C"):
        t_C -= 1
    ba_dic["aC"] = t_C

    S_list.append(ba_dic)

ans = 0
for i in range(len(S)):
    if(S[i:i + 1] == "A" or S[i:i + 1] == "C"):
        continue

    bA = S_list[i]["bA"]
    bQ = S_list[i]["bQ"]
    aC = S_list[i]["aC"]
    aQ = S_list[i]["aQ"]

    Q_0 = int(3**(bQ + aQ))
    if(Q_0 == 1):
        Q_1 = 0
        Q_2 = 0
    elif(Q_0 == 3):
        Q_1 = 1
        Q_2 = 0
    else:
        Q_1 = Q_0 // 3
        Q_2 = Q_1 // 3
    ans += Q_0 * bA * aC + bQ * aQ * Q_2 + Q_1 * (bA * aQ + bQ * aC)
    ans = ans % max_S

print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()

max_S = 10**9 + 7

N_Q = S.count("?")
N_C = S.count("C")

t_A = 0
t_Q = 0
if(S[0:1] == "C"):
    t_C = N_C - 1
else:
    t_C = N_C

S_list = [{"bA": t_A, "bQ": t_Q, "aC": t_C, "aQ": N_Q - t_Q}]
for i in range(1, len(S)):
    if(S[i - 1:i] == "A"):
        t_A += 1
    elif(S[i - 1:i] == "?"):
        t_Q += 1

    ba_dic = {}
    ba_dic["bA"] = t_A
    ba_dic["bQ"] = t_Q
    if(S[i:i + 1] == "?"):
        ba_dic["aQ"] = N_Q - t_Q - 1
    else:
        ba_dic["aQ"] = N_Q - t_Q
    if(S[i:i + 1] == "C"):
        t_C -= 1
    ba_dic["aC"] = t_C

    S_list.append(ba_dic)

ans = 0
for i in range(len(S)):
    if(S[i:i + 1] == "A" or S[i:i + 1] == "C"):
        continue

    bA = S_list[i]["bA"]
    bQ = S_list[i]["bQ"]
    aC = S_list[i]["aC"]
    aQ = S_list[i]["aQ"]

    ans += bA * aC * int(3**(bQ + aQ))
    ans = ans % max_S

    ans += bQ * aQ * int(3**(bQ + aQ - 2))
    ans = ans % max_S

    ans += (bA * aQ + bQ * aC) * int(3**(bQ + aQ - 1))
    ans = ans % max_S

print(ans)

Submission status: Time Limit Exceeded

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

for i in range(n):
    if s[i] == "A":
        dp[i + 1][1] = dp[i + 1][1] + dp[i][0]
        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][3]
    elif s[i] == "B":
        dp[i + 1][2] = dp[i + 1][2] + dp[i][1]
        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][3]
    elif s[i] == "C":
        dp[i + 1][3] = dp[i + 1][3] + dp[i][2]
        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][3]
    else:
        for j in range(4):
            dp[i + 1][j] += 3 * dp[i][j]
        dp[i + 1][1] += dp[i][0]
        dp[i + 1][2] += dp[i][1]
        dp[i + 1][3] += dp[i][2]

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

Submission status: Time Limit Exceeded

Solution code:
S=input()
s=len(S)
dp=[[0,0,0,0]for i in range(s+1)]
dp[s][3]=1
for i in range(s-1,-1,-1):
    for j in[3,2,1,0]:
        dp[i][j]=(3 if S[i]=='?'else 1)*dp[i+1][j]
        if j!=3:dp[i][j]+=(1 if S[i]=='?'or S[i]=='ABC'[j]else 0)*dp[i+1][j+1]
print(dp[0][0]%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import math

def count():
    result=0
    for a in A:
        for b in B:
            if b>a:
                for c in C:
                    if c>b:
                        s_tmp=s[:]
                        del s_tmp[c]
                        del s_tmp[b]
                        del s_tmp[a]
                        ind=s_tmp.count('?')
                        pos=1
                        for _ in range(ind):
                            pos=pos*3%1000000007
                        result+=pos
                        if(result>1000000007):
                            result=result%1000000007
    return result
                
s=list(input())
A=[]
B=[]
C=[]

for i in range(len(s)):
    if s[i]=='A':
        A.append(i)
    if s[i]=='B':
        B.append(i)
    if s[i]=='C':
        C.append(i)
    if s[i]=='?':
        A.append(i)
        B.append(i)
        C.append(i)
        
print(count())

Submission status: Time Limit Exceeded

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

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

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