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:
#!/mnt/c/Users/moiki/bash/env/bin/python
# N,M = map(int, input().split())
S = input()
from collections import defaultdict
from bisect import bisect_left
a = []
b = []
c = []
q = []

for e,s in enumerate(S):
    if s == "A" :
        a.append(e)
    if s == "B" :
        b.append(e)
    if s == "C" :
        c.append(e)
    if s == "?":
        q.append(e)

ans = 0
MOD = int(1e9+7)

for ea in a:
    for ib in range( bisect_left(b, ea+1), len(b)):
        eb = b[ib]
        if len(q) >= 0:
            ans += (len(c) - bisect_left(c, eb+1)  ) * pow(3, len(q), MOD)

        # use q in c 
        if len(q) >= 1:
            ans += (len(q) - bisect_left(q, eb+1)  ) * pow(3,len(q)-1, MOD)

    # use q in b
    for iq in range(bisect_left(q, ea+1), len(q)):
        eq = q[iq]
        if len(q) >= 1:
            ans += (len(c) - bisect_left(c, eq+1) ) * pow(3, len(q)-1, MOD) 

        # use q in b, c
        if len(q) >= 2:
            ans += (len(q) - bisect_left(q, eq+1) ) * pow(3, len(q)-2, MOD)
        # (len(q) - bisect_left(c, eq+1) ) ** pow(3, len(q)-1, MOD) 

    ans %= MOD
for eaq in q:
    for ib in range( bisect_left(b, eaq+1), len(b)):
        eb = b[ib]
        if len(q) >= 1:
            ans += (len(c) - bisect_left(c, eb+1)  ) * pow(3, len(q)-1, MOD)

        # use q in c 
        if len(q) >= 2:
            ans += (len(q) - bisect_left(q, eb+1)  ) * pow(3,len(q)-2, MOD)

    # use q in b
    for iq in range(bisect_left(q, eaq+1), len(q)):
        eq = q[iq]
        if len(q) >= 2:
            ans += (len(c) - bisect_left(c, eq+1) ) * pow(3, len(q)-2, MOD) 

        # use q in b, c
        if len(q) >= 3:
            ans += (len(q) - bisect_left(q, eq+1) ) * pow(3, len(q)-3, MOD)

    ans %= MOD
print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
# N,M = map(int, input().split())
S = input()
from collections import defaultdict
from bisect import bisect_left
a = []
b = []
c = []
# a = defaultdict(list)
# b = defaultdict(list)
# c = defaultdict(list)
q = []

for e,s in enumerate(S):
    if s == "A" :
        a.append(e)
    if s == "B" :
        b.append(e)
    if s == "C" :
        c.append(e)
    if s == "?":
        a.append(e)
        b.append(e)
        c.append(e)
        q.append(e)

ans = 0
MOD = int(1e9+7)
for ea in a:
    # print("ea: ", ea, a)
    for ib in range( bisect_left(b, ea+1), len(b)):
        eb = b[ib]
        # print("\teb: ", eb, b)
        # print("\t\tec: ", bisect_left(c, eb+1), "c: ", c, "ans += ", len(c) - bisect_left(c,eb+1) )
        for ic in range(bisect_left(c, eb+1), len(c)):
            ec = c[ic]
            qcnt = len(q) - (1 if ea in q else 0) - (1 if eb in q else 0) - (1 if ec in q else 0)
            ans += pow(3, qcnt, MOD) 

        ans %= MOD
        # ans += len(c) - bisect_left(c, eb+1)  
        # ans += (len(c) - bisect_left(c, eb+1)  ) ** pow(3, 
print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
S = input()

a=0
ab=0
ans=0
q=0
m=10**9+7
for s in S:
    if s=='A':
        a+=3**q
    elif s=='B':
        ab+=a
    elif s=='C':
        ans+=ab
    else:
        ans+=2*ans+ab
        ab+=2*ab+a
        a+=2*a+3**q
        q+=1
    ans%=m
    ab%=m
    a%=m
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from collections import defaultdict

S = input()

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

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

mod = pow(10,9)+7

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

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

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from collections import defaultdict

S = input()

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

hatena = right["?"]

mod = pow(10,9)+7

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
S = input().strip()
mod = 10**9+7
a = 0
ab = 0
ans = 0
q = 1
for c in S:
    if c == 'A':
        a += q
    elif c == 'B':
        ab += a
    elif c == 'C':
        ans += ab
    elif c == '?':
        a, ab, ans, q = a*3+q, ab*3+a, ans*3+ab, q*3
    #a %= mod
    #ab %= mod
    #ans %= mod
    #q %= mod
print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
def func(s):
    alpha = [0, 0, 0]
    ques = 0
    nowQues = 1
    ab = 0  # ABの選び方
    count = 0
    for _s in s:
        if _s == "?":
            count *= 3  # 既にabcとなっている場合の数
            count += ab  # 「? == c」とする場合
            ab *= 3
            # ある?(== B)を末尾とするABの選び方は「A+?」か「?+?」
            ab += alpha[0] * nowQues  # (3 ** ques)
            # ？の中からaを選ぶ場合
            if ques > 0:
                ab += ques * (nowQues//3)  # (3 ** (ques - 1))
            ques += 1
            nowQues *= 3
        elif _s == "A":
            alpha[0] += 1
        elif _s == "B":
            # あるBを末尾とするABの選び方は「A + B」か「? + B」
            ab += alpha[0] * nowQues  # (3 ** ques)
            if ques > 0:
                ab += ques * (nowQues//3)  # (3 ** (ques - 1))
            alpha[1] += 1
        elif _s == "C":
            # あるCを末尾とするABCの選び方は「bSelect通り」
            count += ab
            alpha[2] += 1
        count %= 10 ** 9 + 7
        ab %= 10 ** 9 + 7
        # print("{} -> alpha:{} ab:{} count:{}".format(_s, alpha, ab, count))
    return count % (10 ** 9 + 7)


"""
print(func("A??C") == 8)
print(func("ABCBC") == 3)
print(func("????C?????B??????A???????") == 979596887)
def listToString(_list, split=""):
    maped_list = map(str, _list)  # mapで要素すべてを文字列に
    mojiretu = split.join(maped_list)
    return mojiretu


print(func(listToString(["?" for _ in range(10 ** 5)])))
print("finish")
"""
print(func(input()))

Submission status: Time Limit Exceeded

Solution code:
def func(s):
    alpha = [0, 0, 0]
    ques = 0
    ab = 0  # ABの選び方
    count = 0

    for _s in s:
        if _s == "?":
            # ある?(== C)を末尾とするABCの選び方は
            # 「ABの選び方+?」
            count *= 3
            count += ab
            ab *= 3
            # ある?(== B)を末尾とするABの選び方は「A+?」か「?+?」
            ab += alpha[0] * (3**ques)
            # ？の中からaを選ぶ場合
            if ques > 0:
                ab += ques * 3 ** (ques-1)
            ques += 1
        elif _s == "A":
            alpha[0] += 1
        elif _s == "B":
            # あるBを末尾とするABの選び方は「A + B」か「? + B」
            ab += alpha[0] * (3**ques)
            if ques > 0:
                ab += ques * 3 ** (ques-1)
            alpha[1] += 1
        elif _s == "C":
            # あるCを末尾とするABCの選び方は「bSelect通り」
            count += ab
            alpha[2] += 1
        count %= 10 ** 9 + 7
        ques %= 10 ** 9 + 7
        # print("{} -> alpha:{} ab:{} count:{}".format(_s, alpha, ab, count))
    return count % (10 ** 9 + 7)


# print(func("A??C") == 8)
# print(func("ABCBC") == 3)
# print(func("????C?????B??????A???????") == 979596887)
print(func(input()))

Submission status: Time Limit Exceeded

Solution code:
def func(s):
    alpha = [0, 0, 0]
    ques = 0
    ab = 0  # ABの選び方
    count = 0

    for _s in s:
        if _s == "?":
            # ある?(== C)を末尾とするABCの選び方は
            # 「ABの選び方+?」
            count *= 3
            count += ab
            ab *= 3
            # ある?(== B)を末尾とするABの選び方は「A+?」か「?+?」
            ab += alpha[0] * (3**ques)
            # ？の中からaを選ぶ場合
            if ques > 0:
                ab += ques * 3 ** (ques-1)
            ques += 1
        elif _s == "A":
            alpha[0] += 1
        elif _s == "B":
            # あるBを末尾とするABの選び方は「A + B」か「? + B」
            ab += alpha[0] * (3**ques)
            if ques > 0:
                ab += ques * 3 ** (ques-1)
            alpha[1] += 1
        elif _s == "C":
            # あるCを末尾とするABCの選び方は「bSelect通り」
            count += ab
            alpha[2] += 1
        count %= (10 ** 9 + 7)
        # print("{} -> alpha:{} ab:{} count:{}".format(_s, alpha, ab, count))
    return count % (10 ** 9 + 7)


# print(func("A??C") == 8)
# print(func("ABCBC") == 3)
# print(func("????C?????B??????A???????") == 979596887)
print(func(input()))

Submission status: Time Limit Exceeded

Solution code:
def func(s):
    alpha = [0, 0, 0]
    ques = 0
    ab = 0  # ABの選び方
    count = 0

    for _s in s:
        if _s == "?":
            # ある?(== C)を末尾とするABCの選び方は
            # 「ABの選び方+?」
            count *= 3
            count += ab
            ab *= 3
            # ある?(== B)を末尾とするABの選び方は「A+?」か「?+?」
            ab += alpha[0] * (3**ques)
            # ？の中からaを選ぶ場合
            if ques > 0:
                ab += ques * 3 ** (ques-1)
            ques += 1
        elif _s == "A":
            alpha[0] += 1
        elif _s == "B":
            # あるBを末尾とするABの選び方は「A + B」か「? + B」
            ab += alpha[0] * (3**ques)
            if ques > 0:
                ab += ques * 3 ** (ques-1)
            alpha[1] += 1
        elif _s == "C":
            # あるCを末尾とするABCの選び方は「bSelect通り」
            count += ab
            alpha[2] += 1
        # print("{} -> alpha:{} ab:{} count:{}".format(_s, alpha, ab, count))
    return count % (10 ** 9 + 7)


# print(func("A??C") == 8)
# print(func("ABCBC") == 3)
# print(func("????C?????B??????A???????") == 979596887)
print(func(input()))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
S = input().strip()
mod = 10**9+7
a = 0
ab = 0
ans = 0
q = 1
for c in S:
    if c == 'A':
        a += q
    elif c == 'B':
        ab += a
    elif c == 'C':
        ans += ab
    elif c == '?':
        a, ab, ans, q = a*3+q, ab*3+a, ans*3+ab, q*3
print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
import time
now = time.time()
input = sys.stdin.readline
S = input().strip()
mod = 10**9+7
a = 0
ab = 0
ans = 0
q = 1
for c in S:
    if c == 'A':
        a += q
    elif c == 'B':
        ab += a
    elif c == 'C':
        ans += ab
    elif c == '?':
        a, ab, ans, q = a*3+q, ab*3+a, ans*3+ab, q*3
print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
#input = sys.stdin.readline
S = list(input().strip())
mod = 10**9+7
a = 0
ab = 0
ans = 0
q = 0
for c in S:
    if c == 'A':
        a += 3**q
    elif c == 'B':
        ab += a
    elif c == 'C':
        ans += ab
    elif c == '?':
        a, ab, ans, q = a*3+3**q, ab*3+a, ans*3+ab, q+1
    #a %= mod
    #ab %= mod
    #ans %= mod
    #q %= mod
    #print(c, a, ab, ans, q)
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
S = list(input().strip())
mod = 10**9+7
a = 0
ab = 0
ans = 0
q = 0
for c in S:
    if c == 'A':
        a += 3**q
    elif c == 'B':
        ab += a
    elif c == 'C':
        ans += ab
    elif c == '?':
        a, ab, ans, q = a*3+3**q, ab*3+a, ans*3+ab, q+1
    #a %= mod
    #ab %= mod
    #ans %= mod
    #q %= mod
    #print(c, a, ab, ans, q)
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
S = input().strip()
mod = 10**9+7
a = 0
ab = 0
ans = 0
q = 0
for c in S:
    if c == 'A':
        a += 3**q
    elif c == 'B':
        ab += a
    elif c == 'C':
        ans += ab
    elif c == '?':
        a, ab, ans, q = a*3+3**q, ab*3+a, ans*3+ab, q+1
    #a %= mod
    #ab %= mod
    #ans %= mod
    #q %= mod
    #print(c, a, ab, ans, q)
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
S = input().strip()
mod = 10**9+7
a = 0
ab = 0
ans = 0
q = 0
for c in S:
    if c == 'A':
        a += 3**q
    elif c == 'B':
        ab += a
    elif c == 'C':
        ans += ab
    elif c == '?':
        a, ab, ans, q = a*3+3**q, ab*3+a, ans*3+ab, q+1
    a %= mod
    ab %= mod
    ans %= mod
    q %= mod
    #print(c, a, ab, ans, q)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
mod = 10 ** 9 + 7
S = input()
abc = 0
bc = 0
c = 0
q = 0

for i in S[::-1]:
    if i == 'C':
        c = ((3 ** q) % mod + c) % mod
    if i == 'B':
        bc = (bc + c) % mod
    if i == 'A':
        abc = (abc + bc) % mod
    if i == '?':
        abc = (abc * 3 + bc) % mod
        bc = (bc * 3 + c) % mod
        c = (c * 3 + (3 ** q) %mod) % mod
        q += 1
        
print(abc)

Submission status: Time Limit Exceeded

Solution code:
mod = 10 ** 9 + 7
S = input()
abc = 0
bc = 0
c = 0
q = 0

for i in range(len(S)-1, -1, -1):
    if S[i] == 'C':
        c = ((3 ** q) % mod + c) % mod
    if S[i] == 'B':
        bc = (bc + c) % mod
    if S[i] == 'A':
        abc = (abc + bc) % mod
    if S[i] == '?':
        abc = (abc * 3 + bc) % mod
        bc = (bc * 3 + c) % mod
        c = (c * 3 + (3 ** q) %mod) % mod
        q += 1
        
print(abc)

Submission status: Time Limit Exceeded

Solution code:
mod = 10 ** 9 + 7
S = input()
abc = 0
bc = 0
c = 0
q = 0

for i in range(len(S)-1, -1, -1):
    if S[i] == 'C':
        c = (3 ** q + c) % mod
    if S[i] == 'B':
        bc = (bc + c) % mod
    if S[i] == 'A':
        abc = (abc + bc) % mod
    if S[i] == '?':
        abc = (abc * 3 + bc) % mod
        bc = (bc * 3 + c) % mod
        c = (c * 3 + 3 ** q) % mod
        q += 1
        
print(abc)

Submission status: Time Limit Exceeded

Solution code:
mod = 10 ** 9 + 7
S = input()
abc = 0
bc = 0
c = 0
q = 0

for i in range(len(S)-1, -1, -1):
    if S[i] == 'C':
        c = 3 ** q + c
    if S[i] == 'B':
        bc += c
    if S[i] == 'A':
        abc += bc
    if S[i] == '?':
        abc = abc * 3 + bc
        bc = bc * 3 + c
        c = c * 3 + 3 ** q
        q += 1
        
print(abc % mod)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
mod = 10**9+7
s = input()
q = 0
a = 0
ab = 0
abc = 0
for c in s:
    k = pow(3, q)%mod
    if c == "A":
        a += k
    elif c == "B":
        ab += a
    elif c == "C":
        abc += ab
    else:
        abc = 3*abc + ab
        ab = 3*ab + a
        a = 3*a + k
        q += 1
    a %= mod
    ab %= mod
    abc %= mod
print(abc%mod)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
mod = 10**9+7
s = input()
k = 1
a = 0
ab = 0
abc = 0
for c in s:
    if c == "A":
        a += k
    elif c == "B":
        ab += a
    elif c == "C":
        abc += ab
    else:
        abc = (3*abc + ab)%mod
        ab = (3*ab + a)%mod
        a = (3*a + k)%mod
        k *= 3
print(abc%mod)

Submission status: Time Limit Exceeded

Solution code:
s = input()
mod = 10**9 + 7
abc = 0
bc = 0
c = 0
q = 0
for i in s[::-1]:
  if i == "A":
    abc = (abc + bc) % mod
  if i == "B":
    bc = (bc + c) % mod
  if i == "C":
    c = (3**q+c) % mod
  if i == "?":
    abc = (abc*3 + bc) % mod
    bc = (bc*3 + c) % mod 
    c = (3**q + c*3) % mod
    q += 1
print(abc)

Submission status: Time Limit Exceeded

Solution code:
s = input()
mod = 10**9 + 7
abc = 0
bc = 0
c = 0
q = 0
for i in reversed(s):
  if i == "A":
    abc = (abc + bc) % mod
  if i == "B":
    bc = (bc + c) % mod
  if i == "C":
    c = (3**q+c) % mod
  if i == "?":
    abc = (abc*3 + bc) % mod
    bc = (bc*3 + c) % mod 
    c = (3**q + c*3) % mod
    q += 1
print(abc)

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9 + 7
t = input()
n = len(t)

l_a = [0] * (n + 1)
l_q = [0] * (n + 1)
r_c = [0] * (n + 1)
r_q = [0] * (n + 1)
total = 0

for i in range(1, n):
    l_a[i] = l_a[i - 1] + (1 if t[i - 1] == 'A' else 0)
    l_q[i] = l_q[i - 1] + (1 if t[i - 1] == '?' else 0)
for i in range(n - 1, 0, -1):
    r_c[i - 1] = r_c[i] + (1 if t[i] == 'C' else 0)
    r_q[i - 1] = r_q[i] + (1 if t[i] == '?' else 0)
for i in range(n):
    if t[i] in 'B?':
        total += l_a[i] * r_c[i] * 3**(l_q[i] + r_q[i]) + \
            l_a[i] * r_q[i] * 3**(l_q[i] + r_q[i] - 1) +\
            l_q[i] * r_c[i] * 3**(l_q[i] + r_q[i] - 1) +\
            l_q[i] * r_q[i] * 3**(l_q[i] + r_q[i] - 2)
        total %= mod
print(int(total))

Submission status: Time Limit Exceeded

Solution code:
S=raw_input()
 
M=10**9+7
 
a=0
ab=0
ans=0
all=1
 
for x  in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		ans+=ab
	if x=="?":
		ans = ans*3 + ab
		ab = ab*3 + a
		a = a*3 + all
		all *= 3
 
	ans%=M
	ab%=M
	a%=M
	all%M
 
 
print ans%M

Submission status: Time Limit Exceeded

Solution code:
def main():
  S = reversed(input())
  C = 0
  BC = 0
  ABC = 0
  AB = 1
  X = 1
  for i in S:
    if "?" == i:
      ABC = ABC * 3 + BC
      BC = BC * 3 + C
      C = C * 3 + X
      X *= 3
    elif "C" == i:
      AB = 0
      C += X
    elif "B" == i:
      BC += C
    elif "A" == i:
      ABC += BC

  print(ABC % 1000000007)

main()

Submission status: Time Limit Exceeded

Solution code:
S = [i for i in input()]
C = 0
BC = 0
ABC = 0
AB = 1
X = 1
for i in reversed(S):
  if i == "C":
    AB = 0
    C += X
  elif i == "B":
    BC += C
  elif i == "A":
    ABC += BC
  elif i == "?":
    ABC = (ABC * 3 + BC) % 1000000007
    BC = (BC * 3 + C) % 1000000007
    C = (C * 3 + X) % 1000000007
    X *= 3 % 1000000007
  #print("{} {} {}".format(C, BC, ABC))
print(ABC % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
S = [i for i in input()]
C = 0
BC = 0
ABC = 0
AB = 1
X = 1
for i in reversed(S):
  if i == "C":
    AB = 0
    C += X
  elif i == "B":
    BC += C
  elif i == "A":
    ABC += BC
  elif i == "?":
    ABC = ABC * 3 + BC
    BC = BC * 3 + C
    C = C * 3 + X
    X *= 3
  #print("{} {} {}".format(C, BC, ABC))
print(ABC % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
S=raw_input()

M=10**9+7

a=0
ab=0
ans=0
all=1

for x  in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		ans+=ab
	if x=="?":
		ans = ans*3 + ab
		ab = ab*3 + a
		a = a*3 + all
		all *= 3

	ans%=M
	ab%=M
	a%=M
	all%M


print ans%M

Submission status: Time Limit Exceeded

Solution code:
import sys
S=sys.stdin.readline()

M=10**9+7

a=0
ab=0
ans=0
all=1

for x  in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		ans+=ab
	if x=="?":
		ans = ans*3 + ab
		ab = ab*3 + a
		a = a*3 + all
		all *= 3

	ans%=M
	ab%=M
	a%=M
	all%M


print ans%M

Submission status: Time Limit Exceeded

Solution code:
import sys
S=sys.stdin.readline()

M=10**9+7

a=0
ab=0
ans=0
all=1

for x  in S:
	if x=="A":
		a+=all
	elif x=="B":
		ab+=a
	elif x=="C":
		ans+=ab
	elif x=="?":
		ans = ans*3 + ab
		ab = ab*3 + a
		a = a*3 + all
		all *= 3

	ans%=M
	ab%=M
	a%=M
	all%M


print ans%M

Submission status: Time Limit Exceeded

Solution code:
import sys
S=sys.stdin.readline()

mod=10**9+7

a=0
ab=0
ans=0
all=1

for x  in S:
	if x=="A":
		a+=all
	elif x=="B":
		ab+=a
	elif x=="C":
		ans+=ab
	elif x=="?":
		ans = ans*3 + ab
		ab = ab*3 + a
		a = a*3 + all
		all *= 3

	ans%=mod
	ab%=mod
	a%=mod
	all%mod


print ans%mod

Submission status: Time Limit Exceeded

Solution code:
import sys

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

mod=10**9+7

a=0
ab=0
ans=0
all=1

for x  in S:
	if x=="A":
		a+=all
	elif x=="B":
		ab+=a
	elif x=="C":
		ans+=ab
	elif x=="?":
		ans = ans*3 + ab
		ab = ab*3 + a
		a = a*3 + all
		all *= 3

	ans%=mod
	ab%=mod
	a%=mod
	all%mod


print ans%mod

Submission status: Time Limit Exceeded

Solution code:
import sys

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

mod=10**9+7

a=0
ab=0
ans=0
all=1

for x  in S:
	if x=="A":
		a+=all
	elif x=="B":
		ab+=a
	elif x=="C":
		ans+=ab
	elif x=="?":
		ans = ans*3 + ab
		ab = ab*3 + a
		a = a*3 + all
		all *= 3

	ans%=mod
	ab%=mod
	a%=mod
	all%mod


print ans

Submission status: Time Limit Exceeded

Solution code:
import sys

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

mod=10**9+7

a=0
ab=0
ans=0
all=1

for i,x  in enumerate(S):
	if x=="A":
		a+=all
	elif x=="B":
		ab+=a
	elif x=="C":
		ans+=ab
	elif x=="?":
		ans = ans*3 + ab
		ab = ab*3 + a
		a = a*3 + all
		all *= 3

	ans%=mod
	ab%=mod
	a%=mod
	all%mod


print ans

Submission status: Time Limit Exceeded

Solution code:
import sys

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

mod=10**9+7

a=0
ab=0
ans=0
all=1

for i in range(l):
	if S[i]=="A":
		a+=all
	elif S[i]=="B":
		ab+=a
	elif S[i]=="C":
		ans+=ab
	elif S[i]=="?":
		ans = ans*3 + ab
		ab = ab*3 + a
		a = a*3 + all
		all *= 3

	ans%=mod
	ab%=mod
	a%=mod
	all%mod


print ans

Submission status: Time Limit Exceeded

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

mod=10**9+7

a=0
ab=0
ans=0
all=1

for i in range(l):
	if S[i]=="A":
		a+=all
	elif S[i]=="B":
		ab+=a
	elif S[i]=="C":
		ans+=ab
	elif S[i]=="?":
		ans = ans*3 + ab
		ab = ab*3 + a
		a = a*3 + all
		all *= 3

	ans%=mod
	ab%=mod
	a%=mod
	all%mod


print (ans)

Submission status: Time Limit Exceeded

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

mod=10**9+7

a=0
ab=0
ans=0
all=1

for i in range(l):
	if S[i]=="A":
		a+=all
	elif S[i]=="B":
		ab+=a
	elif S[i]=="C":
		ans+=ab
	elif S[i]=="?":
		ans = ans*3 + ab
		ab = ab*3 + a
		a = a*3 + all
		all *= 3

	ans%=mod
	ab%=mod
	a%=mod
	all%mod


print ans

Submission status: Time Limit Exceeded

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

mod=10**9+7

dp=[ 0  for j in range(4) ] 

all=1  #Joutai-su

for i in range(l):
	t1=dp[1]
	t2=dp[2]
	t3=dp[3]

	if S[i]=="A":
		dp[1]+=all
	elif S[i]=="B":
		dp[2]=t2+t1
	elif S[i]=="C":
		dp[3]=t3+t2
	elif S[i]=="?":
		dp[1]=t1*3+all
		dp[2]=t2*3+t1
		dp[3]=t3*3+t2
		all*=3

	dp[1]%=mod
	dp[2]%=mod
	dp[3]%=mod
	all%mod


print dp[-1]%mod

Submission status: Time Limit Exceeded

Solution code:
S=" "+raw_input()
l=len(S)

mod=10**9+7

dp=[  [ 0  for j in range(4) ]   for i in range(l) ] 

for i in range(l):
	dp[i][0]=1


all=1  #Joutai-su

for i in range(1,l):

	if S[i]=="A":
		dp[i][1]+=dp[i-1][1]+all
		dp[i][2]+=dp[i-1][2]
		dp[i][3]+=dp[i-1][3]
	elif S[i]=="B":
		dp[i][1]+=dp[i-1][1]
		dp[i][2]+=dp[i-1][2]+dp[i-1][1]
		dp[i][3]+=dp[i-1][3]
	elif S[i]=="C":
		dp[i][1]+=dp[i-1][1]
		dp[i][2]+=dp[i-1][2]
		dp[i][3]+=dp[i-1][3]+dp[i-1][2]
	elif S[i]=="?":
		dp[i][1]+=dp[i-1][1]*3+all
		dp[i][2]+=dp[i-1][2]*3+dp[i-1][1]
		dp[i][3]+=dp[i-1][3]*3+dp[i-1][2]
		all*=3

	dp[i][1]%=mod
	dp[i][2]%=mod
	dp[i][3]%=mod
	all%mod


print dp[-1][-1]%mod

Submission status: Time Limit Exceeded

Solution code:
S=" "+raw_input()
l=len(S)

mod=10**9+7

dp=[  [ 0  for j in range(4) ]   for i in range(l) ] 

for i in range(l):
	dp[i][0]=1


all=1  #Joutai-su

for i in range(1,l):

	if S[i]=="A":
		dp[i][1]+=dp[i-1][1]+all
		dp[i][2]+=dp[i-1][2]
		dp[i][3]+=dp[i-1][3]
	elif S[i]=="B":
		dp[i][1]+=dp[i-1][1]
		dp[i][2]+=dp[i-1][2]+dp[i-1][1]
		dp[i][3]+=dp[i-1][3]
	elif S[i]=="C":
		dp[i][1]+=dp[i-1][1]
		dp[i][2]+=dp[i-1][2]
		dp[i][3]+=dp[i-1][3]+dp[i-1][2]
	elif S[i]=="?":
		dp[i][1]+=dp[i-1][1]*3+all
		dp[i][2]+=dp[i-1][2]*3+dp[i-1][1]
		dp[i][3]+=dp[i-1][3]*3+dp[i-1][2]
		all*=3

	dp[i][1]%=mod
	dp[i][2]%=mod
	dp[i][3]%=mod


print dp[-1][-1]%mod

Submission status: Time Limit Exceeded

Solution code:
S=" "+raw_input()
l=len(S)

mod=10**9+7

dp=[  [ 0  for j in range(4) ]   for i in range(l) ] 

for i in range(l):
	dp[i][0]=1


all=1  #Joutai-su

for i in range(1,l):

	if S[i]=="A":
		dp[i][1]+=dp[i-1][1]+all
		dp[i][2]+=dp[i-1][2]
		dp[i][3]+=dp[i-1][3]
	elif S[i]=="B":
		dp[i][1]+=dp[i-1][1]
		dp[i][2]+=dp[i-1][2]+dp[i-1][1]
		dp[i][3]+=dp[i-1][3]
	elif S[i]=="C":
		dp[i][1]+=dp[i-1][1]
		dp[i][2]+=dp[i-1][2]
		dp[i][3]+=dp[i-1][3]+dp[i-1][2]
	elif S[i]=="?":
		dp[i][1]+=dp[i-1][1]*3+all
		dp[i][2]+=dp[i-1][2]*3+dp[i-1][1]
		dp[i][3]+=dp[i-1][3]*3+dp[i-1][2]
		all*=3


print dp[-1][-1]%mod

Submission status: Time Limit Exceeded

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

S = input()
N = len(S)

nums = [1, 0, 0, 0]

for i in range(0, N):
    s = S[i]
    m = 3 if s == "?" else 1
    a = 1 if s == "A" or s == "?" else 0
    b = 1 if s == "B" or s == "?" else 0
    c = 1 if s == "C" or s == "?" else 0

    n0 = nums[0] * m
    n1 = nums[1] * m + nums[0] * a
    n2 = nums[2] * m + nums[1] * b
    n3 = nums[3] * m + nums[2] * c
    nums = [n0, n1, n2, n3]

print(nums[3] % MOD)

Submission status: Time Limit Exceeded

Solution code:
import gc

MOD = (10 ** 9) + 7

S = input()
N = len(S)

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

dp[0][0] = 1
dp[1][0] = 0
dp[2][0] = 0
dp[3][0] = 0

for i in range(1, N + 1):
    gc.collect()
    for j in range(4):
        s = S[i - 1]
        m = 3 if s == "?" else 1
        dp[j][i] += m * dp[j][i - 1]
        if j == 1:
            if s == "A" or s == "?":
                dp[j][i] += dp[j - 1][i - 1]
        elif j == 2:
            if s == "B" or s == "?":
                dp[j][i] += dp[j - 1][i - 1]
        elif j == 3:
            if s == "C" or s == "?":
                dp[j][i] += dp[j - 1][i - 1]
        dp[j][i] = dp[j][i] % MOD 

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

Submission status: Time Limit Exceeded

Solution code:
import gc

MOD = (10 ** 9) + 7

S = input()
N = len(S)

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

dp[0][0] = 1
dp[1][0] = 0
dp[2][0] = 0
dp[3][0] = 0

for i in range(1, N + 1):
    gc.collect()
    for j in range(4):
        s = S[i - 1]
        m = 3 if s == "?" else 1
        dp[j][i] += m * dp[j][i - 1]
        if j == 1:
            if s == "A" or s == "?":
                dp[j][i] += dp[j - 1][i - 1]
        elif j == 2:
            if s == "B" or s == "?":
                dp[j][i] += dp[j - 1][i - 1]
        elif j == 3:
            if s == "C" or s == "?":
                dp[j][i] += dp[j - 1][i - 1]

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

Submission status: Time Limit Exceeded

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

S = input()
N = len(S)

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

dp[0][0] = 1
dp[1][0] = 0
dp[2][0] = 0
dp[3][0] = 0

for i in range(1, N + 1):
    for j in range(4):
        s = S[i - 1]
        m = 3 if s == "?" else 1
        dp[j][i] += m * dp[j][i - 1]
        if j == 1:
            if s == "A" or s == "?":
                dp[j][i] += dp[j - 1][i - 1]
        elif j == 2:
            if s == "B" or s == "?":
                dp[j][i] += dp[j - 1][i - 1]
        elif j == 3:
            if s == "C" or s == "?":
                dp[j][i] += dp[j - 1][i - 1]

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections
from collections import Counter
# from collections import deque
# from collections import defaultdict
import itertools
# from itertools import accumulate
# from itertools import permutations
# from itertools import combinations
# from itertools import takewhile
from itertools import compress
import functools
# from functools import reduce
import math
# from math import gcd
# from math import inf
# from math import ceil
# from math import floor
# from math import log10
# from math import log2
# from math import log
from math import factorial

MOD = (10 ** 9) + 7
# import re

# input = sys.stdin.readline
# sys.setrecursionlimit(10000)

S = input()
N = len(S)

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

dp[0][0] = 1
dp[1][0] = 0
dp[2][0] = 0
dp[3][0] = 0

for i in range(1, N + 1):
    for j in range(4):
        s = S[i - 1]
        m = 3 if s == "?" else 1
        dp[j][i] += m * dp[j][i - 1]
        if j == 1:
            if s == "A" or s == "?":
                dp[j][i] += dp[j - 1][i - 1]
        elif j == 2:
            if s == "B" or s == "?":
                dp[j][i] += dp[j - 1][i - 1]
        elif j == 3:
            if s == "C" or s == "?":
                dp[j][i] += dp[j - 1][i - 1]

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

"""
参考：http://tutuz.hateblo.jp/entry/2018/08/06/074104
・別解
・予め必要なA,C,?の個数は集めておく。
・Bの位置を決めて、4つの選び方パターンを全部数え上げる。
"""

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

# あるBの位置よりも左にあるAと?の個数
A, LQ = [0] * len(S), [0] * len(S)
for i in range(len(S)-1):
    a = lq = 0
    if S[i] == 'A':
        a += 1
    if S[i] == '?':
        lq += 1
    A[i+1] = A[i] + a
    LQ[i+1] = LQ[i] + lq
# あるBの位置よりも右にあるCと?の個数
C, RQ = [0] * len(S), [0] * len(S)
for i in range(len(S)-1, 0, -1):
    c = rq = 0
    if S[i] == 'C':
        c += 1
    if S[i] == '?':
        rq += 1
    C[i-1] = C[i] + c
    RQ[i-1] = RQ[i] + rq

ans = 0
for i in range(len(S)):
    if S[i] == '?' or S[i] == 'B':
        # (A,B,C) と選ぶ場合(後ろの3べきは使わなかった?の分)
        case1 = (A[i] * C[i] * pow(3, LQ[i] + RQ[i])) % MOD
        # (A,B,?) と選ぶ場合
        case2 = (A[i] * RQ[i] * pow(3, max(LQ[i] + RQ[i] - 1, 0))) % MOD
        # (?,B,C) と選ぶ場合
        case3 = (LQ[i] * C[i] * pow(3, max(LQ[i] + RQ[i] - 1, 0))) % MOD
        # (?,B,?) と選ぶ場合
        case4 = (LQ[i] * RQ[i] * pow(3, max(LQ[i] + RQ[i] - 2, 0))) % MOD
        # 全部足し合わせてMOD
        ans = (ans + case1 + case2 + case3 + case4) % MOD

print(int(ans))