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: Runtime Error

Solution code:
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

@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()
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: Runtime Error

Solution code:
S = input()

DEVIDER = 10**9 + 7


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

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

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


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: Runtime Error

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: Runtime Error

Solution code:
S = input()

A_left=[0]
C_left=[0]
Q_left=[0]

for (i,s) in enumerate(S):
    if s == "A":
        A_left.append(A_left[i]+1)
        C_left.append(C_left[i])
        Q_left.append(Q_left[i])
    elif s == "C":
        A_left.append(A_left[i])
        C_left.append(C_left[i]+1)
        Q_left.append(Q_left[i])
    elif s == "?":
        A_left.append(A_left[i])
        C_left.append(C_left[i])
        Q_left.append(Q_left[i]+1)
    else:
        A_left.append(A_left[i])
        C_left.append(C_left[i])
        Q_left.append(Q_left[i])

A_right = []
C_right = []
Q_right = []
for i in range(len(S)):
    A_right.append(A_left[-1] - A_left[i+1])
    C_right.append(C_left[-1] - C_left[i+1])
    Q_right.append(Q_left[-1] - Q_left[i+1])

ans = 0
for (i,s) in enumerate(S):
    if s == "B":
        ans = (ans + A_left[i] * C_right[i] * pow(3,Q_left[-1],10**9+7)) % (10**9+7)
        ans = (ans + (Q_left[i] * C_right[i] + A_left[i] * Q_right[i]) * pow(3,(Q_left[-1]-1),10**9+7)) % (10**9+7)
        ans = (ans + (Q_left[i] * Q_right[i]) * pow(3,(Q_left[-1]-2),10**9+7)) % (10**9+7)
    elif s == "?":
        ans = (ans + A_left[i] * C_right[i] * pow(3,(Q_left[-1]-1),10**9+7)) % (10**9+7)
        ans = (ans + (Q_left[i] * C_right[i] + A_left[i] * Q_right[i]) * pow(3,(Q_left[-1]-2),10**9+7)) % (10**9+7)
        ans = (ans + (Q_left[i] * Q_right[i]) * pow(3,(Q_left[-1]-3),10**9+7)) % (10**9+7)

print(ans)

Submission status: Runtime Error

Solution code:
while True:
    S = input()
    N = len(S)
    MOD = 1000000007
    dp = [[0]*4 for i in range(N+1)]
    for i in range(N, -1, -1):
        for j in range(3, -1, -1):
            if i == N:
                dp[i][j] = 1 if j == 3 else 0
            else:
                dp[i][j] = dp[i+1][j] * (3 if S[i] == '?' else 1)
                if j < 3 and (S[i] == '?' or S[i] == "ABC"[j]):
                    dp[i][j] += dp[i+1][j+1]
                dp[i][j] %= MOD
    print(dp[0][0])

Submission status: Runtime Error

Solution code:
????C?????B??????A???????

Submission status: Runtime Error

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]
                        result+=int(math.pow(3, s_tmp.count('?')))
                        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: Runtime Error

Solution code:
S = input()
mod = 10 ** 9 + 7
def DP(i, j, S, mod):
    if i == len(S) and j == 3:
        return 1
    elif i == len(S) and j < 3:
        return 0
    elif i < len(S) and j == 3:
        if S[i] == "?":
            return 3 * DP(i+1, 3, S, mod) % mod
        else:
            return DP(i+1, 3, S, mod) % mod
    elif i < len(S) and j < 3:
        ABC = "ABC"
        if S[i] == "?":
            return (3 * DP(i+1, j, S, mod) + DP(i+1, j+1, S, mod)) % mod
        elif S[i] == ABC[j]:
            return (DP(i+1, j, S, mod) + DP(i+1, j+1, S, mod)) % mod
        else:
            return DP(i+1, j, S, mod) % mod

print(DP(0, 0, S, mod))

Submission status: Runtime Error

Solution code:
S = input()
mod = 10 ** 9 + 7
def DP(i, j, S):
    if i == len(S) and j == 3:
        return 1
    elif i == len(S) and j < 3:
        return 0
    elif i < len(S) and j == 3:
        if S[i] == "?":
            return 3 * DP(i+1, 3, S) 
        else:
            return DP(i+1, 3, S)
    elif i < len(S) and j < 3:
        ABC = "ABC"
        if S[i] == "?":
            return 3 * DP(i+1, j, S) + DP(i+1, j+1, S)
        elif S[i] == ABC[j]:
            return DP(i+1, j, S) + DP(i+1, j+1, S)
        else:
            return DP(i+1, j, S)

print(DP(0, 0, S)%mod)

Submission status: Runtime Error

Solution code:
T = input()
N = len(T)
mod = 10**9 + 7
A_left = 0
q_left = 0
q_right = T[1:].count('?')
C_right = T[1:].count('C')
ans = 0
for i in range(1, N-1, 1):
    if T[i-1] == 'A':
        A_left += 1
    if T[i-1] =='?':
        q_left += 1
    if T[i] == '?':
        q_right -= 1
    if T[i] == 'C':
        C_right -= 1
    if T[i] == 'B' or T[i] == '?':
        ans += int((A_left * (3 ** q_left) + q_left * (3 ** (q_left - 1))) * (C_right * (3 ** q_right) + q_right * (3 ** (q_right - 1))))
        ans %= mod
print(ans)

Submission status: Runtime Error

Solution code:
S = input()
l = len(S)
Q = S.count('?')
ans = 0
for i in range(l-2):
    for j in range(l-i-2):
        for k in range(l-i-j-2):
            d = 3**Q
            s1 = S[i]; s2 = S[i+j+1]; s3 = S[i+j+k+2]
            if s1 == 'A' or s1 == '?':
                if s1 == '?':
                    d /= 3
                if s2 == 'B' or s2 == '?':
                    if s2 == '?':
                        d /= 3
                    if s3 == 'C' or s3 == '?':
                        if s3 == '?':
                            d /= 3
                        d %= 10**9 + 7
                        ans += d
                        ans = ans%(10**9+7)
print(int(ans))

Submission status: Runtime Error

Solution code:
S = input()
l = len(S)
Q = S.count('?')
ans = 0
for i in range(l-2):
    for j in range(l-i-2):
        for k in range(l-i-j-2):
            d = 3**Q
            s1 = S[i]; s2 = S[i+j+1]; s3 = S[i+j+k+2]
            if s1 == 'A' or s1 == '?':
                if s1 == '?':
                    d /= 3
                if s2 == 'B' or s2 == '?':
                    if s2 == '?':
                        d /= 3
                    if s3 == 'C' or s3 == '?':
                        if s3 == '?':
                            d /= 3
                        ans += d
                        ans = ans%(10**9+7)
print(int(ans))

Submission status: Runtime Error

Solution code:
S = input()
L = len(S)
Q = 10**9 + 7
anum = [ 0 for _ in range(L+1)]
#bnum = [ 0 for _ in range(L+1)]
cnum = [ 0 for _ in range(L+1)]
hnum = [ 0 for _ in range(L+1)]
for i in range(1,L+1):
    if S[i-1] == 'A':
        anum[i] = anum[i-1] + 1
#        bnum[i] = bnum[i-1]
        cnum[i] = cnum[i-1]
        hnum[i] = hnum[i-1]
    elif S[i-1] == 'B':
        anum[i] = anum[i-1]
#        bnum[i] = bnum[i-1] + 1
        cnum[i] = cnum[i-1]
        hnum[i] = hnum[i-1]
    elif S[i-1] == 'C':
        anum[i] = anum[i-1]
#        bnum[i] = bnum[i-1]
        cnum[i] = cnum[i-1] + 1
        hnum[i] = hnum[i-1]
    else:
        anum[i] = anum[i-1]
#        bnum[i] = bnum[i-1]
        cnum[i] = cnum[i-1]
        hnum[i] = hnum[i-1] + 1

ans = 0
czen = cnum[L]
hzen = hnum[L] 
for i in range(1,L+1):
    if S[i-1] == 'B' or S[i-1] == '?':
#        A = ((anum[i-1]*(3**hnum[i-1]))%Q + (hnum[i-1]*(3**(hnum[i-1]-1)))%Q)%Q
#        C = (((czen - cnum[i])*(3**(hzen - hnum[i])))%Q + ((hzen - hnum[i])*(3**(hzen - hnum[i]-1)))%Q)%
        A = ((anum[i-1]*pow(3,hnum[i-1],Q))%Q + (hnum[i-1]*pow(3,hnum[i-1]-1,Q))%Q)%Q
        C = (((czen - cnum[i])*pow(3,hzen - hnum[i],Q))%Q + ((hzen - hnum[i])*pow(3,hzen - hnum[i]-1,Q))%Q)%Q
        K = (A*C)%Q
        ans = (ans + K)%Q
print(int(ans))

Submission status: Runtime Error

Solution code:
S = input()
l = len(S)
Q = S.count('?')
ans = 0
for i in range(l):
    for j in range(l-i-1):
        for k in range(l-i-j-2):
            d = 3**Q
            s1 = S[i]; s2 = S[i+j+1]; s3 = S[i+j+k+2]
            if s1 == 'A' or s1 == '?':
                if s1 == '?':
                    d /= 3
                if s2 == 'B' or s2 == '?':
                    if s2 == '?':
                        d /= 3
                    if s3 == 'C' or s3 == '?':
                        if s3 == '?':
                            d /= 3
                        ans += d
                        ans = ans%(10**9+7)
print(int(ans))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
 
modulo = 10 ** 9 + 7
 
S = input()
 
def nleft(S, c):
    """各位置について，それより左の文字列に含まれる文字 c の総数.
       左に'?'が含まれるときは，それらに文字を入れて得られるすべての
       文字列に渡って，文字 c の個数を合計する. """
 
    def _left(S, c):
        """各位置より左にある c の個数. """
        n = [0 for c in S]
        for i in range(1, len(n)):
            n[i] = n[i-1] + (1 if S[i-1] == c else 0)
        return n
 
    # c の個数, '?'の個数
    n = _left(S, c)
    q = _left(S, '?')
 
    for i in range(len(n)):
        n[i] *= (3 ** q[i]) % modulo               # ?の埋め方の数だけ増やす
        n[i] += (3 ** (q[i] - 1)) * q[i] % modulo  # ?に入る'C'の個数
    return n
 
def nright(S, c):
    n = nleft(list(reversed(S)), c)
    n.reverse()
    return n
 
left  = nleft (S, 'A')
right = nright(S, 'C')
 
# 各文字が'B'のときのABC数を計算
abc = 0
for i in range(0, len(S)):
    if S[i] in 'B?':
        abc += left[i] * right[i]
 
abc = int(abc) % modulo
print(abc)
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

modulo = 10 ** 9 + 7

S = input()

def nleft(S, c):
    """各位置について，それより左の文字列に含まれる文字 c の総数.
       左に'?'が含まれるときは，それらに文字を入れて得られるすべての
       文字列に渡って，文字 c の個数を合計する. """

    def _left(S, c):
        """各位置より左にある c の個数. """
        n = [0 for c in S]
        for i in range(1, len(n)):
            n[i] = n[i-1] + (1 if S[i-1] == c else 0)
        return n

    # c の個数, '?'の個数
    n = _left(S, c)
    q = _left(S, '?')

    for i in range(len(n)):
        n[i] *= (3 ** q[i]) % modulo               # ?の埋め方の数だけ増やす
        n[i] += (3 ** (q[i] - 1)) * q[i] % modulo  # ?に入る'C'の個数
        n[i] %= modulo
    return n

def nright(S, c):
    n = nleft(list(reversed(S)), c)
    n.reverse()
    return n

left  = nleft (S, 'A')
right = nright(S, 'C')

# 各文字が'B'のときのABC数を計算
abc = 0
for i in range(0, len(S)):
    if S[i] in 'B?':
        abc += left[i] * right[i]

abc = int(abc) % modulo
print(abc)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

S = input()

def nleft(S, c):
    """各位置について，それより左の文字列に含まれる文字 c の総数.
       左に'?'が含まれるときは，それらに文字を入れて得られるすべての
       文字列に渡って，文字 c の個数を合計する. """

    def _left(S, c):
        """各位置より左にある c の個数. """
        n = [0 for c in S]
        for i in range(1, len(n)):
            n[i] = n[i-1] + (1 if S[i-1] == c else 0)
        return n

    # c の個数, '?'の個数
    n = _left(S, c)
    q = _left(S, '?')

    for i in range(len(n)):
        n[i] *= 3 ** q[i]                 # ?の埋め方の数だけ増やす
        n[i] += (3 ** (q[i] - 1)) * q[i]  # ?に入る'C'の個数
    return n

def nright(S, c):
    n = nleft(list(reversed(S)), c)
    n.reverse()
    return n

left  = nleft (S, 'A')
right = nright(S, 'C')

# 各文字が'B'のときのABC数を計算
abc = 0
for i in range(0, len(S)):
    if S[i] in 'B?':
        abc += left[i] * right[i]

abc = int(abc) % (10 ** 9 + 7)
print(abc)

Submission status: Runtime Error

Solution code:
S = input()


MOD = 10**9 + 7
# time complexity: O(|S|)
def focus_on_B(S):
    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])

    num_combinations = 0
    for i in range(1, len(S) - 1):
        if S[i] in {"B", "?"}:
            A_L = cuml["A"][i-1]
            Q_L = cuml["?"][i-1]
            C_R = cuml["C"][-1] - cuml["C"][i]
            Q_R = cuml["?"][-1] - cuml["?"][i]
            num_combinations += int((A_L * 3 + Q_L) * 3**(Q_L - 1)\
                            * (C_R * 3 + Q_R) * 3**(Q_R - 1))
            num_combinations %= MOD
        else:
            continue
    print(num_combinations)


focus_on_B(S)

Submission status: Runtime Error

Solution code:
init_input()

S = input()
n = len(S)
mod = (10**9 + 7)

A = [0] * n
C = [0] * n
Q = [0] * n
Bi = []
Qi = []

for i, s in enumerate(S):
    if s == 'A':
        A[i] = 1
    elif s == 'B':
        Bi.append(i)
    elif s == 'C':
        C[i] = 1
    else:
        Q[i] = 1
        Qi.append(i)

for i in range(1, n):
    A[i] += A[i - 1]
    C[i] += C[i - 1]
    Q[i] += Q[i - 1]

def mod_pow(x, n, mod):
    if n == 0: return 1
    d, m = n >> 1, n & 1
    p = mod_pow(x, d, mod)
    return (p * p * (x if m else 1))

from itertools import chain
ans = 0
for b in chain(Bi, Qi):
    if b == 0 or n - 1 <= b: continue
    ai = A[b - 1]
    qa = Q[b - 1]
    a = (ai * mod_pow(3, qa, mod))
    if qa > 0:
        a += (mod_pow(3, qa - 1, mod) * qa)

    lc = C[n - 1] - C[b]
    lqc = Q[n - 1] - Q[b]
    c = (lc * mod_pow(3, lqc, mod))
    if lqc > 0:
        c += (mod_pow(3, lqc - 1, mod) * lqc)
    
    ans += (a * c) % mod

print(ans % mod)

Submission status: Runtime Error

Solution code:
inf = 1000000007

a = 0
ab = 0
abc = 0
r = 1
 
s = input()
 
for c in s:
    if c == "A":
        a += r
    elif c == "B":
        ab += a
    elif c == "C":
        abc += ab
    else:
        abc = abc * 3 + ab
        ab = ab * 3 + a
        a = a * 3 + r
        r *= 3
 
	a %= inf
	ab %= inf
    abc %= inf
    r %= inf

print(abc)

Submission status: Runtime Error

Solution code:
p = [1, 0, 0, 0]

for s in input():
    if s == 'A' :
        p[1] += p[0]
    if s == 'B' :
        p[2] += p[1]
    if s == 'C' :
        p[3] += p[2]
    if s == '?':
        p[3] += p[2] + p[3] * 2
        p[2] += p[1] + p[2] * 2
        p[1] += p[0] + p[1] * 2
        p[0] += p[0] * 2
        
print(int(p[3] % (1e9 + 7)))

Submission status: Runtime Error

Solution code:
# temp

text = str(input())
checking = 0;

#Aと、Aとして扱える?の数
numA=[];
numAQ=[];
numAnow=0
numAQnow=0

for i in text:
    if(i=="A"):
        numAnow+=1;
        numA.append(numAnow);
        numAQ.append(numAQnow);
    elif(i=="?"):
        numAQnow+=1;
        numA.append(numAnow);
        numAQ.append(numAQnow);
    else:
        numA.append(numAnow);
        numAQ.append(numAQnow);

#Cと、Cとして扱える?の数
numC=[];
numCQ=[];
numCnow=0
numCQnow=0

for i in text[::-1]:
    if(i=="C"):
        numCnow+=1;
        numC.insert(0, numCnow);
        numCQ.insert(0, numCQnow);
    elif(i=="?"):
        numCQnow+=1;
        numC.insert(0, numCnow);
        numCQ.insert(0, numCQnow);
    else:
        numC.insert(0, numCnow);
        numCQ.insert(0, numCQnow);

score=0;
nowChecking=0

for i in text[1:-1]:
    nowChecking+=1;
    if(i=="B" or i=="?"):
        numAcal=numA[nowChecking-1] * 3**numAQ[nowChecking-1]
        numAcal+=numAQ[nowChecking-1]*3**(numAQ[nowChecking-1]-1)

        numCcal=numC[nowChecking+1] * 3**numCQ[nowChecking+1]
        numCcal+=numCQ[nowChecking+1]*3**(numCQ[nowChecking+1]-1)

        score+=numAcal*numCcal

score=int(score%1000000007)

print(score);

Submission status: Runtime Error

Solution code:
from collections import Counter

S = input()

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

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

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

Submission status: Runtime Error

Solution code:
s=input()
count=0
for i in range(len(s)):
    if s[i]=="A" or s[i]=="?":
        for j in range(len(s)-1,i+1,-1):
            if s[j]=="C" or s[j]=="?":
                k=s[i+1:j]
                bb=k.count("B")
                dd=k.count("?")
                count=((count+bb*3**dd+dd*3**(dd-1))/(10**9+7))
print(int(count))

Submission status: Runtime Error

Solution code:
"""
問題文
文字列 T の ABC 数 とは、以下の条件をすべて満たす整数の組 (i,j,k) の個数です。

1≤i<j<k≤|T|（|T| は T の長さ）
Ti= A（Ti は T の先頭から i 番目の文字）
Tj= B
Tk= C
例えば、T= ABCBC のとき、条件をすべて満たす組 (i,j,k) は
 (1,2,3),(1,2,5),(1,4,5) の 3 個であるため、T の ABC 数は 3 です。

文字列 S が与えられます。S のそれぞれの文字は A, B, C, ? のいずれかです。

S に含まれる ? の個数を Q とします。S に含まれる ? を
それぞれ A, B, C のいずれかに置き換えることで 3Q 通りの文字列が作られます。
これらの文字列すべての ABC 数の和を求めてください。

ただし、この和は非常に大きくなりうるため、和を 109+7 で割った余りを出力してください。

制約
3≤|S|≤105
S のそれぞれの文字は A, B, C, ? のいずれかである。
入力
入力は以下の形式で標準入力から与えられる。

S
出力
3Q 通りの文字列すべての ABC 数の和を 109+7 で割った余りを出力せよ。
"""

"""左端のAまたは?からBまたは?の個数とそれより右にあるCまたは?の数を掛けた数が答えになる"""

s = input()
a = -1
b = -1
c = []
for i in range(len(s)):
    if s[i] != "A" and s[i] != "B" and s[i] != "C":
        s = s[0:i]+"P"+s[i+1:len(s)]
#print(s)

for i in range(len(s)):
    if (s[i] == "A" or s[i] == "P") and (i <= len(s) - 3):
        #print(s[i])
        for j in range(i + 1, len(s)):
            if (s[j] == "B" or s[j] == "P") and (j <= len(s) - 2):
                a = s[j :s.rfind("C" or "P")].count("B")+s[j:s.rfind("C" or "P")].count("P")
                for k in range(j + 1, len(s)):
                    if s[k] == "C" or s[k] == "P":
                        b = s[k:len(s)].count("C")+s[k:len(s)].count("P")
                        #print(a, b)
                        c.append(a * b)
print(sum(c)%(10**9+7)

Submission status: Runtime Error

Solution code:
import sys
s = sys.stdin.readline().strip()

MOD = 1000000007


def q(s):
    c = 0
    for i in s:
        if i == "?": c += 1
    return (3 ** c) % MOD

def abc(s):
    if len(s) < 3: return 0
    elif len(s) == 3:
        if (s[0] == "A" or s[0] == "?") and (s[1] == "B" or s[1] == "?") \
            and (s[2] == "C" or s[2] == "?"):
            return 1
        else:
            return 0
    elif s[0] == "A":
        return (abc(s[1:]) + bc(s[1:])) % MOD
    elif s[0] == "B" or s[0] == "C":
        return abc(s[1:]) % MOD
    else:
        return (3 * abc(s[1:]) + bc(s[1:])) % MOD


def bc(s):
    if len(s) < 2: return 0
    elif len(s) == 2:
        if (s[0] == "B" or s[0] == "?") and (s[1] == "C" or s[1] == "?"):
            return 1
        else:
            return 0
    elif s[0] == "B":
        return (bc(s[1:]) + c(s[1:])) % MOD
    elif s[0] == "A" or s[0] == "C":
        return bc(s[1:]) % MOD
    else:
        return (3 * bc(s[1:]) + c(s[1:])) % MOD


def c(s):
    if len(s) < 1: return 0
    elif len(s) == 1:
        if s[0] == "C" or s[0] == "?":
            return 1
        else:
            return 0
    elif s[0] == "C":
        return (q(s[1:]) + c(s[1:])) % MOD
    elif s[0] == "A" or s[0] == "B":
        return c(s[1:]) % MOD
    else:
        return (3 * c(s[1:]) + q(s[1:])) % MOD

print(abc(s))

Submission status: Runtime Error

Solution code:
s=input()
count=0
for i in range(len(s)):
    if s[i]=="A" or s[i]=="?":
        for j in range(len(s)-1,i,-1):
            if s[j]=="C" or s[j]=="?":
                k=s[i+1:j]
                bb=k.count("B")
                dd=k.count("?")
                count=(count+bb*3**dd+dd*3**(dd-1))%(10**9+7)
print(count)

Submission status: Runtime Error

Solution code:
from collections import Counter
S = input()
MOD = 10 ** 9 + 7
ans = 0
front = Counter({})
back = Counter(S)
pow3 = [1]
for i in range(back['?']):
  pow3.append(pow3[-1] * 3)

for i in range(len(S)):
  c = S[i]
  back[c] -= 1
  # Bの位置を固定
  if c == 'B' or c == '?':
    # ?を使わない
    ans += front['A'] * back['C'] * (pow3[front['?'] + back['?']])
    # Aだけ?をつかう
    ans += front['?'] * back['C'] * (pow3[front['?'] + back['?'] - 1])
    # Cだけ?をつかう
    ans += front['A'] * back['?'] * (pow3[front['?'] + back['?'] - 1])
    # 両方?をつかう
    ans += front['?'] * back['?'] * (pow3[front['?'] + back['?'] - 2])
    ans %= MOD
  front[c] += 1

print(int(ans))

Submission status: Runtime Error

Solution code:
import sys
s = sys.stdin.readline().strip()

MOD = 1000000007

def abc(s):
    if len(s) < 3: return 0
    elif len(s) == 3:
        if (s[0] == "A" or s[0] == "?") and (s[1] == "B" or s[1] == "?") \
            and (s[2] == "C" or s[2] == "?"):
            return 1
        else:
            return 0
    elif s[0] == "A":
        return (abc(s[1:]) + bc(s[1:])) % MOD
    elif s[0] == "B" or s[0] == "C":
        return abc(s[1:]) % MOD
    else:
        return (3 * abc(s[1:]) + bc(s[1:])) % MOD


def bc(s):
    if len(s) < 2: return 0
    elif len(s) == 2:
        if (s[0] == "B" or s[0] == "?") and (s[1] == "C" or s[1] == "?"):
            return 1
        else:
            return 0
    elif s[0] == "B":
        return (bc(s[1:]) + c(s[1:])) % MOD
    elif s[0] == "A" or s[0] == "C":
        return bc(s[1:]) % MOD
    else:
        return (3 * bc(s[1:]) + c(s[1:])) % MOD


def c(s):
    if len(s) < 1: return 0
    elif len(s) == 1:
        if s[0] == "C" or s[0] == "?":
            return 1
        else:
            return 0
    elif s[0] == "C":
        return (1 + c(s[1:])) % MOD
    elif s[0] == "A" or s[0] == "B":
        return c(s[1:]) % MOD
    else:
        return (3 * c(s[1:]) + 1) % MOD

print(abc(s))

Submission status: Runtime Error

Solution code:
import numpy as np
s=input()
A=np.zeros(4)
B=np.zeros(4)
C=np.zeros(4)
t=0
for c in s:
	if c=="A":
		A[0]+=1
	if c=="B":
		B+=A
	if c=='C':
		C+=B
	if c=='?':
		C+=np.roll(B,1)
		B[1]+=A[0]
		B[2]+=A[1]
		A[1]+=1
		t+=1
ans=0
for i in range(4):
	ans+=pow(3,t-i)*C[i]
print(int(ans%1000000007))

Submission status: Runtime Error

Solution code:
import numpy as np

s = input()

a = np.zeros(len(s))
q = np.zeros(len(s))
ab0 = np.zeros(len(s))
ab1 = np.zeros(len(s))
ab2 = np.zeros(len(s))
abc0 = np.zeros(len(s))
abc1 = np.zeros(len(s))
abc2 = np.zeros(len(s))
abc3 = np.zeros(len(s))

for i in range(len(s)):
    if s[i]=='A':
        a[i] = a[i-1]+1
        q[i] = q[i-1]
        ab0[i] = ab0[i-1]
        ab1[i] = ab1[i-1]
        ab2[i] = ab2[i-1]
        abc0[i] = abc0[i-1]
        abc1[i] = abc1[i-1]
        abc2[i] = abc2[i-1]
        abc3[i] = abc3[i-1]
    elif s[i]=='B':
        a[i] = a[i-1]
        q[i] = q[i-1]
        ab0[i] = ab0[i-1]+a[i-1]
        ab1[i] = ab1[i-1]+q[i-1]
        ab2[i] = ab2[i-1]
        abc0[i] = abc0[i-1]
        abc1[i] = abc1[i-1]
        abc2[i] = abc2[i-1]
        abc3[i] = abc3[i-1]
    elif s[i]== 'C':
        a[i] = a[i-1]
        q[i] = q[i-1]
        ab0[i] = ab0[i-1]
        ab1[i] = ab1[i-1]
        ab2[i] = ab2[i-1]
        abc0[i] = abc0[i-1]+ab0[i-1]
        abc1[i] = abc1[i-1]+ab1[i-1]
        abc2[i] = abc2[i-1]+ab2[i-1]
        abc3[i] = abc3[i-1]
    else:
        a[i] = a[i-1]
        q[i] = q[i-1]+1
        ab0[i] = ab0[i-1]
        ab1[i] = ab1[i-1]+a[i-1]
        ab2[i] = ab2[i-1]+q[i-1]
        abc0[i] = abc0[i-1]
        abc1[i] = abc1[i-1]+ab0[i-1]
        abc2[i] = abc2[i-1]+ab1[i-1]
        abc3[i] = abc3[i-1]+ab2[i-1]

m = q[len(s)-1]
n = abc0[len(s)-1] * (3**m%1000000007)
n %= 1000000007
n += abc1[len(s)-1] * (3**(m-1)%1000000007)
n %= 1000000007
n += abc2[len(s)-1] * (3**(m-2)%1000000007)
n %= 1000000007
n += abc3[len(s)-1] * (3**(m-3)%1000000007)
n %= 1000000007
print(int(n))

Submission status: Runtime Error

Solution code:
import numpy as np

s = input()

a = np.zeros(len(s))
q = np.zeros(len(s))
ab0 = np.zeros(len(s))
ab1 = np.zeros(len(s))
ab2 = np.zeros(len(s))
abc0 = np.zeros(len(s))
abc1 = np.zeros(len(s))
abc2 = np.zeros(len(s))
abc3 = np.zeros(len(s))

for i in range(len(s)):
    if s[i]=='A':
        a[i] = a[i-1]+1
        q[i] = q[i-1]
        ab0[i] = ab0[i-1]
        ab1[i] = ab1[i-1]
        ab2[i] = ab2[i-1]
        abc0[i] = abc0[i-1]
        abc1[i] = abc1[i-1]
        abc2[i] = abc2[i-1]
        abc3[i] = abc3[i-1]
    elif s[i]=='B':
        a[i] = a[i-1]
        q[i] = q[i-1]
        ab0[i] = ab0[i-1]+a[i-1]
        ab1[i] = ab1[i-1]+q[i-1]
        ab2[i] = ab2[i-1]
        abc0[i] = abc0[i-1]
        abc1[i] = abc1[i-1]
        abc2[i] = abc2[i-1]
        abc3[i] = abc3[i-1]
    elif s[i]== 'C':
        a[i] = a[i-1]
        q[i] = q[i-1]
        ab0[i] = ab0[i-1]
        ab1[i] = ab1[i-1]
        ab2[i] = ab2[i-1]
        abc0[i] = abc0[i-1]+ab0[i-1]
        abc1[i] = abc1[i-1]+ab1[i-1]
        abc2[i] = abc2[i-1]+ab2[i-1]
        abc3[i] = abc3[i-1]
    else:
        a[i] = a[i-1]
        q[i] = q[i-1]+1
        ab0[i] = ab0[i-1]
        ab1[i] = ab1[i-1]+a[i-1]
        ab2[i] = ab2[i-1]+q[i-1]
        abc0[i] = abc0[i-1]
        abc1[i] = abc1[i-1]+ab0[i-1]
        abc2[i] = abc2[i-1]+ab1[i-1]
        abc3[i] = abc3[i-1]+ab2[i-1]

m = q[len(s)-1]
n = abc0[len(s)-1] * (3**m)
n %= 1000000007
n += abc1[len(s)-1] * (3**(m-1))
n %= 1000000007
n += abc2[len(s)-1] * (3**(m-2))
n %= 1000000007
n += abc3[len(s)-1] * (3**(m-3))
n %= 1000000007
print(int(n))

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long llint;
llint inf = 1000000007;

llint a = 0;
llint b = 0;
llint c = 0;
llint r = 1;

string s;

int main() {
    cin >> s;
    for (int i = 0; i < s.length(); i++) {
        switch (s[i]) {
        case 'A':
            a = (a + r) % inf;
            break;
        case 'B':
            b = (b + a) % inf;
            break;
        case 'C':
            c = (c + b) % inf;
            break;
        default:
            c = (c * 3 + b) % inf;
            b = (b * 3 + a) % inf;
            a = (a * 3 + r) % inf;
            r = (r * 3) % inf;
        }
    }
    cout << c << endl;
    return 0;
}

Submission status: Runtime Error

Solution code:
import numpy as np
s=input()
A=np.array([0,0,0,0])
B=np.array([0,0,0,0])
C=np.array([0,0,0,0])
t=0
for c in s:
	if c=="A":
		A[0]+=1
	if c=="B":
		B+=A
	if c=='C':
		C+=B
	if c=='?':
		wayC+=np.roll(wayB,1)
		B[1]+=A[0]
		B[2]+=A[1]
		A[1]+=1
		t+=1
ans=0
for i in range(4):
	ans+=pow(3,t-i)*C[i]
print(int(ans%1000000007))

Submission status: Runtime Error

Solution code:
a = 0
ab = 0
abc = 0
r = 1

s = input()

for c in s:
    if c == "A":
        a += r
    elif c == "B":
        ab += a
    elif c == "C":
        abc += ab
    else:
        abc = abc * 3 + ab
        ab = ab * 3 + a
        a = a * 3 + r
        r *= 3

print(abc % 1_000_000_007)

Submission status: Runtime Error

Solution code:
import numpy as np
s=input()
wayA=np.array([0,0,0,0])
wayB=np.array([0,0,0,0])
wayC=np.array([0,0,0,0])
hatena=0
for c in s:
	if c=="A":
		wayA[0]+=1
	if c=="B":
		wayB+=wayA
	if c=='C':
		wayC+=wayB
	if c=='?':
		wayC[1]+=wayB[0]
		wayC[2]+=wayB[1]
		wayC[3]+=wayB[2]
		wayB[1]+=wayA[0]
		wayB[2]+=wayA[1]
		wayA[1]+=1
		hatena+=1
ans=0
for i in range(4):
	ans+=pow(3,hatena-i)*wayC[i]
print(int(ans%MOD))