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
def solve(s, MOD=int(1e9 + 7)):
    k = 1
    a = 0
    ab = 0
    abc = 0
    for c in s:
        if c == 'A':
            a += k
        elif c == 'B':
            ab += a
        elif c == 'C':
            abc += ab
        else:
            abc = 3 * abc + ab
            ab = 3 * ab + a
            a = 3 * a + k
            k *= 3
        k, a, ab, abc = map(lambda x: x % MOD, [ k, a, ab, abc ])
    return abc % MOD
print(solve(input()))

Submission status: Accepted

Solution code:
#a,b=map(int,input().split())
import numpy as np
 
s=input()
n=len(s)
wayA=np.array([0,0,0,0],dtype=np.int64)
wayB=np.array([0,0,0,0],dtype=np.int64)
wayC=np.array([0,0,0,0],dtype=np.int64)
hatena=0
MOD=1000000007
for c in s:
	if c=="A":
		wayA[0]=wayA[0]+1
	if c=="B":
		wayB+=wayA;
	if c=='C':
		wayC=wayC+wayB
	if c=='?':
		wayC[1]=wayC[1]+wayB[0]
		wayC[2]=wayC[2]+wayB[1]
		wayC[3]=wayC[3]+wayB[2]
		wayB[1]=wayB[1]+wayA[0]
		wayB[2]=wayB[2]+wayA[1]
		wayA[1]=wayA[1]+1
		hatena=hatena+1
	for z in range(0,4):
		wayA[z]=wayA[z]%MOD
		wayB[z]=wayB[z]%MOD
		wayC[z]=wayC[z]%MOD
ans=0
for i in range(0,4):
	p3=1
	if wayC[i]<=0:
		continue
	for k in range(0,hatena-i):
		p3=p3*3
		p3=p3%MOD
	ans=ans+p3*wayC[i]
	ans=ans%MOD
print(ans)

Submission status: Accepted

Solution code:
#a,b=map(int,input().split())
s=input()
n=len(s)
wayA=[0,0,0,0]
wayB=[0,0,0,0]
wayC=[0,0,0,0]
hatena=0
MOD=1000000007
for c in s:
	if c=="A":
		wayA[0]=wayA[0]+1
	if c=="B":
		wayB[0]=wayB[0]+wayA[0]
		wayB[1]=wayB[1]+wayA[1]
	if c=='C':
		wayC[0]=wayC[0]+wayB[0]
		wayC[1]=wayC[1]+wayB[1]
		wayC[2]=wayC[2]+wayB[2]
	if c=='?':
		wayC[1]=wayC[1]+wayB[0]
		wayC[2]=wayC[2]+wayB[1]
		wayC[3]=wayC[3]+wayB[2]
		wayB[1]=wayB[1]+wayA[0]
		wayB[2]=wayB[2]+wayA[1]
		wayA[1]=wayA[1]+1
		hatena=hatena+1
	for z in range(0,4):
		wayA[z]=wayA[z]%MOD
		wayB[z]=wayB[z]%MOD
		wayC[z]=wayC[z]%MOD
ans=0
for i in range(0,4):
	p3=1
	for k in range(0,hatena-i):
		p3=p3*3
		p3=p3%MOD
	ans=ans+p3*wayC[i]
ans = ans%1000000007
print(int(ans))

Submission status: Accepted

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

make = [[0 for i in range(4)] for j in range(n + 1)]

make[n][3] = 1

mod = 10**9 + 7

for i in range(n - 1, -1, -1):
	if s[i] == '?':
		make[i][0] += make[i + 1][0] * 3 + make[i + 1][1]
		make[i][1] += make[i + 1][1] * 3 + make[i + 1][2]
		make[i][2] += make[i + 1][2] * 3 + make[i + 1][3]
		make[i][3] += make[i + 1][3] * 3
	elif s[i] == 'A':
		make[i][0] += make[i + 1][0] + make[i + 1][1]
		make[i][1] += make[i + 1][1]
		make[i][2] += make[i + 1][2]
		make[i][3] += make[i + 1][3]
	elif s[i] == 'B':
		make[i][0] += make[i + 1][0]
		make[i][1] += make[i + 1][1] + make[i + 1][2]
		make[i][2] += make[i + 1][2]
		make[i][3] += make[i + 1][3]
	elif s[i] == 'C':
		make[i][0] += make[i + 1][0]
		make[i][1] += make[i + 1][1]
		make[i][2] += make[i + 1][2] + make[i + 1][3]
		make[i][3] += make[i + 1][3]

	make[i][0] %= mod
	make[i][1] %= mod
	make[i][2] %= mod
	make[i][3] %= mod

print(make[0][0])

Submission status: Accepted

Solution code:
#a,b=map(int,input().split())
import numpy as np

s=input()
n=len(s)
wayA=np.array([0,0,0,0],dtype=np.int64)
wayB=np.array([0,0,0,0],dtype=np.int64)
wayC=np.array([0,0,0,0],dtype=np.int64)
hatena=0
MOD=1000000007
for c in s:
	if c=="A":
		wayA[0]=wayA[0]+1
	if c=="B":
		wayB+=wayA;
	if c=='C':
		wayC=wayC+wayB
	if c=='?':
		wayC[1]=wayC[1]+wayB[0]
		wayC[2]=wayC[2]+wayB[1]
		wayC[3]=wayC[3]+wayB[2]
		wayB[1]=wayB[1]+wayA[0]
		wayB[2]=wayB[2]+wayA[1]
		wayA[1]=wayA[1]+1
		hatena=hatena+1
	for z in range(0,4):
		wayA[z]=wayA[z]%MOD
		wayB[z]=wayB[z]%MOD
		wayC[z]=wayC[z]%MOD
ans=0
for i in range(0,4):
	p3=1
	if wayC[i]<=0:
		continue
	for k in range(0,hatena-i):
		p3=p3*3
		p3=p3%MOD
	ans=ans+p3*wayC[i]
	ans=ans%MOD
print(int(ans))

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

mod = 1000000007

s = ns().rstrip()

nums = [0]*4
nums[0] = 1
for c in s:
    if c == 'A':
        nums[1] += nums[0]
        nums[1] %= mod
    elif c == "B":
        nums[2] += nums[1]
        nums[2] %= mod
    elif c == "C":
        nums[3] += nums[2]
        nums[3] %= mod
    else:
        nums[3] = nums[3]*3+nums[2]
        nums[2] = nums[2]*3+nums[1]
        nums[1] = nums[1]*3+nums[0]
        nums[0] = nums[0]*3
        for k in range(4):
            nums[k] %= mod
print(nums[3])

Submission status: Accepted

Solution code:
S = raw_input()
M = 10**9+7

def count(W):
  N = len(S)
  T1 = [0]*N
  for i in range(N):
    T1[i] = (0 if i==0 else T1[i-1]) + int(S[i]==W[0])
  T2 = [0]*N
  for i in range(N)[::-1]:
    T2[i] = (0 if i==N-1 else T2[i+1]) + int(S[i]==W[2])
  ans = 0
  for i in range(1,N-1):
    if S[i]==W[1]:
      ans += T1[i-1]*T2[i+1]
      ans %= M
  return ans

Q = S.count("?")
print (
  count("ABC")*pow(3,Q,M) +
  count("AB?")*pow(3,max(Q-1,0),M) +
  count("A?C")*pow(3,max(Q-1,0),M) +
  count("A??")*pow(3,max(Q-2,0),M) +
  count("?BC")*pow(3,max(Q-1,0),M) +
  count("?B?")*pow(3,max(Q-2,0),M) +
  count("??C")*pow(3,max(Q-2,0),M) +
  count("???")*pow(3,max(Q-3,0),M))%M

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:
def main():
    s = input()
    pa = [0]
    pb = [0]
    pc = [0]
    pd = [0]

    n = len(s)
    for i in range(n):
        pa.append(pa[-1])
        pb.append(pb[-1])
        pc.append(pc[-1])
        pd.append(pd[-1])

        if s[i] == 'A':
            pa[-1] += 1
        elif s[i] == 'B':
            pb[-1] += 1
        elif s[i] == 'C':
            pc[-1] += 1
        elif s[i] == '?':
            pd[-1] += 1

    totq = pd[n]

    MOD = 1000000007
    ans = 0
    for i in range(1, n + 1):
        if s[i - 1] == 'A' or s[i - 1] == 'C':
            continue

        if s[i - 1] == 'B':
            buf = 0
        else:
            buf = 1

        # ABC ?BC AB? ?B?
        a_bef = pa[i - 1]
        d_bef = pd[i - 1]
        c_aft = pc[n] - pc[i]
        d_aft = pd[n] - pd[i]

        if a_bef * c_aft > 0:
            ans += (a_bef * c_aft % MOD) * pow(3, totq - buf, MOD) % MOD
            ans %= MOD

        if d_bef * c_aft > 0:
            ans += (d_bef * c_aft % MOD) * pow(3, totq - buf - 1, MOD) % MOD
            ans %= MOD

        if a_bef * d_aft > 0:
            ans += (a_bef * d_aft % MOD) * pow(3, totq - buf - 1, MOD) % MOD
            ans %= MOD
        
        if d_bef * d_aft > 0:
            ans += (d_bef * d_aft % MOD) * pow(3, totq - buf - 2, MOD) % MOD
            ans %= MOD

    print(ans)

main()

Submission status: Runtime Error

Solution code:
def getval():
    s = input()
    return s
    
def main(s):
    #dp for "a","ab","abc"
    mod = 10**9 + 7
    dp = [0,0,0,0]
    p3 = [1]
    for i in range(n):
        p3.append((3*p3[i])%mod)
    for i in s:
        if i=="A":
            dp[0] += p3[dp[3]]
            dp[0] %= mod
        elif i=="B":
            dp[1] += dp[0]
            dp[1] %= mod
        elif i=="C":
            dp[2] += dp[1]
            dp[2] %= mod
        else:
            temp1 = dp[0]*2
            temp2 = dp[1]*2
            temp3 = dp[2]*2
            dp[2] += dp[1]
            dp[1] += dp[0]
            dp[0] += p3[dp[3]]
            dp[2] += temp3
            dp[1] += temp2
            dp[0] += temp1
            dp[3] += 1
            for j in range(3):
                dp[j] %= mod
            #print(dp)
    print(dp[2])

if __name__=="__main__":
    s = getval()
    main(s)

Submission status: Runtime Error

Solution code:
s=input()
n=len(s)
q=s.count('?')

mod=10**9+7

target='ABC'
ans=0
for i in range(2**3):
    bdp=[1]*(n+1)
    cnt=0
    for j in range(2,-1,-1):
        if (i>>j)&1==1:
            c='?'
            cnt+=1
        else:
            c=target[j]
        
        cdp=[0]*(n+1)
        for k in range(n):
            if s[k]==c:
                cdp[k]=bdp[k+1]
        
        for k in range(n,0,-1):
            cdp[k-1]+=cdp[k]
            cdp[k-1]%=mod
        
        bdp=cdp
    
    ans+=bdp[0]*pow(3,q-cnt,mod)
    ans%=mod

print(ans)

Submission status: Runtime Error

Solution code:
def is_ok(s):
    if s[1:] in ['AGC', 'ACG', 'GAC']:
        return False
    if s[0] == 'A' and s[2:] == 'GC':
        return False
    if s[:2] == 'AG' and s[3] == 'C':
        return False
    return True


m = 1000000007

N = int(input())

d = {}
for i in 'ACGT':
    for j in 'ACGT':
        for k in 'ACGT':
            d[i + j + k] = 1
for k in ['AGC', 'ACG', 'GAC']:
    del d[k]

for i in range(N - 3):
    t = {}
    for k in d:
        for i in 'ACGT':
            s = k + i
            if is_ok(s):
                t.setdefault(s[1:], 0)
                t[s[1:]] += d[k]
                t[s[1:]] %= m
    d = t

print(sum(d.values()) % m)

Submission status: Runtime Error

Solution code:
s=input()
all_hatena = s.count('?')

a_cnt = 0
ab_cnt = 0
hatena_cnt = 0
ans = 0

MOD = 10**9+7
for si in s:
    if si == 'A':
        a_cnt += 1
    elif si == 'B':
        ab_cnt += a_cnt*pow(3,all_hatena,MOD)
        if all_hatena >= 1: ab_cnt += hatena_cnt*pow(3,all_hatena-1,MOD)
    elif si == 'C':
        ans += ab_cnt
    else:
        ans += ab_cnt*333333336 # modinv(3,MOD)
        ab_cnt += a_cnt*pow(3,all_hatena-1,MOD)
        if all_hatena >= 2: ab_cnt += hatena_cnt*pow(3,all_hatena-2,MOD)
        hatena_cnt += 1
    ab_cnt%=MOD
    ans%=MOD
print(ans)
print(modinv(3,MOD))

Submission status: Runtime Error

Solution code:
def modinv(a,m):
    b, u, v = m, 1, 0
    while b:
        t = a//b
        a -= t*b
        a,b = b,a
        u -= t * v
        u,v = v,u
    u %= m
    return u

s=input()
all_hatena = s.count('?')

a_cnt = 0
ab_cnt = 0
hatena_cnt = 0
ans = 0

MOD = 10**9+7
for si in s:
    if si == 'A':
        a_cnt += 1
    elif si == 'B':
        ab_cnt += a_cnt*pow(3,all_hatena,MOD)
        if ab_cnt >= 1:
            ab_cnt += hatena_cnt*pow(3,all_hatena-1,MOD)
    elif si == 'C':
        ans += ab_cnt
    else:
        ans += ab_cnt*modinv(3,MOD)
        ab_cnt += a_cnt*pow(3,all_hatena-1,MOD)
        if all_hatena >= 2:
            ab_cnt += hatena_cnt*pow(3,all_hatena-2,MOD)
        hatena_cnt += 1
    ab_cnt%=MOD
    ans%=MOD
    # print(a_cnt,ab_cnt,ans)
print(ans)

Submission status: Runtime Error

Solution code:
def modinv(a,m):
    b, u, v = m, 1, 0
    while b:
        t = a//b
        a -= t*b
        a,b = b,a
        u -= t * v
        u,v = v,u
    u %= m
    return u

s=input()
all_hatena = s.count('?')

a_cnt = 0
ab_cnt = 0
hatena_cnt = 0
ans = 0

MOD = 10**9+7
for si in s:
    if si == 'A':
        a_cnt += 1
    elif si == 'B':
        ab_cnt += a_cnt*pow(3,all_hatena,MOD)
        ab_cnt += hatena_cnt*pow(3,all_hatena-1,MOD)
    elif si == 'C':
        ans += ab_cnt
    else:
        ans += ab_cnt*modinv(3,MOD)
        ab_cnt += a_cnt*pow(3,all_hatena-1,MOD)
        if all_hatena >= 2:
            ab_cnt += hatena_cnt*pow(3,all_hatena-2,MOD)
        hatena_cnt += 1
    ab_cnt%=MOD
    ans%=MOD
    # print(a_cnt,ab_cnt,ans)
print(ans)

Submission status: Runtime Error

Solution code:
def modinv(a,m):
    b, u, v = m, 1, 0
    while b:
        t = a//b
        a -= t*b
        a,b = b,a
        u -= t * v
        u,v = v,u
    u %= m
    return u

s=input()
all_hatena = s.count('?')

a_cnt = 0
ab_cnt = 0
hatena_cnt = 0
ans = 0

MOD = 10**9+7
for si in s:
    if si == 'A':
        a_cnt += 1
    elif si == 'B':
        ab_cnt += a_cnt*pow(3,all_hatena,MOD)
        ab_cnt += hatena_cnt*pow(3,all_hatena-1,MOD)
    elif si == 'C':
        ans += ab_cnt
    else:
        ans += ab_cnt*modinv(3,MOD)
        ab_cnt += a_cnt*pow(3,all_hatena-1,MOD)
        ab_cnt += hatena_cnt*pow(3,all_hatena-2,MOD)
        hatena_cnt += 1
    ab_cnt%=MOD
    ans%=MOD
    # print(a_cnt,ab_cnt,ans)
print(ans)

Submission status: Runtime Error

Solution code:
# def C(n, r ,mod=10**9+7):
#     if n-r<r: r=n-r
#     if r == 0: return 1
#     if r == 1: return n
# 
#     numerator = [n - r + k + 1 for k in range(r)]
#     denominator = [k + 1 for k in range(r)]
# 
#     for p in range(2,r+1):
#         pivot = denominator[p - 1]
#         if pivot > 1:
#             offset = (n - r) % p
#             for k in range(p-1,r,p):
#                 numerator[k - offset] /= pivot
#                 denominator[k] /= pivot
# 
#     result = 1
#     for k in range(r):
#         if numerator[k] > 1:
#             result *= int(numerator[k]) %mod
# 
#     return result % mod

A=list(input())
n=len(A)
mod=10**9+7
ans=0
numa= A[0]=="A" 
numa_= A[0]=="?"
numc=A[2:].count("C")
numc_= A[2:].count("?")

for i in range(1,n-1):
    #print(numa,numa_,numc,numc_)
    apro=cpro=0
    if A[i]=="B" or A[i]=="?":
        # for k in range(numa_+1):
        #     apro+= (((C(numa_,k)*pow(2,numa_-k,mod))%mod)*(numa+k))%mod
        # for k in range(numc_+1):
        #     cpro+= (((C(numc_,k)*pow(2,numc_-k,mod))%mod)*(numc+k))%mod
        #print(apro,cpro)
        apro= (3*numa+numa_)*3**(numa_-1)
        cpro= (3*numc+numc_)*3**(numc_-1)
        ans+= (apro*cpro)%mod
        ans%=mod
    if A[i] == "A":
        numa+=1
    if A[i]=="?":
        numa_+=1
    if A[i+1] =="C":
        numc-=1
    if A[i+1]=="?":
        numc_-=1
print(ans)

Submission status: Runtime Error

Solution code:
md=10**9+7
s=input()
dp=[[0]*4 for _ in range(3)]
for c in s:
    if c=="A":dp[0][0]=(dp[0][0]+1)%md
    if c=="B":
        for j in range(2):dp[1][j]=(dp[1][j]+dp[0][j])%md
    if c=="C":
        for j in range(3):dp[2][j]=(dp[2][j]+dp[1][j])%md
    if c=="?":
        for j in range(3):dp[2][j+1]=(dp[2][j+1]+dp[1][j])%md
        for j in range(2):dp[1][j+1]=(dp[1][j+1]+dp[0][j])%md
        dp[0][1] = (dp[0][1] + 1) % md
ans=0
q=s.count("?")
for j in range(4):
    ans+=dp[2][j]*pow(3,q-j,md)
    ans%=md
print(ans)

Submission status: Runtime Error

Solution code:
# import bisect
# from collections import Counter, deque, OrderedDict
# from copy import copy, deepcopy
# from functools import reduce
# from heapq import heapify, heappop, heappush
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import statistics # Pythonのみ
# import string
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    S=list(input())
    # https://qiita.com/drken/items/dc53c683d6de8aeacf5a#%E9%A1%9E%E9%A1%8C-3
    
    INF = 10**10  # INF+INFを計算してもオーバーフローしない範囲で大きく
    
    # P = list(map(int, input().split()))  # P[i]:=i番目の問題の点数
    I,J =len(S),3
    # dpテーブル dp[i][j]:=i文字目まででABCとの照合をレベルjまで進めたときの通り数ーーAまでいってなかったらレベル0，Aまでで1，ABまでで2, ABCまでで3ーー．
    MOD=10**9+7
    dp = [[0]*(J+1) for _ in range(I+1)]
    # 初期条件
    for j in range(J+1):
        dp[0][j]=1
    # ループ
    for i in range(1,I+1):
        if S[i-1]!='?':
            for j in range(J+1):
                dp[i][j]+=
        for j in range(J+1):
            dp[i][j]=dp[i-1][j]
        # i番目を選ぶ場合に特有のこと
        
        if S[i-1]=='A' or S[i-1]=='?':
            dp[i][1]=max(dp[i][1],dp[i][1]+dp[i-1][1])
        if S[i-1]=='B' or S[i-1]=='?':
            dp[i][2]=max(dp[i][2],dp[i][2]+dp[i-1][2])
        if S[i-1]=='C' or S[i-1]=='?':
            dp[i][3]=max(dp[i][3],dp[i][3]+dp[i-1][3])
    print(dp[I-1][J]%MOD)
    

    
# resolve()

import sys
from io import StringIO
import unittest

class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """A??C"""
        output = """8"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """ABCBC"""
        output = """3"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """????C?????B??????A???????"""
        output = """979596887"""
        self.assertIO(input, output)

if __name__ == "__main__":
    unittest.main()

Submission status: Runtime Error

Solution code:
def main():
    MOD = 10 ** 9 + 7

    s = input()
    n = len(s)

    acc_a = [0] * (n + 1)
    acc_c = [0] * (n + 1)
    acc_q = [0] * (n + 1)

    a = 0
    c = 0
    q = 0
    for i, char in enumerate(s, 1):
        if char == 'A':
            a += 1
        elif char == 'C':
            c += 1
        elif char == '?':
            q += 1
        acc_a[i] = a
        acc_c[i] = c
        acc_q[i] = q

    sq = [1]
    for _ in range(acc_q[n]):
        sq.append(sq[-1] * 3 % MOD)

    ans = 0
    for i, char in enumerate(s, 1):
        if char == 'B' or char == '?':
            is_q = int(char == '?')
            rq = acc_q[n] - acc_q[i]
            rc = acc_c[n] - acc_c[i]
            t = (acc_a[i - 1] * (
                    rc * sq[acc_q[n] - is_q]
                    + rq * sq[acc_q[n] - 1 - is_q]
            ) + acc_q[i - 1] * (
                         rc * sq[acc_q[n] - 1 - is_q]
                         + rq * sq[acc_q[n] - 2 - is_q]
                 )) % MOD
            ans = (ans + t) % MOD
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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 = aquest[0]*pow(3,aquest[1],mod)+aquest[1]*pow(3,aquest[1]-1,mod)
        c = cquest[0]*pow(3,cquest[1],mod)+cquest[1]*pow(3,cquest[1]-1,mod)
        ans += a*c%mod
    ans %= mod
    return ans
print(solve(S))

Submission status: Runtime Error

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 = aquest[0]*pow(3,aquest[1],mod)+aquest[1]*pow(3,aquest[1]-1,mod)
        c = cquest[0]*pow(3,cquest[1],mod)+cquest[1]*pow(3,cquest[1]-1,mod)
        ans += a*c
        ans %= mod
    return ans
print(solve(S))

Submission status: Runtime Error

Solution code:
from bisect import *
S = input()
mod = 10**9 + 7
A = []
B = []
C = []
X = []
q = 0
for i,s in enumerate(S):
    if s == 'A':
        A.append(i)
    elif s == 'B':
        B.append((i,0))
    elif s == 'C':
        C.append(i)
    else:
        X.append(i)
        B.append((i,1))
        q += 1

pow3 = [pow(3,q,mod),pow(3,q-1,mod),pow(3,q-2,mod),pow(3,q-3,mod)]
ans = 0
for b,flag in B:
    Al = bisect_left(A,b)
    Cr = (len(C) - bisect_right(C,b))
    Xl = bisect_left(X,b)
    Xr = (len(X) - bisect_right(X,b))
    ans += (Al*Cr%mod)*pow3[flag]%mod
    ans %= mod
    ans += (Al*Xr%mod + Xl*Cr%mod)*pow3[flag+1]%mod
    ans %= mod
    ans += (Xl*Xr%mod)*pow3[flag+2]%mod
print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    S=list(input())
    A,C,Q=[0]*(len(S)+1),[0]*(len(S)+1),[0]*(len(S)+1)
    l_B=[]
    l_Q=[]
    q=0
    for i in range(len(S)):
        A[i+1]=A[i]+(S[i]=='A')
        C[i+1]=C[i]+(S[i]=='C')
        Q[i+1]=Q[i]+(S[i]=='?')
        if S[i]=='?':
            q+=1
            l_Q.append(i)
        if S[i]=='B':
            l_B.append(i)
    ans=0
    pow3q=pow(3,q,MOD)
    pow3q_1=pow(3,q-1,MOD)
    pow3q_2=pow(3,q-2,MOD)
    pow3q_3=pow(3,q-3,MOD)
    
    for x in l_B:
        ans+=A[x]*(C[len(S)]-C[x+1])*pow3q
        ans+=Q[x]*(C[len(S)]-C[x+1])*pow3q_1
        ans+=A[x]*(Q[len(S)]-Q[x+1])*pow3q_1
        ans+=Q[x]*(Q[len(S)]-Q[x+1])*pow3q_2
        ans%=MOD
    for x in l_Q:
        ans+=A[x]*(C[len(S)]-C[x+1])*pow3q_1
        ans+=Q[x]*(C[len(S)]-C[x+1])*pow3q_2
        ans+=A[x]*(Q[len(S)]-Q[x+1])*pow3q_2
        ans+=Q[x]*(Q[len(S)]-Q[x+1])*pow3q_3
        ans%=MOD        
    print(ans)
    

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

# i = 0, ..., nについて
# dp[i][0] = i文字目まででありうる文字列の数（ABCなら1、AB?なら3）
# dp[i][1] = i文字目までに含まれるAの数
# dp[i][2] = i文字目までに含まれるABのパターン数
# dp[i][3] = i文字目までに含まれるABCのパターン数
dp = [[0 for j in range(4)] for i in range(n + 1)]
dp[0][0] = 1 # ''空の文字列は1パターン
for j in range(1, 4):
    dp[0][j] = 0  # 空の文字列にはAもABもABCも入っていない

for i in range(1, n + 1):
    m = 3 if s[i - 1] == '?' else 1

    for j in range(4):
        dp[i][j] = dp[i - 1][j] * m

    if s[i - 1] == 'A' or s[i - 1] == '?':
        dp[i][A] =  (dp[i][A] + dp[i - 1][0]) % p
    if s[i - 1] == 'B' or s[i - 1] == '?':
        dp[i][AB] = (dp[i][AB] + dp[i - 1][A]) % p
    if s[i - 1] == 'C' or s[i - 1] == '?':
        dp[i][ABC] = (dp[i][ABC] + dp[i - 1][AB]) % p

print(dp[n][ABC])

Submission status: Runtime Error

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

# i = 0, ..., nについて
# dp[i][0] = i文字目まででありうる文字列の数（ABCなら1、AB?なら3）
# dp[i][1] = i文字目までに含まれるAの数
# dp[i][2] = i文字目までに含まれるABのパターン数
# dp[i][3] = i文字目までに含まれるABCのパターン数
dp = [[0 for j in range(4)] for i in range(n + 1)]
dp[0][0] = 1 # ''空の文字列は1パターン
for j in range(1, 4):
    dp[0][j] = 0  # 空の文字列にはAもABもABCも入っていない

print("dp[0] = {}".format(dp[0]))
for i in range(1, n + 1):
    m = 3 if s[i - 1] == '?' else 1

    for j in range(4):
        dp[i][j] = dp[i - 1][j] * m

    if s[i - 1] == 'A' or s[i - 1] == '?':
        dp[i][A] =  (dp[i][A] + dp[i - 1][0]) % p
    if s[i - 1] == 'B' or s[i - 1] == '?':
        dp[i][AB] = (dp[i][AB] + dp[i - 1][A]) % p
    if s[i - 1] == 'C' or s[i - 1] == '?':
        dp[i][ABC] = (dp[i][ABC] + dp[i - 1][AB]) % p

print(dp[n][ABC])

Submission status: Runtime Error

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]+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+pow(3,count))%mod
        count+=1
        
print(dp[2]%mod)

Submission status: Runtime Error

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))
  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: Runtime Error

Solution code:
import numpy as np
S = input()
INF = 10**9+7
dp = np.array([0,0,0], dtype=np.int64)
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]
    dp[1] %= INF
  elif S[i]=='C':
    dp[2] += dp[1]
    dp[2] %= INF
  else:
    dp[1:] = dp[1:]*3+dp[:-1]
    dp[0] = dp[0]*3+N
    dp %= INF
    N *= 3
print(dp[2])

Submission status: Runtime Error

Solution code:
import numpy as np
S = input()
INF = 10**9+7
dp = np.array([0,0,0], dtype=np.int64)
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:
    dp[1:] = dp[1:]*3+dp[:-1]
    dp[0] = dp[0]*3+N
    dp %= INF
    N *= 3
print(dp[2]%INF)

Submission status: Runtime Error

Solution code:
import statistics
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: Runtime Error

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 i in range(0,4):
        dp[i + 1][i] %= MOD




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

Submission status: Runtime Error

Solution code:
import statistics
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 i in range(0,4):
        dp[i + 1][i] %= MOD




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

Submission status: Runtime Error

Solution code:
def main():
    S = input()
    
    mod = 10**9 + 7
    Ans = [[0,0,0,0,0]]
    import copy
    
    S = S[::-1]

    for i in S:
        tmp = copy.deepcopy(Ans[-1])
        if i == "C":
            tmp[2] += 1
            Ans.append(tmp)
        elif i == "B":
            tmp[1] += 1
            tmp[3] += tmp[2]
            tmp[3] %= mod
            Ans.append(tmp)
        elif i == "A":
            tmp[0] += 1
            tmp[4] += tmp[3]
            tmp[4] %= mod
            Ans.append(tmp)
        elif i == "?":
            print(S[mod])
            a,b,c,bc,abc = copy.deepcopy(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()