Buggy python submission (verdict: Time Limit Exceeded):
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()


Fixed submission:
S = input()

MOD = 10**9 + 7
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])

Buggy python submission (verdict: Time Limit Exceeded):
S = input()


MOD = 10**9 + 7

# time complexity: O(|S|)
def focus_on_B():
    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()


Fixed submission:
S = input()

MOD = 10**9 + 7
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])

Buggy python submission (verdict: Time Limit Exceeded):
S = input()


MOD = 10**9 + 7



# time complexity: O(|S|)
def focus_on_B():
    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)
            num_combinations %= MOD
        else:
            continue
    print(num_combinations)

focus_on_B()


Fixed submission:
S = input()

MOD = 10**9 + 7
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])

Buggy python submission (verdict: Time Limit Exceeded):
S = input()


MOD = 10**9 + 7

# time complexity: O(|S|)
def focus_on_B():
    char_to_idx = {"A": 0,
                     "C": 1,
                     "?": 2}

    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)
            num_combinations %= MOD
        else:
            continue
    print(num_combinations)


focus_on_B()


Fixed submission:
S = input()

MOD = 10**9 + 7
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])

Buggy python submission (verdict: Runtime Error):
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)


Fixed submission:
S = input()

MOD = 10**9 + 7
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])

Buggy python submission (verdict: Time Limit Exceeded):
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])
    assert len(cuml['A']) == len(S)

    # num_combinations[i]: i番目をBとした時に、可能な組み合わせの数
    num_combinations = [0] * len(S)
    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[i] = (A_L * 3**Q_L + Q_L * int(3**(Q_L - 1)))\
                                * (C_R * 3**Q_R + Q_R * int(3**(Q_R - 1)))
            num_combinations[i] %= MOD
        else:
            continue
    print(sum(num_combinations) % MOD)

focus_on_B(S)


Fixed submission:
S = input()

MOD = 10**9 + 7
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])

Buggy python submission (verdict: Time Limit Exceeded):
S = input()


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(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])
    assert len(cuml['A']) == len(S)

    # num_combinations[i]: i番目をBとした時に、可能な組み合わせの数
    num_combinations = [0] * len(S)
    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[i] = (A_L * 3**Q_L + Q_L * int(3**(Q_L - 1)))\
                                * (C_R * 3**Q_R + Q_R * int(3**(Q_R - 1)))
            num_combinations[i] %= MOD
        else:
            continue
    print(sum(num_combinations) % MOD)

focus_on_B(S)


Fixed submission:
S = input()

MOD = 10**9 + 7
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])