Problem:


Score : 400 points

Problem Statement

The ABC number of a string T is the number of triples of integers (i, j, k) that satisfy all of the following conditions:

1 ≤ i < j < k ≤ |T| (|T| is the length of T.)

T_i = A (T_i is the i-th character of T from the beginning.)

T_j = B

T_k = C

For example, when T = ABCBC, there are three triples of integers (i, j, k) that satisfy the conditions: (1, 2, 3), (1, 2, 5), (1, 4, 5). Thus, the ABC number of T is 3.

You are given a string S. Each character of S is A, B, C or ?.

Let Q be the number of occurrences of ? in S. We can make 3^Q strings by replacing each occurrence of ? in S with A, B or C. Find the sum of the ABC numbers of all these strings.

This sum can be extremely large, so print the sum modulo 10^9 + 7.

Constraints

3 ≤ |S| ≤ 10^5

Each character of S is A, B, C or ?.

Input

Input is given from Standard Input in the following format:

S

Output

Print the sum of the ABC numbers of all the 3^Q strings, modulo 10^9 + 7.

Sample Input 1

A??C

Sample Output 1

8

In this case, Q = 2, and we can make 3^Q = 9 strings by by replacing each occurrence of ? with A, B or C. The ABC number of each of these strings is as follows:

AAAC: 0

AABC: 2

AACC: 0

ABAC: 1

ABBC: 2

ABCC: 2

ACAC: 0

ACBC: 1

ACCC: 0

The sum of these is 0 + 2 + 0 + 1 + 2 + 2 + 0 + 1 + 0 = 8, so we print 8 modulo 10^9 + 7, that is, 8.

Sample Input 2

ABCBC

Sample Output 2

3

When Q = 0, we print the ABC number of S itself, modulo 10^9 + 7. This string is the same as the one given as an example in the problem statement, and its ABC number is 3.

Sample Input 3

????C?????B??????A???????

Sample Output 3

979596887

In this case, the sum of the ABC numbers of all the 3^Q strings is 2291979612924, and we should print this number modulo 10^9 + 7, that is, 979596887.



Sample input:
A??C


Sample output:
8

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
s = input()
n = len(s)
dp = [[0] * 4 for _ in range(n + 1)]
dp[0][0] = 1
for i in range(n):
  if s[i] == '?':
    dp[i + 1][0] += dp[i][0] * 3
    dp[i + 1][0] %= MOD
  else:
    dp[i + 1][0] += dp[i][0]
  for j in range(3):
    if s[i] == 'ABC'[j] or s[i] == '?':
      dp[i + 1][j + 1] += dp[i][j]
    dp[i + 1][j + 1] += dp[i][j + 1] * (3 if s[i] == '?' else 1)
    dp[i + 1][j + 1] %= MOD
print(dp[n][3] % MOD)

Submission status: Accepted

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

list_=[[0,0,0,0]]*(N+1)
for cur in range(N,-1,-1):
    for i in range(4):
        if cur==N:
            if i==3:
                list_[N][i]=1
            else:
                list_[N][i]=0
        else:
            if S[cur]=='ABCD'[i]:
                list_[cur][i]=(list_[cur+1][i+1]+list_[cur+1][i])%mod
            elif S[cur]=='?' and i!=3:
                list_[cur][i]=(list_[cur+1][i+1]+3*list_[cur+1][i])%mod
            elif S[cur]=='?':
                list_[cur][i]=3*list_[cur+1][i]%mod
            else:
                list_[cur][i]=list_[cur+1][i]%mod

print(list_[0][0]%mod)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
s=input()
n=len(s)
q=s.count("?")
mod=10**9+7
def f(x,y,z):
  DP=[[0]*3 for _ in range(n+1)]
  for i in range(n):
    if s[i]==x:
      DP[i+1][0]=DP[i][0]+1
    else:
      DP[i+1][0]=DP[i][0]
    if s[i]==y:
      DP[i+1][1]=DP[i][1]+DP[i][0]
    else:
      DP[i+1][1]=DP[i][1]
    if s[i]==z:
      DP[i+1][2]=DP[i][2]+DP[i][1]
    else:
      DP[i+1][2]=DP[i][2]
  return DP[n][2]
ans=0
ans+=f("A","B","C")*3**q%mod
if q>=1:
  ans+=f("?","B","C")*3**(q-1)%mod
  ans+=f("A","?","C")*3**(q-1)%mod
  ans+=f("A","B","?")*3**(q-1)%mod
if q>=2:
  ans+=f("A","?","?")*3**(q-2)%mod
  ans+=f("?","B","?")*3**(q-2)%mod
  ans+=f("?","?","C")*3**(q-2)%mod
if q>=3:
  ans+=f("?","?","?")*3**(q-3)%mod
print(ans%mod)

Submission status: Accepted

Solution code:
S=input()
N = len(S)
A = [0]*N
C = [0]*N
L = [0]*N
R = [0]*N
for i in range(1,N):
    A[i] = A[i-1] + (S[i-1] == "A")
    L[i] = L[i-1] + (S[i-1] == "?")
    C[N-1-i] = C[N-i] + (S[N-i] == "C")
    R[N-1-i] = R[N-i] + (S[N-i] == "?")
mod = 10**9+7
d={0:1}
def pow_mod(x,n):
    if d.get(n,False) :return d[n]
    if n<0: return pow_mod(x,mod-1+n)
    if n%2  :
        d[n] = (x*pow_mod(x,n-1))%mod
    else:
        d[n] = (pow_mod(x,n//2)**2)%mod
    return d[n]
ans = 0
for i in range(1,N-1):
    if S[i] in "B?":
        ans += (3*A[i]+L[i])*(3*C[i]+R[i])*pow_mod(3,L[i]+R[i]-2)
        ans %= mod
print(ans)

Submission status: Accepted

Solution code:
"""
We Love ABC
DP使う問題
T : 文字列
i < j < k < len(T)
Ti = "A"
Tj = "B"
Tk = "C"
i j k の順で取れたら、1カウント
- TはA, B, C, ? で構成される
- ? は　ABC のいずれか
これらを満たす場合の数

i番目の文字において、ABCのどこまで進んだか
null:   0
A   :   1
B   :   2
C   :   3

?の扱いが厄介
?があると単純に選択肢が3倍になる
A? -> AA, AB, AC
B? -> BA, BB, BC
まだ選んでいない時 : 入力の選択肢が3倍に増える
dp[i+1][1]: 
    すでにAを選んでいる時 : iまでのAの選び方が3倍に増えるので、dp[i][1]*3
    何も選んでいない場合  : ?がAになれるので、dp[i][0]を加える
ほかも同じ
"""
mod = 10**9 + 7

S = input()
N = len(S)
dp = [[0]*4 for i in range(100800)]
dp[0][0] = 1
for i in range(N):
    s = S[i]
    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] 
    if s == "A":
        # Aを選ぶ選択肢がそれまでのA,?分増える
        dp[i+1][1] += dp[i][0]
    if s == "B":
        # Bを選ぶ選択肢がそれまでのAの選択肢分増える
        dp[i+1][2] = dp[i][2] + dp[i][1] 
    if s == "C":
        # Cを選ぶ選択肢がBまでを選んだ分だけ増える
        dp[i+1][3] = dp[i][3] + dp[i][2]
    if s == "?":
        # ?を選んだ場合。選択肢は3倍に広がる
        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
        
# Cまで行った数を求める
print(dp[N][3]%mod)

Submission status: Accepted

Solution code:
mod = 10**9+7
S = input()
A = 0
AB = 0
ABC = 0

N = 1
for i in range(len(S)):
    if S[i] == 'A':
        A += N
    elif S[i] == 'B':
        AB += A
    elif S[i] == 'C':
        ABC += AB
    else:
        ABC = 3*ABC + AB
        AB = 3*AB + A 
        A = 3*A + N
        N *= 3
    A %= mod
    AB %= mod
    ABC %= mod
    N %= mod

print(ABC)

Submission status: Accepted

Solution code:
from itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

S = input()
l = len(S)
d = {"A":1,"B":2,"C":3}

dp = [0 for _ in range(4)]
dp[0] = 1
for i in range(l):
    if S[i] == "?":
        dp = [dp[0]*3,dp[1]*3+dp[0],dp[2]*3+dp[1],dp[3]*3+dp[2]]
        for j in range(4):
            dp[j] %= mod
    else:
        j = d[S[i]]
        dp[j] += dp[j-1] % mod

print(dp[3]%mod)

Submission status: Accepted

Solution code:
s = input().strip()
MOD = pow(10, 9) + 7
# dp: dp[0][...] = ABCカウントを更新しない時の数
# dp: dp[1][...] = Aまで合わせた時の数
# dp: dp[2][...] = Bまで合わせた時の数
# dp: dp[3][...] = Cまで合わせた時の数
dp = [[0 for _ in range(len(s) + 1)] for _ in range(4)]
dp[0][0] = 1

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

print(dp[3][-1])

Submission status: Accepted

Solution code:
S = input()

A = [0]
C = [0]
Q = [0]
a=0
c=0
q=0
for i in range(len(S)):
    if S[i]=="A":
        a+=1
    if S[i]=="C":
        c+=1
    if S[i]=="?":
        q+=1
    A.append(a)
    C.append(c)
    Q.append(q)

a = 1
a0 = 1
a1 = 1
a2 = 1
a3 = 1
for i in range(Q[len(S)]):
    a = (a*3)%(10**9 + 7)
    if i==Q[len(S)]-4:
        a3 = a
    elif i==Q[len(S)]-3:
        a2 = a
    elif i==Q[len(S)]-2:
        a1 = a
    elif i==Q[len(S)]-1:
        a0 = a

count = 0
for i in range(1,len(S)):
    if S[i]=="B":
        count=(count+a0*A[i]*(C[len(S)]-C[i+1])+a1*A[i]*(Q[len(S)]-Q[i+1])+a1*Q[i]*(C[len(S)]-C[i+1])+a2*Q[i]*(Q[len(S)]-Q[i+1]))%(10**9 + 7)
    elif S[i]=="?":
        count=(count+a1*A[i]*(C[len(S)]-C[i+1])+a2*A[i]*(Q[len(S)]-Q[i+1])+a2*Q[i]*(C[len(S)]-C[i+1])+a3*Q[i]*(Q[len(S)]-Q[i+1]))%(10**9 + 7)
print(count)

Submission status: Accepted

Solution code:
import sys
# input = sys.stdin.readline
S = list(input())
p = 10 ** 9 + 7
# p = 10 ** 18

A = AB = ABC = 0
power = 1
for i, Si in enumerate(S):
    # print("#", A, AB, ABC)
    if Si == 'A':
        A = (A + 1 * power) % p
    elif Si == 'B':
        AB = (AB + A) % p
    elif Si == 'C':
        ABC = (ABC + AB) % p
    else:
        ABC = (3 * ABC + AB) % p
        AB = (3 * AB + A) % p
        A = (3 * A + 1 * power) % p
        power = (power * 3) % p

print(ABC)

Submission status: Accepted

Solution code:
S = input()

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

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

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

Submission status: Accepted

Solution code:



def main():
    data = list(input())
    # dp = [[0 for i in range(4)] for i in range(len(data) + 1)]
    # dp[len(data)][3] += 1

    dp = [0, 0, 0, 1]
    mod = 10 ** 9 + 7

    dic = {0:'A', 1:'B', 2:'C'}
    for i in range(len(data))[::-1]:
        element = data[i]
        for j in range(4):
            if j == 3:
                if element == '?':
                    dp[j] *= 3
            else:
                if dic[j] == element:
                    dp[j] += dp[j + 1]

                elif element == '?':
                    dp[j] = dp[j] * 3 + dp[j + 1]

            dp[j] %= mod



    print(dp[0] % mod)





if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
S = input()
MOD = 10**9+7

a, b, c , d = 0, 0, 0, 1

for s in S:
    if s == 'A':
        a += d
        a %= MOD
    elif s == 'B':
        b += a
        b %= MOD
    elif s == 'C':
        c += b
        c %= MOD
    else:
        a, b, c, d = 3*a+d, 3*b+a, 3*c+b, 3*d
        a %= MOD
        b %= MOD
        c %= MOD
        d %= MOD
ans = c
print(ans)

Submission status: Accepted

Solution code:
S = input().strip()
mod = 10**9+7
dp = [1] + [0]*3
for s in S:
    dp1 = dp[:]
    if s == 'A':
        dp1[1] += dp[0]
    elif s == 'B':
        dp1[2] += dp[1]
    elif s == 'C':
        dp1[3] += dp[2]
    else:
        dp1[1] += dp[0]
        dp1[2] += dp[1]
        dp1[3] += dp[2]
        dp1[0] += 2*dp[0]
        dp1[1] += 2*dp[1]
        dp1[2] += 2*dp[2]
        dp1[3] += 2*dp[3]
    dp = [d % mod for d in dp1]
print(dp[-1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
try:
    from math import gcd
except Exception:
    from fractions import gcd

MOD = 1000000007  # type: int

def solve(S: str):
    dp = [[0] * 5 for _ in range(len(S) + 1)]
    dp[0][1] = 1

    for i, s in enumerate(S):
        for j, a in enumerate('_ABC', 1):
            dp[i+1][j] = (3 * dp[i][j]) if s == '?' else dp[i][j]
            if s == a or s == '?':
                dp[i+1][j] += dp[i][j-1]
            dp[i+1][j] %= MOD
    return dp[-1][-1] % MOD


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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
try:
    from math import gcd
except Exception:
    from fractions import gcd

MOD = 1000000007  # type: int

def solve(S: str):
    dp = [[0] * 4 for _ in range(len(S) + 1)]
    dp[0][0] = 1

    for i, s in enumerate(S):
        for j, a in enumerate('_ABC'):
            dp[i+1][j] = dp[i][j]
            if s == '?':
                dp[i+1][j] = 3 * dp[i][j] + (dp[i][j-1] if 1 <= j else 0)
            if s == a:
                dp[i+1][j] += dp[i][j-1]
            dp[i+1][j] %= MOD
    return dp[-1][-1] % MOD


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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
mod=1000000007

s=input()
x=len(s)
dp=[[0 for i in range(4)] for j in range(100005)]
for i in range(x,-1,-1):
    for j in range(3,-1,-1):
        if i==x:
            dp[i][j]=[0,1][j==3]
        else:
            dp[i][j]=dp[i+1][j]*([1,3][s[i]=="?"])
            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:
import sys, os

f = lambda:list(map(int,input().split()))
if 'local' in os.environ :
    sys.stdin = open('./input.txt', 'r')

def solve():
    s = input()
    slen = len(s)
    cnt = [0] * 4
    mod = 1000*1000*1000+7
    cnt[0] = 1
    for i in range(slen):
        if s[i] == 'A':
            cnt[1] += cnt[0]
        elif s[i] == 'B':
            cnt[2] += cnt[1]
        elif s[i] == 'C':
            cnt[3] += cnt[2]
        else:
            cnt[0], cnt[1], cnt[2], cnt[3] =  3*cnt[0], 3*cnt[1] + cnt[0] , 3*cnt[2] + cnt[1], 3*cnt[3] + cnt[2]


        cnt[0]%= mod
        cnt[1]%= mod
        cnt[2]%= mod
        cnt[3]%= mod
    
    print(cnt[3])

solve()

Submission status: Accepted

Solution code:
S = input()
MOD = 10**9 + 7
# A,B,Cまで作れた個数、および保留中
a,b,c,d = 0,0,0,1

for s in S:
  if s == 'A':
    a += d
    a %= MOD
  elif s == 'B':
    b += a
    b %= MOD
  elif s == 'C':
    c += b
    c %= MOD
  else:
    # 使わなかった ? 分も増える
    a,b,c,d = 3*a+d,3*b+a,3*c+b,3*d
    a %= MOD
    b %= MOD
    c %= MOD
    d %= MOD

answer = c
print(c)

Submission status: Accepted

Solution code:
def solve(string):
    s = string.replace("?", "d").lower()
    n = len(s)
    dp = [[0] * (n + 1) for _ in range(4)]
    dp[0][0] = 1
    mod = 10**9 + 7
    for i, _s in enumerate(s):
        dp[0][i + 1] = dp[0][i] % mod
        dp[1][i + 1] = dp[1][i] % mod
        dp[2][i + 1] = dp[2][i] % mod
        dp[3][i + 1] = dp[3][i] % mod
        if _s == "d":
            dp[0][i + 1] *= 3
            dp[1][i + 1] *= 3
            dp[2][i + 1] *= 3
            dp[3][i + 1] *= 3
        if _s in ["a", "d"]:
            dp[1][i + 1] += dp[0][i]
        if _s in ["b", "d"]:
            dp[2][i + 1] += dp[1][i]
        if _s in ["c", "d"]:
            dp[3][i + 1] += dp[2][i]
    return str(int(dp[3][-1] % (10**9 + 7)))


if __name__ == '__main__':
    print(solve(input()))

Submission status: Accepted

Solution code:
def solve(string):
    s = string.replace("?", "d").lower()
    n = len(s)
    dp = [[0] * (n + 1) for _ in range(4)]
    dp[0][0] = 1
    mod = 10**9 + 7
    for i, _s in enumerate(s):
        dp[0][i + 1] = dp[0][i] % mod
        dp[1][i + 1] = dp[1][i] % mod
        dp[2][i + 1] = dp[2][i] % mod
        dp[3][i + 1] = dp[3][i] % mod
        if _s == "a":
            dp[1][i + 1] += dp[0][i]
        if _s == "b":
            dp[2][i + 1] += dp[1][i]
        if _s == "c":
            dp[3][i + 1] += dp[2][i]
        if _s == "d":
            dp[0][i + 1] *= 3
            dp[1][i + 1] *= 3
            dp[1][i + 1] += dp[0][i]
            dp[2][i + 1] *= 3
            dp[2][i + 1] += dp[1][i]
            dp[3][i + 1] *= 3
            dp[3][i + 1] += dp[2][i]
    return str(int(dp[3][-1] % (10**9 + 7)))


if __name__ == '__main__':
    print(solve(input()))

Submission status: Accepted

Solution code:
S = input()

# dp[i][n] := i文字目までのNONE,A,AB,ABCを決めた数
dp = [[0]*4 for i in range(len(S)+1)]
NO, A, AB, ABC = 0, 1, 2, 3
MOD = 10**9+7
dp[0][NO] = 1
for i in range(len(S)):
    # カウントを進めない時
    for j in range(4):
        if S[i] == "?":
            dp[i+1][j] += dp[i][j]*3
        else:
            dp[i+1][j] += dp[i][j]
    # それ以外
    if S[i] == "A" or S[i] == "?":
        dp[i+1][A] += dp[i][NO]
    if S[i] == "B" or S[i] == "?":
        dp[i+1][AB] += dp[i][A]
    if S[i] == "C" or S[i] == "?":
        dp[i+1][ABC] += dp[i][AB]
    for j in range(4):
        dp[i+1][j] %= MOD
    
print(dp[len(S)][ABC])

Submission status: Accepted

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

MOD = 1000000007  # type: int

def solve(S: str):
    total = 0
    for s in S:
        if s == '?':
            total += 1
    tri = [1]
    for i in range(1, total + 1):
        tri.append(tri[i - 1] * 3 % MOD)
    n = len(S)
    dp = [[0] * 4 for _ in range(n + 1)]
    cnt = 0
    for i in range(n):
        s = S[i]
        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]
        if s == '?':
            dp[i + 1][1] = dp[i][1] + 1
            dp[i + 1][2] = (dp[i][2] * 3 + dp[i][0] * tri[cnt] + dp[i][1] * tri[cnt - 1]) % MOD
            dp[i + 1][3] = (dp[i][3] + dp[i][2] * tri[total - cnt - 1]) % MOD
            cnt += 1
        elif s == 'A':
            dp[i + 1][0] = dp[i][0] + 1
        elif s == 'B':
            dp[i + 1][2] = (dp[i][2] + dp[i][0] * tri[cnt] + dp[i][1] * tri[cnt - 1]) % MOD
        elif s == 'C':
            dp[i + 1][3] = (dp[i][3] + dp[i][2] * tri[total - cnt]) % MOD
    #print(dp)
    ret = dp[n][3] % MOD
    print(ret)
    return


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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

MOD = 1000000007  # type: int

def solve(S: str):
    total = 0
    for s in S:
        if s == '?':
            total += 1
    tri = [1]
    for i in range(1, total + 1):
        tri.append(tri[i - 1] * 3 % MOD)
    n = len(S)
    dp = [[0] * 4 for _ in range(n + 1)]
    cnt = 0
    for i in range(n):
        s = S[i]
        #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]
        if s == '?':
            dp[i + 1][0] = dp[i][0]
            dp[i + 1][1] = dp[i][1] + 1
            dp[i + 1][2] = (dp[i][2] * 3 + dp[i][0] * tri[cnt] + dp[i][1] * tri[cnt - 1]) % MOD
            dp[i + 1][3] = (dp[i][3] + dp[i][2] * tri[total - cnt - 1]) % MOD
            cnt += 1
        elif s == '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][3] = dp[i][3]
        elif s == 'B':
            dp[i + 1][0] = dp[i][0]
            dp[i + 1][1] = dp[i][1]
            dp[i + 1][2] = (dp[i][2] + dp[i][0] * tri[cnt] + dp[i][1] * tri[cnt - 1]) % MOD
            dp[i + 1][3] = dp[i][3]
        elif s == '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] * tri[total - cnt]) % MOD
    #print(dp)
    ret = dp[n][3] % MOD
    print(ret)
    return


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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
###############################################################################

from sys import stdout
from bisect import bisect_left as binl
from copy import copy, deepcopy
from collections import defaultdict


mod = 1


def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return tuple(map(int, input_tuple))


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def modadd(x, y):
    global mod
    return (x + y) % mod


def modmlt(x, y):
    global mod
    return (x * y) % mod


def lcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


def combination(x, y):
    assert(x >= y)

    if y > x // 2:
        y = x - y

    ret = 1

    for i in range(0, y):
        j = x - i
        i = i + 1

        ret = ret * j
        ret = ret // i

    return ret


def get_divisors(x):
    retlist = []
    for i in range(1, int(x**0.5) + 3):
        if x % i == 0:
            retlist.append(i)
            retlist.append(x // i)
    return retlist


def get_factors(x):
    retlist = []
    for i in range(2, int(x**0.5) + 3):
        while x % i == 0:
            retlist.append(i)
            x = x // i
    retlist.append(x)
    return retlist


def make_linklist(xylist):
    linklist = {}
    for a, b in xylist:
        linklist.setdefault(a, [])
        linklist.setdefault(b, [])
        linklist[a].append(b)
        linklist[b].append(a)
    return linklist


def calc_longest_distance(linklist, v=1):
    distance_list = {}
    distance_count = 0
    distance = 0
    vlist_previous = []
    vlist = [v]
    nodecount = len(linklist)

    while distance_count < nodecount:
        vlist_next = []
        for v in vlist:
            distance_list[v] = distance
            distance_count += 1
            vlist_next.extend(linklist[v])
        distance += 1
        vlist_to_del = vlist_previous
        vlist_previous = vlist
        vlist = list(set(vlist_next) - set(vlist_to_del))

    max_distance = -1
    max_v = None
    for v, distance in distance_list.items():
        if distance > max_distance:
            max_distance = distance
            max_v = v

    return (max_distance, max_v)


def calc_tree_diameter(linklist, v=1):
    _, u = calc_longest_distance(linklist, v)
    distance, _ = calc_longest_distance(linklist, u)
    return distance


###############################################################################


mod = 10**9 + 7


def main():
    s = input()

    qsum = 0
    for c in s:
        if c == '?':
            qsum += 1

    ccount = defaultdict(int)
    qcount = defaultdict(int)

    for i in reversed(range(len(s))):
        if s[i] == 'C':
            ccount[i] = modadd(ccount[i+1], 1)
            qcount[i] = qcount[i+1]
        elif s[i] == '?':
            ccount[i] = ccount[i+1]
            qcount[i] = modadd(qcount[i+1], 1)
        else:
            ccount[i] = ccount[i+1]
            qcount[i] = qcount[i+1]

    bccount = defaultdict(int)
    qccount = defaultdict(int)
    bqcount = defaultdict(int)
    qqcount = defaultdict(int)

    for i in reversed(range(len(s) - 1)):
        if s[i] == 'A' or s[i] == 'C':
            bccount[i] = bccount[i+1]
            qccount[i] = qccount[i+1]
            bqcount[i] = bqcount[i+1]
            qqcount[i] = qqcount[i+1]
        elif s[i] == 'B':
            bccount[i] = modadd(bccount[i+1], ccount[i+1])
            qccount[i] = qccount[i+1]
            bqcount[i] = modadd(bqcount[i+1], qcount[i+1])
            qqcount[i] = qqcount[i+1]
        elif s[i] == '?':
            bccount[i] = bccount[i+1]
            qccount[i] = modadd(qccount[i+1], ccount[i+1])
            bqcount[i] = bqcount[i+1]
            qqcount[i] = modadd(qqcount[i+1], qcount[i+1])

    ans = 0

    for i in range(len(s) - 2):
        if s[i] == 'A':
            if bccount[i+1]:
                ans = modadd(ans, modmlt(bccount[i+1], pow(3, qsum, mod)))
            if qccount[i+1]:
                ans = modadd(ans, modmlt(qccount[i+1], pow(3, qsum - 1, mod)))
            if bqcount[i+1]:
                ans = modadd(ans, modmlt(bqcount[i+1], pow(3, qsum - 1, mod)))
            if qqcount[i+1]:
                ans = modadd(ans, modmlt(qqcount[i+1], pow(3, qsum - 2, mod)))
        if s[i] == '?':
            if bccount[i+1]:
                ans = modadd(ans, modmlt(bccount[i+1], pow(3, qsum - 1, mod)))
            if qccount[i+1]:
                ans = modadd(ans, modmlt(qccount[i+1], pow(3, qsum - 2, mod)))
            if bqcount[i+1]:
                ans = modadd(ans, modmlt(bqcount[i+1], pow(3, qsum - 2, mod)))
            if qqcount[i+1]:
                ans = modadd(ans, modmlt(qqcount[i+1], pow(3, qsum - 3, mod)))

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
s=input()
a_count=[0]
c_count=[0]
q_lcount=[0]
q_rcount=[0]
n=len(s)
for i in range(n):
    if s[i]=='A':
        a_count.append(a_count[i]+1)
        q_lcount.append(q_lcount[i])
    elif s[i]=='?':
        a_count.append(a_count[i])
        q_lcount.append(q_lcount[i]+1)
    else:
        a_count.append(a_count[i])
        q_lcount.append(q_lcount[i])
    if s[n-1-i]=='C':
        c_count.append(c_count[i]+1)
        q_rcount.append(q_rcount[i])
    elif s[n-1-i]=='?':
        c_count.append(c_count[i])
        q_rcount.append(q_rcount[i]+1)
    else:
        c_count.append(c_count[i])
        q_rcount.append(q_rcount[i])
q=q_lcount[n]
ans=0
INF=10**9+7
a=3**q
b=a//3
c=b//3
d=c//3
a=a%INF
b=b%INF
c=c%INF
d=d%INF
for i in range(n):
    if s[i]=='B':
        x=a_count[i]*c_count[n-1-i]*a
        y=a_count[i]*q_rcount[n-1-i]*b
        z=q_lcount[i]*c_count[n-1-i]*b
        w=q_lcount[i]*q_rcount[n-1-i]*c
        ans=(ans+x+y+z+w)%INF
    elif s[i]=='?':
        x=a_count[i]*c_count[n-1-i]*b
        y=a_count[i]*q_rcount[n-1-i]*c
        z=q_lcount[i]*c_count[n-1-i]*c
        w=q_lcount[i]*q_rcount[n-1-i]*d
        ans=(ans+x+y+z+w)%INF
print(int(ans))

Submission status: Accepted

Solution code:
S = input()
dp = [[0 for i in range(4)] for i in range(len(S)+1)]
MOD = 10**9+7
dp[0][3] = 1
for i in range(len(S)):
    if S[i] == '?': k = 3
    else: k = 1
    for _ in range(k):
        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] 
    if S[i] == 'A':
        dp[i+1][0] +=  dp[i][3]
    elif S[i] == 'B':
        dp[i+1][1] +=  dp[i][0]
    elif S[i] == 'C':
        dp[i+1][2] += dp[i][1]
    else:
        dp[i+1][0] += dp[i][3]
        dp[i+1][1] += dp[i][0]
        dp[i+1][2] += dp[i][1]
    for j in range(4):
        if dp[1+i][j] > MOD: dp[i+1][j] %= MOD
print(dp[len(S)][2]%MOD)

Submission status: Accepted

Solution code:
s=input()
import numpy as np
dp=np.zeros((len(s)+1,4),dtype=np.int64)
dp[0][0]=1
mod=10**9+7
for i in range(len(s)):
    if s[i]=='?':
        dp[i+1]=dp[i]*3
        dp[i+1][1:]+=dp[i][:3]
        dp[i+1]%=mod
    else:
        dp[i+1]=dp[i]
        j=ord(s[i])-ord('A')
        dp[i+1][j+1]=(dp[i+1][j+1]+dp[i][j])%mod
print(dp[-1][3])

Submission status: Accepted

Solution code:
#coding:utf-8
S=raw_input()

all=1
a=ab=abc=0
MOD=(10**9)+7
for _ in range(len(S)):
    i=_+1
    c=S[_]
    if c=="A":
        a+=all
    if c=="B":
        ab+=a
    if c=="C":
        abc+=ab
    if c=="?":
        abc=abc*3+ab
        ab=ab*3+a
        a=a*3+all
        all*=3
    a%=MOD
    ab%=MOD
    abc%=MOD
    all%=MOD
print(abc%((10**9)+7))

Submission status: Accepted

Solution code:
# Input
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

s = ns()
t = len(s)

a__ = [0]*(t+1)
ab_ = [0]*(t+1)
abc = [0]*(t+1)

MOD = 10**9 + 7
q = 0
for i, si in enumerate(s):
    if si == 'A':
        a__[i+1] = a__[i] + pow(3,q,MOD)
        ab_[i+1] = ab_[i]
        abc[i+1] = abc[i]

    elif si == 'B':
        a__[i+1] = a__[i]
        ab_[i+1] = ab_[i] + a__[i]
        abc[i+1] = abc[i]

    elif si == 'C':
        a__[i+1] = a__[i]
        ab_[i+1] = ab_[i]
        abc[i+1] = abc[i] + ab_[i]

    elif si == '?':
        a__[i+1] = 3 * a__[i] + pow(3,q,MOD)
        ab_[i+1] = 3 * ab_[i] + a__[i]
        abc[i+1] = 3 * abc[i] + ab_[i]

        q += 1


    a__[i + 1] %= MOD
    ab_[i + 1] %= MOD
    abc[i + 1] %= MOD

print(abc[t])

Submission status: Accepted

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

dp[0][0]=1
for i in range(1,len(dp)):
    if S[i-1]!="?":
        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 S[i-1]=="A":
            dp[i][1]+=dp[i-1][0]
        if S[i-1]=="B":
            dp[i][2]+=dp[i-1][1]
        if S[i-1]=="C":
            dp[i][3]+=dp[i-1][2]
        dp[i][0]%=mod
        dp[i][1]%=mod
        dp[i][2]%=mod
        dp[i][3]%=mod
    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]
        dp[i][0]%=mod
        dp[i][1]%=mod
        dp[i][2]%=mod
        dp[i][3]%=mod
print(dp[len(S)][3])

Submission status: Accepted

Solution code:
s = input()

ans = 0

rc = [0]
rq = [0]
la = [0]
lq = [0]
q3 = [1]
t = 10**9+7

for i in range(len(s)-1):
    if s[len(s)-i-1]=='C':
        rc.append(rc[-1]+1)
        rq.append(rq[-1])
    elif s[len(s)-i-1]=='?':
        rc.append(rc[-1])
        rq.append(rq[-1]+1)
    else:
        rc.append(rc[-1])
        rq.append(rq[-1])
    if s[i]=='A':
        la.append(la[-1]+1)
        lq.append(lq[-1])
    elif s[i]=='?':
        la.append(la[-1])
        lq.append(lq[-1]+1)
    else:
        la.append(la[-1])
        lq.append(lq[-1])
    q3.append(q3[-1] * 3 % t)
rc.reverse()
rq.reverse()

q3.append(1/3)

for i in range(len(s)):
    if s[i]=='B' or s[i]=='?':
        l = q3[lq[i]-1]
        r = q3[rq[i]-1]
        ans += l*r*(3*la[i]+lq[i])*(3*rc[i]+rq[i]) % t

print(round(ans%t))