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: Accepted

Solution code:
mod=10**9+7
s=input()
n=len(s)
dp=[[0]*4 for i in range(n+1)] # A B C ABC
dp[0][0]=1
for i in range(1,n+1):
    if s[i-1]=="A":
        dp[i][0]=dp[i-1][0]
        dp[i][1]=(dp[i-1][1] + dp[i-1][0]) % mod
        dp[i][2]=dp[i-1][2]
        dp[i][3]=dp[i-1][3]
    elif s[i-1]=="B":
        dp[i][0]=dp[i-1][0]
        dp[i][1]=dp[i-1][1]
        dp[i][2]=(dp[i-1][2] + dp[i-1][1]) % mod
        dp[i][3]=dp[i-1][3]
    elif s[i-1]=="C":
        dp[i][0]=dp[i-1][0]
        dp[i][1]=dp[i-1][1]
        dp[i][2]=dp[i-1][2]
        dp[i][3]=(dp[i-1][3] + dp[i-1][2]) % mod
    else:
        dp[i][0]=dp[i-1][0]*3 % mod
        dp[i][1]=(dp[i-1][1]*3 + dp[i-1][0]) % mod
        dp[i][2]=(dp[i-1][2]*3 + dp[i-1][1]) % mod
        dp[i][3]=(dp[i-1][3]*3 + dp[i-1][2]) % mod
print(dp[-1][-1]% mod)

Submission status: Accepted

Solution code:
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 >= 0:
                p = pow(3, l + r - 1, MOD)
                aq = a * r * p
                qc = l * c * p
            if l + r - 2 >= 0:
                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()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int

def solve(S: str):
    current = [0, 0, 0]
    power = 1
    for c in S:
        if c == 'A':
            current[0] = (current[0] + power) % MOD
        elif c == 'B':
            current[1] = (current[1] + current[0]) % MOD
        elif c == 'C':
            current[2] = (current[2] + current[1]) % MOD
        else:
            current[2] = (3 * current[2] + current[1]) % MOD
            current[1] = (3 * current[1] + current[0]) % MOD
            current[0] = (3 * current[0] + power) % MOD
            power = power * 3 % MOD
    print(current[2])
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    """
    1 <= i < j < k <= |T|
    Ti = A
    Tj = B
    Tk = C
    """
    S = input()
    ans2 = dp_simple(S)
    print(ans2)


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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

MOD = 10 ** 9 + 7

def nLeftA(S, A):
    """(S[:i]の'A'の選び方, S[:i]の'?'の埋め方)"""
    l = [(0, 1)]
    for s in S:
        a, q = l[-1]
        if s == A:
            a = q + a      # S[i-1]を選ぶ + S[:i]のどれかを選ぶ
        elif s == '?':
            a = q + a * 3  # S[i-1]を選ぶ + S[:i]のどれかを選ぶ(?に3通り)
            q = q * 3
        l.append((a % MOD, q % MOD))
    return l

l = nLeftA(S, 'A')
r = nLeftA(reversed(S), 'C')
r.reverse()
r = r[1:]

n = 0
for i in range(N):
    if S[i] in 'B?':
        n += l[i][0] * r[i][0] % MOD

print(n % MOD)

Submission status: Accepted

Solution code:
S=input()
N=len(S)
MOD=10**9+7
res=0
dp = [[0]*4 for _ in range(100001)]
for i in reversed(range(N + 1)):
    for j in reversed(range(4)):
        if i == N:
            dp[i][j] = int(j == 3)
        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: Accepted

Solution code:
S = input()

dp = [[0]*(len(S)+1) for i in range(4)]
dp[0][0] = 1

for i in range(4):
    for j in range(1, len(S)+1):
        if S[j-1] == '?':
            dp[i][j] = 3 * dp[i][j-1]
        else:
            dp[i][j] = dp[i][j-1]
        if i > 0:
            if S[j-1] == '?' or 'ABC'.find(S[j-1]) == i-1:
                dp[i][j] += dp[i-1][j-1]
        dp[i][j] %= 10**9+7

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

Submission status: Accepted

Solution code:
from itertools import product

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

dp = {i: {j: 0 for j in range(3+1)} for i in range(N+1)}
for i, j in reversed(list(product(range(N+1), range(3+1)))):
    if i < N and j < 3:
        m1 = 3 if S[i] == '?' else 1
        m2 = 1 if S[i] == '?' or S[i] == ['A', 'B', 'C'][j] else 0
        dp[i][j] = m1*dp[i+1][j] + m2*dp[i+1][j+1]
    elif i < N and j == 3:
        dp[i][j] = 3*dp[i+1][j] if S[i] == '?' else dp[i+1][j]
    elif i == N and j == 3:
        dp[i][j] = 1
    dp[i][j] %= MOD
print(dp[0][0])

Submission status: Accepted

Solution code:
mod=10**9+7
s=input()
n=len(s)
Sum_A=[0]*(n+1)
Sum_B=[0]*(n+1)
Sum_C=[0]*(n+1)
Sum_q=[0]*(n+1)
for i in range(1, n+1):
    Sum_A[i]=Sum_A[i-1]
    Sum_C[i]=Sum_C[i-1]
    Sum_q[i]=Sum_q[i-1]
    if s[i-1]=='A':
        Sum_A[i]+=1
    elif s[i-1]=='C':
        Sum_C[i]+=1
    elif s[i-1]=='?':
        Sum_q[i]+=1
ans=0
def count(x, q):
    return int(x*pow(3, q, mod)+q*pow(3, (q-1), mod)) if q>0 else int(x*pow(3, q, mod))
for i in range(n):
    if s[i]=='B' or s[i]=='?':
        ans+=count(Sum_A[i], Sum_q[i])*count(Sum_C[n]-Sum_C[i+1], Sum_q[n]-Sum_q[i+1])
        ans%=mod
print(ans)

Submission status: Accepted

Solution code:
S=input()
N=len(S)
INF=1e9+7
dp=[[0]*4 for _ in range(N+1)]
dp[0][0]=1
for i in range(N):
    if S[i]=="?":
        for j in range(4):
            dp[i+1][j]+=dp[i][j]*3%INF
    else:
        for j in range(4):
            dp[i+1][j]+=dp[i][j]%INF
    if S[i]=="A" or S[i]=="?":
        dp[i+1][1]+=dp[i][0]%INF
    if S[i]=="B" or S[i]=="?":
        dp[i+1][2]+=dp[i][1]%INF
    if S[i]=="C" or S[i]=="?":
        dp[i+1][3]+=dp[i][2]%INF
print(int(dp[N][3]%INF))

Submission status: Accepted

Solution code:
import functools
import os
import sys

sys.setrecursionlimit(10000)
INF = float('inf')


def debug(fn):
    if not os.getenv('LOCAL'):
        return fn

    @functools.wraps(fn)
    def wrapper(*args, **kwargs):
        ret = fn(*args, **kwargs)
        print('DEBUG: {}({}) -> '.format(
            fn.__name__,
            ', '.join(
                list(map(str, args)) +
                ['{}={}'.format(k, str(v)) for k, v in kwargs.items()]
            )
        ), end='')
        print(ret)
        return ret

    return wrapper


# @debug
# @functools.lru_cache(maxsize=None)
# def solve(idx, abc=3):
#     """
#     S[0:idx+1] の ABC 数の数
#     abc=2 なら AB 数、abc=1 なら A 数、abc=0 なら今までのパターン数
#     :param idx:
#     :param abc:
#     :return:
#     """
#     if idx < 0:
#         return 1 if abc == 0 else 0
#     c = S[idx]
#     if 1 <= abc <= 3:
#         if c == '0ABC'[abc]:
#             return (solve(idx - 1, abc=abc) + solve(idx - 1, abc=abc - 1)) % MOD
#         elif c == '?':
#             return (solve(idx - 1, abc=abc) * 3 + solve(idx - 1, abc=abc - 1)) % MOD
#         else:
#             return (solve(idx - 1, abc=abc)) % MOD
#     elif abc == 0:
#         if c == '?':
#             return (solve(idx - 1, abc=0) * 3) % MOD
#         else:
#             return (solve(idx - 1, abc=0)) % MOD


S = input()
MOD = 10 ** 9 + 7
# print(solve(len(S) - 1) % MOD)

# ↑の DP 版
# dp[i][3]: S[0:i] の ABC 数
# dp[i][2]: S[0:i] の AB 数
# dp[i][1]: S[0:i] の A 数
# dp[i][0]: S[0:i] の組み合わせ数
# dp = np.empty((len(S) + 1, 4))
# dp[0][0] = 1
# for i in range(len(S)):
#     c = S[i]
#     if c == '?':
#         dp[i + 1][0] = dp[i][0] * 3 % MOD
#     else:
#         dp[i + 1][0] = dp[i][0] % MOD
#     for abc in [1, 2, 3]:
#         if c == '0ABC'[abc]:
#             dp[i + 1][abc] = (dp[i][abc] + dp[i][abc - 1]) % MOD
#         elif c == '?':
#             dp[i + 1][abc] = (dp[i][abc] * 3 + dp[i][abc - 1]) % MOD
#         else:
#             dp[i + 1][abc] = dp[i][abc] % MOD
#     # dp[i + 1, :] %= MOD
# print(int(dp[len(S), 3]))


# ↑の配列再利用版
dp = [0] * 4
dp[0] = 1
for i in range(len(S)):
    c = S[i]
    for abc in [3, 2, 1]:
        if c == '0ABC'[abc]:
            dp[abc] = (dp[abc] + dp[abc - 1]) % MOD
        elif c == '?':
            dp[abc] = (dp[abc] * 3 + dp[abc - 1]) % MOD
    if c == '?':
        dp[0] = dp[0] * 3 % MOD
print(int(dp[3]))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int


def solve(S: str):
    dp = [[0 for j in range(4)] for i in range(len(S) + 1)]
    STR = "XABC"
    dp[0][0] = 1
    for i in range(len(S)):
        c = S[i]
        for j in range(4):
            next = dp[i][j]
            if c == "?":
                next *= 3
                if j > 0:
                    next += dp[i][j-1]
            if STR[j] == c:  # 選んだ文字列が次選ぶべき文字列だったら
                next += dp[i][j-1]
            dp[i+1][j] = next % MOD
    #  print(dp)
    print(dp[len(S)][3])
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

dp = [1,0,0,0]


for s in S:
    if s == 'A':
        dp[1] += dp[0]
    elif s == 'B':
        dp[2] += dp[1]
    elif s == 'C':
        dp[3] += dp[2]
    elif s == '?':
        dp[3] *= 3
        dp[3] += dp[2]
        dp[2] *= 3
        dp[2] += dp[1]
        dp[1] *= 3
        dp[1] += dp[0]
        dp[0] *= 3

    for i in range(4):
        dp[i] %= MOD


print(dp[3])

Submission status: Accepted

Solution code:
s=input()
a=[1,0,0,0]
for i in s:
    if i=="A": a[1]+=a[0]
    elif i=="B": a[2]+=a[1]
    elif i=="C": a[3]+=a[2]
    else: a=[ a[0]*3 ] + [ a[j+1]*3+a[j] for j in range(3) ]

    a=[a[i]%1000000007 for i in range(4)]
print(a[3])

Submission status: Accepted

Solution code:
s=input()

a=[1,0,0,0]

for i in range(len(s)):
    c=s[i]
    if c=="A":
        a[1]+=a[0]
    elif c=="B":
        a[2]+=a[1]
    elif c=="C":
        a[3]+=a[2]
    else:
        a=[ a[0]*3 ] + [ a[j+1]*3+a[j] for j in range(3) ]

    a=[a[i]%1000000007 for i in range(4)]

print(a[3])

Submission status: Accepted

Solution code:
s=input()

a=[1,0,0,0]

for i in range(len(s)):
    if s[i]=="A":
        a[1]+=a[0]
    elif s[i]=="B":
        a[2]+=a[1]
    elif s[i]=="C":
        a[3]+=a[2]
    else:
        a=[ a[0]*3 ] + [ a[j]*3+a[j-1] for j in range(1,4) ]

    a=[a[i]%1000000007 for i in range(4)]

print(a[3])

Submission status: Accepted

Solution code:
s=input()

a=[1,0,0,0]

for i in range(len(s)):
    c=s[i]
    if c=="A":
        a[1]+=a[0]
    elif c=="B":
        a[2]+=a[1]
    elif c=="C":
        a[3]+=a[2]
    elif c=="?":
        a=[ a[0]*3 ] + [ a[j]*3+a[j-1] for j in range(1,4) ]

    a=[a[i]%1000000007 for i in range(4)]
    
print(a[3])

Submission status: Accepted

Solution code:
s=input()

a=[1,0,0,0]

for i in range(len(s)):
    c=s[i]
    if c=="A":
        a[1]=(a[1]+a[0])%1000000007
    elif c=="B":
        a[2]=(a[2]+a[1])%1000000007
    elif c=="C":
        a[3]=(a[3]+a[2])%1000000007
    elif c=="?":
        tmp=[a[i] for i in range(4)]
        a[0]=tmp[0]*3
        for j in range(3):
            a[j+1]=tmp[j+1]*3+tmp[j]
        a=list(map(lambda x: x%1000000007,a))

    
print(a[3]%1000000007)

Submission status: Accepted

Solution code:
s=input()

a=[1,0,0,0]

for i in range(len(s)):
    c=s[i]
    if c=="A":
        a[1]+=a[0]
    elif c=="B":
        a[2]+=a[1]
    elif c=="C":
        a[3]+=a[2]
    elif c=="?":
        tmp=[a[i] for i in range(4)]
        a[0]=tmp[0]*3
        for j in range(3):
            a[j+1]=tmp[j+1]*3+tmp[j]

    a=[a[i]%1000000007 for i in range(4)]

print(a[3])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import itertools
import collections
import functools
import math
from queue import Queue
INF = float("inf")

MOD = 1000000007  # type: int

d = {}


def thpow(q):
    if q < 0:
        return 0
    if q == 0:
        return 1
    if q in d:
        return d[q]
    else:
        d[q] = (3*thpow(q-1)) % MOD
        return d[q]


def solve(S: str):
    dp = [0, 0, 0]
    q = 0
    for ch in S:
        a, b, c = dp
        if ch == "A":
            dp = [(a+thpow(q)) % MOD, b, c]
        elif ch == "B":
            dp = [a, (b+a) % MOD, c]
        elif ch == "C":
            dp = [a, b, (c+b) % MOD]
        elif ch == "?":
            dp = [((a*3 % MOD)+thpow(q)) % MOD,
                  ((b*3) % MOD+a) % MOD,
                  ((c*3)+b) % MOD]
            q += 1
        # print(dp)
    # print(dp)

    # print(d)
    print(dp[2])
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

mod=10**9+7

all_strings=1
a=0
ab=0
abc=0

for i,s in enumerate(S):
	if s =="A":
		a+=all_strings
	elif s=="B":
		ab+=a
	elif s=="C":
		abc+=ab
	elif s=="?":
		abc*=3
		abc+=ab
		ab*=3
		ab+=a
		a*=3
		a+=all_strings
	if s == "?":
		all_strings*=3

	all_strings%=mod
	a%=mod
	ab%=mod
	abc%=mod

print abc

Submission status: Accepted

Solution code:
s=input()
d=[[0]*(len(s)+1)for i in range(4)]
d[3][-1]+=1
e="ABC"
for i in range(len(s)-1,-1,-1):
    for j in range(3,-1,-1):
        if j==3:
            if s[i]=="?":
                d[3][i]=(d[3][i+1]*3)%(10**9+7)
            else:
                d[3][i]=d[3][i+1]%(10**9+7)
        else:
            if s[i]=="?":
                d[j][i]=(3*d[j][i+1]+d[j+1][i+1])%(10**9+7)
            else:
                d[j][i]=d[j][i+1]
                if e[j]==s[i]:
                    d[j][i]=(d[j][i]+d[j+1][i])%(10**9+7)
print(d[0][0]%(10**9+7))

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    def dfs(i,k):
        if i == d:
            l.append(k)
        else:
            for j in range(2):
                dfs(i+1,k+[j])
    d,g = LI()
    p = LIR(d)
    ans = float("inf")
    l = []
    dfs(0,[])
    for k in l:
        m = 0
        o = 0
        q = [[p[i][0],p[i][1]] for i in range(d)]
        for i in range(d):
            if k[i]:
                o += q[i][0]
                m += q[i][0]*(i+1)*100+q[i][1]
                q[i][0] = 0
        while m < g:
            for i in range(d)[::-1]:
                for j in range(q[i][0]):
                    m += (i+1)*100
                    o += 1
                    if m >= g:break
                if m >= g:break
        ans = min(ans,o)
    print(ans)
#D
def D():
    s = S()
    n = len(s)
    dp = [[0,0,0,0] for i in range(n+1)]
    dp[0][0] = 1
    for i in range(n):
        if s[i] == "?":
            dp[i+1] = [3*dp[i][0]%mod,3*dp[i][1]%mod,3*dp[i][2]%mod,3*dp[i][3]%mod]
        else:
            dp[i+1] = [dp[i][0],dp[i][1],dp[i][2],dp[i][3]]
        if s[i] == "A":
            dp[i+1][1] += dp[i][0]
            dp[i+1][1] %= mod
        elif s[i] == "B":
            dp[i+1][2] += dp[i][1]
            dp[i+1][2] %= mod
        elif s[i] == "C":
            dp[i+1][3] += dp[i][2]
            dp[i+1][3] %= mod
        else:
            dp[i+1][1] += dp[i][0]
            dp[i+1][2] += dp[i][1]
            dp[i+1][3] += dp[i][2]
            dp[i+1][1] %= mod
            dp[i+1][2] %= mod
            dp[i+1][3] %= mod
    print(dp[n][3])
#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    D()

Submission status: Accepted

Solution code:
def main():
    s = input()
    N = len(s)

    dp = [[-1]*4 for n in range(N)]
    for i in reversed(list(range(N))):
        for j in range(4):
            if i == N-1:
                if j == 3:
                    dp[i][j] = 3 if s[i] == "?" else 1
                elif j == 2:
                    dp[i][j] = 1 if s[i] in ("?", "C") else 0
                else:
                    dp[i][j] = 0
            else:
                if j == 3:
                    dp[i][j] = (3 if s[i] == "?" else 1) * dp[i+1][j]
                elif s[i] == "?":
                    dp[i][j] = 3 * dp[i+1][j] + dp[i+1][j+1]
                elif s[i] == "ABC"[j]:
                    dp[i][j] = dp[i+1][j+1] + dp[i+1][j]
                else:
                    dp[i][j] = dp[i+1][j]
            dp[i][j] %= 10 ** 9 + 7
    print(dp[0][0])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
S = input()

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

mod = 10**9+7

for i in range(len(S)):
    for j in range(4):
        if S[i] != '?':
            dp[i+1][j] += dp[i][j]
            dp[i+1][j] %= mod
        else:
            dp[i+1][j] += dp[i][j]*3
            dp[i+1][j] %= mod

    if S[i] == 'A' or S[i] == '?':
        dp[i+1][1] += dp[i][0]
        dp[i+1][1] %= mod

    if S[i] == 'B' or S[i] == '?':
        dp[i+1][2] += dp[i][1]
        dp[i+1][2] %= mod

    if S[i] == 'C' or S[i] == '?':
        dp[i+1][3] += dp[i][2]
        dp[i+1][3] %= mod

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

Submission status: Accepted

Solution code:
S = str(input())
mod = 10 ** 9 + 7
L = len(S)
d = "ABC".index
dp = [[0 for _ in range(4)] for _ in range(L+1)]
dp[0][0] = 1
for i in range(len(S)):
    if S[i] == '?':
        dp[i+1][0] = dp[i][0] * 3
        dp[i+1][1] = dp[i][1] * 3 + dp[i][0]
        dp[i+1][2] = dp[i][2] * 3 + dp[i][1]
        dp[i+1][3] = dp[i][3] * 3 + dp[i][2]
        for j in range(4):
            dp[i+1][j] %= mod
    else:
        dp[i+1] = dp[i]
        j = d(S[i])
        dp[i+1][j+1] += dp[i][j] % mod

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

Submission status: Accepted

Solution code:
S = str(input())
mod = 10 ** 9 + 7
L = len(S)
d = "ABC".index
dp = [0 for _ in range(4)]
dp[0] = 1
for i in range(len(S)):
    if S[i] == '?':
        dp = [dp[0]*3, dp[1]*3+dp[0], dp[2]*3+dp[1], dp[3]*3+dp[2]]
        for j in range(4):
            dp[j] %= mod
    else:
        j = d(S[i])
        dp[j+1] += dp[j] % mod

print(dp[-1]%mod)

Submission status: Accepted

Solution code:
s = input()

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

for i, c in enumerate(s):
  # use c
  if c == "A" or c == "?":
    dp[1][i+1] = dp[0][i]
  if c == "B" or c == "?":
    dp[2][i+1] = dp[1][i]
  if c == "C" or c == "?":
    dp[3][i+1] = dp[2][i]
  # not use c
  for j in range(4):
    if c == "?":
      dp[j][i+1] += dp[j][i] * 3  
    else:
      dp[j][i+1] += dp[j][i]
    dp[j][i+1] %= 10**9+7
print(dp[-1][-1])

Submission status: Accepted

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

dp[0][3] = 1
mod = 1000000007

for i in range(1,len(s)+1):
  if s[i-1] == "A":
    dp[i][0] += dp[i-1][0] + dp[i-1][3]
    dp[i][1] += dp[i-1][1]
    dp[i][2] += dp[i-1][2]
    dp[i][3] += dp[i-1][3]
    
  elif s[i-1] == "B":
    dp[i][0] += dp[i-1][0]
    dp[i][1] += dp[i-1][1] + dp[i-1][0]
    dp[i][2] += dp[i-1][2]
    dp[i][3] += dp[i-1][3]
    
  elif s[i-1] == "C":
    dp[i][0] += dp[i-1][0]
    dp[i][1] += dp[i-1][1]
    dp[i][2] += dp[i-1][2] + dp[i-1][1]
    dp[i][3] += dp[i-1][3]
    
  else:
    dp[i][0] += dp[i-1][0]*3 + dp[i-1][3]
    dp[i][1] += dp[i-1][1]*3 + dp[i-1][0]
    dp[i][2] += dp[i-1][2]*3 + dp[i-1][1]
    dp[i][3] += dp[i-1][3]*3
    
  dp[i][0] %= mod
  dp[i][1] %= mod
  dp[i][2] %= mod
  dp[i][3] %= mod

print(dp[len(s)][2])
#print(dp)

Submission status: Accepted

Solution code:
mod = 1000000007

S = input()
n = 1
a = 0
ab = 0
abc = 0
for s in S:
    if s in "A":
        a += n
    if s in "B":
        ab += a
    if s == "C":
        abc += ab
    if s in "?":
        n, a, ab, abc = 3 * n, 3 * a + n, 3 * ab + a, 3 * abc + ab
    n %= mod
    a %= mod
    ab %= mod
    abc %= mod

print(abc % mod)

Submission status: Accepted

Solution code:
a=[1]+[0]*4
m=10**9+7
for s in input():
 i=ord(s)-64
 if i>0:a[i]+=a[i-1]
 else:a=[a[i]*3%m+a[i-1]for i in range(4)]+[0]
print(a[3]%m)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
X = list(input())

q_num = X.count("?")
a_num = 0
c_num = X.count("C")
left_q_num = 0
right_q_num = q_num
ans = 0
len_x = len(X)
q_dict = []
b_ans = 0
q_ans = 0
q_dict = {}
q_dict[q_num - 1] = (3 ** (q_num - 1)) % (10 ** 9 + 7)
q_dict[q_num - 2] = (3 ** (q_num - 2)) % (10 ** 9 + 7)
q_dict[q_num - 3] = (3 ** (q_num - 3)) % (10 ** 9 + 7)
q_dict[q_num] = (3 ** (q_num)) % (10 ** 9 + 7)

if X[0] == "?":
    right_q_num -= 1
elif X[0] == "C":
    c_num -= 1
for i, x in enumerate(X):
    if x == "B" or x == "?":
        ans += (a_num * c_num)  * (q_dict[(left_q_num + right_q_num)])
        if left_q_num + right_q_num >= 2:
            ans += (right_q_num * left_q_num  + 3*(left_q_num * c_num) + 3*(right_q_num * a_num)) * (q_dict[(left_q_num + right_q_num - 2)])
        elif left_q_num + right_q_num == 1:
            ans += ((left_q_num * c_num) + (right_q_num * a_num)) * (q_dict[(left_q_num + right_q_num - 1)])
        ans = ans % (10 ** 9 + 7)
    if  i == len_x - 1:
        break
    if x == "A":
        a_num += 1
    elif x == "?":
        left_q_num += 1
    if X[i + 1] == "C":
        c_num -= 1
    elif X[i + 1] == "?":
        right_q_num -= 1

print(ans % (10 ** 9 + 7))

Submission status: Accepted

Solution code:
s=input()

n=len(s)
dc=dict()
dc['A']=0
dc['B']=1
dc['C']=2
dc['?']=3
dp=[[0 for i in range(4)] for j in range(n+1)]
dp[0][0]=1
mo=10**9+7
for i in range(n):
    for t in range(4):
        ch=s[i]
        m = 1 if dc[ch]==t-1 or dc[ch]==3 else 0
        if t!=0:
            dp[i+1][t]+=(dp[i][t-1]*m)%mo
        dp[i+1][t]+=(dp[i][t]*(3 if dc[ch]==3 else 1))%mo

ans=dp[n][3]
print(ans%mo)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
#def input():
#    return sys.stdin.readline()[:-1]

'''
n=int(input())
for i in range(n):
    a[i]=int(input())
    a[i],b[i]=map(int,input().split())
a=[int(x) for x in input().split()]
n,m=map(int,input.split())
from operator import itemgetter
a = [(1, "c", 1), (1, "b", 3), (2, "a", 0), (1, "a", 2)]
print(sorted(a))  # 0 番目の要素でソート、先頭の要素が同じなら 1 番目以降の要素も見る
print(sorted(a, key=itemgetter(0)))  # 0 番目の要素だけでソート
print(sorted(a, key=itemgetter(0, 2)))  # 0 番目と 2 番目の要素でソート
print(sorted(a, key=lambda x: x[0] * x[2]))  # 0 番目の要素 * 2 番目の要素でソート
print(sorted(a, reverse=True))  # 降順にソート
a.sort()  # 破壊的にソート、sorted() よりも高速
try: # エラーキャッチ list index out of range
    for i in range():
        k=b[i]
except IndexError as e:
    print(i)
'''

test_data1 = '''\
A??C
'''

test_data2 = '''\
ACACAC
'''

test_data3 = '''\
????C?????B??????A???????
'''

test_data4 = '''\
?AC?AC
'''
td_num=3

def GetTestData(index):
    if index==1:
        return test_data1
    if index==2:
        return test_data2
    if index==3:
        return test_data3
    if index==4:
        return test_data4
    
if False:
    with open("../test.txt", mode='w') as f:
        f.write(GetTestData(td_num))
    with open("../test.txt") as f:
        # Start Input code ---------------------------------------
        s=f.readline()
        # End Input code ---------------------------------------
else:
    # Start Input code ---------------------------------------
    s=input()
    # End Input code ---------------------------------------
n=len(s)
dc=dict()
dc['A']=0
dc['B']=1
dc['C']=2
dc['?']=3
dp=[[0 for i in range(4)] for j in range(n+1)]
dp[0][0]=1
mo=10**9+7
for i in range(n):
    for t in range(4):
        ch=s[i]
        if dc[ch]==t-1 or dc[ch]==3:
            m=1
        else:
            m=0
        if t!=0:
            dp[i+1][t]+=(dp[i][t-1]*m)%mo
        dp[i+1][t]+=(dp[i][t]*max(int(dc[ch]/3)*3,1))%mo
#print(dp)
ans=dp[n][3]

#mo=2291979612924+1
#print(ans,'n,s=',n,s,'lc(a,w)=',lc_a,lc_w,'rc(c,w)=',rc_c,rc_w)
    #print('i,ans',i,ans)
#print(ans,'n,s=',n,s,'lc(a,w)=',lc_a,lc_w,'rc(c,w)=',rc_c,rc_w)
print(ans%mo)
#ans=count(0)+2^(count(n)-1)