Buggy python submission (verdict: Runtime Error):
def main():
    """
    1 <= i < j < k <= |T|
    Ti = A
    Tj = B
    Tk = C
    """
    S = input()
    ans3 = cumsum(S)
    print(ans3)


def cumsum(S):
    """
    考えたときに累積和が浮かんだ
    ABCとあるので
    i文字目までのA相当の数、つまり?も含んだ数
    これをBとCにも適用する
    Aを決め打ちで進めるとBも走査することになる
    Cは定数倍で求められるが、|S|^2: TLE で意味がない

    ここで断念していろいろ調べると
    Bを決め打ちすれば
    A: 0-(B-1)
    C: (B+1)-N
    なのでNでおｋ

    と、思ったがWAと同じ間違いをしている
    3^q パターンをきちんと考える
    """
    n = len(S)
    aa = [0 for _ in range(n+1)]
    cc = [0 for _ in range(n+1)]
    q = [0 for _ in range(n+1)]
    for i in range(n):
        aa[i+1] += aa[i] + int(S[i] == "A")
        cc[i+1] += cc[i] + int(S[i] == "C")
        q[i+1] += q[i] + int(S[i] == "?")

    ans = 0
    MOD = 10 ** 9 + 7
    for i in range(1, n-1):
        a = aa[i]
        c = cc[n] - cc[i+1]
        l = q[i]
        r = q[n] - q[i+1]
        # ABC の作り方
        # AB?: ? 1つをCに割り当てる
        # ?BC: ? 1つをAに割り当てる
        # ?B?: ? 2つをACに割り当てる
        if S[i] in ("B", "?"):
            ac = a * c * pow(3, l + r, MOD)
            aq, qc, qq = (0, 0, 0)
            if l + r - 1:
                p = pow(3, l + r - 1, MOD)
                aq = a * r * p
                qc = l * c * p
            if l + r - 1:
                qq = l * r * pow(3, l + r - 2, MOD)
            # print(a, c, l, r, ((l+r, l+r-1, l+r-2)), (ac, aq, qc, qq))
            # 3^x: xが負になるときに少数になってしまうので、float -> int にする必要がある
            # 上記が重いのでTLE: pow+mod引数で対応
            ans += ac + aq + qc + qq
            ans %= MOD

    return ans


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    """
    1 <= i < j < k <= |T|
    Ti = A
    Tj = B
    Tk = C
    """
    S = input()
    ans = editorial(S)

    print(ans)


def editorial(S):
    MOD = 10 ** 9 + 7
    n = len(S)
    dp = [[0] * (3+1) for _ in range(n+1)]

    for i in range(n, -1, -1):
        for j in range(3, -1, -1):
            if i == n:
                x = int(j == 3)
                # ≠3: 丸を3個つける前に最後の文字まで見終わってしまい、手遅れ
                # =3: 処理が正常終了
                dp[i][j] = x
            else:
                m1 = 1
                if S[i] == "?":
                    m1 = 3

                if j == 3:
                    # 丸は3個つけ終わったので、あとは?を置換するのみ
                    dp[i][j] = m1 * dp[i+1][j]
                else:
                    m2 = int(S[i] == "?" or S[i] == "ABC"[j])
                    # 前半:i文字目に丸をつけない場合, 後半:丸をつける場合に対応
                    dp[i][j] = m1 * dp[i+1][j] + m2 * dp[i+1][j+1]

                dp[i][j] %= MOD

    ans = dp[0][0]
    return ans


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    """
    1 <= i < j < k <= |T|
    Ti = A
    Tj = B
    Tk = C
    """
    S = input()
    #ans = editorial(S)
    #ans2 = dp_simple(S)
    ans3 = cumsum(S)

    #assert ans == ans2 == ans3
    #if len(S) <= 5:
    #    ans4 = TLE(S)
    #    assert ans == ans4

    print(ans3)


def TLE(S):
    """文字列全列挙
    ?をすべて置き換えるパターンを作成し
    それについてABC数を算出
    """
    s = list(S)
    qi = [i for i, c in enumerate(S) if c == "?"]
    nq = len(qi)
    mod = 10 ** 9 + 7
    import sys
    sys.setrecursionlimit(mod)

    def rec(i):
        if i == nq:
            return n_ABC(s)

        ans = 0
        for x in list("ABC"):
            s[qi[i]] = x
            ans += rec(i+1)

        return ans

    ans = rec(0) % mod
    return ans


def n_ABC(S):
    """3^Q を考えていないパターン がABCを求めるパターンになっていた
    """
    ans = 0
    n = len(S)
    for i in range(n):
        for j in range(i+1, n):
            for k in range(j+1, n):
                # print(i, j, k, S[i] + S[j] + S[k])
                if S[i] in ("A", "?") and S[j] in ("B", "?") and S[k] in ("C", "?"):
                    ans += 1

    return ans


def editorial(S):
    MOD = 10 ** 9 + 7
    n = len(S)
    dp = [[0] * (3+1) for _ in range(n+1)]

    for i in range(n, -1, -1):
        for j in range(3, -1, -1):
            if i == n:
                x = int(j == 3)
                # ≠3: 丸を3個つける前に最後の文字まで見終わってしまい、手遅れ
                # =3: 処理が正常終了
                dp[i][j] = x
            else:
                m1 = 1
                if S[i] == "?":
                    m1 = 3

                if j == 3:
                    # 丸は3個つけ終わったので、あとは?を置換するのみ
                    dp[i][j] = m1 * dp[i+1][j]
                else:
                    m2 = int(S[i] == "?" or S[i] == "ABC"[j])
                    # 前半:i文字目に丸をつけない場合, 後半:丸をつける場合に対応
                    dp[i][j] = m1 * dp[i+1][j] + m2 * dp[i+1][j+1]

                dp[i][j] %= MOD

    ans = dp[0][0]
    return ans


def dp_simple(S):
    n = len(S)
    MOD = 10 ** 9 + 7
    dp = [[0] * (3+1) for _ in range(n+1)]
    # 組合せ列挙なので掛け算としての単位元
    dp[0][0] = 1

    for i in range(n):
        # i文字目まで
        for j in range(3+1):
            # 0-3文字揃ってる
            m = 1
            if S[i] == "?":
                # 置換できるので3パターン
                m = 3
            dp[i+1][j] += dp[i][j] * m
            dp[i+1][j] %= MOD

            # 3文字揃ってないとき, 対応する文字になるか？
            if j < 3 and (S[i] == "?" or S[i] == "ABC"[j]):
                dp[i+1][j+1] += dp[i][j]
                dp[i+1][j+1] %= MOD

    ans = dp[n][3]
    return ans


def cumsum(S):
    """
    考えたときに累積和が浮かんだ
    ABCとあるので
    i文字目までのA相当の数、つまり?も含んだ数
    これをBとCにも適用する
    Aを決め打ちで進めるとBも走査することになる
    Cは定数倍で求められるが、|S|^2: TLE で意味がない

    ここで断念していろいろ調べると
    Bを決め打ちすれば
    A: 0-(B-1)
    C: (B+1)-N
    なのでNでおｋ

    と、思ったがWAと同じ間違いをしている
    3^q パターンをきちんと考える
    """
    n = len(S)
    aa = [0 for _ in range(n+1)]
    cc = [0 for _ in range(n+1)]
    q = [0 for _ in range(n+1)]
    for i in range(n):
        aa[i+1] += aa[i] + int(S[i] == "A")
        cc[i+1] += cc[i] + int(S[i] == "C")
        q[i+1] += q[i] + int(S[i] == "?")

    ans = 0
    MOD = 10 ** 9 + 7
    for i in range(1, n-1):
        a = aa[i]
        c = cc[n] - cc[i+1]
        l = q[i]
        r = q[n] - q[i+1]
        # ABC の作り方
        # AB?: ? 1つをCに割り当てる
        # ?BC: ? 1つをAに割り当てる
        # ?B?: ? 2つをACに割り当てる
        if S[i] in ("B", "?"):
            ac = a * c * (3 ** (l + r))
            aq = a * r * (3 ** (l + r - 1))
            qc = l * c * (3 ** (l + r - 1))
            qq = l * r * (3 ** (l + r - 2))
            # print(a, c, l, r, ((l+r, l+r-1, l+r-2)), (ac, aq, qc, qq))
            # 3^x: xが負になるときに少数になってしまう
            ans += int(ac + aq + qc + qq)
            ans %= MOD

    return ans


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    """
    1 <= i < j < k <= |T|
    Ti = A
    Tj = B
    Tk = C
    """
    S = input()
    ans = editorial(S)

    print(ans)


def editorial(S):
    MOD = 10 ** 9 + 7
    n = len(S)
    dp = [[0] * (3+1) for _ in range(n+1)]

    for i in range(n, -1, -1):
        for j in range(3, -1, -1):
            if i == n:
                x = int(j == 3)
                # ≠3: 丸を3個つける前に最後の文字まで見終わってしまい、手遅れ
                # =3: 処理が正常終了
                dp[i][j] = x
            else:
                m1 = 1
                if S[i] == "?":
                    m1 = 3

                if j == 3:
                    # 丸は3個つけ終わったので、あとは?を置換するのみ
                    dp[i][j] = m1 * dp[i+1][j]
                else:
                    m2 = int(S[i] == "?" or S[i] == "ABC"[j])
                    # 前半:i文字目に丸をつけない場合, 後半:丸をつける場合に対応
                    dp[i][j] = m1 * dp[i+1][j] + m2 * dp[i+1][j+1]

                dp[i][j] %= MOD

    ans = dp[0][0]
    return ans


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    """
    1 <= i < j < k <= |T|
    Ti = A
    Tj = B
    Tk = C
    """
    S = input()
    #ans = editorial(S)
    #ans2 = dp_simple(S)
    ans3 = cumsum(S)

    #assert ans == ans2 == ans3
    #if len(S) <= 5:
    #    ans4 = TLE(S)
    #    assert ans == ans4

    print(ans3)


def TLE(S):
    """文字列全列挙
    ?をすべて置き換えるパターンを作成し
    それについてABC数を算出
    """
    s = list(S)
    qi = [i for i, c in enumerate(S) if c == "?"]
    nq = len(qi)
    mod = 10 ** 9 + 7
    import sys
    sys.setrecursionlimit(mod)

    def rec(i):
        if i == nq:
            return n_ABC(s)

        ans = 0
        for x in list("ABC"):
            s[qi[i]] = x
            ans += rec(i+1)

        return ans

    ans = rec(0) % mod
    return ans


def n_ABC(S):
    """3^Q を考えていないパターン がABCを求めるパターンになっていた
    """
    ans = 0
    n = len(S)
    for i in range(n):
        for j in range(i+1, n):
            for k in range(j+1, n):
                # print(i, j, k, S[i] + S[j] + S[k])
                if S[i] in ("A", "?") and S[j] in ("B", "?") and S[k] in ("C", "?"):
                    ans += 1

    return ans


def editorial(S):
    MOD = 10 ** 9 + 7
    n = len(S)
    dp = [[0] * (3+1) for _ in range(n+1)]

    for i in range(n, -1, -1):
        for j in range(3, -1, -1):
            if i == n:
                x = int(j == 3)
                # ≠3: 丸を3個つける前に最後の文字まで見終わってしまい、手遅れ
                # =3: 処理が正常終了
                dp[i][j] = x
            else:
                m1 = 1
                if S[i] == "?":
                    m1 = 3

                if j == 3:
                    # 丸は3個つけ終わったので、あとは?を置換するのみ
                    dp[i][j] = m1 * dp[i+1][j]
                else:
                    m2 = int(S[i] == "?" or S[i] == "ABC"[j])
                    # 前半:i文字目に丸をつけない場合, 後半:丸をつける場合に対応
                    dp[i][j] = m1 * dp[i+1][j] + m2 * dp[i+1][j+1]

                dp[i][j] %= MOD

    ans = dp[0][0]
    return ans


def dp_simple(S):
    n = len(S)
    MOD = 10 ** 9 + 7
    dp = [[0] * (3+1) for _ in range(n+1)]
    # 組合せ列挙なので掛け算としての単位元
    dp[0][0] = 1

    for i in range(n):
        # i文字目まで
        for j in range(3+1):
            # 0-3文字揃ってる
            m = 1
            if S[i] == "?":
                # 置換できるので3パターン
                m = 3
            dp[i+1][j] += dp[i][j] * m
            dp[i+1][j] %= MOD

            # 3文字揃ってないとき, 対応する文字になるか？
            if j < 3 and (S[i] == "?" or S[i] == "ABC"[j]):
                dp[i+1][j+1] += dp[i][j]
                dp[i+1][j+1] %= MOD

    ans = dp[n][3]
    return ans


def cumsum(S):
    """
    考えたときに累積和が浮かんだ
    ABCとあるので
    i文字目までのA相当の数、つまり?も含んだ数
    これをBとCにも適用する
    Aを決め打ちで進めるとBも走査することになる
    Cは定数倍で求められるが、|S|^2: TLE で意味がない

    ここで断念していろいろ調べると
    Bを決め打ちすれば
    A: 0-(B-1)
    C: (B+1)-N
    なのでNでおｋ

    と、思ったがWAと同じ間違いをしている
    3^q パターンをきちんと考える
    """
    n = len(S)
    aa = [0 for _ in range(n+1)]
    cc = [0 for _ in range(n+1)]
    q = [0 for _ in range(n+1)]
    for i in range(n):
        aa[i+1] += aa[i] + int(S[i] == "A")
        cc[i+1] += cc[i] + int(S[i] == "C")
        q[i+1] += q[i] + int(S[i] == "?")

    ans = 0
    MOD = 10 ** 9 + 7
    for i in range(1, n-1):
        a = aa[i]
        c = cc[n] - cc[i+1]
        l = q[i]
        r = q[n] - q[i+1]
        # ABC の作り方
        # AB?: ? 1つをCに割り当てる
        # ?BC: ? 1つをAに割り当てる
        # ?B?: ? 2つをACに割り当てる
        if S[i] in ("B", "?"):
            ac = a * c * (3 ** (l + r))
            aq = a * r * (3 ** (l + r - 1))
            qc = l * c * (3 ** (l + r - 1))
            qq = l * r * (3 ** (l + r - 2))
            # print(a, c, l, r, ((l+r, l+r-1, l+r-2)), (ac, aq, qc, qq))
            # 3^x: xが負になるときに少数になってしまう
            ans += int(ac + aq + qc + qq)
            ans %= MOD

    return ans


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    """
    1 <= i < j < k <= |T|
    Ti = A
    Tj = B
    Tk = C
    """
    S = input()
    ans = editorial(S)

    print(ans)


def editorial(S):
    MOD = 10 ** 9 + 7
    n = len(S)
    dp = [[0] * (3+1) for _ in range(n+1)]

    for i in range(n, -1, -1):
        for j in range(3, -1, -1):
            if i == n:
                x = int(j == 3)
                # ≠3: 丸を3個つける前に最後の文字まで見終わってしまい、手遅れ
                # =3: 処理が正常終了
                dp[i][j] = x
            else:
                m1 = 1
                if S[i] == "?":
                    m1 = 3

                if j == 3:
                    # 丸は3個つけ終わったので、あとは?を置換するのみ
                    dp[i][j] = m1 * dp[i+1][j]
                else:
                    m2 = int(S[i] == "?" or S[i] == "ABC"[j])
                    # 前半:i文字目に丸をつけない場合, 後半:丸をつける場合に対応
                    dp[i][j] = m1 * dp[i+1][j] + m2 * dp[i+1][j+1]

                dp[i][j] %= MOD

    ans = dp[0][0]
    return ans


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    """
    1 <= i < j < k <= |T|
    Ti = A
    Tj = B
    Tk = C
    """
    S = input()
    ans = editorial(S)
    ans2 = dp_simple(S)
    ans3 = cumsum(S)
    assert ans == ans2 == ans3
    if len(S) <= 5:
        ans4 = TLE(S)
        assert ans == ans4

    print(ans)


def TLE(S):
    """文字列全列挙
    ?をすべて置き換えるパターンを作成し
    それについてABC数を算出
    """
    s = list(S)
    qi = [i for i, c in enumerate(S) if c == "?"]
    nq = len(qi)
    mod = 10 ** 9 + 7
    import sys
    sys.setrecursionlimit(mod)

    def rec(i):
        if i == nq:
            return n_ABC(s)

        ans = 0
        for x in list("ABC"):
            s[qi[i]] = x
            ans += rec(i+1)

        return ans

    ans = rec(0) % mod
    return ans


def n_ABC(S):
    """3^Q を考えていないパターン がABCを求めるパターンになっていた
    """
    ans = 0
    n = len(S)
    for i in range(n):
        for j in range(i+1, n):
            for k in range(j+1, n):
                # print(i, j, k, S[i] + S[j] + S[k])
                if S[i] in ("A", "?") and S[j] in ("B", "?") and S[k] in ("C", "?"):
                    ans += 1

    return ans


def editorial(S):
    MOD = 10 ** 9 + 7
    n = len(S)
    dp = [[0] * (3+1) for _ in range(n+1)]

    for i in range(n, -1, -1):
        for j in range(3, -1, -1):
            if i == n:
                x = int(j == 3)
                # ≠3: 丸を3個つける前に最後の文字まで見終わってしまい、手遅れ
                # =3: 処理が正常終了
                dp[i][j] = x
            else:
                m1 = 1
                if S[i] == "?":
                    m1 = 3

                if j == 3:
                    # 丸は3個つけ終わったので、あとは?を置換するのみ
                    dp[i][j] = m1 * dp[i+1][j]
                else:
                    m2 = int(S[i] == "?" or S[i] == "ABC"[j])
                    # 前半:i文字目に丸をつけない場合, 後半:丸をつける場合に対応
                    dp[i][j] = m1 * dp[i+1][j] + m2 * dp[i+1][j+1]

                dp[i][j] %= MOD

    ans = dp[0][0]
    return ans


def dp_simple(S):
    n = len(S)
    MOD = 10 ** 9 + 7
    dp = [[0] * (3+1) for _ in range(n+1)]
    # 組合せ列挙なので掛け算としての単位元
    dp[0][0] = 1

    for i in range(n):
        # i文字目まで
        for j in range(3+1):
            # 0-3文字揃ってる
            m = 1
            if S[i] == "?":
                # 置換できるので3パターン
                m = 3
            dp[i+1][j] += dp[i][j] * m
            dp[i+1][j] %= MOD

            # 3文字揃ってないとき, 対応する文字になるか？
            if j < 3 and (S[i] == "?" or S[i] == "ABC"[j]):
                dp[i+1][j+1] += dp[i][j]
                dp[i+1][j+1] %= MOD

    ans = dp[n][3]
    return ans


def cumsum(S):
    """
    考えたときに累積和が浮かんだ
    ABCとあるので
    i文字目までのA相当の数、つまり?も含んだ数
    これをBとCにも適用する
    Aを決め打ちで進めるとBも走査することになる
    Cは定数倍で求められるが、|S|^2: TLE で意味がない

    ここで断念していろいろ調べると
    Bを決め打ちすれば
    A: 0-(B-1)
    C: (B+1)-N
    なのでNでおｋ

    と、思ったがWAと同じ間違いをしている
    3^q パターンをきちんと考える
    """
    n = len(S)
    q = [0 for _ in range(n+1)]
    abc = [[0] * 3 for _ in range(n+1)]
    for i in range(n):
        is_q = S[i] == "?"
        q[i+1] += q[i] + int(is_q)

        # for j, c in enumerate("ABC"):
        #    add = int(is_q or S[i] == c)
        for j, c in enumerate("ABC"):
            if c == "B":
                add = int(is_q or S[i] == c)
            else:
                add = int(S[i] == c)
            abc[i+1][j] += abc[i][j] + add

    ans = 0
    MOD = 10 ** 9 + 7
    for i in range(1, n-1):
        a = abc[i][0]
        b = abc[i+1][1] - abc[i][1]
        c = abc[n][2] - abc[i+1][2]
        l = q[i]
        r = q[n] - q[i+1]

        # WA: ? を無視している
        # ans += a * b * c

        # ABC の作り方
        # AB?: ? 1つをCに割り当てる
        # ?BC: ? 1つをCに割り当てる
        # ?B?: ? 2つをACに割り当てる
        ac = a * b * c * (3 ** (l + r))
        aq = a * b * r * (3 ** (l + r - 1))
        qc = l * b * c * (3 ** (l + r - 1))
        qq = l * b * r * (3 ** (l + r - 2))
        ans += ac + aq + qc + qq
        ans %= MOD

    return ans


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    """
    1 <= i < j < k <= |T|
    Ti = A
    Tj = B
    Tk = C
    """
    S = input()
    ans = editorial(S)

    print(ans)


def editorial(S):
    MOD = 10 ** 9 + 7
    n = len(S)
    dp = [[0] * (3+1) for _ in range(n+1)]

    for i in range(n, -1, -1):
        for j in range(3, -1, -1):
            if i == n:
                x = int(j == 3)
                # ≠3: 丸を3個つける前に最後の文字まで見終わってしまい、手遅れ
                # =3: 処理が正常終了
                dp[i][j] = x
            else:
                m1 = 1
                if S[i] == "?":
                    m1 = 3

                if j == 3:
                    # 丸は3個つけ終わったので、あとは?を置換するのみ
                    dp[i][j] = m1 * dp[i+1][j]
                else:
                    m2 = int(S[i] == "?" or S[i] == "ABC"[j])
                    # 前半:i文字目に丸をつけない場合, 後半:丸をつける場合に対応
                    dp[i][j] = m1 * dp[i+1][j] + m2 * dp[i+1][j+1]

                dp[i][j] %= MOD

    ans = dp[0][0]
    return ans


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    """
    1 <= i < j < k <= |T|
    Ti = A
    Tj = B
    Tk = C
    """
    S = input()
    ans = editorial(S)
    ans2 = dp_simple(S)
    ans3 = cumsum(S)
    assert ans == ans2 == ans3
    if len(S) <= 5:
        ans4 = TLE(S)
        assert ans == ans4

    print(ans)


def TLE(S):
    """文字列全列挙
    ?をすべて置き換えるパターンを作成し
    それについてABC数を算出
    """
    s = list(S)
    qi = [i for i, c in enumerate(S) if c == "?"]
    nq = len(qi)
    mod = 10 ** 9 + 7
    import sys
    sys.setrecursionlimit(mod)

    def rec(i):
        if i == nq:
            return n_ABC(s)

        ans = 0
        for x in list("ABC"):
            s[qi[i]] = x
            ans += rec(i+1)

        return ans

    ans = rec(0) % mod
    return ans


def n_ABC(S):
    """3^Q を考えていないパターン がABCを求めるパターンになっていた
    """
    ans = 0
    n = len(S)
    for i in range(n):
        for j in range(i+1, n):
            for k in range(j+1, n):
                # print(i, j, k, S[i] + S[j] + S[k])
                if S[i] in ("A", "?") and S[j] in ("B", "?") and S[k] in ("C", "?"):
                    ans += 1

    return ans


def editorial(S):
    MOD = 10 ** 9 + 7
    n = len(S)
    dp = [[0] * (3+1) for _ in range(n+1)]

    for i in range(n, -1, -1):
        for j in range(3, -1, -1):
            if i == n:
                x = int(j == 3)
                # ≠3: 丸を3個つける前に最後の文字まで見終わってしまい、手遅れ
                # =3: 処理が正常終了
                dp[i][j] = x
            else:
                m1 = 1
                if S[i] == "?":
                    m1 = 3

                if j == 3:
                    # 丸は3個つけ終わったので、あとは?を置換するのみ
                    dp[i][j] = m1 * dp[i+1][j]
                else:
                    m2 = int(S[i] == "?" or S[i] == "ABC"[j])
                    # 前半:i文字目に丸をつけない場合, 後半:丸をつける場合に対応
                    dp[i][j] = m1 * dp[i+1][j] + m2 * dp[i+1][j+1]

                dp[i][j] %= MOD

    ans = dp[0][0]
    return ans


def dp_simple(S):
    n = len(S)
    MOD = 10 ** 9 + 7
    dp = [[0] * (3+1) for _ in range(n+1)]
    # 組合せ列挙なので掛け算としての単位元
    dp[0][0] = 1

    for i in range(n):
        # i文字目まで
        for j in range(3+1):
            # 0-3文字揃ってる
            m = 1
            if S[i] == "?":
                # 置換できるので3パターン
                m = 3
            dp[i+1][j] += dp[i][j] * m
            dp[i+1][j] %= MOD

            # 3文字揃ってないとき, 対応する文字になるか？
            if j < 3 and (S[i] == "?" or S[i] == "ABC"[j]):
                dp[i+1][j+1] += dp[i][j]
                dp[i+1][j+1] %= MOD

    ans = dp[n][3]
    return ans


def cumsum(S):
    """
    考えたときに累積和が浮かんだ
    ABCとあるので
    i文字目までのA相当の数、つまり?も含んだ数
    これをBとCにも適用する
    Aを決め打ちで進めるとBも走査することになる
    Cは定数倍で求められるが、|S|^2: TLE で意味がない

    ここで断念していろいろ調べると
    Bを決め打ちすれば
    A: 0-(B-1)
    C: (B+1)-N
    なのでNでおｋ

    と、思ったがWAと同じ間違いをしている
    3^q パターンをきちんと考える
    """
    n = len(S)
    q = [0 for _ in range(n+1)]
    abc = [[0] * 3 for _ in range(n+1)]
    for i in range(n):
        is_q = S[i] == "?"
        q[i+1] += q[i] + int(is_q)

        # for j, c in enumerate("ABC"):
        #    add = int(is_q or S[i] == c)
        for j, c in enumerate("ABC"):
            if c == "B":
                add = int(is_q or S[i] == c)
            else:
                add = int(S[i] == c)
            abc[i+1][j] += abc[i][j] + add

    ans = 0
    MOD = 10 ** 9 + 7
    for i in range(1, n-1):
        a = abc[i][0]
        b = abc[i+1][1] - abc[i][1]
        c = abc[n][2] - abc[i+1][2]
        l = q[i]
        r = q[n] - q[i+1]

        # WA: ? を無視している
        # ans += a * b * c

        # ABC の作り方
        # AB?: ? 1つをCに割り当てる
        # ?BC: ? 1つをCに割り当てる
        # ?B?: ? 2つをACに割り当てる
        ac = a * b * c * (3 ** (l + r))
        aq = a * b * r * (3 ** (l + r - 1))
        qc = l * b * c * (3 ** (l + r - 1))
        qq = l * b * r * (3 ** (l + r - 2))
        ans += ac + aq + qc + qq
        ans %= MOD

    return ans


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    """
    1 <= i < j < k <= |T|
    Ti = A
    Tj = B
    Tk = C
    """
    S = input()
    ans = editorial(S)

    print(ans)


def editorial(S):
    MOD = 10 ** 9 + 7
    n = len(S)
    dp = [[0] * (3+1) for _ in range(n+1)]

    for i in range(n, -1, -1):
        for j in range(3, -1, -1):
            if i == n:
                x = int(j == 3)
                # ≠3: 丸を3個つける前に最後の文字まで見終わってしまい、手遅れ
                # =3: 処理が正常終了
                dp[i][j] = x
            else:
                m1 = 1
                if S[i] == "?":
                    m1 = 3

                if j == 3:
                    # 丸は3個つけ終わったので、あとは?を置換するのみ
                    dp[i][j] = m1 * dp[i+1][j]
                else:
                    m2 = int(S[i] == "?" or S[i] == "ABC"[j])
                    # 前半:i文字目に丸をつけない場合, 後半:丸をつける場合に対応
                    dp[i][j] = m1 * dp[i+1][j] + m2 * dp[i+1][j+1]

                dp[i][j] %= MOD

    ans = dp[0][0]
    return ans


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    """
    1 <= i < j < k <= |T|
    Ti = A
    Tj = B
    Tk = C
    """
    S = input()
    #ans = editorial(S)
    ans = TLE(S)

    print(ans)


def TLE(S):
    """文字列全列挙
    ?をすべて置き換えるパターンを作成し
    それについてABC数を算出
    """
    s = list(S)
    qi = [i for i, c in enumerate(S) if c == "?"]
    nq = len(qi)
    mod = 10 ** 9 + 7
    import sys
    sys.setrecursionlimit(mod)

    def rec(i):
        if i == nq:
            return n_ABC(s)

        ans = 0
        for x in list("ABC"):
            s[qi[i]] = x
            ans += rec(i+1)

        return ans

    ans = rec(0) % mod
    return ans


def n_ABC(S):
    """3^Q を考えていないパターン がABCを求めるパターンになっていた
    """
    ans = 0
    n = len(S)
    for i in range(n):
        for j in range(i+1, n):
            for k in range(j+1, n):
                # print(i, j, k, S[i] + S[j] + S[k])
                if S[i] in ("A", "?") and S[j] in ("B", "?") and S[k] in ("C", "?"):
                    ans += 1

    return ans


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    """
    1 <= i < j < k <= |T|
    Ti = A
    Tj = B
    Tk = C
    """
    S = input()
    ans = editorial(S)

    print(ans)


def editorial(S):
    MOD = 10 ** 9 + 7
    n = len(S)
    dp = [[0] * (3+1) for _ in range(n+1)]

    for i in range(n, -1, -1):
        for j in range(3, -1, -1):
            if i == n:
                x = int(j == 3)
                # ≠3: 丸を3個つける前に最後の文字まで見終わってしまい、手遅れ
                # =3: 処理が正常終了
                dp[i][j] = x
            else:
                m1 = 1
                if S[i] == "?":
                    m1 = 3

                if j == 3:
                    # 丸は3個つけ終わったので、あとは?を置換するのみ
                    dp[i][j] = m1 * dp[i+1][j]
                else:
                    m2 = int(S[i] == "?" or S[i] == "ABC"[j])
                    # 前半:i文字目に丸をつけない場合, 後半:丸をつける場合に対応
                    dp[i][j] = m1 * dp[i+1][j] + m2 * dp[i+1][j+1]

                dp[i][j] %= MOD

    ans = dp[0][0]
    return ans


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
def main():
    """
    1 <= i < j < k <= |T|
    Ti = A
    Tj = B
    Tk = C
    """
    S = input()
    #ans = editorial(S)
    ans = TLE(S)

    print(ans)


def TLE(S):
    """文字列全列挙
    ?をすべて置き換えるパターンを作成し
    それについてABC数を算出
    """
    s = list(S)
    qi = [i for i, c in enumerate(S) if c == "?"]
    nq = len(qi)

    def rec(i):
        if i == nq:
            return n_ABC(s)

        ans = 0
        for x in list("ABC"):
            s[qi[i]] = x
            ans += rec(i+1)

        return ans

    ans = rec(0)
    return ans


def n_ABC(S):
    """3^Q を考えていないパターン がABCを求めるパターンになっていた
    """
    ans = 0
    n = len(S)
    for i in range(n):
        for j in range(i+1, n):
            for k in range(j+1, n):
                # print(i, j, k, S[i] + S[j] + S[k])
                if S[i] in ("A", "?") and S[j] in ("B", "?") and S[k] in ("C", "?"):
                    ans += 1

    return ans


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    """
    1 <= i < j < k <= |T|
    Ti = A
    Tj = B
    Tk = C
    """
    S = input()
    ans = editorial(S)

    print(ans)


def editorial(S):
    MOD = 10 ** 9 + 7
    n = len(S)
    dp = [[0] * (3+1) for _ in range(n+1)]

    for i in range(n, -1, -1):
        for j in range(3, -1, -1):
            if i == n:
                x = int(j == 3)
                # ≠3: 丸を3個つける前に最後の文字まで見終わってしまい、手遅れ
                # =3: 処理が正常終了
                dp[i][j] = x
            else:
                m1 = 1
                if S[i] == "?":
                    m1 = 3

                if j == 3:
                    # 丸は3個つけ終わったので、あとは?を置換するのみ
                    dp[i][j] = m1 * dp[i+1][j]
                else:
                    m2 = int(S[i] == "?" or S[i] == "ABC"[j])
                    # 前半:i文字目に丸をつけない場合, 後半:丸をつける場合に対応
                    dp[i][j] = m1 * dp[i+1][j] + m2 * dp[i+1][j+1]

                dp[i][j] %= MOD

    ans = dp[0][0]
    return ans


if __name__ == '__main__':
    main()