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: Wrong Answer

Solution code:
# dp[i][j] := sのi文字目まで見たときに、ABCのj文字目までを部分列として取り出す方法の数。

s = input()

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

for idx, letter in enumerate(s):
    dp[idx] = dp[idx-1].copy()

    if letter == 'A':
        dp[idx][1] += 1
    elif letter == 'B':
        dp[idx][2] += dp[idx-1][1]
    elif letter == 'C':
        dp[idx][3] += dp[idx-1][2]
    elif letter == '?':
        dp[idx][1] *= 3
        dp[idx][2] *= 3
        dp[idx][3] *= 3
        dp[idx][1] += 1
        dp[idx][2] += dp[idx-1][1]
        dp[idx][3] += dp[idx-1][2]


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

Submission status: Wrong Answer

Solution code:
S = input()
lct_A = 0
lct_q = 0
rct_C = S.count("C")
rct_q = S.count("?")

MOD = 10**9 + 7

ans = 0
for s in S:
  if s == "C":
    rct_C -= 1
  elif s == "?":
    rct_q -= 1
    
  if s == "B" or s == "?":
    ans += (lct_A * rct_C * pow(3, lct_q+rct_q, MOD)) % MOD
    if lct_q > 0:
      ans += (lct_q * rct_C * pow(3, lct_q+rct_q-1, MOD) ) % MOD
    if lct_q > 0:
      ans += (rct_q * lct_A * pow(3, lct_q+rct_q-1, MOD) ) % MOD
    if lct_q > 0 and rct_q > 0:
      ans += (lct_q * rct_q * pow(3, lct_q+rct_q-2, MOD) ) % MOD   
    ans %= MOD
    
  if s == "A":
    lct_A += 1
  elif s == "?":
    lct_q += 1
    
print(ans % MOD)

Submission status: Wrong Answer

Solution code:
S = input()
a = [1,0,0,0]

for s in S:
  if s=="A":
    a[1]+=a[0]
  elif s=="B":
    a[2]+=a[1]
  elif s=="C":
    a[3]+=a[2]
  else:
    a=[3*a[0]]+[3*a[n+1]+a[n] for n in range(3)]
    a=[a[n]%1000000007 for n in range(4)]

print(a[3])

Submission status: Wrong Answer

Solution code:
S=input()
N=len(S)
As=[0]*N
ABs=[0]*N
ABCs=[0]*N
p=10**9+7

if S[0]=="A":
    As[0]=1

for i in range(1,N):
    s=S[i]
    if s=="A":
        As[i]=(As[i-1]+1)%p
        ABs[i]=ABs[i-1]
        ABCs[i]=ABCs[i-1]+1
    elif s=="B":
        As[i]=As[i-1]
        ABs[i]=(ABs[i-1]+As[i-1])%p
        ABCs[i]=ABCs[i-1]

    elif s=="C":
        As[i]=As[i-1]
        ABs[i]=ABs[i-1]
        ABCs[i]=(ABCs[i-1]+ABs[i-1])%p

    else:
        As[i]=(3*As[i-1]+1)%p
        ABs[i]=(3*ABs[i-1]+As[i-1])%p
        ABCs[i]=(ABCs[i-1]+ABs[i-1])%p

print(ABCs[-1])
#print(As)
#print(ABs)
#print(ABCs)

Submission status: Wrong Answer

Solution code:
S=input()
N=len(S)
A=[0]
B=[0]
C=[0]
X=[0]
for i in range(N):
  A.append(A[i])
  B.append(B[i])
  C.append(C[i])
  X.append(X[i])
  if S[i]=='A':
    A[-1]+=1
  elif S[i]=='B':
    B[-1]+=1
  elif S[i]=='C':
    C[-1]+=1
  else:
    X[-1]+=1
P=0
mod=10**9+7
def p(x,y):
  return pow(x,max(y,1)-1,mod)

for i in range(N):
  if S[i]=='B' or S[i]=='?':
    P=(P+p(3,X[i])*(X[i]+3*A[i])*p(3,X[N]-X[i+1])*(X[N]-X[i+1]+3*(C[N]-C[i])))%mod
print(P)

Submission status: Wrong Answer

Solution code:
# D - We Love ABC
import sys
readline = sys.stdin.readline

S = list(str(readline().rstrip()))
print(S)
MOD = 10**9 + 7
a = 0
ab = 0
abc = 0
pat = 1
for s in S:
    if s == 'A':
        a = (a + pat) % MOD
    elif s == 'B':
        ab = (ab + a) % MOD
    elif s == 'C':
        abc = (abc + ab) % MOD
    else: # s == '?'
        tmpa = a
        tmpab = ab
        a = (3*a + pat) % MOD
        ab = (3*ab + tmpa) % MOD
        abc = (3*abc + tmpab) % MOD
        pat = (pat*3) % MOD

print(abc)

Submission status: Wrong Answer

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

#i文字目まで見たときj文字目まで確定しているときの組み合わせ
dp = [[0 for i in range(4)]for j in range(S+1)]
mod = 10**9+7

dp[0][0] = 1

for j in range(4):
    for i in range(S):
        dp[i+1][j] = dp[i][j]%mod
        if s[i] == "?":
            dp[i+1][j] = dp[i][j]*3%mod
            if j > 0:
                dp[i+1][j] += dp[i][j-1]%mod
        else:
            if "ABC".index(s[i])+1 == j:
                dp[i+1][j] += dp[i][j-1]%mod

print(dp[S][3])

Submission status: Wrong Answer

Solution code:
#何も思い浮かばない
#完全に負けた死にたいわかんない
#やっぱりDPだけど式が全く立てれない
#頭悪すぎしね
mod=10**9+7
s=input()
l=len(s)
dp=[[0]*4 for i in range(l)]
for i in range(l):
    if i==0:
        if s[i]=="A":
            dp[i][0]=1
            dp[i][3]=1
        elif s[i]=="?":
            dp[i][0]=1
            dp[i][3]=3
    else:
        if s[i]=="A":
            dp[i]=[(dp[i-1][0]+dp[i-1][3])%mod,dp[i-1][1],dp[i-1][2],dp[i-1][3]]
        elif s[i]=="B":
            dp[i]=[dp[i-1][0],(dp[i-1][0]+dp[i-1][1])%mod,dp[i-1][2],dp[i-1][3]]
        elif s[i]=="C":
            dp[i]=[dp[i-1][0],dp[i-1][1],(dp[i-1][1]+dp[i-1][2])%mod,dp[i-1][3]]
        else:
            dp[i]=[(3*dp[i-1][0]+dp[i-1][3])%mod,(3*dp[i-1][1]+dp[i-1][0])%mod,(3*dp[i-1][2]+dp[i-1][1])%mod,(3*dp[i-1][3])%mod]
print(dp[-1][2])

Submission status: Wrong Answer

Solution code:
#何も思い浮かばない
#完全に負けた死にたいわかんない
#やっぱりDPだけど式が全く立てれない
#頭悪すぎしね
mod=10**9+7
s=input()
l=len(s)
dp=[[0]*4 for i in range(l)]
for i in range(l):
    if i==0:
        if s[i]=="A":
            dp[i][0]=1
            dp[i][3]=1
        elif s[i]=="?":
            dp[i][0]=1
            dp[i][3]=3
    else:
        if s[i]=="A":
            dp[i]=[dp[i-1][0]+dp[i-1][3],dp[i-1][1],dp[i-1][2],dp[i-1][3]]
        elif s[i]=="B":
            dp[i]=[dp[i-1][0],(dp[i-1][0]+dp[i-1][1])%mod,dp[i-1][2],dp[i-1][3]]
        elif s[i]=="C":
            dp[i]=[dp[i-1][0],dp[i-1][1],(dp[i-1][1]+dp[i-1][2])%mod,dp[i-1][3]]
        else:
            dp[i]=[(3*dp[i-1][0]+dp[i-1][3])%mod,(3*dp[i-1][1]+dp[i-1][0])%mod,(3*dp[i-1][2]+dp[i-1][1])%mod,3*dp[i-1][3]]
print(dp[-1][2])

Submission status: Wrong Answer

Solution code:
#何も思い浮かばない
#完全に負けた死にたいわかんない
#やっぱりDPだけど式が全く立てれない
#頭悪すぎしね
mod=10**9+7
s=input()
l=len(s)
dp=[[0]*3 for i in range(l)]
for i in range(l):
    if i==0:
        if s[i]=="A" or s[i]=="?":
            dp[i][0]=1
    else:
        if s[i]=="A":
            dp[i]=[dp[i-1][0]+1,dp[i-1][1],dp[i-1][2]]
        elif s[i]=="B":
            dp[i]=[dp[i-1][0],(dp[i-1][0]+dp[i-1][1])%mod,dp[i-1][2]]
        elif s[i]=="C":
            dp[i]=[dp[i-1][0],dp[i-1][1],(dp[i-1][1]+dp[i-1][2])%mod]
        else:
            dp[i]=[(3*dp[i-1][0]+1)%mod,(3*dp[i-1][1]+dp[i-1][0])%mod,(3*dp[i-1][2]+dp[i-1][1])%mod]
print(dp[-1][-1])

Submission status: Wrong Answer

Solution code:
S = input()

def solve(S):
    mod = 10**9+7
    N = len(S)
    Aquest = []
    Cquest = []
    cntA,cntquest = 0,0
    for i in range(N):
        if S[i] in 'B?':
            Aquest.append([cntA,cntquest])
        if S[i]=='A':
            cntA += 1
        if S[i]=='?':
            cntquest += 1
    cntC,cntquest = 0,0
    for i in range(N-1,-1,-1):
        if S[i] in 'B?':
            Cquest.append([cntC,cntquest])
        if S[i]=='C':
            cntC += 1
        if S[i]=='?':
            cntquest += 1
    Cquest = Cquest[::-1]
    ans = 0
    for aquest,cquest in zip(Aquest,Cquest):
        a = 0
        for i in range(aquest[1]+1):
            a += (aquest[0]+i)*pow(2,aquest[1]-i,mod)
        c = 0
        for i in range(cquest[1]+1):
            c += (cquest[0]+i)*pow(2,cquest[1]-i,mod)
        ans += a*c%mod
    return ans%mod
print(solve(S))

Submission status: Wrong Answer

Solution code:
S = str(input())
c_cnts = [0 for i in range(len(S))]
q_cnts = [0 for i in range(len(S))]
a_inds = []
b_inds = []

if S[-1] == 'C':
  c_cnts[-1] += 1
elif S[-1] == '?':
  c_cnts[-1] += 1
  q_cnts[-1] += 1
  
for i in range(len(S))[-2::-1]:
  if S[i] == 'A':
    a_inds.append(i)
    c_cnts[i] = c_cnts[i + 1]
    q_cnts[i] = q_cnts[i + 1]
  elif S[i] == 'B':
    b_inds.append(i)
    c_cnts[i] = c_cnts[i + 1]
    q_cnts[i] = q_cnts[i + 1]
  elif S[i] == 'C':
    q_cnts[i] = q_cnts[i + 1]
    c_cnts[i] = c_cnts[i + 1] + 1
  else:
    a_inds.append(i)
    b_inds.append(i)
    q_cnts[i] = q_cnts[i + 1] + 1
    c_cnts[i] = c_cnts[i + 1] + 1

a_inds = sorted(a_inds)
b_inds = sorted(b_inds)
print(a_inds)
print(b_inds)
print(c_cnts)
print(q_cnts)
result = 0
for a_ind in a_inds:
  for b_ind in b_inds:
    if b_ind < a_ind or b_ind == len(S) - 1:
      continue
    result += c_cnts[b_ind + 1] * ((q_cnts[a_ind] - q_cnts[b_ind]) ** 3)
    result %= 10 ** 9 + 7

print(result)

Submission status: Wrong Answer

Solution code:
s=input()

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

dp[0][0] = 1

for i in range(len(s)):
    for j in range(4):
        dp[i][j] %= 10**9+7
        if s[i]=="?":
            dp[i+1][j] += (3*dp[i][j])
        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[-1][-1])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

s = input()
n = len(s)
p = 10 ** 9 + 7

q = s.count('?')
l_a = [0] * n  # l_a[i] := s[i]より左にあるAの数
l_x = [0] * n  # l_x[i] := s[i]より左にある?の数
r_c = [0] * n  # r_c[i] := s[i]より右にあるCの数
r_x = [0] * n  # r_x[i] := s[i]より右にある?の数

for i in range(1, n):  # 1〜n-1
    l_a[i] = l_a[i - 1] + int(s[i - 1] == 'A')
    l_x[i] = l_x[i - 1] + int(s[i - 1] == '?')
    r_c[n - i - 1] = r_c[n - i] + int(s[n - i] == 'C')
    r_x[n - i - 1] = r_x[n - i] + int(s[n - i] == '?')

ans = 0
pow_q3 = max(1, 3 ** (q - 3) % p)
pow_q2 = max(1, pow_q3 * 3 % p)
pow_q1 = max(1, pow_q2 * 3 % p)
pow_q = max(1, pow_q1 * 3 % p)

for i in range(n):
    if s[i] == 'B':
        ans += (l_a[i] * r_c[i] % p) * pow_q % p  # ABC
        ans += (l_x[i] * r_c[i] % p) * pow_q1 % p # ?BC
        ans += (l_a[i] * r_x[i] % p) * pow_q1 % p # AB?
        ans += (l_x[i] * r_x[i] % p) * pow_q2 % p # ?B?
        ans %= p
    elif s[i] == '?':
        ans += (l_a[i] * r_c[i] % p) * pow_q1 % p # A?C
        ans += (l_x[i] * r_c[i] % p) * pow_q2 % p # ??C
        ans += (l_a[i] * r_x[i] % p) * pow_q2 % p # A??
        ans += (l_x[i] * r_x[i] % p) * pow_q3 % p # ???
        ans %= p

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
s=input()
mod=10**9+7
nagasa=len(s)-1
dp=[[0 for _ in range(4)] for _ in range(nagasa+1)]
dp[0][0]=1
for i in range(nagasa):
    moji=s[i]
    for j in range(4):
        ni=i+1
        nj=j    
        if moji == '?':
            dp[ni][nj]+=3*dp[i][j]
            if j==0:
                nj=1
                dp[ni][nj]+=dp[i][j]
                dp[ni][nj]%=mod
            elif j==1:
                nj=2
                dp[ni][nj]+=dp[i][j]
                dp[ni][nj]%=mod
            elif j==2:
                nj=3
                dp[ni][nj]+=dp[i][j]
                dp[ni][nj]%=mod
        else:
            dp[ni][nj]+=dp[i][j]        
            if moji=='A' and j==0:
                nj=1
                dp[ni][nj]+=dp[i][j]
            if moji=='B' and j==1:
                nj=2
                dp[ni][nj]+=dp[i][j]
            if moji=='C' and j==2:
                nj=3
                dp[ni][nj]+=dp[i][j]
            dp[ni][nj]%=mod
print(dp[nagasa][3]%mod)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
s=input()
mod=10**9+7
nagasa=len(s)
dp=[[0 for _ in range(4)] for _ in range(nagasa+1)]
dp[0][0]=1
for i in range(nagasa):
    moji=s[i]
    for j in range(4):
        ni=i+1
        nj=j    
        if moji == '?':
            dp[ni][nj]+=3*dp[i][j]
            if j==0:
                nj=1
                dp[ni][nj]+=dp[i][j]
                dp[ni][nj]%=mod
            elif j==1:
                nj=2
                dp[ni][nj]+=dp[i][j]
                dp[ni][nj]%=mod
            elif j==2:
                nj=3
                dp[ni][nj]+=dp[i][j]
                dp[ni][nj]%=mod
        else:
            dp[ni][nj]+=dp[i][j]        
            if moji=='A' and j==0:
                nj=1
                dp[ni][nj]+=dp[i][j]
            if moji=='B' and j==1:
                nj=2
                dp[ni][nj]+=dp[i][j]
            if moji=='C' and j==2:
                nj=3
                dp[ni][nj]+=dp[i][j]
            dp[ni][nj]%=mod
print(dp[nagasa][3]%mod)

Submission status: Wrong Answer

Solution code:
S=str(input())
N=len(S)
dp=[[0 for _ in range(4)] for _ in range(N+1)]
dp[0][0]=1
mod=10**9+7
for i in range(N):
  if S[i]=='A':
    dp[i+1][0]+=dp[i][0]%mod
    dp[i+1][1]+=dp[i][1]%mod+dp[i][0]%mod
    dp[i+1][2]+=dp[i][2]%mod
    dp[i+1][3]+=dp[i][3]%mod
  if S[i]=='B':
    dp[i+1][0]+=dp[i][0]%mod
    dp[i+1][1]+=dp[i][1]%mod
    dp[i+1][2]+=dp[i][2]%mod+dp[i][1]%mod
    dp[i+1][3]+=dp[i][3]%mod
  if S[i]=='C':
    dp[i+1][0]+=dp[i][0]%mod
    dp[i+1][1]+=dp[i][1]%mod
    dp[i+1][2]+=dp[i][2]%mod
    dp[i+1][3]+=dp[i][3]%mod+dp[i][2]%mod
  if S[i]=='?':
    dp[i+1][0]+=3*dp[i][0]%mod
    dp[i+1][1]+=3*dp[i][1]%mod+dp[i][0]%mod
    dp[i+1][2]+=3*dp[i][2]%mod+dp[i][1]%mod
    dp[i+1][3]+=3*dp[i][3]%mod+dp[i][2]%mod
print(dp[N][3])

Submission status: Wrong Answer

Solution code:
s= list(input())
n=len(s)

mod=10**9+7

ans=0
dp=[[0,0,0] for i in range(n+1)]

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

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

Submission status: Wrong Answer

Solution code:
s = list(str(input()))
n = len(s)

dl = {'A':0, 'C':0, '?':0}
dr = {'A':0, 'C':0, '?':0}

dls = []
drs = []

import copy

for i in range(n):
    if s[i] == 'A' or s[i] == 'C':
        dl[s[i]] += 1
    elif s[i] == 'B':
        dl_ = copy.copy(dl)
        dls.append(dl_)
    else:
        dl_ = copy.copy(dl)
        dls.append(dl_)
        dl[s[i]] += 1
    j = n - 1- i
    if s[j] == 'A' or s[j] == 'C':
        dr[s[j]] += 1
    elif s[j] == 'B':
        dr_ = copy.copy(dr)
        drs.append(dr_)
    else:
        dr_ = copy.copy(dr)
        drs.append(dr_)
        dr[s[j]] += 1

drs = list(reversed(drs))
#print(dls)
#print(drs)

ans = 0
mod = 10**9+7
x = s.count('?')

def power(a, n, mod):
  bi=str(format(n,"b")) #2進数
  res=1
  for i in range(len(bi)):
    res=(res*res) %mod
    if bi[i]=="1":
      res=(res*a) %mod
  return res

for i in range(len(dls)):
    a = (dls[i]['A']*power(3, dls[i]['?'], mod) + dls[i]['?'])%mod
    b = (drs[i]['C']*power(3, drs[i]['?'], mod) + drs[i]['?'])%mod
    ans += (a*b)%mod
    #print(ans)
ans %=mod
print(ans)

Submission status: Wrong Answer

Solution code:
s = list(str(input()))
n = len(s)

dl = {'A':0, 'C':0, '?':0}
dr = {'A':0, 'C':0, '?':0}

dls = []
drs = []

print(s)
import copy

for i in range(n):
    if s[i] == 'A' or s[i] == 'C':
        dl[s[i]] += 1
    elif s[i] == 'B':
        dl_ = copy.copy(dl)
        dls.append(dl_)
    else:
        dl_ = copy.copy(dl)
        dls.append(dl_)
        dl[s[i]] += 1
    j = n - 1- i
    if s[j] == 'A' or s[j] == 'C':
        dr[s[j]] += 1
    elif s[j] == 'B':
        dr_ = copy.copy(dr)
        drs.append(dr_)
    else:
        dr_ = copy.copy(dr)
        drs.append(dr_)
        dr[s[j]] += 1

drs = list(reversed(drs))
#print(dls)
#print(drs)

ans = 0
mod = 10**9+7
x = s.count('?')

def power(a, n, mod):
  bi=str(format(n,"b")) #2進数
  res=1
  for i in range(len(bi)):
    res=(res*res) %mod
    if bi[i]=="1":
      res=(res*a) %mod
  return res

for i in range(len(dls)):
    a = (dls[i]['A']*power(3, dls[i]['?'], mod) + dls[i]['?'])%mod
    b = (drs[i]['C']*power(3, drs[i]['?'], mod) + drs[i]['?'])%mod
    ans += (a*b)%mod
    #print(ans)
ans %=mod
print(ans)

Submission status: Wrong Answer

Solution code:
S=input()
N=len(S)
dp=[0,0,0]

mod=10**9+7

p=[1]*(N+1)
for i in range(N):
    p[i+1]=p[i]*3

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
S = input()
N = len(S)
mod = 10**9+7
numofA = 0
numofAB = 0
numofABC = 0
numofquestion = 0
for i in range(N):
    if S[i] == "?":
        numofABC = (numofABC*3+numofAB) % mod
        numofAB = (numofAB*3+numofA) % mod
        numofA = (max(1, numofquestion**3)+3*numofA) % mod
        numofquestion += 1
    elif S[i] == "C":
        numofABC = (numofAB+numofABC) % mod
    elif S[i] == "B":
        numofAB = (numofAB + numofA) % mod
    else:
        numofA = (max(1, numofquestion**3)+numofA) % mod
print(numofABC)

Submission status: Wrong Answer

Solution code:
S = input()
N = len(S)
mod = 10**9+7
numofA = 0
numofAB = 0
numofABC = 0
numofquestion = 0
for i in range(N):
    if S[i] == "?":
        numofABC = (numofABC*3+numofAB) % mod
        numofAB = (numofAB*3+numofA) % mod
        numofA = (numofA * 3 + 1) % mod
        numofquestion += 1
    elif S[i] == "C":
        numofABC = (numofAB+numofABC) % mod
    elif S[i] == "B":
        numofAB = (numofAB + numofA) % mod
    else:
        numofA += (numofquestion**3) % mod
print(numofABC)

Submission status: Wrong Answer

Solution code:
MOD = 1e9 + 7
p3 = [1]

S = input()
n = len(S)

a = []
c = []
q = []
for i in range(n):
  p3.append(int(p3[i] * 3 % MOD))
  if S[i] == 'A':
    a.append(1)
  else:
    a.append(0)
  if S[i] == 'C':
    c.append(1)
  else:
    c.append(0)
  if S[i] == '?':
    q.append(1)
  else:
    q.append(0)

for i in range(1, n):
  a[i] += a[i - 1]
  c[i] += c[i - 1]
  q[i] += q[i - 1]

count = 0
for i in range(1, n - 1):
  if S[i] == 'B' or S[i] == '?':
    bq = 0 if S[i] == 'B' else 1
    count += a[i - 1] * (c[n - 1] - c[i]) * p3[q[n - 1] - bq]
    count += q[i - 1] * (c[n - 1] - c[i]) * p3[q[n - 1] - 1 - bq]
    count += a[i - 1] * (q[n - 1] - q[i]) * p3[q[n - 1] - 1 - bq]
    count += q[i - 1] * (q[n - 1] - q[i]) * p3[q[n - 1] - 2 - bq]

print(int(count % MOD))

Submission status: Wrong Answer

Solution code:
MOD = 1e9 + 7
p3 = [1]

S = input()
n = len(S)

a = []
c = []
q = []
for i in range(n):
  p3.append(int(p3[i] * 3 % MOD))
  if S[i] == 'A':
    a.append(1)
  else:
    a.append(0)
  if S[i] == 'C':
    c.append(1)
  else:
    c.append(0)
  if S[i] == '?':
    q.append(1)
  else:
    q.append(0)

for i in range(1, n):
  a[i] += a[i - 1]
  c[i] += c[i - 1]
  q[i] += q[i - 1]

count = 0
for i in range(1, n - 1):
  if S[i] == 'B' or S[i] == '?':
    bq = 0 if S[i] == 'B' else 1
    count += a[i - 1] * (c[n - 1] - c[i]) * p3[q[n - 1] - bq]
    count += q[i - 1] * (c[n - 1] - c[i]) * p3[q[n - 1] - 1 - bq]
    count += a[i - 1] * (q[n - 1] - q[i]) * p3[q[n - 1] - 1 - bq]
    count += q[i - 1] * (q[n - 1] - q[i]) * p3[q[n - 1] - 2 - bq]
    
print(int(count % MOD))

Submission status: Wrong Answer

Solution code:
MOD = 1e9 + 7
p3 = [1]

S = input()
n = len(S)

a = []
c = []
q = []
for i in range(n):
  p3.append(int(p3[i] * 3 % MOD))
  if S[i] == 'A':
    a.append(1)
  else:
    a.append(0)
  if S[i] == 'C':
    c.append(1)
  else:
    c.append(0)
  if S[i] == '?':
    q.append(1)
  else:
    q.append(0)

for i in range(1, n):
  a[i] += a[i - 1]
  c[i] += c[i - 1]
  q[i] += q[i - 1]

count = 0
for i in range(1, n - 1):
  if S[i] == 'B' or S[i] == '?':
    bq = 0 if S[i] == 'B' else 1
    count += a[i - 1] * (c[n - 1] - c[i]) * p3[q[n - 1] - bq]
    count %= MOD
    count += q[i - 1] * (c[n - 1] - c[i]) * p3[q[n - 1] - 1 - bq]
    count %= MOD
    count += a[i - 1] * (q[n - 1] - q[i]) * p3[q[n - 1] - 1 - bq]
    count %= MOD
    count += q[i - 1] * (q[n - 1] - q[i]) * p3[q[n - 1] - 2 - bq]
    count %= MOD
    

print(int(count))

Submission status: Wrong Answer

Solution code:
s=input()
l=len(s)

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

for i in range(1,l+1):
  si = s[i-1]
  if si == "?":
    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
  else:
    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]
    
  if si == "A":
    dp[i][1] = dp[i-1][0] + dp[i][1]
  elif si == "B":
    dp[i][2] = dp[i-1][1] + dp[i][2]
  elif si == "C":
    dp[i][3] = dp[i-1][2] + dp[i][3]
  else:
    dp[i][1] = dp[i-1][0] + dp[i][1]
    dp[i][2] = dp[i-1][1] + dp[i][2]
    dp[i][3] = dp[i-1][2] + dp[i][3]
  
  #print(dp)  
print(dp[-1][-1])

Submission status: Wrong Answer

Solution code:
s = input()

dp_prev = [1, 0, 0, 0]

MODE_BASE = 1000000007

for c in s:
    dp_new = [dp_prev[i] for i in range(0, 4)]
    for i in range(0, 4):
        if c == "A":
            dp_new[1] = dp_prev[0] + dp_prev[1]

        elif c == "B":
            dp_new[2] = dp_prev[1] + dp_prev[2]

        elif c == "C":
            dp_new[3] = dp_prev[2] + dp_prev[3]

        else:
            dp_new[0] = (dp_prev[0] * 3) % MODE_BASE
            dp_new[1] = (dp_prev[0] + dp_prev[1] * 3) % MODE_BASE
            dp_new[2] = (dp_prev[1] + dp_prev[2] * 3) % MODE_BASE
            dp_new[3] = (dp_prev[2] + dp_prev[3] * 3) % MODE_BASE

    dp_prev = dp_new

ans = dp_prev[3]
print(ans)

Submission status: Wrong Answer

Solution code:
s = input()
n = len(s)
mod = 10**9 + 7
ol = [0]*3
for x in s:
  if x == "A":
    ol[0] = (ol[0] + 1)%mod
  elif x == "B":
    ol[1] = (ol[1] + ol[0])%mod
  elif x == "C":
    ol[2] = (ol[2] + ol[1])%mod
  else:
    ol[2] = (ol[2]*3 + ol[1])%mod
    ol[1] = (ol[1]*3 + ol[0])%mod
    ol[0] = (ol[0]*3 + 1)%mod
print(ol[-1])

Submission status: Wrong Answer

Solution code:
S = input()
INF = 10**9+7
dp = [0,0,0]
Q = 0
N = 1
for i in range(len(S)):
  if S[i]=='A':
    dp[0] += N%INF
    dp[0] %= INF
  elif S[i]=='B':
    dp[1] += (dp[0]%INF)
  elif S[i]=='C':
    dp[2] += (dp[1]%INF)
  else:
    a = dp[0]
    b = dp[1]
    dp[0] = 3**Q + dp[0]*3
    dp[1] = a + dp[1]*3
    dp[2] = b + dp[2]*3
    dp[0] %= INF
    dp[1] %= INF
    dp[2] %= INF
    N *= 3
print(dp[2]%INF)

Submission status: Wrong Answer

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

def find_cumsum(X):
    output = [1] if S[0] == X else [0]    
    for idx in range(1,N):
        if S[idx] == X:
            output.append(output[-1]+1)
        else:
            output.append(output[-1])
    return output

q_count = S.count("?")
A_cumsum = find_cumsum("A")
q_cumsum = find_cumsum("?")
        
# last_b[i][j] : S[j]を末尾の"B"とするABのインデックスのパターンの中で、i個の?を"AB"のために使用したもの
last_b = [[0] for _ in range(3)]
for idx in range(1,N):
    if S[idx] == "B":
        last_b[0].append(A_cumsum[idx-1]) # AB
        last_b[1].append(q_cumsum[idx-1]) # ?B
        last_b[2].append(0)
    elif S[idx] == "?":
        last_b[0].append(0)
        last_b[1].append(A_cumsum[idx-1]) # A?
        last_b[2].append(q_cumsum[idx-1]) # ??
    else:
        for i in [0,1,2]:
            last_b[i].append(0)

last_b_cumsum = [[last_b[0][0]], [last_b[1][0]], [last_b[2][0]]]
for i in range(3):
    for idx in range(1,N):
        last_b_cumsum[i].append((last_b[i][idx] + last_b_cumsum[i][-1]) % MOD)

Submission status: Wrong Answer

Solution code:
s = input()
n = len(s)
mod = 10**9+7

a = [0]*n
b = [0]*n
c = [0]*n
d = [0]*n

x = 0
y = 0
for i in range(n):
    a[i] = x
    b[i] = y
    if s[i] == 'A':
        x += 1
    elif s[i] == '?':
        y += 1

x = 0
y = 0
for i in range(n-1,-1,-1):
    c[i] = x
    d[i] = y
    if s[i] == 'C':
        x += 1
    elif s[i] == '?':
        y += 1

def f(A,B,C,D):
    if B+D == 0:
        return pow(3,B+D,mod)*A*C%mod
    if B+D == 1:
        return pow(3,B+D,mod)*A*C%mod + pow(3,B+D-1,mod)*A*D%mod + pow(3,B+D-1,mod)*A*D%mod

    return pow(3,B+D,mod)*A*C%mod + pow(3,B+D-1,mod)*B*C%mod + pow(3,B+D-1,mod)*A*D%mod + pow(3,B+D-2,mod)*B*D%mod

res = 0
for i in range(1,n-1):
    if s[i] == 'B' or s[i]=='?':
        res = (res+f(a[i],b[i],c[i],d[i]))%mod
print(res%mod)

Submission status: Wrong Answer

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
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007

#A
def A():
    r = II()
    if r < 1200:
        print("ABC")
    elif r < 2800:
        print("ARC")
    else:
        print("AGC")
    return

#B
def B():
    return

#C
def C():
    d, g = LI()
    pc = LIR(d)
    ans = float("INF")
    tokumono = list(itertools.product((0, 1), repeat=d))
    for toku in tokumono:
        ansa = 0
        ansb = 0
        for i in range(len(toku)):
            if toku[i] == 1:
                ansa += pc[i][0]
                ansb += pc[i][0] * (i + 1) * 100 + pc[i][1]
        for k in range(len(toku) - 1, -1, -1):
            if toku[k] == 0:
                for i in range(pc[k][0] + 1):
                    if i == pc[k][0]:
                        ansb += pc[k][1]
                    if ansb >= g:
                        ans = min(ans, ansa)
                        break
                    ansa += 1
                    ansb += (k+1) * 100
                break
    print(ans)
    return

#D ? 
def D_():
    N, X = LI()
    def dfs(n, x):
        #print(n, x)
        if x == 1 and n > 0:
            return 0 
        elif x < 2 ** (n + 1) - 1:
            return dfs(n - 1, x - 1)
        elif x == 2 ** (n + 1) - 1:
            return 2 ** n 
        elif x == 2 ** (n + 2) - 3:
            return 2 ** (n + 1) - 1
        else:
            return dfs(n - 1, x - 2 ** (n + 1) + 1) + 2 ** n 
    a = dfs(N, X)
    print(a)
    return

def D():
    s = S()
    dp = [0] * 3
    s = s[::-1]
    x = 1
    for i, si in enumerate(s):
        if si == "A":
            dp[0] = (dp[0] + dp[1]) % mod
        elif si == "B":
            dp[1] = (dp[1] + dp[2]) % mod
        elif si == "C":
            dp[2] = (dp[2] + 1) % mod
        else:
            # ?がAのとき
            dp[0] = (dp[0] * 3 + dp[1]) % mod
            
            # ?がBのとき
            dp[1] = (dp[1] * 3 + dp[2]) % mod

            # ?がCのとき
            dp[2] = (dp[2] * 3 + x) % mod
            x *= 3
            x %= mod
    print(dp[0])

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

Submission status: Wrong Answer

Solution code:
#初期化
m = (10 ** 9) + 7
S = list(input())
N = len(S)
dp = [[0 for i in range(N + 2)] for j in range(3)]
three = [0 for i in range(10 ** 5 + 1)]
three[0] = 1
for i in range(1, 10 ** 5 + 1):
	three[i] = (three[i - 1] * 3) % m

#DP
que = 0
for i in range(N):
	if S[i] == "A":
		dp[0][i + 1] = dp[0][i] + three[que]
		dp[1][i + 1] = dp[1][i]
		dp[2][i + 1] = dp[2][i]
	elif S[i] == "B":
		dp[0][i + 1] = dp[0][i]
		dp[1][i + 1] = dp[0][i] + dp[1][i]
		dp[2][i + 1] = dp[2][i]
	elif S[i] == "C":
		dp[0][i + 1] = dp[0][i]
		dp[1][i + 1] = dp[1][i]
		dp[2][i + 1] = dp[1][i] + dp[2][i]
	else:
		dp[0][i + 1] = 3 * dp[0][i] + three[que]
		dp[1][i + 1] = 3 * dp[1][i] + dp[0][i]
		dp[2][i + 1] = 3 * dp[2][i] + dp[1][i]
		que += 1
	dp[0][i + 1], dp[1][i + 1], dp[2][i + 1] = dp[0][i + 1] % m, dp[1][i + 1] % m, dp[2][i + 1] % m

print(dp)
print(dp[2][N])

Submission status: Wrong Answer

Solution code:
MOD = 10 ** 9 + 7

S = list(input())

a = [0] * len(S)
ab = [0] * len(S)
abc = [0] * len(S)

if S[0] == "A" or S[0] == "?":
    a[0] = 1

for i in range(1,len(S)):
    if S[i] == "A":
        a[i] = a[i-1] + 1
        ab[i] = ab[i-1]
        abc[i] = abc[i-1]
    elif S[i] == "B":
        a[i] = a[i-1]
        ab[i] = (ab[i-1] + a[i-1]) % MOD
        abc[i] = abc[i-1]
    elif S[i] == "C":
        a[i] = a[i-1]
        ab[i] = ab[i-1]
        abc[i] = (abc[i-1] + ab[i-1]) % MOD
    else:
        a[i] = (a[i-1] * 3 + 1) % MOD
        ab[i] = (ab[i-1] * 3 + a[i-1]) % MOD
        abc[i] = (abc[i-1] * 3 + ab[i-1]) % MOD

#print(a)
#print(ab)
#print(abc)
print(abc[-1])

Submission status: Wrong Answer

Solution code:
MOD = 10 ** 9 + 7

S = list(input())

a = [0] * len(S)
ab = [0] * len(S)
abc = [0] * len(S)

if S[0] == "A" or S[0] == "?":
    a[0] = 1

for i in range(1,len(S)):
    if S[i] == "A":
        a[i] = a[i-1] + 1
        ab[i] = ab[i-1]
        abc[i] = abc[i-1]
    elif S[i] == "B":
        a[i] = a[i-1]
        ab[i] = (ab[i-1] + a[i-1]) % MOD
        abc[i] = abc[i-1]
    elif S[i] == "C":
        a[i] = a[i-1]
        ab[i] = ab[i-1]
        abc[i] = (abc[i-1] + ab[i-1]) % MOD
    else:
        a[i] = (a[i-1] * 3 + 1) % MOD
        ab[i] = (ab[i-1] * 3 + a[i-1]) % MOD
        abc[i] = (abc[i-1] * 3 + ab[i-1]) % MOD

print(a)
print(ab)
print(abc)
print(abc[-1])

Submission status: Wrong Answer

Solution code:
def main():
    S = input()
    
    mod = 10**9 + 7
    Ans = [[0,0,0,0,0]]
    import copy
    
    S = S[::-1]
    for i in range(len(S)):
        tmp = copy.deepcopy(Ans[i])
        if S[i] == "C":
            tmp[2] += 1
            Ans.append(tmp)
        elif S[i] == "B":
            tmp[1] += 1
            tmp[3] += tmp[2]
            tmp[3] %= mod
            Ans.append(tmp)
        elif S[i] == "A":
            tmp[0] += 1
            tmp[4] += tmp[3]
            tmp[4] %= mod
            Ans.append(tmp)
        elif S[i] == "?":
            a,b,c,bc,abc = tmp
            Ans.append([(3*a+1)%mod, (3*b+1)%mod, (3*c+1)%mod, (3*bc+c)%mod, (3*abc+bc)%mod])
            
    print(Ans[-1][-1])
    
    
main()