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:
#!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] + x) % mod
        else:
            dp[0] = (dp[0] * 3 + dp[1]) % mod
            dp[1] = (dp[1] * 3 + dp[2]) % mod
            dp[2] = (dp[2] * 3 + x) % mod
            x *= 3
            x %= mod
    print(dp[0])

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

Submission status: Accepted

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[2][N])

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
S = input()
d = "ABC".index
s = [0]*4
s[0] = 1
for c in S:
    if c == "?":
        s = [s[0]*3, s[1]*3 + s[0], s[2]*3 + s[1], s[3]*3 + s[2]]
        for i in range(4):s[i] %= MOD
    else:
        i = d(c)
        s[i+1] += s[i] % MOD
print(s[3] % MOD)

Submission status: Accepted

Solution code:
#22:24
s = input()
mod = 10 ** 9 + 7
cum = [[0],[0],[0],[0]]
for i in range(len(s)):
  tmp = ord(s[i]) - 65
  if tmp == -2:
    tmp = 3
  for j in range(4):
    if j == tmp:
      cum[j].append(cum[j][-1]+1)
    else:
      cum[j].append(cum[j][-1])
q = cum[3][-1]
tri = [1]
for _ in range(len(s)):
  tri.append(tri[-1] * 3 % mod)
ans = 0
for i in range(len(s)):
  if s[i] == 'B':
    ans += cum[0][i] * (cum[2][-1]-cum[2][i+1]) * tri[q]
    ans += cum[0][i] * (cum[3][-1]-cum[3][i+1]) * tri[q-1]
    ans += cum[3][i] * (cum[2][-1]-cum[2][i+1]) * tri[q-1]
    ans += cum[3][i] * (cum[3][-1]-cum[3][i+1]) * tri[q-2]
  if s[i] == '?':
    ans += cum[0][i] * (cum[2][-1]-cum[2][i+1]) * tri[q-1]
    ans += cum[0][i] * (cum[3][-1]-cum[3][i+1]) * tri[q-2]
    ans += cum[3][i] * (cum[2][-1]-cum[2][i+1]) * tri[q-2]
    ans += cum[3][i] * (cum[3][-1]-cum[3][i+1]) * tri[q-3]
  ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

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

S = str(input())
N = len(S)

h_all = 0
for i in range(N):
    if S[i]=='?':
        h_all += 1

a = 0
b = 0
h = 0
numAB = 0
numAH = 0
numHB = 0
numHH = 0
dp = [0]*N

beki3 = pow(3,h_all-3,mod) if h_all>=4 else 1
beki2 = beki3*3 % mod if h_all>=3 else 1
beki1 = beki2*3 %mod if h_all>=2 else 1
beki0 = beki1*3 %mod if h_all>=1 else 1

for i in range(N):
    if S[i]=='A':
        if i>=1:
            dp[i] = dp[i-1]
        a += 1
    elif S[i]=='B':
        if i>=1:
            dp[i] = dp[i-1]
        numAB += a
        numHB += h
        b += 1
    elif S[i]=='?':
        if i>=1:
            if h_all>=1:
                dp[i] = (dp[i-1]+numAB*beki1) %mod
            if h_all>=2:
                dp[i] = (dp[i]+numAH*beki2) %mod
                dp[i] = (dp[i]+numHB*beki2) %mod
            if h_all>=3:
                dp[i] = (dp[i]+numHH*beki3)%mod
        numAH += a
        numHH += h
        h += 1
    else:
        if i>=1:
            dp[i] = (dp[i-1]+numAB*beki0) %mod
            if h_all>=1:
                dp[i] = (dp[i]+numAH*beki1) %mod
                dp[i] = (dp[i]+numHB*beki1) %mod
            if h_all>=2:
                dp[i] = (dp[i]+numHH*beki2)%mod

print(dp[N-1])

Submission status: Accepted

Solution code:
def main():
    S = input()
    MOD = 10 ** 9 + 7
    a = 0
    ab = 0
    abc = 0
    # ?によって分岐する文字列の総数
    total = 1
    for s in S:
        if s == 'A':
            a += total
        elif s == 'B':
            ab += a
        elif s == 'C':
            abc += ab
        else:
            # abc実施しないと、足し算がおかしくなる
            abc = abc * 3 + ab
            ab = ab * 3 + a
            a = a * 3 + total
            total *= 3
        a %= MOD
        ab %= MOD
        abc %= MOD
        total %= MOD
    
    print(abc)


main()

Submission status: Accepted

Solution code:
import math
# N = int( input())

MOD = (10 ** 9) + 7
S = input()
dp = [ [ 0 for _ in range(4)]  for _ in range(len(S) + 1)]
dp[0][0] = 1
for i in range(len(S) ):
    if S[i] == "A":
        dp[i + 1][0] += dp[i][0]
        dp[i + 1][1] += (dp[i][0] + dp[i][1])
        dp[i + 1][2] += (dp[i][2])
        dp[i + 1][3] += dp[i][3]
    if S[i] == "B":
        dp[i + 1][0] += dp[i][0]
        dp[i + 1][1] +=dp[i][1]
        dp[i + 1][2] +=  (dp[i][1] + dp[i][2])
        dp[i + 1][3] +=dp[i][3]

    if 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][3] += (dp[i][2] + dp[i][3])

    if S[i] == "?":
        dp[i + 1][0] +=  (dp[i][0] * 3)
        dp[i + 1][1] += (dp[i][0] + (dp[i][1]) * 3)
        dp[i + 1][2] += (dp[i][1]+ (dp[i][2]) * 3)
        dp[i + 1][3] += (dp[i][2]+ (dp[i][3]) * 3)
    for j in range(0,4):
        dp[i + 1][j] %= MOD




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

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LIM(): return list(map(lambda x:int(x) - 1, sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def LIRM(n): return [LIM() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 1000000007


s = S()
n = 1
a = ab = abc = 0
for i in s:
    if i == 'A':
        a = (a + n) % mod
    elif i == 'B':
        ab = (ab + a) % mod
    elif i == 'C':
        abc = (abc + ab) % mod
    else:
        abc = (abc * 3 + ab) % mod
        ab = (ab * 3 + a) % mod
        a = (a * 3 + n) % mod
        n = n * 3 % mod





print(abc)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

S = [0] + list(input())
n = len(S) - 1

yet = [0] * (n+1)
a = [0] * (n+1)
ab = [0] * (n+1)
abc = [0] * (n+1)
#i番目まで見終わった後の考えられる手数

abc[n] = 1

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

print(yet[0])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    S = input()
    mod = pow(10, 9) + 7
    n = len(S)
    # print(S)
    countA, countAB, countABC = 0, 0, 0
    strA, strNonA = 0, 1
    for i in range(n):
        if S[i] == "A":
            countA += strNonA + strA
            strA += strNonA
            strNonA = 0
        elif S[i] == "B":
            countAB += countA
        elif S[i] == "C":
            countABC += countAB
        else:
            countABC = 3*countABC + countAB
            countAB = 3*countAB + countA
            countA = 3*countA + strNonA + strA
            strA = 3*strA + strNonA
            strNonA *= 2

        countA %= mod
        countAB %= mod
        countABC %= mod
        strA %= mod
        strNonA %= mod
        # print(countA, countAB, countABC, strA, strNonA)

    return countABC % mod

if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:

S = input()

lis = [1,0,0,0]
nlis = [1,0,0,0]

for s in S:

    if s == "?":

        nlis[0] += lis[0] * 2
        nlis[1] += lis[1] * 2
        nlis[2] += lis[2] * 2
        nlis[3] += lis[3] * 2

    if s == "A" or s == "?":

        nlis[1] += lis[0]

    if s == "B" or s == "?":

        nlis[2] += lis[1]

    if s == "C" or s == "?":

        nlis[3] += lis[2]

    lis = []
    for i in range(4):

        lis.append(nlis[i] % (10 ** 9 + 7))

print (lis[3]  % (10 ** 9 + 7))

Submission status: Accepted

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

    pre = [1, 0, 0, 0]

    MOD = int(1e9) + 7

    for i in range(len(s)):
        next_ = [pre[0], pre[1], pre[2], pre[3]]
        if s[i] == "A":
            next_[1] += pre[0]
        elif s[i] == "B":
            next_[2] += pre[1]
        elif s[i] == "C":
            next_[3] += pre[2]
        else:
            next_[0] = pre[0] * 3
            next_[1] = pre[1] * 3 + pre[0]
            next_[2] = pre[2] * 3 + pre[1]
            next_[3] = pre[3] * 3 + pre[2]
        for i in range(4):
            next_[i] %= MOD
        pre = next_
    
    print(pre[3])

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

for i in range(size):
  cn = dp[i][0]%mod
  a = dp[i][1]%mod
  b = dp[i][2]%mod
  c = dp[i][3]%mod
  if(S[i] == 'A'):
    dp[i+1][0] += cn
    dp[i+1][1] += (a+cn)
    dp[i+1][2] += b
    dp[i+1][3] += c
  elif(S[i] == 'B'):
    dp[i+1][0] += cn
    dp[i+1][1] += a
    dp[i+1][2] += (b+a)
    dp[i+1][3] += c
  elif(S[i] == 'C'):
    dp[i+1][0] += cn
    dp[i+1][1] += a
    dp[i+1][2] += b
    dp[i+1][3] += (c+b)
  else:
    dp[i+1][0] += (3*cn)
    dp[i+1][1] += (3*a+cn)
    dp[i+1][2] += (3*b+a)
    dp[i+1][3] += (3*c+b)

print(dp[size][3]%mod)

Submission status: Accepted

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