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:
S = input().replace("A","1").replace("B","2").replace("C","3").replace("?","0")
#while S[0:1] == "B" or S[0:1] == "C":
#    S = S[1:]
#while S[-1:] == "A" or S[-1:] == "B":
#    S = S[:-1]

# ABC
# AB?,A?C,?BC
# A??,?B?,??C
# ???
front = [0,0,0,0]
back = []
for i in range(4):
    back.append(S.count(str(i)))
Q = back[0]
q3s = [(3**t)%1000000007 for t in [Q-3,Q-2,Q-1,Q]]

ans = 0

for i in range(len(S)):
    num = S[i:i+1]
    back[int(num)] -= 1
    if num == "2":
        ans += front[1]*back[3]*q3s[3] #ABC
        ans += front[1]*back[0]*q3s[2] #AB?
        ans += front[0]*back[3]*q3s[2] #?BC
        ans += front[0]*back[0]*q3s[1] #?B?
    elif num == "0":
        ans += front[1]*back[3]*q3s[2] #A?C
        ans += front[1]*back[0]*q3s[1] #A??
        ans += front[0]*back[3]*q3s[1] #??C
        ans += front[0]*back[0]*q3s[0] #???
    front[int(num)] += 1
    ans = int(ans)%1000000007

print(ans)

Submission status: Accepted

Solution code:
def ary(r, c, v): return [[v for _ in range(c)] for _ in range(r)]

s = input()
ls = len(s)
dp = ary(ls + 1, 4, 0)
dp[0][0] = 1
mod = 10 ** 9 + 7

for i in range(1, ls + 1):
    for j in range(4):
        #'?'のとき'ABC'の3通りに分岐させ、いずれも取らないので3倍
        dp[i][j] += dp[i - 1][j] * (3 if s[i - 1] == '?' else 1)

       #ほしい文字に変えた場合　または　ほしい文字の場合で取ったとき
        if j > 0:
            if s[i - 1] == '?' or s[i - 1] == 'ABC'[j - 1]:
                dp[i][j] += dp[i - 1][j - 1]
        dp[i][j] %= mod
print(dp[ls][3])

Submission status: Accepted

Solution code:
from itertools import accumulate as ac
s=input()
n=len(s)
mod=int(1e9)+7

*aca,=ac([0]+[1 if i=="A" else 0 for i in s])
*acc,=ac([0]+[1 if i=="C" else 0 for i in s])
*acq,=ac([0]+[1 if i=="?" else 0 for i in s])

v=0
for i in range(1,n-1):
  if s[i]=="B" or s[i]=="?":
    a=aca[i]
    l=acq[i]
    c=acc[n]-acc[i+1]
    r=acq[n]-acq[i+1]
    v+=(a*c*pow(3,l+r,mod))
    if l+r-1>=0:
      v+=(a*r*pow(3,l+r-1,mod))+(l*c*pow(3,l+r-1,mod))
    if l+r-2>=0:
      v+=(l*r*pow(3,l+r-2,mod))
    v%=mod
print(v)

Submission status: Accepted

Solution code:
s=input()
abc="ABCD"
n=len(s)
mod=10**9+7
dp=[[0]*4 for i in range(n+1)]
dp[n][3]=1
for i in range(n-1,-1,-1):
    for j in range(4):
        if s[i]=='?' :
            if j==3:
                dp[i][j]=3*dp[i+1][j]
            else :
                dp[i][j]=3*dp[i+1][j]+dp[i+1][j+1]
        elif s[i]==abc[j]:
            if j!=3:
                dp[i][j]=dp[i+1][j]+dp[i+1][j+1]
            else :
                dp[i][j]=dp[i+1][j]
        else :
            dp[i][j]=dp[i+1][j]
        dp[i][j]%=mod
print(dp[0][0])

Submission status: Accepted

Solution code:
S = input()
MOD = 10**9+7
A = 0
C = S.count('C')
Q = 0
QMAX = S.count('?')

ans = 0
# <ABCとして選んだ場所>* 3**(残された_の数)
b = 3 ** (QMAX-2) % MOD
q = 3 ** (QMAX-3) % MOD

for s in S:
    if s == 'A':
        A += 1
    elif s == 'C':
        C -= 1
    elif s == 'B':
        ans = (ans + (3*A+Q) * b * (3*C+QMAX-Q))%MOD
    else:
        ans = (ans + (3*A+Q) * q * (3*C+QMAX-Q-1))%MOD
        Q += 1

print(int(ans))

Submission status: Accepted

Solution code:
M = 10**9 + 7
N, A, AB, ABC = 1, 0, 0, 0
idx = {'A': 1, 'B': 2, 'C': 3}
for c in input():
    if c == '?':
        N, A, AB, ABC = (N*3)%M, (A*3+N)%M, (AB*3+A)%M, (ABC*3+AB)%M
    elif c == 'A':
        A = (A+N)%M
    elif c == 'B':
        AB = (AB+A)%M
    else:
        ABC = (ABC+AB)%M
print(ABC)

Submission status: Accepted

Solution code:
M = 10**9 + 7
N, A, AB, ABC = 1, 0, 0, 0
idx = {'A': 1, 'B': 2, 'C': 3}
for c in input():
    if c == '?':
        ABC = (ABC * 3 + AB) % M
        AB = (AB * 3 + A) % M
        A = (A * 3 + N) % M
        N = (N * 3) % M
    elif c == 'A':
        A += N
    elif c == 'B':
        AB += A
    else:
        ABC += AB
print(ABC % M)

Submission status: Accepted

Solution code:
M = 10**9 + 7
N, A, AB, ABC = 1, 0, 0, 0
idx = {'A': 1, 'B': 2, 'C': 3}
for c in input():
    if c == '?':
        N, A, AB, ABC = (N * 3) % M, (A * 3 + N) % M, (AB * 3 + A) % M, (ABC * 3 + AB) % M
    elif c == 'A':
        A += N
    elif c == 'B':
        AB += A
    else:
        ABC += AB
print(ABC % M)

Submission status: Accepted

Solution code:
M = 10**9 + 7
N, A, AB, ABC = 1, 0, 0, 0
idx = {'A': 1, 'B': 2, 'C': 3}
for c in input():
    if c == '?':
        N, A, AB, ABC = (N * 3) % M, (A * 3 + N) % M, (AB * 3 + A) % M, (ABC * 3 + AB) % M
    else:
        dp = [N, A, AB, ABC]
        dp[idx[c]] += dp[idx[c] - 1]
        N, A, AB, ABC = dp
print(ABC % M)

Submission status: Accepted

Solution code:
M = 10**9 + 7
dp = [0] * 4
dp[0] = 1
idx = {'A': 1, 'B': 2, 'C': 3}
m = lambda x: x % M if x > M else x
for c in input():
    if c == '?':
        N, A, AB, ABC = dp
        dp = [m(N * 3), m(A * 3 + N), m(AB * 3 + A), m(ABC * 3 + AB)]
    else:
        dp[idx[c]] += dp[idx[c] - 1]
print(dp[3] % M)

Submission status: Accepted

Solution code:
M = 10**9 + 7
dp = [0] * 4
dp[0] = 1
idx = {'A': 1, 'B': 2, 'C': 3}
for c in input():
    if c == '?':
        N, A, AB, ABC = dp
        dp = [(N * 3) % M, (A * 3 + N) % M, (AB * 3 + A) % M, (ABC * 3 + AB) % M]
    else:
        dp[idx[c]] += dp[idx[c] - 1]
        dp[idx[c]] %= M
print(dp[3] % M)

Submission status: Accepted

Solution code:
M = 10**9 + 7
dp = [0] * 4
dp[0] = 1
idx = {'A': 1, 'B': 2, 'C': 3}
for c in input():
    if c == '?':
        N, A, AB, ABC = dp
        dp = [(N * 3) % M, (A * 3 + N) % M, (AB * 3 + A) % M, (ABC * 3 + AB) % M]
    else:
        dp[idx[c]] += dp[idx[c] - 1]
print(dp[3] % M)

Submission status: Accepted

Solution code:
mod = 1000000007
s = input()
n = len(s)
c = [0 for i in range(n)] #c[i]=(s[i:]に存在する'C'の個数)
d = [0 for i in range(n)] #d[i]=(s[i:]に存在する'?'の個数) これ以降も、変数名に現れる'd'は'?'に対応する
bc = [0 for i in range(n)] #bc[i]=(s[i:]に存在する"BC"の個数)
bd = [0 for i in range(n)] #上と同様、"B?"
dc = [0 for i in range(n)] #"?C"
dd = [0 for i in range(n)] #"??"


if s[-1] == "C":
    c[-1] = 1
if s[-1] == "?":
    d[-1] = 1
for i in range(-2, -n-1, -1): #後ろから2文字目～先頭を見る
    c[i] = c[i+1]
    d[i] = d[i+1]
    bc[i] = bc[i+1]
    bd[i] = bd[i+1]
    dc[i] = dc[i+1]
    dd[i] = dd[i+1]
    if s[i] == "B":
        bc[i] += c[i+1] #今見つけた'B'と、今までに見つけた'C'で"BC"をつくる。後に続くのも同様。
        bd[i] += d[i+1]
    elif s[i] == "C":
        c[i] += 1
    elif s[i] == "?":
        d[i] += 1
        dc[i] += c[i+1]
        dd[i] += d[i+1]

# d[0]は'?'の総数で、問題文中のQに対応する
if d[0] == 0: #d[0]が3に満たないときはバグるので別扱い
    mul = [0, 0, 0, 1]
elif d[0] == 1:
    mul = [0, 0, 1, 3]
elif d[0] == 2:
    mul = [0, 1, 3, 9]
else:
    mul = [1, 1, 1, 1] #以下の処理でmul=[3**(Q-3),3**(Q-2),3**(Q-1),3**Q]となる
    for i in range(d[0]-3): #3をQ-3乗
        mul[0] *= 3
        mul[0] %= mod
    for i in range(3): #あとは順に3倍
        mul[i+1] = (mul[i]*3) % mod

res = 0
for i in range(n-2): #一文字ずつ見ていって足し上げる
    if s[i] == "A":
        res += bc[i+1]*mul[3]+(dc[i+1]+bd[i+1])*mul[2]+dd[i+1]*mul[1]
    if s[i] == "?":
        res += bc[i+1]*mul[2]+(dc[i+1]+bd[i+1])*mul[1]+dd[i+1]*mul[0]
    res %= 1000000007
print(res)

Submission status: Accepted

Solution code:
mod = 1000000007
s = input()
n = len(s)
c = [0 for i in range(n)]
d = [0 for i in range(n)]
bc = [0 for i in range(n)]
bd = [0 for i in range(n)]
dc = [0 for i in range(n)]
dd = [0 for i in range(n)]


if s[-1] == "C":
    c[-1] = 1
if s[-1] == "?":
    d[-1] = 1
for i in range(-2, -n-1, -1):
    c[i] = c[i+1]
    d[i] = d[i+1]
    bc[i] = bc[i+1]
    bd[i] = bd[i+1]
    dc[i] = dc[i+1]
    dd[i] = dd[i+1]
    if s[i] == "B":
        bc[i] += c[i+1]
        bd[i] += d[i+1]
    elif s[i] == "C":
        c[i] += 1
    elif s[i] == "?":
        d[i] += 1
        dc[i] += c[i+1]
        dd[i] += d[i+1]


if d[0] == 0:
    mul = [0, 0, 0, 1]
elif d[0] == 1:
    mul = [0, 0, 1, 3]
elif d[0] == 2:
    mul = [0, 1, 3, 9]
else:
    mul = [1, 1, 1, 1]
    for i in range(d[0]-3):
        mul[0] *= 3
        mul[0] %= mod
    for i in range(3):
        mul[i+1] = (mul[i]*3) % mod

res = 0
for i in range(n-2):
    if s[i] == "A":
        res += bc[i+1]*mul[3]+(dc[i+1]+bd[i+1])*mul[2]+dd[i+1]*mul[1]
    if s[i] == "?":
        res += bc[i+1]*mul[2]+(dc[i+1]+bd[i+1])*mul[1]+dd[i+1]*mul[0]
    res %= 1000000007
print(res)

Submission status: Accepted

Solution code:
mod = 1000000007
s = input()[-1::-1] #入力のタイミングで文字列を反転してしまう
n = len(s)
dp = [[0]*4 for i in range(n+1)]
dp[0][0] = 1 #0文字から0文字選ぶ方法だけ1で初期化。他は0。
for i in range(n):
    for j in range(4):
        dp[i+1][j] = dp[i][j] % mod #とりあえず一つ前の値はコピー
    if s[i] == "?":
        dp[i+1][0] += (2*dp[i][0]) % mod #コピーしたものに2倍を足せば合計3倍。0だけは一項少ないので別扱い。
        for j in range(1, 4):
            dp[i+1][j] += (2*dp[i][j]+dp[i][j-1]) % mod
    else:
        index = "CBA".find(s[i])+1 #indexを1-originにするために1を加えている
        dp[i+1][index] += dp[i][index-1] % mod
print(dp[n][3] % mod)

Submission status: Accepted

Solution code:
def main():
    S = input()
    mod = 10**9+7
    dp0 = 1
    dp1 = 0
    dp2 = 0
    dp3 = 0

    for s in S:
        tmp0 = dp0
        tmp1 = dp1
        tmp2 = dp2
        tmp3 = dp3

        if s == '?':
            tmp0 += 2*dp0 % mod
            tmp1 += (2*dp1 + dp0) % mod
            tmp2 += (2*dp2 + dp1) % mod
            tmp3 += (2*dp3 + dp2) % mod
        elif s == 'A':
            tmp1 += dp0 % mod
        elif s == 'B':
            tmp2 += dp1 % mod
        elif s == 'C':
            tmp3 += dp2 % mod
        dp0 = tmp0
        dp1 = tmp1
        dp2 = tmp2
        dp3 = tmp3

    print(dp3%(mod))
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
S = input()
l = len(S)
A,B,C,q = [0]*l,[0]*l,[0]*l,[0]*l
inf = 1000000007
for i in range(l):
    if S[i] == 'A':
        A[i] = 1
    elif S[i] == 'B':
        B[i] = 1
    elif S[i] == 'C':
        C[i] = 1
    else:
        q[i] = 1

for i in range(l-1):
    A[i+1] += A[i]
    B[i+1] += B[i]
    C[i+1] += C[i]
    q[i+1] += q[i]

ans = 0
for i in range(1,l-1):
    if S[i] == 'B':
        ans += (A[i-1]) * (C[-1]-C[i]) * pow(3,q[-1],inf)
        ans %= inf
        if q[-1] >= 1:
            ans += (q[i-1]) * (C[-1] - C[i]) * pow(3,q[-1]-1,inf)
            ans %= inf
            ans += (A[i-1]) * (q[-1] - q[i]) * pow(3,q[-1]-1,inf)
            ans %= inf
        if q[-1] >= 2:
            ans += (q[i-1]) * (q[-1] - q[i]) * pow(3,q[-1]-2,inf)
            ans %= inf

    elif S[i] == '?':
        ans += (A[i-1]) * (C[-1]-C[i]) * pow(3,q[-1]-1,inf)
        ans %= inf
        if q[-1] >= 2:
            ans += (q[i-1]) * (C[-1] - C[i]) * pow(3,q[-1]-2,inf)
            ans %= inf
            ans += (A[i-1]) * (q[-1] - q[i]) * pow(3,q[-1]-2,inf)
            ans %= inf
        if q[-1] >= 3:
            ans += (q[i-1]) * (q[-1] - q[i]) * pow(3,q[-1]-3,inf)
            ans %= inf

print(ans%inf)

Submission status: Accepted

Solution code:
S = input()
m = 10**9+7
d = "ABC".index

dp = [0]*4
dp[0] = 1

for c in S:
	if(c == '?'):
		dp = [(3*dp[0])%m, (3*dp[1]+dp[0])%m, (3*dp[2]+dp[1])%m, (3*dp[3]+dp[2])%m]
	else:
		i = d(c)
		dp[i+1] += dp[i]%m 
print(dp[3]%m)

Submission status: Accepted

Solution code:
S = input()
dp = [[0,0,0,0] for k in range(len(S)+1)]
dp[0][0] = 1
m = 1000000007

for k in range(len(S)):
    if S[k] == "?":
        dp[k+1][0] += (dp[k][0]*3)%m
        dp[k+1][1] += (dp[k][1]*3)%m
        dp[k+1][2] += (dp[k][2]*3)%m
        dp[k+1][3] += (dp[k][3]*3)%m
    else:
        dp[k+1][0] += dp[k][0]
        dp[k+1][1] += dp[k][1]
        dp[k+1][2] += dp[k][2]
        dp[k+1][3] += dp[k][3]
    if S[k] == "A" or S[k] == "?":
        dp[k+1][1] += dp[k][0]
    if S[k] == "B" or S[k] == "?":
        dp[k+1][2] += dp[k][1]
    if S[k] == "C" or S[k] == "?":
        dp[k+1][3] += dp[k][2]
    dp[k+1][0] %= m
    dp[k+1][1] %= m
    dp[k+1][2] %= m
    dp[k+1][3] %= m

print(dp[-1][3])

Submission status: Accepted

Solution code:
s = input()
q = s.count('?')
res = 0
mod = 10**9+7

""" 前処理 """
# ある地点(pivot)まで(から)のA(C),?の数
bp_A,bp_Q,ap_C,ap_Q = [0],[0],[0],[0]
for c in s:
    bp_A.append(bp_A[-1]+(c=='A'))
    bp_Q.append(bp_Q[-1]+(c=='?'))
for c in s[::-1]:
    ap_C.append(ap_C[-1]+(c=='C'))
    ap_Q.append(ap_Q[-1]+(c=='?'))
# 3の累乗のmod
three = [3]
i = 1
while i<q:
    three.append((three[-1]**2)%mod)
    i *= 2
""" ここまで """

# 3の累乗
def pow(num):
    if num<0:
        return 0
    elif num==0:
        return 1
    else:
        ans = 1
        for i,j in enumerate(three):
            if num&(1<<i):
                ans *= j
                ans %= mod
        return ans

for pivot in range(1,len(s)-1):
    if s[pivot]=='B' or s[pivot]=='?':
        tmp = q - (s[pivot]=='?')
        s1_a,s1_q = bp_A[pivot],bp_Q[pivot]
        s2_c,s2_q = ap_C[-pivot-2],ap_Q[-pivot-2]
        res += (s1_a*s2_c)%mod * pow(tmp)
        res += (s1_a*s2_q)%mod * pow(tmp-1)
        res += (s1_q*s2_c)%mod * pow(tmp-1)
        res += (s1_q*s2_q)%mod * pow(tmp-2)

print(int(res)%mod)

Submission status: Accepted

Solution code:
s = input()
dp = [0 for _ in range(0,4)]
dp[3] = 1
dp[0] = 0
dp[1] = 0
dp[2] = 0
abc = "ABC".index
mod = 10**9 + 7
for i in range(len(s)-1,-1,-1):
    if s[i] == "?":
        dp = [
        (dp[0]*3+ dp[1])%mod
        ,(dp[1]*3+ dp[2])%mod
        ,(dp[2]*3 + dp[3])%mod
        ,(dp[3]*3)%mod
        ]
    else:
        num = abc(s[i])
        dp[num] += dp[num+1] % mod
print(dp[0] %mod)

Submission status: Accepted

Solution code:
# encoding: utf-8
S = input()

A = 0
C = S.count("C") # N
q = 0

q_max = S.count("?") # N

ABC = 0
div = 10 ** 9 + 7
B_base = 3 ** (q_max - 2) % div
q_base = 3 ** (q_max - 3) % div
for si in S: # N
    if si == "A": A += 1
    elif si == "C": C -= 1
    elif si == "B":
        # ABC = (ABC + (A * C) * (3 ** q_max)) % div
        # ABC = (ABC + (q * C) * (3 ** (q_max - 1))) % div
        # ABC = (ABC + (A * (q_max - q)) * (3 ** (q_max - 1))) % div
        # ABC = (ABC + (q * (q_max - q)) * (3 ** (q_max - 2))) % div
        ABC = (ABC + (3 * A + q) * (3 * C + q_max - q) * B_base) % div
    else: # "?"
        # ABC = (ABC + (A * C) * (3 ** (q_max - 1))) % div
        # ABC = (ABC + (q * C) * (3 ** (q_max - 2))) % div
        # ABC = (ABC + (A * (q_max - q - 1)) * (3 ** (q_max - 2))) % div
        # ABC = (ABC + (q * (q_max - q - 1)) * (3 ** (q_max - 3))) % div        
        ABC = (ABC + (3 * A + q) * (3 * C + q_max - q - 1) * q_base) % div
        q += 1
    # print(si, ABC)
    
print(int(ABC))

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    s = S()
    l = len(s)
    r = [[0]*4 for _ in range(l+1)]
    r[0][0] = 1
    for i in range(l):
        c = s[i]
        if c == 'A' or c == '?':
            r[i+1][0] += r[i][0]
            r[i+1][1] += r[i][1] + r[i][0]
            r[i+1][2] += r[i][2]
            r[i+1][3] += r[i][3]
        if c == 'B' or c == '?':
            r[i+1][0] += r[i][0]
            r[i+1][1] += r[i][1]
            r[i+1][2] += r[i][2] + r[i][1]
            r[i+1][3] += r[i][3]
        if c == 'C' or c == '?':
            r[i+1][0] += r[i][0]
            r[i+1][1] += r[i][1]
            r[i+1][2] += r[i][2]
            r[i+1][3] += r[i][3] + r[i][2]
        for j in range(4):
            r[i+1][j] %= mod


    return r[-1][3]


print(main())

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

MOD = 1000000007
S = input()

def add(a,b):
    a += b
    if a >= MOD:
        a -= MOD
    return a

dp = [[0 for i in range(5)] for j in range(200000)]

dp[0][0] = 1

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

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

Submission status: Accepted

Solution code:
MOD = 1000000007


def main():
    s = input()

    dp = [[0 for j in range(4)] for i in range(len(s)+1)]
    dp[len(s)][3] = 1

    for i in range(len(s)-1, -1, -1):
        for j in range(3, -1, -1):
            if i < j:
                continue
            if j == 3:
                dp[i][j] = dp[i+1][3]
                if s[i] == "?":
                    dp[i][j] = 3 * dp[i][j] % MOD
            else:
                m1, m2 = 1, 0
                if s[i] == "?":
                    m1 = 3
                    m2 = 1
                if s[i] == "ABC"[j]:
                    m2 = 1
                dp[i][j] = (m1*dp[i+1][j]+m2*dp[i+1][j+1]) % MOD

    print(dp[0][0] % MOD)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
mod = 1000000007

pow3 = [1] * 100001
for i in range(1, 100001):
    pow3[i] = pow3[i - 1] * 3 % mod

s = input()

all_a = 0
all_c = 0
all_q = 0
for c in s:
    if c == 'A':
        all_a += 1
    elif c == 'C':
        all_c += 1
    elif c == '?':
        all_q += 1
sum_a = 0
sum_c = 0
sum_q = 0
ans = 0

for c in s:
    n = 0
    if c == 'B':
        n += sum_a * (all_c - sum_c) * pow3[all_q] % mod
        n += sum_a * (all_q - sum_q) * pow3[all_q - 1] % mod
        n += sum_q * (all_c - sum_c) * pow3[all_q - 1] % mod
        n += sum_q * (all_q - sum_q) * pow3[all_q - 2] % mod
    elif c == '?':
        n += sum_a * (all_c - sum_c) * pow3[all_q - 1] % mod
        n += sum_a * (all_q - sum_q - 1) * pow3[all_q - 2] % mod
        n += sum_q * (all_c - sum_c) * pow3[all_q - 2] % mod
        n += sum_q * (all_q - sum_q - 1) * pow3[all_q - 3] % mod
    ans += n % mod
    if c == 'A':
        sum_a += 1
    elif c == 'C':
        sum_c += 1
    elif c == '?':
        sum_q += 1
print(int(ans % mod))

Submission status: Accepted

Solution code:
S = input()
DP = [0, 0, 0, 1]
p = 10 ** 9 + 7
for s in S[::-1]:
  dp = [0, 0, 0, 0]
  dp[3] = DP[3] * (3 if s == '?' else 1) % p
  for i in range(2, -1, -1):
    dp[i] += DP[i] * (3 if s == '?' else 1)
    dp[i] += DP[i + 1] if s == chr(65 + i) or s == '?' else 0
    dp[i] %= p
  DP = dp
print(DP[0] % p)

Submission status: Accepted

Solution code:
S = input()

N = len(S)
mod = 10 ** 9 + 7

dp = [[0 for _ in range(4)] for _ in range(N + 1)]
dp [0][0] = 1
for i in range(N):
    if S[i] == 'A':
        for j in range(4):
            dp[i + 1][j] += dp[i][j]
        dp[i + 1][1] += dp[i][0]
    elif S[i] == 'B':
        for j in range(4):
            dp[i + 1][j] += dp[i][j]
        dp[i + 1][2] += dp[i][1]
    elif S[i] == 'C':
        for j in range(4):
            dp[i + 1][j] += dp[i][j]
        dp[i + 1][3] += dp[i][2]
    else:
        for j in range(4):
            dp[i + 1][j] += dp[i][j] * 3
        dp[i + 1][1] += dp[i][0]
        dp[i + 1][2] += dp[i][1]
        dp[i + 1][3] += dp[i][2]

    for j in range(4):
        dp[i + 1][j] %= mod

print(dp[N][3])

Submission status: Accepted

Solution code:
S = input()

d = [0, 0, 0, 1]

max_ans = 10**9 + 7

for c in reversed(S):
    # print(c, d)
    m = [c == "A", c == "B", c == "C", c == "?"]
    if(m[3] is True):
        tmp = 3
    else:
        tmp = 1

    for j in range(3):
        d[j] = (tmp * d[j] + int(m[j] or m[3]) * d[j + 1]) % max_ans
    d[3] = (tmp * d[3]) % max_ans

print(d[0])

Submission status: Accepted

Solution code:
S = input()
N = len(S)
mod = 10 ** 9 + 7

# dp[i][j]: i番目までの文字までで、状態jになる組み合わせ数
dp = [[0 for _ in range(4)] for _ in range(N + 1)]
dp[0][0] = 1

for i in range(N):
    if S[i] in ['A', '?']:
        for j in range(4):
            dp[i + 1][j] += dp[i][j]
        dp[i + 1][1] += dp[i][0]
    if S[i] in ['B', '?']:
        for j in range(4):
            dp[i + 1][j] += dp[i][j]
        dp[i + 1][2] += dp[i][1]
    if S[i] in ['C', '?']:
        for j in range(4):
            dp[i + 1][j] += dp[i][j]
        dp[i + 1][3] += dp[i][2]

    for j in range(4):
        dp[i + 1][j] %= mod

print(dp[N][3])

Submission status: Accepted

Solution code:
S=raw_input()

M=10**9+7

all=1
abc=0
ab=0
a=0

for x in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		abc+=ab

	if x=="?":
		abc=abc*3+ab
		ab=ab*3+a
		a= a*3+all
		all*=3

	abc%=M
	ab%=M
	a%=M
	all%=M


print abc%M

Submission status: Accepted

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

# N[i]を持つ必要はないはず。まあ10^5だからメモリパンクはしない・・・？
Nz = [0] * (len(S)+1)
Na = [0] * (len(S)+1)
Nb = [0] * (len(S)+1)
Nc = [0] * (len(S)+1)
Nz[0] = 1

for i in range(len(S)):
  if S[i] == '?':
    Nz[i+1] = (Nz[i] * 3) % MODN
    Na[i+1] = (Nz[i] + Na[i] * 3) % MODN
    Nb[i+1] = (Na[i] + Nb[i] * 3) % MODN
    Nc[i+1] = (Nb[i] + Nc[i] * 3) % MODN
  elif S[i] == 'A':
    Nz[i+1] = Nz[i]
    Na[i+1] = (Nz[i] + Na[i]) % MODN
    Nb[i+1] = Nb[i]
    Nc[i+1] = Nc[i]
  elif S[i] == 'B':
    Nz[i+1] = Nz[i]
    Na[i+1] = Na[i]
    Nb[i+1] = (Na[i] + Nb[i]) % MODN
    Nc[i+1] = Nc[i]
  elif S[i] == 'C':
    Nz[i+1] = Nz[i]
    Na[i+1] = Na[i]
    Nb[i+1] = Nb[i]
    Nc[i+1] = (Nb[i] + Nc[i]) % MODN
  else:
    print("Error!!")

print(Nc[len(S)])

Submission status: Accepted

Solution code:

S = input()

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

B = 10 ** 9 + 7
for i in range(1, len(S) + 1):
    if S[i - 1] == 'A':
        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] += dp[i - 1][0]
    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][3] += dp[i - 1][3]

        dp[i][2] += dp[i - 1][1]
    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][3] += dp[i - 1][2]
    else:
        dp[i][0] += dp[i - 1][0] * 3
        dp[i][1] += dp[i - 1][1] * 3
        dp[i][2] += dp[i - 1][2] * 3
        dp[i][3] += dp[i - 1][3] * 3

        dp[i][1] += dp[i - 1][0]
        dp[i][2] += dp[i - 1][1]
        dp[i][3] += dp[i - 1][2]

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


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

Submission status: Accepted

Solution code:
s = input()

dp = [[0]*(len(s)+1) for _ in [0]*4]
dp[0][0] = 1
mod = 10**9 + 7

for i, (c, n0, n1, n2, n3) in enumerate(zip(s, dp[0], dp[1], dp[2], dp[3]), start=1):
    m = 3 if c=="?" else 1
    dp[0][i] = (n0*m) % mod
    dp[1][i] = (n1*m + n0*(c=="A" or c=="?")) % mod
    dp[2][i] = (n2*m + n1*(c=="B" or c=="?")) % mod
    dp[3][i] = (n3*m + n2*(c=="C" or c=="?")) % mod

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

Submission status: Accepted

Solution code:
s = input()
dp = [[0 for _ in range(len(s) + 1)] for _ in range(4)]
# 0文字目までで0個の照合が住んだ数
dp[0][0] = 1
for i in range(0,4):
  for j in range(1, len(s) + 1):
    # ABCを進めない道
    if s[j-1] == '?':
      dp[i][j] += dp[i][j - 1] * 3
    else:
      dp[i][j] += dp[i][j - 1]
    # ABCを進める道
    if 0 < i and (s[j - 1] == '?' or s[j - 1] == 'ABC'[i - 1]):
      dp[i][j] += dp[i - 1][j - 1]
    dp[i][j] %= 1000000007

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

Submission status: Accepted

Solution code:
import sys

S = input()

DEVIDER = 10**9 + 7


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

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

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


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


for i in range(len(S)):
    for j in range(4):
        if S[i] == '?':
            cache[i + 1][j] += 3 * cache[i][j]
        else:
            cache[i + 1][j] += cache[i][j]
        if j > 0:
            if check(S[i], j-1) or S[i] == '?':
                cache[i+1][j] += cache[i][j - 1]
        cache[i+1][j] %= DEVIDER

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

Submission status: Accepted

Solution code:
s = input()
m = 10**9 + 7

a = [1,0,0,0]
for ch in s:
    if ch == 'A':
        a[1] = (a[0]+a[1]) % m
    elif ch == 'B':
        a[2] = (a[1]+a[2]) % m
    elif ch == 'C':
        a[3] = (a[2]+a[3]) % m
    else:
        a[3] = (a[2]+3*a[3]) % m
        a[2] = (a[1]+3*a[2]) % m
        a[1] = (a[0]+3*a[1]) % m
        a[0] = (3*a[0]) % m

print(a[3])

Submission status: Accepted

Solution code:
s = input()

#動的計画表で解決
s0 = len(s)


dp = [[0 for i in range(4)] for j in range(s0+1)]
dp[0][0]=1
mod = 10**9+7


for i in range(0,s0):
    if (s[i]=='A') or (s[i]=="?"):
        for j in range(0,4):
            dp[i+1][j]+= dp[i][j]
            dp[i+1][j]%=mod
        dp[i+1][1]+=dp[i][0]
        dp[i+1][1]%=mod

    if (s[i]=='B') or (s[i]=="?"):
        for j in range(0,4):
            dp[i+1][j]+= dp[i][j]
            dp[i+1][j]%=mod
        dp[i+1][2]+=dp[i][1]
        dp[i+1][2]%=mod

    if (s[i]=='C') or (s[i]=="?"):
        for j in range(0,4):
            dp[i+1][j]+= dp[i][j]
            dp[i+1][j]%=mod
        dp[i+1][3]+=dp[i][2]
        dp[i+1][3]%=mod
  
    
print(dp[s0][3])

Submission status: Accepted

Solution code:
m = 10**9+7
n = 1
a = ab = abc = 0
for c in input():
    if c == 'A':
        a += n
    elif c == 'B':
        ab += a
    elif c == 'C':
        abc += ab
    else:
        ta, tab = a, ab
        a *= 3
        ab *= 3
        abc *= 3
        a += n
        ab += ta
        abc += tab
        n *= 3
    a %= m
    ab %= m
    abc %= m
    n %= m
print(abc)

Submission status: Accepted

Solution code:
S=input()
P=10**9+7
N=len(S)
dp=[[0 for j in range(4)]for i in range(N+1)]
for i in range(N+1)[::-1]:
    for j in range(4)[::-1]:
        if i==N and j==3:
            dp[i][j]=1
        elif i==N and j!=3:
            dp[i][j]=0
        elif i!=N and j==3:
            m=0
            if S[i]=="?":
                m=3
            else:
                m=1
            dp[i][j]=m*dp[i+1][j]
        else:
            m1=0
            if S[i]=="?":
                m1=3
            else:
                m1=1
            m2=0
            if S[i]=="?" or S[i]=="ABC"[j]:
                m2=1
            else:
                m2=0
            dp[i][j]=m1*dp[i+1][j]+m2*dp[i+1][j+1]
        dp[i][j]=(dp[i][j]%P)
print(dp[0][0])

Submission status: Accepted

Solution code:
box = [1,0,0,0]
for c in input():
    if c == "A":
        box[1] = box[0]+box[1]
    elif c == "B":
        box[2] = box[1]+box[2]
    elif c == "C":
        box[3] = box[2]+box[3] 
    elif c == "?":
        box = [box[0]*3,box[1]*3+box[0],box[2]*3+box[1],box[3]*3+box[2]]

    box = [i%(10**9+7) for i in box]
print(box[3])

Submission status: Accepted

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)
        if Q_left[-1]>=1:
            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)
        if Q_left[-1]>=2:
            ans = (ans + (Q_left[i] * Q_right[i]) * pow(3,(Q_left[-1]-2),10**9+7)) % (10**9+7)
    elif s == "?":
        if Q_left[-1]>=1:
            ans = (ans + A_left[i] * C_right[i] * pow(3,(Q_left[-1]-1),10**9+7)) % (10**9+7)
        if Q_left[-1]>=2:
            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)
        if Q_left[-1]>=3:
            ans = (ans + (Q_left[i] * Q_right[i]) * pow(3,(Q_left[-1]-3),10**9+7)) % (10**9+7)

print(ans)

Submission status: Accepted

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

Solution code:
s = input()
a,c,x,q,m1,m2,n1,n2 = [],[],len(s),s.count("?"),0,0,0,0
for i in range(x-2):
	if s[i]=="A": m1+=1
	elif s[i]=="?": m2+=1
	if s[x-1-i]=="C": n1+=1
	elif s[x-1-i]=="?": n2+=1
	a.append([m1,m2])
	c.append([n1,n2])
c,z0,z1,z2,z3,mod,num = c[::-1],0,0,0,0,10**9+7,1
for i in range(x-2):
	if s[i+1]=="B":
		z0,z2 = (z0+a[i][0]*c[i][0])%mod,(z2+a[i][1]*c[i][1])%mod
		z1 = (z1+a[i][0]*c[i][1]+a[i][1]*c[i][0])%mod
	elif s[i+1]=="?":
		z1,z3 = (z1+a[i][0]*c[i][0])%mod,(z3+a[i][1]*c[i][1])%mod
		z2 = (z2+a[i][0]*c[i][1]+a[i][1]*c[i][0])%mod
for i in range(q-3): num = (num*3)%mod
if q>=3: print((num*z3+num*3*z2+num*9*z1+num*27*z0)%mod)
elif q==2: print((z0*9+z1*3+z2)%mod)
elif q==1: print((z0*3+z1)%mod)
elif q==0: print(z0)