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()
n=len(s)
mod=10**9+7
dp=[ [0]*3 for _ in range(n)]
#dp[i][0] count of A's in all possible strings u generate till i
#dp[i][1] count of AB's ''
#dp[i][2] count of ABC's ''
cnt=1
for i in range(n):
    if s[i]=='?':
        if i>0:
            dp[i][2]=dp[i-1][1]+3*dp[i-1][2]
            dp[i][2]%=mod
            dp[i][1]=dp[i-1][0]+3*dp[i-1][1]
            dp[i][1]%=mod
            dp[i][0]=3*dp[i-1][0]+1*cnt
            dp[i][0]%=mod
        else:
            dp[i][0]=1
        cnt*=3
        cnt%=mod
    elif s[i]=='C':
        if i>0:
            dp[i][2]=dp[i-1][1]+dp[i-1][2]
            dp[i][2]%=mod
            dp[i][1]=dp[i-1][1]
            dp[i][0]=dp[i-1][0]
    elif s[i]=='B':
        if i>0:
            dp[i][2]=dp[i-1][2]
            dp[i][1]=dp[i-1][0]+dp[i-1][1]
            dp[i][1]%=mod
            dp[i][0]=dp[i-1][0]
    elif s[i]=='A':
        if i>0:
            dp[i][2]=dp[i-1][2]
            dp[i][1]=dp[i-1][1]
            dp[i][0]=dp[i-1][0]+1*cnt
            dp[i][0]%=mod
        else:
            dp[0][0]=1

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

Submission status: Accepted

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

dp=[]
for i in range(len(S)+1):
  dp.append([0,0,0,0])
  
dp[-1][3]=1
for i in reversed(range(len(S))):
  if S[i]=="?":
    m1=3
  else:
    m1=1        
  dp[i][3]=m1*dp[i+1][3]
  dp[i][3]%=MOD
  
  for j in range(3):
    if S[i]=="?":
      m2=1
    else:
      if S[i]==["A","B","C"][j]:
        m2=1
      else:
        m2=0    
    dp[i][j]=m1*dp[i+1][j]+m2*dp[i+1][j+1]
    dp[i][j]%=MOD
    
print(dp[0][0])

Submission status: Accepted

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

base = 1
for i, s in enumerate(S, 1):
  dp[i][0] = dp[i-1][0]
  dp[i][1] = dp[i-1][1]
  dp[i][2] = dp[i-1][2]
  if s == 'A':
    dp[i][0] += base
    dp[i][0] %= MOD
  elif s == 'B':
    dp[i][1] += dp[i-1][0]
    dp[i][1] %= MOD
  elif s == 'C':
    dp[i][2] += dp[i-1][1]
    dp[i][2] %= MOD
  else: # s == '?'
    dp[i][0] += 2*dp[i-1][0] + base
    dp[i][1] += 2*dp[i-1][1] + dp[i-1][0]
    dp[i][2] += 2*dp[i-1][2] + dp[i-1][1]
    dp[i][0] %= MOD
    dp[i][1] %= MOD
    dp[i][2] %= MOD
    base *= 3
    base %= MOD

print(dp[-1][2])

Submission status: Accepted

Solution code:
s=input()
mod=10**9+7
a,ab,abc=0,0,0
q=0
for c in s:
  if c=='A':
    a=(a+pow(3,q,mod))%mod
  elif c=='B':
    ab=(a+ab)%mod
  elif c=='C':
    abc=(ab+abc)%mod
  else:
    a,ab,abc=(3*a+pow(3,q,mod))%mod,(3*ab+a)%mod,(3*abc+ab)%mod
    q+=1
print(abc)

Submission status: Accepted

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

Submission status: Accepted

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

dp = [[0]*4 for i in range(len(s)+1)]
dp[0][0] = 1
for i in range(len(s)):
    
    if s[i] == "A":
        dp[i+1][1] += dp[i][0]
    elif s[i] =="B":
        dp[i+1][2] += dp[i][1]
    elif s[i] == "C":
        dp[i+1][3] += dp[i][2]
    else:
        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):
        if s[i] == "?":
            dp[i+1][j] = (dp[i+1][j]+dp[i][j]*3)%mod
        else:
            dp[i+1][j] = (dp[i+1][j]+dp[i][j])%mod


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

Submission status: Accepted

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

def main():
    S = input()
    l = len(S)
    MOD = 10**9+7
    dp = [[0 for _ in range(3)] for _ in range(2)]
    cq = 1
    for st in S:
        if st == "A":
            dp[1][0] = dp[0][0]+cq
            dp[1][1] = dp[0][1]
            dp[1][2] = dp[0][2]
        elif st == "B":
            dp[1][0] = dp[0][0]
            dp[1][1] = dp[0][0]+dp[0][1]
            dp[1][2] = dp[0][2]
        elif st == "C":
            dp[1][0] = dp[0][0]
            dp[1][1] = dp[0][1]
            dp[1][2] = dp[0][1]+dp[0][2]
        else:
            dp[1][0] = dp[0][0]*3+cq
            dp[1][1] = dp[0][1]*3+dp[0][0]
            dp[1][2] = dp[0][2]*3+dp[0][1]
            cq *= 3
            cq %= MOD
        for i in range(3):
            dp[0][i] = dp[1][i]%MOD
    
    print(dp[0][-1])

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

for i in range(N):
    for j in range(4):
        s = S[i]
        m1 = 3 if s == '?' else 1
        m2 = 1 if j != 0 and (s == '?' or s == 'ABC'[j - 1]) else 0
        dp[i + 1][j] = (m1 * dp[i][j] + m2 * dp[i][j - 1]) % MOD

print(dp[N][3])

Submission status: Accepted

Solution code:
from collections import Counter


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

cnt = Counter()

for s in S:
    if s == 'B':
        cnt['?B'] += cnt['?']
        cnt['AB'] += cnt['A']
    elif s == 'C':
        cnt['ABC'] += cnt['AB']
        cnt['A?C'] += cnt['A?']
        cnt['?BC'] += cnt['?B']
        cnt['??C'] += cnt['??']
    elif s == '?':
        for t in ['??', 'A?', '?B', 'AB']:
            cnt[t + '?'] += cnt[t]
        for t in ['A', '?']:
            cnt[t + '?'] += cnt[t]
    cnt[s] += 1

q = cnt['?']
ans = 0
for key in [x for x in list(cnt.keys()) if len(x) == 3]:
    if cnt[key]:
        ans += cnt[key] * pow(3, q - key.count('?'), MOD)
        ans %= MOD

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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]%mod)

Submission status: Accepted

Solution code:
MOD = 10**9+7

s=input()
Anum = 0
ABnum = 0
ABCnum = 0
q = 0
for c in s:
    if c == 'A':
        Anum = (Anum+pow(3,q,MOD))%MOD
    elif c == 'B':
        ABnum = (ABnum+Anum)%MOD
    elif c == 'C':
        ABCnum = (ABCnum+ABnum)%MOD
    else:
        Anum,ABnum,ABCnum = 3*Anum+pow(3,q,MOD),3*ABnum+Anum,3*ABCnum+ABnum
        Anum,ABnum,ABCnum = Anum%MOD,ABnum%MOD,ABCnum%MOD
        q += 1
print(ABCnum)

Submission status: Accepted

Solution code:
S=input()
mod=10**9+7
La,Lq,Rc,Rq=0,0,S.count("C"),S.count("?")
ans=0
f=lambda x,y:pow(x,y,mod) if y>=0 else 0
for s in S:
	Rc-=s=="C";Rq-=s=="?"
	if s=="B" or s=="?":
		ans+=(La*f(3,Lq)+Lq*f(3,Lq-1))*(Rc*f(3,Rq)+Rq*f(3,Rq-1))
		ans%=mod
	La+=s=="A";Lq+=s=="?"
print(ans)

Submission status: Accepted

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

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

for i, e in enumerate(s, 1):
	# do not use in ABC
	for j in range(4):
		if e == "?":
			dp[i][j] += dp[i-1][j] * 3
		else:
			dp[i][j] += dp[i-1][j]

	# use in ABC
	if e == "A" or e == "?":
		dp[i][1] += dp[i-1][0]
	if e == "B" or e == "?":
		dp[i][2] += dp[i-1][1]
	if e == "C" or e == "?":
		dp[i][3] += dp[i-1][2]

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


ans = dp[l][3]
print(ans)

Submission status: Accepted

Solution code:
#we love abc
s=input()
mod=10**9+7
dpa=[[0,0] for i in range(len(s)+1)]
dpc=[[0,0] for i in range(len(s)+1)]
power3=[1 for i in range(10**5+100)]
for i in range(10**5+3):
    power3[i+1]=(power3[i]*3)%mod
for i in range(len(s)):
    if s[i]=="A":
        dpa[i+1][0]=(dpa[i][0]+power3[dpa[i][1]])%mod
        dpa[i+1][1]=dpa[i][1]  
    elif s[i]=="?":
        dpa[i+1][0]=(3*dpa[i][0]+power3[dpa[i][1]])%mod
        dpa[i+1][1]=dpa[i][1]+1   
    else:
        dpa[i+1]=dpa[i]
for i in range(len(s)):
    if s[len(s)-1-i]=="C":
        dpc[i+1][0]=(dpc[i][0]+power3[dpc[i][1]])%mod
        dpc[i+1][1]=dpc[i][1]  
    elif s[len(s)-1-i]=="?":
        dpc[i+1][0]=(3*dpc[i][0]+power3[dpc[i][1]])%mod
        dpc[i+1][1]=dpc[i][1]+1   
    else:
        dpc[i+1]=dpc[i]    
ans=0
for i in range(1,len(s)-1):
    if s[i]=="B" or s[i]=="?":
        ans+=dpa[i][0]*dpc[len(s)-1-i][0]
        ans=ans%mod
print(ans)

Submission status: Accepted

Solution code:
S=input()
pr=10**9+7
a1,a2,a3=0,0,0
c=0
for i in S:
    if i=="A":
        a1=(a1+pow(3,c,pr))%pr
    elif i=="B":
        a2=(a2+a1)%pr
    elif i=="C":
        a3=(a3+a2)%pr
    else:
        a1,a2,a3=(3*a1+pow(3,c,pr))%pr,(3*a2+a1)%pr,(3*a3+a2)%pr
        c+=1
print(a3)

Submission status: Accepted

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

mod=10**9+7

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

for i in range(n):
    if s[i]=='A':
        dp[i+1][0]=dp[i][0]+cnt
        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]+cnt
        dp[i+1][1]=3*dp[i][1]+dp[i][0]
        dp[i+1][2]=3*dp[i][2]+dp[i][1]
        cnt*=3
        cnt%=mod
        dp[i+1][0]%=mod
        dp[i+1][1]%=mod
        dp[i+1][2]%=mod

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

Submission status: Accepted

Solution code:
s = input()
n = len(s)
MOD = 10 ** 9 + 7
dp = [[0] * 4 for _ in range(n + 1)]
dp[0][0] = 1

for i, x in enumerate(s):
    if x == 'A' or x == '?':
        dp[i + 1][0] += dp[i][0]
        dp[i + 1][1] += dp[i][1]
        dp[i + 1][2] += dp[i][2]
        dp[i + 1][3] += dp[i][3]
        dp[i + 1][1] += dp[i][0]
    if x == 'B' or x == '?':
        dp[i + 1][0] += dp[i][0]
        dp[i + 1][1] += dp[i][1]
        dp[i + 1][2] += dp[i][2]
        dp[i + 1][3] += dp[i][3]
        dp[i + 1][2] += dp[i][1]
    if x == 'C' or x == '?':
        dp[i + 1][0] += dp[i][0]
        dp[i + 1][1] += dp[i][1]
        dp[i + 1][2] += dp[i][2]
        dp[i + 1][3] += dp[i][3]
        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()
MOD = 10 ** 9 + 7
dp = [1, 0, 0, 0]

for x in s:
    emp, a, b, c = dp
    if x == 'A':
        dp[1] += emp
    if x == 'B':
        dp[2] += a
    if x == 'C':
        dp[3] += b
    if x == '?':
        dp = [v * 3 for v in dp]
        dp[1] += emp
        dp[2] += a
        dp[3] += b

    dp = [v % MOD for v in dp]

print(dp[3])

Submission status: Accepted

Solution code:
import sys
s = input()
mod = 10**9+7
memo_ls = [[0 for j in range(4)] for i in range(len(s) + 1)]
memo_ls[0][0] = 1
for i, _s in enumerate(s, 1):
    memo_ls[i][0] = memo_ls[i-1][0]
    memo_ls[i][1] = memo_ls[i-1][1]
    memo_ls[i][2] = memo_ls[i-1][2]
    memo_ls[i][3] = memo_ls[i - 1][3]
    if _s == "A":
        memo_ls[i][1] += memo_ls[i-1][0]
    elif _s == "B":
        memo_ls[i][2] += memo_ls[i-1][1]
    elif _s == "C":
        memo_ls[i][3] += memo_ls[i-1][2]
    else:
        memo_ls[i][0] *= 3
        memo_ls[i][1] *= 3
        memo_ls[i][2] *= 3
        memo_ls[i][3] *= 3
        memo_ls[i][1] += memo_ls[i - 1][0]
        memo_ls[i][2] += memo_ls[i - 1][1]
        memo_ls[i][3] += memo_ls[i - 1][2]
    memo_ls[i][0] %= mod
    memo_ls[i][1] %= mod
    memo_ls[i][2] %= mod
    memo_ls[i][3] %= mod
print(memo_ls[-1][-1] % mod)

Submission status: Accepted

Solution code:
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

S = sr()[::-1]
MOD = 10 ** 9 + 7
answer = 0
dp = [0, 0, 1] #Cの数, BC数, 総数
for i in range(len(S)):
    s = S[i]
    if s == 'A':
        answer += dp[1]
    elif s == 'B':
        dp[1] += dp[0]
    elif s == 'C':
        dp[0] += dp[2]
    elif s == '?':
        answer *= 3
        answer += dp[1]
        dp[1] *= 3
        dp[1] += dp[0]
        dp[0] *= 3
        dp[0] += dp[2]
        dp[2] *= 3
    answer %= MOD
    dp[0] %= MOD; dp[1] %= MOD; dp[2] %= MOD
print(answer)

Submission status: Accepted

Solution code:
def main():
    S=input()
    N=len(S)
    abccounter=0
    abcounter=0
    acounter=0
    for i in range(0,N):
        if S[i]=='A':
            acounter+=1
        elif S[i]=='B':
            abcounter+=acounter
        elif S[i]=='C':
            abccounter+=abcounter
    hbccounter=0
    hbcounter=0
    hcounter=0
    for i in range(0,N):
        if S[i]=='?':
            hcounter+=1
        elif S[i]=='B':
            hbcounter+=hcounter
        elif S[i]=='C':
            hbccounter+=hbcounter
    ahccounter=0
    ahcounter=0
    acounter=0
    for i in range(0,N):
        if S[i]=='A':
            acounter+=1
        elif S[i]=='?':
            ahcounter+=acounter
        elif S[i]=='C':
            ahccounter+=ahcounter
    abhcounter=0
    abcounter=0
    acounter=0
    for i in range(0,N):
        if S[i]=='A':
            acounter+=1
        elif S[i]=='B':
            abcounter+=acounter
        elif S[i]=='?':
            abhcounter+=abcounter
    ahhcounter=0
    ahcounter=0
    acounter=0
    for i in range(0,N):
        if S[i]=='A':
            acounter+=1
        elif S[i]=='?':
            ahhcounter+=ahcounter
            ahcounter+=acounter
    hbhcounter=0
    hbcounter=0
    hcounter=0
    for i in range(0,N):
        if S[i]=='B':
            hbcounter+=hcounter
        elif S[i]=='?':
            hbhcounter+=hbcounter
            hcounter+=1
    hhccounter=0
    hhcounter=0
    hcounter=0
    for i in range(0,N):
        if S[i]=='C':
            hhccounter+=hhcounter
        elif S[i]=='?':
            hhcounter+=hcounter
            hcounter+=1
    Q=hcounter
    if Q>=3:
        ans=abccounter*3**Q+(hbccounter+ahccounter+abhcounter)*3**(Q-1)+(ahhcounter+hbhcounter+hhccounter)*3**(Q-2)+(Q*(Q-1)*(Q-2)//6)*3**(Q-3)
    elif Q==2:
        ans=abccounter*3**Q+(hbccounter+ahccounter+abhcounter)*3**(Q-1)+(ahhcounter+hbhcounter+hhccounter)*3**(Q-2)
    elif Q==1:
        ans=abccounter*3**Q+(hbccounter+ahccounter+abhcounter)*3**(Q-1)
    else:
        ans=abccounter*3**Q
    print(ans%(10**9+7))
if __name__ == '__main__':
    main()

Submission status: Accepted

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

dp = [[0] * 4 for _ in range(n)]
dp[-1][0] = 1
# dp[i文字目までの?を確定させた][i文字目までで文字をn個選んだ]

for i, s in enumerate(S):
    if s == '?':
        dp[i][0] = dp[i - 1][0] * 3 % mod
        dp[i][1] = (dp[i - 1][0] + dp[i - 1][1] * 3) % mod
        dp[i][2] = (dp[i - 1][1] + dp[i - 1][2] * 3) % mod
        dp[i][3] = (dp[i - 1][2] + dp[i - 1][3] * 3) % mod
    elif s == '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 == 'B':
        dp[i][0] = dp[i - 1][0]
        dp[i][1] = dp[i - 1][1]
        dp[i][2] = (dp[i - 1][1] + dp[i - 1][2]) % mod
        dp[i][3] = dp[i - 1][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] + dp[i - 1][2]) % mod

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

Submission status: Accepted

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

A = 0
AB = 0
ABC = 0
cnt = 1

for s in S:
    if s == "A":
        A = (A + cnt) % MOD
    elif s == "B":
        AB = (A + AB) % MOD
    elif s == "C":
        ABC = (AB + ABC) % MOD
    else:
        A, AB, ABC = (A * 3 + cnt) % MOD, (AB * 3 + A) % MOD, (ABC * 3 + AB) % MOD
        cnt = (cnt * 3) % MOD
    # print(A, AB, ABC, cnt)
    
print(ABC)

Submission status: Accepted

Solution code:
S = input()

dp = [[0] * 4 for _ in range(len(S) + 1)]
dp[0][0] = 1
W = 'ABC'

MOD = 10 ** 9 + 7


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


def update2(i, c):
    ic = W.index(c)
    dp[i + 1][ic + 1] += dp[i][ic] % MOD


for i in range(len(S)):
    if S[i] == '?':
        for c in W:
            update1(i)
            update2(i, c)
    else:
        update1(i)
        update2(i, S[i])
print(dp[len(S)][-1] % MOD)

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left as bl
from collections import defaultdict as dd
input = sys.stdin.readline
S = list(input())[: -1]
d = dd(list)
mod = 10 ** 9 + 7
res = 0
for i in range(len(S)):
  d[S[i]].append(i)
for i in range(len(S)):
  if S[i] == "B":
    l = bl(d["A"], i)
    m = bl(d["?"], i)
    r = bl(d["C"], i)
    res += l * (len(d["C"]) - r) * pow(3, len(d["?"]), mod)
    res %= mod
    res += m * (len(d["C"]) - r) * pow(3, max(len(d["?"]) - 1, 0), mod) * (len(d["?"]) > 0)
    res %= mod
    res += l * (len(d["?"]) - m) * pow(3, max(len(d["?"]) - 1, 0), mod) * (len(d["?"]) > 0)
    res %= mod
    res += m * (len(d["?"]) - m) * pow(3, max(len(d["?"]) - 2, 0), mod) * (len(d["?"]) > 1)
    res %= mod
  elif S[i] == "?":
    l = bl(d["A"], i)
    m = bl(d["?"], i)
    r = bl(d["C"], i)
    res += l * (len(d["C"]) - r) * pow(3, len(d["?"]) - 1, mod)
    res %= mod
    res += m * (len(d["C"]) - r) * pow(3, max(len(d["?"]) - 2, 0), mod) * (len(d["?"]) > 1)
    res %= mod
    res += l * (len(d["?"]) - m - 1) * pow(3, max(len(d["?"]) - 2, 0), mod) * (len(d["?"]) > 1)
    res %= mod
    res += m * (len(d["?"]) - m - 1) * pow(3, max(len(d["?"]) - 3, 0), mod) * (len(d["?"]) > 2)
    res %= mod
  #print(res, i)
print(res)

Submission status: Accepted

Solution code:
#i文字目を見て，それより前のAの個数，ABの個数，ABCの個数を持っておく

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

mod=10**9+7


count=0#?の数
for i in range(N):
    if S[i]=="A":
        dp[0]=(dp[0]+pow(3,count,mod)) %mod
    elif S[i]=="B":
        dp[1]=(dp[1]+dp[0])%mod
    elif S[i]=="C":
        dp[2]=(dp[2]+dp[1])%mod
    else:
        dp[2]=(dp[2]*3+dp[1])%mod
        dp[1]=(dp[1]*3+dp[0])%mod
        dp[0]=(dp[0]*3+pow(3,count,mod))%mod
        count+=1
        
print(dp[2]%mod)

Submission status: Accepted

Solution code:
#i文字目を見て，それより前のAの個数，ABの個数，ABCの個数を持っておく

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)%mod


count=0#?の数
for i in range(N):
    if S[i]=="A":
        dp[0]=(dp[0]+p[count]) %mod
    elif S[i]=="B":
        dp[1]=(dp[1]+dp[0])%mod
    elif S[i]=="C":
        dp[2]=(dp[2]+dp[1])%mod
    else:
        dp[2]=(dp[2]*3+dp[1])%mod
        dp[1]=(dp[1]*3+dp[0])%mod
        dp[0]=(dp[0]*3+p[count])%mod
        count+=1
        
print(dp[2]%mod)

Submission status: Accepted

Solution code:
#i文字目を見て，それより前のAの個数，ABの個数，ABCの個数を持っておく

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)%mod


count=0#?の数
for i in range(N):
    if S[i]=="A":
        dp[0]=(dp[0]+p[count]) %mod
    elif S[i]=="B":
        dp[1]=(dp[1]+dp[0])%mod
    elif S[i]=="C":
        dp[2]=(dp[2]+dp[1])%mod
    else:
        dp[2]=(dp[2]*3+dp[1])%mod
        dp[1]=(dp[1]*3+dp[0])%mod
        dp[0]=(dp[0]*3+p[count])%mod
        count+=1
        
print(dp[2]%mod)

Submission status: Accepted

Solution code:
S = input()

mod = 10**9+7
A = 0
AB = 0
ABC = 0
cnt = 0
for i in range(len(S)):
    if S[i] == "A":
        A += pow(3, cnt, mod)
        A %= mod
    elif S[i] == "B":
        AB += A
        AB %= mod
    elif S[i] == "C":
        ABC += AB
        ABC %= mod
    else:
        ABC = (3*ABC + AB) % mod
        AB = (3*AB + A) % mod
        A = (3*A + pow(3, cnt, mod)) % mod
        cnt += 1
        
        
print(ABC)

Submission status: Accepted

Solution code:
from collections import *
from itertools import *
import copy
from heapq import *

S=input()
mod=10**9+7


"""def mpow(x,n):
    num=1
    while n > 0:
        if n&1:
            num=num*x%mod
        x=x*x%mod
        n=n>>1
    return(num)"""

A=0
AB=0
ABC=0
count=0
for s in S:
    if s=="A":
        A+=pow(3,count,mod)
    elif s=="B":
        AB+=A
    elif s=="C":
        ABC+=AB
    else:
        ABC=(ABC*3+AB)%mod
        AB=(AB*3+A)%mod
        A=(A*3+pow(3,count,mod) )%mod
        count+=1
print(ABC%mod)

Submission status: Accepted

Solution code:
S = input(); N = len(S)
a,b,c,d = 0,0,0,1
mod = 10**9+7
for x in reversed(S):
  if x == "?":
    a,b,c,d = (3*a+b)%mod, (3*b+c)%mod, (3*c+d)%mod, 3*d%mod
  elif x == "A": a = (a+b)%mod
  elif x == "B": b = (b+c)%mod
  elif x == "C": c = (c+d)%mod
print(a)

Submission status: Accepted

Solution code:
S = input()
N = len(S)
a,b,c,d = 0,0,0,1
mod = 10**9+7
for x in reversed(S):
  if x == "?":
    a,b,c,d = 3*a+b, 3*b+c, 3*c+d, 3*d
  elif x == "A":
    a += b
  elif x == "B":
    b += c
  elif x == "C":
    c += d
  a %= mod; b %= mod; c %= mod; d %= mod
print(a)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
MOD = 10**9 + 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: Accepted

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]
  
  for j in range(4):
    dp[i][j] = dp[i][j] % 1000000007
  
print(int(dp[-1][-1]))

Submission status: Accepted

Solution code:
S = 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][0] + dp[i][1]) % 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][1] + dp[i][2]) % 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][2] + dp[i][3]) % MOD
    
    if S[i] == '?':
        dp[i+1][0] = 3 * dp[i][0] % MOD
        dp[i+1][1] = (dp[i][0] + 3 * dp[i][1]) % MOD
        dp[i+1][2] = (dp[i][1] + 3 * dp[i][2]) % MOD
        dp[i+1][3] = (dp[i][2] + 3 * dp[i][3]) % MOD

print(dp[N][3] % MOD)

Submission status: Accepted

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

l = len(S)
nAB = [0]*(l+1)
nA = [0]*(l+1)
nB = [0]*(l+1)
nC = [0]*(l+1)
nABC = [0]*(l+1)

add = 1
for i,s in enumerate(S):
    if s == '?':
        nA[i+1] = 3*nA[i] + add
        nB[i+1] = 3*nB[i] + add
        nC[i+1] = 3*nC[i] + add
        nAB[i+1] = 3*nAB[i] + nA[i]
        nABC[i+1] = 3*nABC[i] + nAB[i]
        add = (add * 3) % MOD
    if s == 'A':
        nA[i+1] = nA[i] + add
        nB[i+1] = nB[i]
        nC[i+1] = nC[i]
        nAB[i+1] = nAB[i]
        nABC[i+1] = nABC[i]
    if s == 'B':
        nA[i+1] = nA[i]
        nB[i+1] = nB[i] + add
        nC[i+1] = nC[i]
        nAB[i+1] = nAB[i] + nA[i]
        nABC[i+1] = nABC[i]
    if s == 'C':
        nA[i+1] = nA[i]
        nB[i+1] = nB[i]
        nC[i+1] = nC[i] + add
        nAB[i+1] = nAB[i]
        nABC[i+1] = nABC[i] + nAB[i]
    nA[i+1] = nA[i+1] % MOD
    nB[i+1] = nB[i+1] % MOD
    nC[i+1] = nC[i+1] % MOD
    nAB[i+1] = nAB[i+1] % MOD
    nABC[i+1] = nABC[i+1] % MOD

print(nABC[l] % MOD)

Submission status: Accepted

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

suma,sumc,sumq=0,0,0
maxC=S.count("C")%mod
maxQ=S.count("?")%mod
ans1,ans2,ans3,ans4=0,0,0,0

for i,s in enumerate(S):
  if s=="A":
    suma+=1
    suma%=mod
  elif s=="C":
    sumc+=1
    sumc%=mod
  elif s=="?":
    sumq+=1
    sumq%=mod
  
  if i==0 or i==len(S):
    continue
  
  if s=="?":
    ans2+=suma    *(maxC-sumc)%mod
    ans3+=(sumq-1)*(maxC-sumc)%mod
    ans3+=suma    *(maxQ-sumq)%mod
    ans4+=(sumq-1)*(maxQ-sumq)%mod
  elif s=="B":
    ans1+=suma*(maxC-sumc)%mod
    ans2+=sumq*(maxC-sumc)%mod
    ans2+=suma*(maxQ-sumq)%mod
    ans3+=sumq*(maxQ-sumq)%mod
    
ans1*=3**maxQ%mod
ans2*=3**(maxQ-1)%mod
ans3*=3**(maxQ-2)%mod
ans4*=3**(maxQ-3)%mod
ans=ans1+ans2+ans3+ans4
print(int(ans%mod))

Submission status: Accepted

Solution code:
S = input()
nQ_r = S.count('?')
nC_r = S.count('C')
nQ_l = 0
nA_l = 0
N = len(S)
mod = 10**9+7

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

ans = 0
for n, c in enumerate(S):
    if c=='C': nC_r-=1
    if c=='?': nQ_r-=1
    
    if n>0 and n<N-1 and (c=='B' or c=='?'):
        p = ( nQ_l*pow3[max(0, nQ_l-1)] + nA_l*pow3[nQ_l] ) % mod
        q = ( nQ_r*pow3[max(0, nQ_r-1)] + nC_r*pow3[nQ_r] ) % mod
        ans += p * q
        ans %= mod

    if c=='A': nA_l+=1
    if c=='?': nQ_l+=1

print(ans)

Submission status: Accepted

Solution code:
def examA():
    R = I()
    if R<1200:
        ans = "ABC"
    elif R<2800:
        ans = "ARC"
    else:
        ans = "AGC"
    print(ans)
    return

def examB():
    S = SI(); N = len(S)
    ans = "AC"
    if not S[0]=="A":
        ans = "WA"
    flag = False
    for i in range(2,N-1):
        if S[i]=="C":
            flag = True
    if not flag:
        ans = "WA"
    num = 0
    for i in S:
        if ord("A")<=ord(i)<=ord('Z'):
            num +=1
    if not num==2:
        ans = "WA"
    print(ans)
    return

def examC():
    return

def examD():
    S = SI(); N = len(S)
    dp = [[0]*4 for _ in range(N+1)]
    dp[0][0] = 1
    for i in range(N):
        C = S[i]
        if C=="?":
            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]
        elif C=="A":
            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][3] = dp[i][3]
        elif C=="B":
            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][3] = dp[i][3]
        elif C=="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][3] = dp[i][3] + dp[i][2]
        for j in range(4):
            dp[i+1][j] %=mod
    ans = dp[-1][3]
    print(ans)
    return


import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examD()

Submission status: Accepted

Solution code:
D=[0,0,0,1,0]
for s in input():D=[(D[j]*((s=="?")*2+1)+D[j+1]*(s in t+"?"))%(10**9+7) for j,t in enumerate("CBA.")]+[0]
print(D[0])