Problem:


Score : 400 points

Problem Statement

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

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

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

T_j = B

T_k = C

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

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

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

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

Constraints

3 ≤ |S| ≤ 10^5

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

Input

Input is given from Standard Input in the following format:

S

Output

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

Sample Input 1

A??C

Sample Output 1

8

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

AAAC: 0

AABC: 2

AACC: 0

ABAC: 1

ABBC: 2

ABCC: 2

ACAC: 0

ACBC: 1

ACCC: 0

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

Sample Input 2

ABCBC

Sample Output 2

3

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

Sample Input 3

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

Sample Output 3

979596887

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



Sample input:
A??C


Sample output:
8

Submission status: Wrong Answer

Solution code:
S=raw_input()
L=len(S)
mod=10**9+7

num=[ [ 0 for i in range(4) ] for j in range(L) ]		# i=0 A, i=1 B, i=2 C, i=3 ?

for i in range(L):
	if i==0:
		if S[i]=="A":  num[i][0]=1
		elif S[i]=="B":  num[i][1]=1		
		elif S[i]=="C":  num[i][2]=1
		elif S[i]=="?":  num[i][3]=1
	else:
		for j in range(4):
			num[i][j]=num[i-1][j]
			
		if S[i]=="A":  num[i][0]+=1
		elif S[i]=="B":  num[i][1]+=1		
		elif S[i]=="C":  num[i][2]+=1
		elif S[i]=="?":  num[i][3]+=1		



ans=0
for b_pos in range(1,L-1):

	if S[b_pos]=="B" or S[b_pos]=="?":
		cnt_c=num[L-1][2]-num[b_pos][2]
		cnt_q=num[L-1][3]-num[b_pos][3]
		total=cnt_c+cnt_q

		r=0
		for i in range(cnt_c, total+1):
			r+=i* (2**(total-i))

		l=0
		cnt_a=num[b_pos-1][0]
		cnt_q=num[b_pos-1][3]
		total=cnt_a+cnt_q

		for i in range(cnt_a, total+1):
			l+=i* (2**(total-i))

#		print "b_pos,l,r:::",b_pos,l,r
		ans+=(l*r)%mod

print ans%mod

Submission status: Wrong Answer

Solution code:
S=raw_input()
L=len(S)

num=[ [ 0 for i in range(4) ] for j in range(L) ]		# i=0 A, i=1 B, i=2 C, i=3 ?

for i in range(L):
	if i==0:
		if S[i]=="A":  num[i][0]=1
		elif S[i]=="B":  num[i][1]=1		
		elif S[i]=="C":  num[i][2]=1
		elif S[i]=="?":  num[i][3]=1
	else:
		for j in range(4):
			num[i][j]=num[i-1][j]
			
		if S[i]=="A":  num[i][0]+=1
		elif S[i]=="B":  num[i][1]+=1		
		elif S[i]=="C":  num[i][2]+=1
		elif S[i]=="?":  num[i][3]+=1		



ans=0
for b_pos in range(1,L-1):

	if S[b_pos]=="B" or S[b_pos]=="?":
		cnt_c=num[L-1][2]-num[b_pos][2]
		cnt_q=num[L-1][3]-num[b_pos][3]
		total=cnt_c+cnt_q

		r=0
		for i in range(cnt_c, total+1):
			r+=i* (2**(total-i))

		l=0
		cnt_a=num[b_pos-1][0]
		cnt_q=num[b_pos-1][3]
		total=cnt_a+cnt_q

		for i in range(cnt_a, total+1):
			l+=i* (2**(total-i))

#		print "b_pos,l,r:::",b_pos,l,r
		ans+=l*r

print ans

Submission status: Wrong Answer

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

moji = [[0,0,0,0] for _ in range(n+1)]

for i in range(1,n+1):
    for k in range(4):
        moji[i][k] += moji[i-1][k]
    if s[i-1] == 'A':
        moji[i][0] += 1
        continue
    elif s[i-1] == 'B':
        moji[i][1] += 1
        continue
    elif s[i-1] == 'C':
        moji[i][2] += 1
        continue
    else:
        moji[i][3] += 1

h = s.count('?')
mt = [1]
for i in range(h+1):
    mt.append(mt[-1]*3 % mod)

ans = 0
for i in range(n):
    al,cr,hl,hr = moji[i][0], moji[n][2]-moji[i+1][2], moji[i][3], moji[n][3]-moji[i+1][3]
    if s[i] == 'B' or s[i] == '?':
        k = (al*3 + hl) * (cr*3 + hr) * mt[hr+hl-2]
        ans += k % mod
print(ans%mod)

Submission status: Wrong Answer

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

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

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

        elif j == 1:
            if S[i-1] == "?":
                dp[i][j] = dp[i-1][j] * 3 + max(dp[i-1][j-1], 1)
            elif S[i-1] == "A":
                dp[i][j] = max(1, dp[i-1][j-1])
            else:
                dp[i][j] = dp[i - 1][j]
        elif j == 2:
            if S[i-1] == "?":
                dp[i][j] = dp[i - 1][j] * 3 + dp[i-1][j-1]
            elif S[i-1] == "B":
                dp[i][j] = dp[i - 1][j] + dp[i-1][j-1]
            else:
                dp[i][j] = dp[i - 1][j]
        elif j == 3:
            if S[i-1] == "?":
                dp[i][j] = dp[i-1][j] * 3 + dp[i-1][j-1]
            elif S[i-1] == "C":
                dp[i][j] = dp[i-1][j] + dp[i-1][j-1]
            else:
                dp[i][j] = dp[i-1][j]

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

Submission status: Wrong Answer

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

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

for i in range(1, len(S) + 1):
    print("==== i = {} ====".format(i))
    print(S[:i])
    for j in range(4):
        if j == 0:
            dp[i][j] = 3 ** (len([p for p in S[:i] if p == "?"]))

        elif j == 1:
            if S[i-1] == "?":
                dp[i][j] = dp[i-1][j] * 3 + max(dp[i-1][j-1], 1)
            elif S[i-1] == "A":
                dp[i][j] = max(1, dp[i-1][j-1])
            else:
                dp[i][j] = dp[i - 1][j]
        elif j == 2:
            if S[i-1] == "?":
                dp[i][j] = dp[i - 1][j] * 3 + dp[i-1][j-1]
            elif S[i-1] == "B":
                dp[i][j] = dp[i - 1][j] + dp[i-1][j-1]
            else:
                dp[i][j] = dp[i - 1][j]
        elif j == 3:
            if S[i-1] == "?":
                dp[i][j] = dp[i-1][j] * 3 + dp[i-1][j-1]
            elif S[i-1] == "C":
                dp[i][j] = dp[i-1][j] + dp[i-1][j-1]
            else:
                dp[i][j] = dp[i-1][j]

            for r in dp:
                print(r)

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

Submission status: Wrong Answer

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

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

for i in range(1, len(S) + 1):
    # print("==== i = {} ====".format(i))
    # print(S[:i])
    for j in range(4):
        if j == 0:
            if S[i-1] == "?":
                dp[i][j] = max(dp[i-1][j] * 3, 3)
            else:
                dp[i][j] = dp[i-1][j]
        elif j == 1:
            if S[i-1] == "?":
                dp[i][j] = dp[i-1][j] * 3 + max(dp[i-1][j-1], 1)
            elif S[i-1] == "A":
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = dp[i - 1][j]
        elif j == 2:
            if S[i-1] == "?":
                dp[i][j] = dp[i - 1][j] * 3 + dp[i-1][j-1]
            elif S[i-1] == "B":
                dp[i][j] = dp[i - 1][j] + dp[i-1][j-1]
            else:
                dp[i][j] = dp[i - 1][j]
        elif j == 3:
            if S[i - 1] == "?":
                dp[i][j] = dp[i - 1][j] * 3 + dp[i - 1][j - 1]
            elif S[i - 1] == "C":
                dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1]
            else:
                dp[i][j] = dp[i - 1][j]

            # for r in dp:
            #     print(r)

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

Submission status: Wrong Answer

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

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

for i in range(1, len(S) + 1):
    for j in range(1, 4):
        # print(i, j)
        if j == 1:
            if S[i-1] == "?":
                dp[i][j] = dp[i-1][j] * 3 + 1
            elif S[i-1] == "A":
                dp[i][j] = dp[i - 1][j] + 1
            else:
                dp[i][j] = dp[i - 1][j]
        elif j == 2:
            if S[i-1] == "?":
                dp[i][j] = dp[i - 1][j] * 3 + dp[i-1][j-1]
            elif S[i-1] == "B":
                dp[i][j] = dp[i - 1][j] + dp[i-1][j-1]
            else:
                dp[i][j] = dp[i - 1][j]
        elif j == 3:
            if S[i - 1] == "?":
                dp[i][j] = dp[i - 1][j] * 3 + dp[i - 1][j - 1]
            elif S[i - 1] == "C":
                dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1]
            else:
                dp[i][j] = dp[i - 1][j]

        # for r in dp:
        #     print(r)

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

Submission status: Wrong Answer

Solution code:
s=input()
l=len(s)
a=[[0,0,0] for i in range(l)]
num=1
for i in range(l):
    if s[i]=='A':
        a[i][0]=a[i-1][0]+1*num
        a[i][1]=a[i-1][1]
        a[i][2]=a[i-1][2]
    if s[i]=='B':
        a[i][0]=a[i-1][0]
        a[i][1]=a[i-1][1]+a[i-1][0]
        a[i][2]=a[i-1][2]
    if s[i]=='C':
        a[i][0]=a[i-1][0]
        a[i][1]=a[i-1][1]
        a[i][2]=a[i-1][2]+a[i-1][1]
    if s[i]=='?':
        
        a[i][0]=a[i-1][0]*3+1*num
        a[i][1]=a[i-1][1]*3+a[i-1][0]
        a[i][2]=a[i-1][2]*3+a[i-1][1]
        
        num=(num*3)%1000000007


    a[i][0]=a[i][0]%1000000007
    a[i][1]=a[i][1]%1000000007
    a[i][2]=a[i][2]%1000000007
print(a)

Submission status: Wrong Answer

Solution code:
s=input()
l=len(s)
a=[[0,0,0] for i in range(l)]
for i in range(l):
    if s[i]=='A':
        a[i][0]=a[i-1][0]+1
        a[i][1]=a[i-1][1]
        a[i][2]=a[i-1][2]
    if s[i]=='B':
        a[i][0]=a[i-1][0]
        a[i][1]=a[i-1][1]+a[i-1][0]
        a[i][2]=a[i-1][2]
    if s[i]=='C':
        a[i][0]=a[i-1][0]
        a[i][1]=a[i-1][1]
        a[i][2]=a[i-1][2]+a[i-1][1]
    if s[i]=='?':
        a[i][0]=a[i-1][0]*3+1
        a[i][1]=a[i-1][1]*3+a[i-1][0]
        a[i][2]=a[i-1][2]*3+a[i-1][1]
print(a[-1][2])

Submission status: Wrong Answer

Solution code:
from itertools import accumulate as ac
s=input()
n=len(s)
mod=int(1e9)+7

*aca,=ac([0]+[1 if i=="A" else 0 for i in s])
*acc,=ac([0]+[1 if i=="C" else 0 for i in s])
*acq,=ac([0]+[1 if i=="?" else 0 for i in s])

v=0
for i in range(1,n-1):
  if s[i]=="B" or s[i]=="?":
    a=aca[i]
    l=acq[i]
    c=acc[n]-acc[i+1]
    r=acq[n]-acq[i+1]
    v+=(a*c*pow(3,l+r,mod))
    if l+r-1>=0:
      v+=(a*r*pow(3,l+r-1,mod))+(l*c*pow(3,l+r-1,mod))
    if l+r-2>=0:
      v+=(l*r*pow(3,l+r-2,mod))
    v%=mod

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
S = input()
MOD = 10**9+7
A = 0
C = S.count('C')
Q = 0
QMAX = S.count('?')

ans = 0
# <ABCとして選んだ場所>* 3**(残された_の数)
b = 3 ** (QMAX-2) % MOD
q = 3 ** (QMAX-3) % MOD

for s in S:
    if s == 'A':
        A += 1
    elif s == 'C':
        C -= 1
    elif s == 'B':
        
        ans = (ans + (3*A+q) * (3*C+QMAX-q) * b)%MOD
    else:
        ans = (ans + (3*A+q) * (3*C+QMAX-q-1) * q)%MOD

print(int(ans))

Submission status: Wrong Answer

Solution code:
S = input()
MOD = 10**9+7
A = 0
C = S.count('C')
Q = 0
QMAX = S.count('?')

ans = 0
# <ABCとして選んだ場所>* 3**(残された_の数)
b = 3 ** (QMAX-2) % MOD
q = 3 ** (QMAX-3) % MOD

for s in S:
    if s == 'A':
        A += 1
    elif s == 'C':
        C -= 1
    elif s == 'B':
        
        ans = (ans + (3*A+q) * (3*C+QMAX-q) * b)%MOD
    else:
        ans = (ans + (3*A+q) * (3*C+QMAX-q-1) * q)%MOD

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
s = input()
dp = np.array([[0 for _ in range(0,4)] for _ in range(0,len(s)+1)])
dp[len(s)][3] = 1
dp[len(s)][0] = 0
dp[len(s)][1] = 0
dp[len(s)][2] = 0
abc = ["A","B","C"]
for i in range(len(s)-1,-1,-1):
    m = 1
    if s[i] ==  "?":
        m=3
    dp[i][3] += m * dp[i+1][3]

for i in range(len(s)-1,-1,-1):
    for j in range(0,3):
        m1,m2 = 1,0
        if s[i] == "?":
            m1,m2 = 3,1
        if s[i] == abc[j]:
            m1,m2 = 1,1
        dp[i][j] += m1 * dp[i+1][j] + m2 * dp[i+1][j+1]
        dp[i][j] %= (10**9 + 7)
# for i in range(len(s),-1,-1):
#     print(dp[i])
print(dp[0][0] % (10**9 + 7))

Submission status: Wrong Answer

Solution code:
s = input()
dp = [[0 for _ in range(0,4)] for _ in range(0,len(s)+1)]
dp[len(s)][3] = 1
dp[len(s)][0] = 0
dp[len(s)][1] = 0
dp[len(s)][2] = 0
abc = ["A","B","C"]
for i in range(len(s)-1,-1,-1):
    m = 1
    if s[i] ==  "?":
        m=3
    dp[i][3] += m * dp[i+1][3]

for i in range(len(s)-1,-1,-1):
    for j in range(0,3):
        m1,m2 = 1,0
        if s[i] == "?":
            m1,m2 = 3,1
        if s[i] == abc[j]:
            m1,m2 = 1,1
        dp[i][j] += m1 * dp[i+1][j] + m2 * dp[i+1][j+1]
        dp[i][j] %= (10**9 + 7)
for i in range(len(s),-1,-1):
    print(dp[i])
print(dp[0][0] % (10**9 + 7))

Submission status: Wrong Answer

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

# dp[i][j]: i番目までの文字までで、状態jになる組み合わせ数
dp = [[0 for _ in range(4)] for _ in range(N + 1)]
dp[0][0] = 1

for i in range(N):
    if S[i] in ['A', '?']:
        for j in range(4):
            dp[i + 1][j] += dp[i][j] % mod
        dp[i + 1][1] += dp[i][0] % mod
    if S[i] in ['B', '?']:
        for j in range(4):
            dp[i + 1][j] += dp[i][j] % mod
        dp[i + 1][2] += dp[i][1] % mod
    if S[i] in ['C', '?']:
        for j in range(4):
            dp[i + 1][j] += dp[i][j] % mod
        dp[i + 1][3] += dp[i][2] % mod

print(dp[N][3])

Submission status: Wrong Answer

Solution code:
S = input()

dp = [[0 for _ in range(3 + 1)] for _ in range(len(S) + 1)]
dp[0][0] = 1

B = 10 ** 9 + 7
for i in range(1, len(S) + 1):
    if S[i - 1] == 'A':
        dp[i][0] += dp[i - 1][0] % B
        dp[i][1] += dp[i - 1][1] % B
        dp[i][2] += dp[i - 1][2] % B
        dp[i][3] += dp[i - 1][3] % B

        dp[i][1] += dp[i - 1][0] % B
    elif S[i - 1] == 'B':
        dp[i][0] += dp[i - 1][0] % B
        dp[i][1] += dp[i - 1][1] % B
        dp[i][2] += dp[i - 1][2] % B
        dp[i][3] += dp[i - 1][3] % B

        dp[i][2] += dp[i - 1][1] % B
    elif S[i - 1] == 'C':
        dp[i][0] += dp[i - 1][0] % B
        dp[i][1] += dp[i - 1][1] % B
        dp[i][2] += dp[i - 1][2] % B
        dp[i][3] += dp[i - 1][3] % B

        dp[i][3] += dp[i - 1][2] % B
    else:
        dp[i][0] += dp[i - 1][0] * 3 % B
        dp[i][1] += dp[i - 1][1] * 3 % B
        dp[i][2] += dp[i - 1][2] * 3 % B
        dp[i][3] += dp[i - 1][3] * 3 % B

        dp[i][1] += dp[i - 1][0] % B
        dp[i][2] += dp[i - 1][1] % B
        dp[i][3] += dp[i - 1][2] % B


print(dp[len(S)][3])

Submission status: Wrong Answer

Solution code:
S = input()

max_S = 10**9 + 7

N_Q = S.count("?")
N_C = S.count("C")

t_A = 0
t_Q = 0
if(S[0:1] == "C"):
    t_C = N_C - 1
else:
    t_C = N_C

S_list = [{"bA": t_A, "bQ": t_Q, "aC": t_C, "aQ": N_Q - t_Q}]
for i in range(1, len(S)):
    if(S[i - 1:i] == "A"):
        t_A += 1
    elif(S[i - 1:i] == "?"):
        t_Q += 1

    ba_dic = {}
    ba_dic["bA"] = t_A
    ba_dic["bQ"] = t_Q
    if(S[i:i + 1] == "?"):
        ba_dic["aQ"] = N_Q - t_Q - 1
    else:
        ba_dic["aQ"] = N_Q - t_Q
    if(S[i:i + 1] == "C"):
        t_C -= 1
    ba_dic["aC"] = t_C

    S_list.append(ba_dic)

ans = 0
for i in range(len(S)):
    if(S[i:i + 1] == "A" or S[i:i + 1] == "C"):
        continue

    bA = S_list[i]["bA"]
    bQ = S_list[i]["bQ"]
    aC = S_list[i]["aC"]
    aQ = S_list[i]["aQ"]

    tmp = 9 * bA * aC + bQ * aQ + 3 * (bA * aQ + bQ * aC)
    ans += tmp * int(3**(bQ + aQ - 2))
    ans = ans % max_S

print(ans)

Submission status: Wrong Answer

Solution code:
S = input()

max_S = 10**9 + 7

N_Q = S.count("?")
N_C = S.count("C")

t_A = 0
t_Q = 0
if(S[0:1] == "C"):
    t_C = N_C - 1
else:
    t_C = N_C

S_list = [{"bA": t_A, "bQ": t_Q, "aC": t_C, "aQ": N_Q - t_Q}]
for i in range(1, len(S)):
    if(S[i - 1:i] == "A"):
        t_A += 1
    elif(S[i - 1:i] == "?"):
        t_Q += 1

    ba_dic = {}
    ba_dic["bA"] = t_A
    ba_dic["bQ"] = t_Q
    if(S[i:i + 1] == "?"):
        ba_dic["aQ"] = N_Q - t_Q - 1
    else:
        ba_dic["aQ"] = N_Q - t_Q
    if(S[i:i + 1] == "C"):
        t_C -= 1
    ba_dic["aC"] = t_C

    S_list.append(ba_dic)

ans = 0
for i in range(len(S)):
    if(S[i:i + 1] == "A" or S[i:i + 1] == "C"):
        continue

    bA = S_list[i]["bA"]
    bQ = S_list[i]["bQ"]
    aC = S_list[i]["aC"]
    aQ = S_list[i]["aQ"]

    tmp = 9 * bA * aC + bQ * aQ + 3 * (bA * aQ + bQ * aC)
    kk = tmp * int(3**(bQ + aQ - 2))
    ans = ans % max_S

print(ans)

Submission status: Wrong Answer

Solution code:
S = input()*10000
memo = [[0,0,0,0] for i in range(len(S))]
Q = 0
memo[0][0] = 1
if S[0] == 'A':
  memo[0][1] = 1
elif S[0] == '?':
  memo[0][0] = 3
  memo[0][1] = 1
l = 1
while l < len(S):
  s = S[l]
  if s == 'A':
    memo[l][0] = memo[l-1][0]
    memo[l][1] = memo[l-1][1] + memo[l-1][0]
    memo[l][2] = memo[l-1][2]
    memo[l][3] = memo[l-1][3]
  elif s == 'B':
    memo[l][0] = memo[l-1][0]
    memo[l][1] = memo[l-1][1]
    memo[l][2] = memo[l-1][2] + memo[l-1][0]
    memo[l][3] = memo[l-1][3]
  elif s == 'C':
    memo[l][0] = memo[l-1][0]
    memo[l][1] = memo[l-1][1]
    memo[l][2] = memo[l-1][2]
    memo[l][3] = memo[l-1][3] + memo[l-1][1]
  else:
    memo[l][0] = memo[l-1][0]*3
    memo[l][1] = memo[l-1][1]*3 + memo[l-1][0]
    memo[l][2] = memo[l-1][2]*3 + memo[l-1][0]
    memo[l][3] = memo[l-1][3]*3 + memo[l-1][1]
    Q += 1
  memo[l] = [i%(10**9+7) for i in memo[l]]
  l += 1
print(int(memo[l-1][2]))

Submission status: Wrong Answer

Solution code:
S = input()
memo = [[0,0,0] for i in range(len(S))]
if S[0] == 'A' or '?':
  memo[0][0] = 1
l = 1
while l < len(S):
  Q = S[:l].count('?')
  if S[l] == 'A':
    memo[l][0] = memo[l-1][0] + 3**Q
    memo[l][1] = memo[l-1][1]
    memo[l][2] = memo[l-1][2]
  elif S[l] == 'B':
    memo[l][0] = memo[l-1][0]
    memo[l][1] = memo[l-1][1] + memo[l-1][0]
    memo[l][2] = memo[l-1][2]
  elif S[l] == 'C':
    memo[l][0] = memo[l-1][0]
    memo[l][1] = memo[l-1][1]
    memo[l][2] = memo[l-1][2] + memo[l-1][1]
  else:
    memo[l][0] = memo[l-1][0]*3 + 3**Q
    memo[l][1] = memo[l-1][1]*3 + memo[l-1][0]
    memo[l][2] = memo[l-1][2]*3 + memo[l-1][1]
  l += 1
print(memo[len(S)-1][2] % (10**9+7))

Submission status: Wrong Answer

Solution code:
s=input()
n=len(s)
c=[0 for i in range(n)]
d=[0 for i in range(n)]
bc=[0 for i in range(n)]
bd=[0 for i in range(n)]
dc=[0 for i in range(n)]
dd=[0 for i in range(n)]
if s[-1]=="C":
    c[-1]=1
if s[-1]=="?":
    d[-1]=1
for i in range(-2,-n-1,-1):
    c[i]=c[i+1]
    d[i]=d[i+1]
    bc[i]=bc[i+1]
    bd[i]=bd[i+1]
    dc[i]=dc[i+1]
    dd[i]=dd[i+1]
    if s[i]=="B":
        bc[i]+=c[i+1]
        bd[i]+=d[i+1]
    if s[i]=="C":
        c[i]+=1
    if s[i]=="?":
        d[i]+=1
        dc[i]+=c[i+1]
        dd[i]+=d[i+1]
mul=[1,1,1,1]
for i in range(d[0]):
    mul[3]*=3
    mul[3]%=1000000007
for i in range(2,-1,-1):
    if mul[i+1]%3==0:
        mul[i]=mul[i+1]//3
    elif mul[i+1]%3==1:
        mul[i]=(mul[i+1]+1000000007)%3
    else:
        mul[i]=(mul[i+1]+2000000014)%3
res=0
for i in range(n-2):
    if s[i]=="A":
        res+=bc[i+1]*mul[3]+(dc[i+1]+bd[i+1])*mul[2]+dd[i+1]*mul[1]
    if s[i]=="?":
        res+=bc[i+1]*mul[2]+(dc[i+1]+bd[i+1])*mul[1]+dd[i+1]*mul[0]
    res%=1000000007
print(res)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
 
modulo = 10 ** 9 + 7
 
S = input()
 
def nleft(S, c):
    """各位置について，それより左の文字列に含まれる文字 c の総数.
       左に'?'が含まれるときは，それらに文字を入れて得られるすべての
       文字列に渡って，文字 c の個数を合計する. """
 
    # c の個数
    n = [0 for c in S]
    for i in range(len(S)):
        n[i] = n[i-1] + (1 if S[i-1] == c else 0)

    q = 0      # '?'の個数
    pow3q = 1  # 3 ** q
    for i in range(len(n)):
        if q > 0:
            n[i] *= pow3q         # ?の埋め方の数だけ増やす
            n[i] += pow3q1 * q    # ?に入る'C'の個数
            n[i] %= modulo
        if S[i] == '?':
            q += 1
            pow3q1 = pow3q
            pow3q  = pow3q * 3 % modulo
    return n
 
def nright(S, c):
    # c の個数
    n = [0 for c in S]
    for i in range(len(S) - 1, 0, -1):
        n[i-1] = n[i] + (1 if S[i] == c else 0)

    q = 0      # '?'の個数
    pow3q = 1  # 3 ** q
    for i in range(len(n) - 1, -1, -1):
        if q > 0:
            n[i] *= pow3q         # ?の埋め方の数だけ増やす
            n[i] += pow3q1 * q    # ?に入る'C'の個数
            n[i] %= modulo
        if S[i] == '?':
            q += 1
            pow3q1 = pow3q
            pow3q  = pow3q * 3 % modulo
    return n
 
 
left  = nleft (S, 'A')
right = nright(S, 'C')
 
# 各文字が'B'のときのABC数を計算
abc = 0
for i in range(0, len(S)):
    if S[i] in 'B?':
        abc += left[i] * right[i]
 
abc = int(abc) % modulo
print(abc)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
 
modulo = 10 ** 9 + 7
 
S = input()
 
def nleft(S, c):
    """各位置について，それより左の文字列に含まれる文字 c の総数.
       左に'?'が含まれるときは，それらに文字を入れて得られるすべての
       文字列に渡って，文字 c の個数を合計する. """
 
    # c の個数
    n = [0 for c in S]
    for i in range(len(S)):
        n[i] = n[i-1] + (1 if S[i-1] == c else 0)

    q = 0      # '?'の個数
    pow3q = 1  # 3 ** q
    for i in range(len(n)):
        if q > 0:
            n[i] *= pow3q             # ?の埋め方の数だけ増やす
            n[i] += pow3q * q // 3    # ?に入る'C'の個数
            n[i] %= modulo
        if S[i] == '?':
            q += 1
            pow3q = pow3q * 3
    return n
 
def nright(S, c):
    n = nleft(list(reversed(S)), c)
    n.reverse()
    return n
 
left  = nleft (S, 'A')
right = nright(S, 'C')
 
# 各文字が'B'のときのABC数を計算
abc = 0
for i in range(0, len(S)):
    if S[i] in 'B?':
        abc += left[i] * right[i]
 
abc = int(abc) % modulo
print(abc)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
 
modulo = 10 ** 9 + 7
 
S = input()
 
def nleft(S, c):
    """各位置について，それより左の文字列に含まれる文字 c の総数.
       左に'?'が含まれるときは，それらに文字を入れて得られるすべての
       文字列に渡って，文字 c の個数を合計する. """
 
    # c の個数
    n = [0 for c in S]
    for i in range(len(S)):
        n[i] = n[i-1] + (1 if S[i-1] == c else 0)

    q = 0  # '?'の個数
    for i in range(len(n)):
        if q > 0:
            n[i] *= (3 ** q) % modulo            # ?の埋め方の数だけ増やす
            n[i] += (3 ** (q - 1)) * q % modulo  # ?に入る'C'の個数
            n[i] %= modulo
        if S[i] == '?': q += 1
    return n
 
def nright(S, c):
    n = nleft(list(reversed(S)), c)
    n.reverse()
    return n
 
left  = nleft (S, 'A')
right = nright(S, 'C')
 
# 各文字が'B'のときのABC数を計算
abc = 0
for i in range(0, len(S)):
    if S[i] in 'B?':
        abc += left[i] * right[i]
 
abc = int(abc) % modulo
print(abc)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
 
modulo = 10 ** 9 + 7
 
S = input()
 
def nleft(S, c):
    """各位置について，それより左の文字列に含まれる文字 c の総数.
       左に'?'が含まれるときは，それらに文字を入れて得られるすべての
       文字列に渡って，文字 c の個数を合計する. """
 
    def _left(S, c):
        """各位置より左にある c の個数. """
        n = [0 for c in S]
        for i in range(1, len(n)):
            n[i] = n[i-1] + (1 if S[i-1] == c else 0)
        return n
 
    # c の個数, '?'の個数
    n = _left(S, c)
    q = _left(S, '?')
 
    for i in range(len(n)):
        n[i] *= (3 ** q[i]) % modulo               # ?の埋め方の数だけ増やす
        n[i] += (3 ** (q[i] - 1)) * q[i] % modulo  # ?に入る'C'の個数
        n[i] %= modulo
    return n
 
def nright(S, c):
    n = nleft(list(reversed(S)), c)
    n.reverse()
    return n
 
left  = nleft (S, 'A')
right = nright(S, 'C')
 
# 各文字が'B'のときのABC数を計算
abc = 0
for i in range(0, len(S)):
    if S[i] in 'B?':
        abc += left[i] * right[i]
 
abc = int(abc) % modulo
print(abc)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

modulo = 10 ** 9 + 7

S = input()

def nleft(S, c):
    """各位置について，それより左の文字列に含まれる文字 c の総数.
       左に'?'が含まれるときは，それらに文字を入れて得られるすべての
       文字列に渡って，文字 c の個数を合計する. """

    def _left(S, c):
        """各位置より左にある c の個数. """
        n = [0 for c in S]
        for i in range(1, len(n)):
            n[i] = n[i-1] + (1 if S[i-1] == c else 0)
        return n

    # c の個数, '?'の個数
    n = _left(S, c)
    q = _left(S, '?')

    for i in range(len(n)):
        n[i] *= (3 ** q[i]) % modulo               # ?の埋め方の数だけ増やす
        n[i] += (3 ** (q[i] - 1)) * q[i] % modulo  # ?に入る'C'の個数
    return n

def nright(S, c):
    n = nleft(list(reversed(S)), c)
    n.reverse()
    return n

left  = nleft (S, 'A')
right = nright(S, 'C')

# 各文字が'B'のときのABC数を計算
abc = 0
for i in range(0, len(S)):
    if S[i] in 'B?':
        abc += left[i] * right[i]

abc = int(abc) % modulo
print(abc)

Submission status: Wrong Answer

Solution code:
s = list(input())

div = 10 ** 9 + 7

n = len(s)

all_q = s.count('?')

a0 = 0
a1 = 0
b0 = 0
b1 = 0
b2 = 0
c0 = 0
c1 = 0
c2 = 0
c3 = 0
for x in s:
    if x == 'A':
        a0 += 1
    elif x == 'B':
        b0 += a0
        b1 += a1
    elif x == 'C':
        c0 += b0
        c1 += b1
        c2 += b2
    else:
        c1 += b0
        c2 += b1
        c3 += b2
        b1 += a0
        b2 += a1
        a1 += 1

c = 0
temp = 3 ** all_q
if c3 > 0:
    c += c3 * (temp // 27) % div
if c2 > 0:
    c += c2 * (temp // 9) % div
if c1 > 0:
    c += c1 * (temp // 3) % div
c += c0 * temp % div

print(c)

Submission status: Wrong Answer

Solution code:
a = dict()
a['A'] = []
a['B'] = []
a['C'] = []
a['?'] = []

string = input()

for i in range(0, len(string)):
    temp = string[i]
    a[temp].append(i)
    
result = 0
dp = [0] * 4
MOD = 10**9 + 7
dp[0] = 1

for c in string:
    if c == '?':
        for i in range(3, 0, -1):
            dp[i] = dp[i]*3 + dp[i-1]
            dp[i] %= MOD
        dp[0] = dp[0]*3
        dp[0] %= MOD
    elif c == 'A':
        dp[1] += dp[0] % MOD
    elif c == 'B':
        dp[2] += dp[1] % MOD
    elif c == 'C':
        dp[3] += dp[2] % MOD
print (dp[3] % MOD)
print (a)

Submission status: Wrong Answer

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

mod=10**9+7

Alist=[0]*lens
Blist=[0]*lens
Clist=[0]*lens
qlist=[0]*lens

Asum=[0]*lens
Bsum=[0]*lens
Csum=[0]*lens
qsum=[0]*lens

for i in range(lens):
    if S[i]=="A":
        Alist[i]=1
    elif S[i]=="B":
        Blist[i]=1
    elif S[i]=="C":
        Clist[i]=1
    elif S[i]=="?":
        qlist[i]=1

    Asum[i]=Asum[i-1]+Alist[i]
    Bsum[i]=Bsum[i-1]+Blist[i]
    Csum[i]=Csum[i-1]+Clist[i]
    qsum[i]=qsum[i-1]+qlist[i]

ASUM=Asum[lens-1]
CSUM=Csum[lens-1]
QSUM=qsum[lens-1]


count=0
for i in range(1,lens-1):
    if S[i]=="B":
        count+=Asum[i-1]*(CSUM-Csum[i])*(3**max(0,QSUM))%mod
        count+=Asum[i-1]*(QSUM-qsum[i])*(3**max(0,(QSUM-1)))%mod
        count+=qsum[i-1]*(CSUM-Csum[i])*(3**max(0,(QSUM-1)))%mod
        count+=qsum[i-1]*(QSUM-qsum[i])*(3**max(0,(QSUM-2)))%mod


    elif S[i]=="?":
        count+=Asum[i-1]*(CSUM-Csum[i])*(3**max(0,(QSUM-1)))%mod
        count+=Asum[i-1]*(QSUM-qsum[i])*(3**max(0,(QSUM-2)))%mod
        count+=qsum[i-1]*(CSUM-Csum[i])*(3**max(0,(QSUM-2)))%mod
        count+=qsum[i-1]*(QSUM-qsum[i])*(3**max(0,(QSUM-3)))%mod

Submission status: Wrong Answer

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

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

dp[n] = [0, 0, 0, 1]
for i in range(n-1, -1, -1):
    if S[i] == '?':
        dp[i][3] =  dp[i+1][3] * 3 % mod
        dp[i][2] = (dp[i+1][2] * 3 + dp[i+1][3]) % mod
        dp[i][1] = (dp[i+1][1] * 3 + dp[i+1][2]) % mod
        dp[i][0] = (dp[i+1][0] * 3 + dp[i+1][1]) % mod
    elif S[i] == 'C':
        dp[i][3] =  dp[i+1][3] % mod
        dp[i][2] = (dp[i+1][2] + dp[i+1][3]) % mod
        dp[i][1] =  dp[i+1][1] % mod
        dp[i][0] =  dp[i+1][0] % mod
    elif S[i] == 'B':
        dp[i][3] =  dp[i+1][3] % mod
        dp[i][2] =  dp[i+1][2] % mod
        dp[i][1] = (dp[i+1][1] + dp[i+1][2]) % mod
        dp[i][0] =  dp[i+1][0] % mod
    elif S[i] == 'A':
        dp[i][3] =  dp[i+1][3]
        dp[i][2] =  dp[i+1][2]
        dp[i][1] =  dp[i+1][1]
        dp[i][0] = (dp[i+1][0] + dp[i+1][2]) % mod
print(dp[0][0])

Submission status: Wrong Answer

Solution code:
S = input()


MOD = 10**9 + 7

# time complexity: O(|S|)
def dp(S):
    dp = [[0] * 4 for _ in range(len(S) + 1)]
    dp[len(S)][3] = 1
    for i in range(len(S))[::-1]:
        dp[i][3] = 3 * dp[i + 1][3] if S[i] == "?" else dp[i + 1][3]
        dp[i][3] %= MOD
        if S[i] == "?":
            dp[i][0] = (3 * dp[i + 1][0] + dp[i + 1][1]) % MOD
            dp[i][1] = (3 * dp[i + 1][1] + dp[i + 1][2]) % MOD
            dp[i][2] = (3 * dp[i + 1][2] + dp[i + 1][3]) % MOD
        else:
            dp[i][0] = (dp[i + 1][0] + int(S[i] == "A") * dp[i + 1][1]) % MOD
            dp[i][1] = (dp[i + 1][1] + int(S[i] == "B") * dp[i + 1][2]) % MOD
            dp[i][2] = (dp[i + 1][2] + int(S[i] == "C") * dp[i + 1][3]) % MOD
    print(dp[0][0])


# time complexity: O(|S|)
def focus_on_B(S):
    cuml = {"A": [], 
            "C": [],
            "?": []}
    current_nums = {"A": 0,
                    "C": 0,
                    "?": 0}
    for char in S:
        if char in cuml.keys():
            current_nums[char] += 1
        for key in cuml.keys():
            cuml[key].append(current_nums[key])

    # num_combinations[i]: i番目をBとした時に、可能な組み合わせの数
    num_combinations = [0] * len(S)
    for i in range(1, len(S) - 1):
        if S[i] in {"B", "?"}:
            A_L = cuml["A"][i-1]
            Q_L = cuml["?"][i-1]
            C_R = cuml["C"][-1] - cuml["C"][i]
            Q_R = cuml["?"][-1] - cuml["?"][i]
            num_combinations[i] = ((A_L * 3 + Q_L) * int(3**(Q_L - 1))\
                                * (C_R * 3 + Q_R) * int(3**(Q_R - 1))) % MOD
        else:
            continue
    print(sum(num_combinations) % MOD)

focus_on_B(S)

Submission status: Wrong Answer

Solution code:
S = input()
p = 10 ** 9 + 7
DP = [0, 0, 0, 1]
dp = [0] * 4
for i in range(len(S) - 1, -1, -1):
  for j in range(3, -1, -1):
    if j == 3:
      dp[j] = DP[3] * (3 if S[i] == '?' else 1) % p
    else:
      dp[j] += DP[j + 1] * (1 if S[i] == chr(65 + j) or S[i] == '?' else 0)
      dp[j] += DP[j] * (3 if S[i] == '?' else 1)
      dp[j] % p
  DP = [x for x in dp]
print(DP[0] % p)

Submission status: Wrong Answer

Solution code:
S = input()
p = 10 ** 9 + 7
DP = [[0 for j in range(4)] for i in range(len(S) + 1)]
DP[len(S)][3] = 1
for i in range(len(S) - 1, -1, -1):
  for j in range(3, -1, -1):
    if j == 3:
      DP[i][j] = DP[i + 1][3] * (3 if S[i] == '?' else 1)
    else:
      DP[i][j] += DP[i + 1][j + 1] * (1 if S[i] == chr(65 + j) or S[i] == '?' else 0)
      DP[i][j] += DP[i + 1][j] * (3 if S[i] == '?' else 1)
      DP[i][j] % p
print(DP[0][0] % p + 1)