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=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,0,0,0]
for i in range(d[0]-3):
    mul[0]*=3
    mul[0]%=1000000007
for i in range(3):
    mul[i+1]=(mul[i]*3)%1000000007
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:
s = input()

ans = 0

z = [[0]*4 for i in range(len(s))]

t = 10**9+7

for i in range(1,len(s)-1):
    z[i][0] = z[i - 1][0]
    z[i][1] = z[i - 1][1]
    if s[i-1]=='A':
        z[i][0] +=1
    elif s[i-1]=='?':
        z[i][1] += 1

for i in range(1,len(s)-1):
    z[-i-1][2] = z[-i][2]
    z[-i-1][3] = z[-i][3]
    if s[-i]=='C':
        z[-i-1][2] += 1
    elif s[-i] =='?':
        z[-i-1][3] += 1


for i in range(1,len(s)-1):
    if s[i]=='B' or s[i]=='?':
        x = z[i][1]
        a = z[i][0]
        a1 = 3*a+x
        a2 = 3**(-1)
        for j in range(x):
            a2 = (a2*3)%t
        y = z[i][3]
        c = z[i][2]
        c1 = 3*c+y
        c2 = 3**(-1)
        for j in range(y):
            c2 = (c2*3)%t
        ans += (a1*a2*c1*c2)%t
    ans %=t

print(int(ans))

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=(3**d[0])%1000000007
res=0
for i in range(n-2):
    if s[i]=="A":
        res+=bc[i+1]*mul+(dc[i+1]+bd[i+1])*(mul//3)+dd[i+1]*(mul//9)
    if s[i]=="?":
        res+=bc[i+1]*(mul//3)+(dc[i+1]+bd[i+1])*(mul//9)+dd[i+1]*(mul//27)
    res%=1000000007
print(res)

Submission status: Wrong Answer

Solution code:
s = input()

ans = 0

z = [[0]*4 for i in range(len(s))]

t = 10**9+7
t1 = (3**100)%t

for i in range(1,len(s)-1):
    z[i][0] = z[i - 1][0]
    z[i][1] = z[i - 1][1]
    if s[i-1]=='A':
        z[i][0] +=1
    elif s[i-1]=='?':
        z[i][1] += 1

for i in range(1,len(s)-1):
    z[-i-1][2] = z[-i][2]
    z[-i-1][3] = z[-i][3]
    if s[-i]=='C':
        z[-i-1][2] += 1
    elif s[-i] =='?':
        z[-i-1][3] += 1


for i in range(1,len(s)-1):
    if s[i]=='B' or s[i]=='?':
        x = z[i][1]
        a = z[i][0]
        a1 = 3*a+x
        x1 = x//100
        x2 = x%100
        a2 = 3**(x2-1)%t
        a3 = (t1**x1)%t
        y = z[i][3]
        c = z[i][2]
        c1 = 3*c+y
        y1 = y//100
        y2 = y%100
        c2 = 3**(y2-1)%t
        c3 = (t1**y1)%t
        ans += (a1*a2*a3*c1*c2*c3)%t
    ans %=t

print(int(ans))

Submission status: Wrong Answer

Solution code:
s = input()

ans = 0

z = [[0]*4 for i in range(len(s))]

t = 10**9+7
t1 = (3**20)%t

for i in range(1,len(s)-1):
    z[i][0] = z[i - 1][0]
    z[i][1] = z[i - 1][1]
    if s[i-1]=='A':
        z[i][0] +=1
    elif s[i-1]=='?':
        z[i][1] += 1

for i in range(1,len(s)-1):
    z[-i-1][2] = z[-i][2]
    z[-i-1][3] = z[-i][3]
    if s[-i]=='C':
        z[-i-1][2] += 1
    elif s[-i] =='?':
        z[-i-1][3] += 1


for i in range(1,len(s)-1):
    if s[i]=='B' or s[i]=='?':
        x = z[i][1]
        a = z[i][0]
        a1 = 3*a+x
        x1 = x//20
        x2 = x%20
        a2 = 3**(x2-1)%t
        a3 = (t1**x1)%t
        y = z[i][3]
        c = z[i][2]
        c1 = 3*c+y
        y1 = y//20
        y2 = y%20
        c2 = 3**(y2-1)%t
        c3 = (t1**y1)%t
        ans += (a1*a2*a3*c1*c2*c3)%t
    ans %=t

print(int(ans))

Submission status: Wrong Answer

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

N = len(S)
A1,A2,A3,C1,C2,C3 = [1]*N,[0]*N,[1]*N,[1]*N,[0]*N,[1]*N
A4,C4 = [1]*N,[1]*N
a,aa = 0,0
c,cc = 0,0
for i in range(1,N):
    if S[i-1]=="A":
        a += 1
    if S[i-1]=="?":
        aa += 1
        A3[i] = A3[i-1]*3
    else:
        A3[i] = A3[i-1]
    A1[i],A2[i] = a,aa
    A4[i] = A3[i]//3
    if A4[i]>mod:
        A3[i] %= mod
        A4[i] %= mod
for i in range(1,N):
    if S[N-1-i+1]=="C":
        c += 1
    if S[N-1-i+1]=="?":
        cc += 1
        C3[N-1-i] = C3[N-1-i+1]*3
    else:
        C3[N-1-i] = C3[N-1-i+1]
    C1[N-1-i],C2[N-1-i] = c,cc
    C4[N-1-i] = C3[N-1-i]//3
    if C4[N-1-i]>mod:
        C3[N-1-i] %= mod
        C4[N-1-i] %= mod

Ans = 0
for i in range(1,N-1):
    if S[i]=="B" or S[i]=="?":
        ta,tc = 0,0
        if A2[i]==0:
            ta = A1[i]
        else:
            ta = (A4[i]*(A1[i]*3 + A2[i])) % mod 
        if C2[i]==0:
            tc = C1[i]
        else:
            tc = (C3[i]//3*(C1[i]*3 + C2[i])) % mod
        Ans += ta*tc
        
print(Ans % mod)

Submission status: Wrong Answer

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

N = len(S)
A1,A2,A3,C1,C2,C3 = [1]*N,[0]*N,[1]*N,[1]*N,[0]*N,[1]*N
A4,C4 = [1]*N,[1]*N
a,aa = 0,0
c,cc = 0,0
for i in range(1,N):
    if S[i-1]=="A":
        a += 1
    if S[i-1]=="?":
        aa += 1
        A3[i] = A3[i-1]*3
        if A3[i] > mod:
            A3[i] %= mod
    else:
        A3[i] = A3[i-1]
    A1[i],A2[i] = a,aa
for i in range(1,N):
    if S[N-1-i+1]=="C":
        c += 1
    if S[N-1-i+1]=="?":
        cc += 1
        C3[N-1-i] = C3[N-1-i+1]*3
        if C3[N-1-i] > mod:
            C3[N-1-i] %= mod
    else:
        C3[N-1-i] = C3[N-1-i+1]
    C1[N-1-i] = c
    C2[N-1-i] = cc

Ans = 0
for i in range(1,N-1):
    if S[i]=="B" or S[i]=="?":
        ta,tc = 0,0
        if A2[i]==0:
            ta = A1[i]
        else:
            ta = (A3[i]//3*(A1[i]*3 + A2[i])) % mod 
        if C2[i]==0:
            tc = C1[i]
        else:
            tc = (C3[i]//3*(C1[i]*3 + C2[i])) % mod
        Ans += ta*tc

print(Ans % mod)

Submission status: Wrong Answer

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

N = len(S)
A1,A2,A3,C1,C2,C3 = [1]*N,[0]*N,[1]*N,[1]*N,[0]*N,[1]*N
A4,C4 = [1]*N,[1]*N
a,aa = 0,0
c,cc = 0,0
for i in range(1,N):
    if S[i-1]=="A":
        a += 1
    if S[i-1]=="?":
        aa += 1
        A3[i] = A3[i-1]*3
        if A3[i] > mod:
            A3[i] %= mod
    else:
        A3[i] = A3[i-1]
    A1[i],A2[i] = a,aa
    A4[i] = A3[i]//3 % mod
for i in range(1,N):
    if S[N-1-i+1]=="C":
        c += 1
    if S[N-1-i+1]=="?":
        cc += 1
        C3[N-1-i] = C3[N-1-i+1]*3
        if C3[N-1-i] > mod:
            C3[N-1-i] %= mod
    else:
        C3[N-1-i] = C3[N-1-i+1]
    C1[N-1-i] = c
    C2[N-1-i] = cc
    C4[N-1-i] = C3[N-1-i]//3 % mod

Ans = 0
for i in range(1,N-1):
    if S[i]=="B" or S[i]=="?":
        ta,tc = 0,0
        if A2[i]==0:
            ta = A1[i]
        else:
            ta = (A4[i]*(A1[i]*3 + A2[i])) % mod 
        if C2[i]==0:
            tc = C1[i]
        else:
            tc = (C4[i]*(C1[i]*3 + C2[i])) % mod
        Ans += ta*tc

print(Ans % mod)

Submission status: Wrong Answer

Solution code:
s = input()

dp1 = {'A': 0, 'AB': 0, 'ABC': 0}
if s[0] == 'A' or s[0] == '?':
    dp1['A'] = 1

c = 1000000000 + 7

#print(dp1)
for i in range(1, len(s)):
    dp2 = {'A': 0, 'AB': 0, 'ABC': 0}

    if s[i] == '?':
        dp2['A'] = dp1['A']*3 + 1
    elif s[i] == 'A':
        dp2['A'] = dp1['A'] + 1
    else:
        dp2['A'] = dp1['A']

    if s[i] == '?':
        dp2['AB'] = dp1['AB']*3 + dp1['A']
    elif s[i] == 'B':
        dp2['AB'] = dp1['AB'] + dp1['A']
    else:
        dp2['AB'] = dp1['AB']

    if s[i] == '?':
        dp2['ABC'] = dp1['ABC']*3 + dp1['AB']
    elif s[i] == 'C':
        dp2['ABC'] = dp1['ABC'] + dp1['AB']
    else:
        dp2['ABC'] = dp1['ABC']

    for i in dp2.keys():
        dp2[i] = dp2[i] % c
    dp1 = dp2.copy()
    #print(i, dp1)

print(dp1['ABC'])

Submission status: Wrong Answer

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

N = len(S)
A1,A2,A3,C1,C2,C3 = [1]*N,[1]*N,[1]*N,[1]*N,[1]*N,[1]*N
a,aa = 0,0
c,cc = 0,0
for i in range(1,N):
    if S[i-1]=="A":
        a += 1
    if S[i-1]=="?":
        aa += 1
        A3[i] = A3[i-1]*3 % mod
    else:
        A3[i] = A3[i-1]
    A1[i],A2[i] = a,aa
for i in range(1,N):
    if S[N-1-i+1]=="C":
        c += 1
    if S[N-1-i+1]=="?":
        cc += 1
        C3[N-1-i] = C3[N-1-i+1]*3 % mod
    else:
        C3[N-1-i] = C3[N-1-i+1]
    C1[N-1-i] = c
    C2[N-1-i] = cc

Ans = 0
for i in range(1,N-1):
    if S[i]=="B" or S[i]=="?":
        ta,tc = 0,0
        if A2[i]==0:
            ta = A1[i]
        else:
            ta = A3[i]*(A1[i]*3 + A2[i])//3
        if C2[i]==0:
            tc = C1[i]
        else:
            tc = C3[i]*(C1[i]*3 + C2[i])//3
        Ans += ta*tc
        Ans %= mod

print(Ans)

Submission status: Wrong Answer

Solution code:
s = input()
count = 0
q_count = s.count("?")

for i in range(3**q_count):
    s_in_A = s.replace("?","A", q_count-i)
    s_in_AB = s_in_A.replace("?","B", q_count-i)
    s_in_ABC = s_in_AB.replace("?","C")
    
    while s_in_ABC in "A":
        i = s_in_ABC.find("A")

        while s_in_ABC[i:] in "B":
            j = s_in_ABC.find("B")

            while s_in_ABC[j:] in "C":
                count += s_in_ABC[j:].count("C")
            
            s_in_ABC = s_in_ABC.replace("B", "b")

        s_in_ABC = s_in_ABC.replace("A","a")

print(count % (10**9+7))

Submission status: Wrong Answer

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

N = len(S)
A1,A2,A3,C1,C2,C3 = [1]*N,[1]*N,[1]*N,[1]*N,[1]*N,[1]*N
a,aa = 0,0
c,cc = 0,0
for i in range(1,N):
    if S[i-1]=="A":
        a += 1
    if S[i-1]=="?":
        aa += 1
        A3[i] = (A3[i-1]*3) % mod
    else:
        A3[i] = A3[i-1]
    A1[i],A2[i] = a,aa
for i in range(1,N):
    if S[N-1-i+1]=="C":
        c += 1
    if S[N-1-i+1]=="?":
        cc += 1
        C3[N-1-i] = (C3[N-1-i+1]*3) % mod
    else:
        C3[N-1-i] = C3[N-1-i+1]
    C1[N-1-i] = c
    C2[N-1-i] = cc

Ans = 0
for i in range(1,N-1):
    if S[i]=="B" or S[i]=="?":
        ta,tc = 0,0
        if A2[i]==0:
            ta = A1[i]
        else:
            ta = A3[i]*A1[i] + A3[i]//3*A2[i]
            ta %= mod
        if C2[i]==0:
            tc = C1[i]
        else:
            tc = C3[i]*C1[i] + C3[i]//3*C2[i]
            tc %= mod
        Ans += ta*tc
        Ans %= mod

print(Ans)

Submission status: Wrong Answer

Solution code:
s = input()

m = 1000000007
dp = [0] * 4
dp[0] = 1

for c in s:
  if c=='A':
    dp[1] += dp[0]
  elif c=='B':
    dp[2] += dp[1]
  elif c=='C':
    dp[3] += dp[2]
  elif c=='?':
    dp = [(dp[0]*3)%m, (dp[0]+dp[1]*3)%m, (dp[1]+dp[2]*3)%m, (dp[2]+dp[3]*3)%m]

print(dp[3])

Submission status: Wrong Answer

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

a = [0]*len(s)
c = [0]*len(s)
lq = [0]*len(s)
rq = [0]*len(s)

for i in range(1, len(s)):
  if s[i-1]=="A":
    a[i] = a[i-1]+1
  else:
    a[i] = a[i-1]
  if s[i-1]=="?":
    lq[i] = lq[i-1]+1
  else:
    lq[i] = lq[i-1]
for i in range(len(s)-2, -1, -1):
  if s[i+1]=="C":
    c[i] = c[i+1]+1
  else:
    c[i] = c[i+1]
  if s[i+1]=="?":
    rq[i] = rq[i+1]+1
  else:
    rq[i] = rq[i+1]

ans = 0
for i in range(1, len(s)-1):
  if s[i]=="B" or s[i]=="?":
    ans += (3*a[i]+lq[i])*(3*c[i]+rq[i])*3**(lq[i]+rq[i]-2)
print(ans%MOD)

Submission status: Wrong Answer

Solution code:
s = input()
count = 0
len = len(s)
def isa(char):
    if char == 'A' or char == '?':
        return 1
    else:
        return 0
def isc(char):
    if char == 'C' or char == '?':
        return 1
    else:
        return 0
q = 0
for i in range(len):
    if s[i] == '?':
        q += 1
    else:
        continue
for i in range(len):
    a, c = 0, 0
    if s[i] == 'A' or s[i] == 'C':
        continue
    else:
        for j in range(i):
            a += isa(s[j])
        for j in range(i+1, len):
            c += isc(s[j])
    if s[i] == 'B':
        count += a * c * pow(3, q)
    else:
        count += a * c * pow(3, q-1)
print(count % 1000000007)

Submission status: Wrong Answer

Solution code:
from collections import Counter
from collections import defaultdict

S = input()

right = Counter(S)
left = defaultdict(int)

hatena = right["?"]
#print(hatena)

ans = 0
mod = pow(10,9)+7
for s in S:
    right[s] -=1
    if s=="B":
        ans = (ans + right["C"]*left["A"]*pow(3,hatena) + right["?"]*left["A"]*pow(3,hatena-1) \
        + right["C"]*left["?"]*pow(3,hatena-1) + right["?"]*left["?"]*pow(3,hatena-2))%mod
        #print(s,ans)
    if s=="?":
        ans = (ans + right["C"]*left["A"]*pow(3,hatena-1) + right["?"]*left["A"]*pow(3,hatena-2) \
        + right["C"]*left["?"]*pow(3,hatena-2) + right["?"]*left["?"]*pow(3,hatena-3))%mod
        #print(s,ans)
    left[s] +=1
    #print(right,left)
    
print(ans)

Submission status: Wrong Answer

Solution code:
s = input()
count = 0
len = len(s)
def isa(char):
    if char == 'A' or char == '?':
        return 1
    else:
        return 0
def isc(char):
    if char == 'C' or char == '?':
        return 1
    else:
        return 0
q = 0
for i in range(len):
    if s[i] == '?':
        q += 1
    else:
        continue
for i in range(len):
    a, c = 0, 0
    if s[i] == 'A' or s[i] == 'C':
        continue
    else:
        for j in range(i):
            a += isa(s[j])
        for j in range(i+1, len):
            c += isc(s[j])
    if s[i] == 'B':
        count += a * c * pow(2, q)
    else:
        count += a * c * pow(2, q-1)
print(count % 1000000007)

Submission status: Wrong Answer

Solution code:
S = input()
L = len(S)
Q = 10**9 + 7
anum = [ 0 for _ in range(L+1)]
#bnum = [ 0 for _ in range(L+1)]
cnum = [ 0 for _ in range(L+1)]
hnum = [ 0 for _ in range(L+1)]
for i in range(1,L+1):
    if S[i-1] == 'A':
        anum[i] = anum[i-1] + 1
#        bnum[i] = bnum[i-1]
        cnum[i] = cnum[i-1]
        hnum[i] = hnum[i-1]
    elif S[i-1] == 'B':
        anum[i] = anum[i-1]
#        bnum[i] = bnum[i-1] + 1
        cnum[i] = cnum[i-1]
        hnum[i] = hnum[i-1]
    elif S[i-1] == 'C':
        anum[i] = anum[i-1]
#        bnum[i] = bnum[i-1]
        cnum[i] = cnum[i-1] + 1
        hnum[i] = hnum[i-1]
    else:
        anum[i] = anum[i-1]
#        bnum[i] = bnum[i-1]
        cnum[i] = cnum[i-1]
        hnum[i] = hnum[i-1] + 1

ans = 0
czen = cnum[L]
hzen = hnum[L] 
for i in range(1,L+1):
    if S[i-1] == 'B' or S[i-1] == '?':
        A = (anum[i-1]*(3**hnum[i-1]) + hnum[i-1]*(2**(hnum[i-1]-1)))%Q
        C = ((czen - cnum[i])*(3**(hzen - hnum[i])) + (hzen - hnum[i])*(2**(hzen - hnum[i]-1)))%Q
        ans = (ans + A*C)%Q
print(int(ans))

Submission status: Wrong Answer

Solution code:
s = input()

ans = 0

z = [[0]*4 for i in range(len(s))]

for i in range(1,len(s)-1):
    z[i][0] = z[i - 1][0]
    z[i][1] = z[i - 1][1]
    if s[i-1]=='A':
        z[i][0] +=1
    elif s[i-1]=='?':
        z[i][1] += 1

for i in range(1,len(s)-1):
    z[-i-1][2] = z[-i][2]
    z[-i-1][3] = z[-i][3]
    if s[-i]=='C':
        z[-i-1][2] += 1
    elif s[-i] =='?':
        z[-i-1][3] += 1


for i in range(1,len(s)-1):
    if s[i]=='B' or s[i]=='?':
        x = z[i][1]
        a = z[i][0]
        a_ = ((3*a+x)*(3 ** (x-1))) % (10 ** 9 + 7)
        y = z[i][3]
        c = z[i][2]
        c_ = ((3*c+y)*(3**(y-1)))%(10**9+7)
        ans += (a_*c_)%(10**9+7)

ans %=(10**9+7)
print(ans)

Submission status: Wrong Answer

Solution code:
s=list(input())
l=len(s)
m=10**9 +7
def ck(X):
  a=[]
  an=0
  for i in s:
    if i==X:
      an+=1
    a+=[an]
  return a
a=ck("A")
c=ck("C")
x=ck("?")

ans=0
for i in range(1,l-1):
  if s[i] in ('B','?'):
    aa=a[i-1]
    cc=c[l-1]-c[i]
    if x[i-1] !=0:
      aa=max(aa,1)
    if x[l-1]-x[i] !=0:
      cc=max(cc,1)      
    ac=aa * cc
    xa=x[i-1] if a[i-1] !=0 else max(x[i-1]-1,0)
    xc=x[l-1]-x[i] if c[l-1]-c[i]!=0 else max(x[l-1]-x[i]-1,0) 
    if xa!=0:
      ans += 3**xa
    if xc!=0:
      ans += 3**xc
    ans += ac 
print(ans%m)

Submission status: Wrong Answer

Solution code:
"""
問題文
文字列 T の ABC 数 とは、以下の条件をすべて満たす整数の組 (i,j,k) の個数です。

1≤i<j<k≤|T|（|T| は T の長さ）
Ti= A（Ti は T の先頭から i 番目の文字）
Tj= B
Tk= C
例えば、T= ABCBC のとき、条件をすべて満たす組 (i,j,k) は
 (1,2,3),(1,2,5),(1,4,5) の 3 個であるため、T の ABC 数は 3 です。

文字列 S が与えられます。S のそれぞれの文字は A, B, C, ? のいずれかです。

S に含まれる ? の個数を Q とします。S に含まれる ? を
それぞれ A, B, C のいずれかに置き換えることで 3Q 通りの文字列が作られます。
これらの文字列すべての ABC 数の和を求めてください。

ただし、この和は非常に大きくなりうるため、和を 109+7 で割った余りを出力してください。

制約
3≤|S|≤105
S のそれぞれの文字は A, B, C, ? のいずれかである。
入力
入力は以下の形式で標準入力から与えられる。

S
出力
3Q 通りの文字列すべての ABC 数の和を 109+7 で割った余りを出力せよ。
"""

"""左端のAまたは?からBまたは?の個数とそれより右にあるCまたは?の数を掛けた数が答えになる"""

s = input()
a = -1
b = -1
c = []
for i in range(len(s)):
    if s[i] != "A" and s[i] != "B" and s[i] != "C":
        s = s[0:i]+"P"+s[i+1:len(s)]
#print(s)

for i in range(len(s)):
    if (s[i] == "A" or s[i] == "P") and (i <= len(s) - 3):
        #print(s[i])
        for j in range(i + 1, len(s)):
            if (s[j] == "B" or s[j] == "P") and (j <= len(s) - 2):
                a = s[j :s.rfind("C" or "P")].count("B")+s[j:s.rfind("C" or "P")].count("P")
                for k in range(j + 1, len(s)):
                    if s[k] == "C" or s[k] == "P":
                        b = s[k:len(s)].count("C")+s[k:len(s)].count("P")
                        #print(a, b)
                        c.append(a * b)
print(sum(c)%(10**9+7))

Submission status: Wrong Answer

Solution code:
print(3)

Submission status: Wrong Answer

Solution code:
import numpy as np

s = input()

a = np.zeros(len(s))
q = np.zeros(len(s))
ab0 = np.zeros(len(s))
ab1 = np.zeros(len(s))
ab2 = np.zeros(len(s))
abc0 = np.zeros(len(s))
abc1 = np.zeros(len(s))
abc2 = np.zeros(len(s))
abc3 = np.zeros(len(s))

for i in range(len(s)):
    if s[i]=='A':
        a[i] = a[i-1]+1
        q[i] = q[i-1]
        ab0[i] = ab0[i-1]
        ab1[i] = ab1[i-1]
        ab2[i] = ab2[i-1]
        abc0[i] = abc0[i-1]
        abc1[i] = abc1[i-1]
        abc2[i] = abc2[i-1]
        abc3[i] = abc3[i-1]
    elif s[i]=='B':
        a[i] = a[i-1]
        q[i] = q[i-1]
        ab0[i] = ab0[i-1]+a[i-1]
        ab1[i] = ab1[i-1]+q[i-1]
        ab2[i] = ab2[i-1]
        abc0[i] = abc0[i-1]
        abc1[i] = abc1[i-1]
        abc2[i] = abc2[i-1]
        abc3[i] = abc3[i-1]
    elif s[i]== 'C':
        a[i] = a[i-1]
        q[i] = q[i-1]
        ab0[i] = ab0[i-1]
        ab1[i] = ab1[i-1]
        ab2[i] = ab2[i-1]
        abc0[i] = abc0[i-1]+ab0[i-1]
        abc1[i] = abc1[i-1]+ab1[i-1]
        abc2[i] = abc2[i-1]+ab2[i-1]
        abc3[i] = abc3[i-1]
    else:
        a[i] = a[i-1]
        q[i] = q[i-1]+1
        ab0[i] = ab0[i-1]
        ab1[i] = ab1[i-1]+a[i-1]
        ab2[i] = ab2[i-1]+q[i-1]
        abc0[i] = abc0[i-1]
        abc1[i] = abc1[i-1]+ab0[i-1]
        abc2[i] = abc2[i-1]+ab1[i-1]
        abc3[i] = abc3[i-1]+ab2[i-1]
        
m = int(q[len(s)-1])        
p = 1000000007
l3 = 1
l2 = 1
l1 = 1
l0 = 1
for i in range(m):
    l0 *= 3
    l0 %= p
    if i<m-1:
        l1 *= 3
        l1 %= p
    if i<m-2:
        l2 *= 3
        l2 %= p
    if i<m-3:
        l3 *= 3
        l3 %= p


n = int(abc0[len(s)-1]%p * (l0))
n %= 1000000007
n += int(abc1[len(s)-1]%p * (l1))
n %= 1000000007
n += int(abc2[len(s)-1]%p * (l2))
n %= 1000000007
n += int(abc3[len(s)-1]%p * (l3))
n %= 1000000007
print(int(n))

Submission status: Wrong Answer

Solution code:
import numpy as np

s = input()

a = np.zeros(len(s))
q = np.zeros(len(s))
ab0 = np.zeros(len(s))
ab1 = np.zeros(len(s))
ab2 = np.zeros(len(s))
abc0 = np.zeros(len(s))
abc1 = np.zeros(len(s))
abc2 = np.zeros(len(s))
abc3 = np.zeros(len(s))

for i in range(len(s)):
    if s[i]=='A':
        a[i] = a[i-1]+1
        q[i] = q[i-1]
        ab0[i] = ab0[i-1]
        ab1[i] = ab1[i-1]
        ab2[i] = ab2[i-1]
        abc0[i] = abc0[i-1]
        abc1[i] = abc1[i-1]
        abc2[i] = abc2[i-1]
        abc3[i] = abc3[i-1]
    elif s[i]=='B':
        a[i] = a[i-1]
        q[i] = q[i-1]
        ab0[i] = ab0[i-1]+a[i-1]
        ab1[i] = ab1[i-1]+q[i-1]
        ab2[i] = ab2[i-1]
        abc0[i] = abc0[i-1]
        abc1[i] = abc1[i-1]
        abc2[i] = abc2[i-1]
        abc3[i] = abc3[i-1]
    elif s[i]== 'C':
        a[i] = a[i-1]
        q[i] = q[i-1]
        ab0[i] = ab0[i-1]
        ab1[i] = ab1[i-1]
        ab2[i] = ab2[i-1]
        abc0[i] = abc0[i-1]+ab0[i-1]
        abc1[i] = abc1[i-1]+ab1[i-1]
        abc2[i] = abc2[i-1]+ab2[i-1]
        abc3[i] = abc3[i-1]
    else:
        a[i] = a[i-1]
        q[i] = q[i-1]+1
        ab0[i] = ab0[i-1]
        ab1[i] = ab1[i-1]+a[i-1]
        ab2[i] = ab2[i-1]+q[i-1]
        abc0[i] = abc0[i-1]
        abc1[i] = abc1[i-1]+ab0[i-1]
        abc2[i] = abc2[i-1]+ab1[i-1]
        abc3[i] = abc3[i-1]+ab2[i-1]
        
m = int(q[len(s)-1])        
p = 1000000007
l3 = 1
l2 = 1
l1 = 1
l0 = 1
for i in range(m):
    l0 *= 3
    l0 %= p
    if i<m-1:
        l1 *= 3
        l1 %= p
    if i<m-2:
        l2 *= 3
        l2 %= p
    if i<m-3:
        l3 *= 3
        l3 %= p


n = int(abc0[len(s)-1] * (l0))
n %= 1000000007
n += int(abc1[len(s)-1] * (l1))
n %= 1000000007
n += int(abc2[len(s)-1] * (l2))
n %= 1000000007
n += int(abc3[len(s)-1] * (l3))
n %= 1000000007
print(int(n))

Submission status: Wrong Answer

Solution code:
print(8)

Submission status: Wrong Answer

Solution code:
S = input()
L = len(S)
Q = 10**9 + 7
anum = [ 0 for _ in range(L+1)]
bnum = [ 0 for _ in range(L+1)]
cnum = [ 0 for _ in range(L+1)]
hnum = [ 0 for _ in range(L+1)]
for i in range(1,L+1):
    if S[i-1] == 'A':
        anum[i] = anum[i-1] + 1
        bnum[i] = bnum[i-1]
        cnum[i] = cnum[i-1]
        hnum[i] = hnum[i-1]
    elif S[i-1] == 'B':
        anum[i] = anum[i-1]
        bnum[i] = bnum[i-1] + 1
        cnum[i] = cnum[i-1]
        hnum[i] = hnum[i-1]
    elif S[i-1] == 'C':
        anum[i] = anum[i-1]
        bnum[i] = bnum[i-1]
        cnum[i] = cnum[i-1] + 1
        hnum[i] = hnum[i-1]
    else:
        anum[i] = anum[i-1]
        bnum[i] = bnum[i-1]
        cnum[i] = cnum[i-1]
        hnum[i] = hnum[i-1] + 1

ans = 0
czen = cnum[L]
hzen = hnum[L] 
for i in range(1,L+1):
    if S[i-1] == 'B' or S[i-1] == '?':
        A = (anum[i-1]*(3**hnum[i-1]) + hnum[i-1]*(2**(hnum[i-1]-1)))%Q
        C = ((czen - cnum[i])*(3**(hzen - hnum[i])) + (hzen - hnum[i])*(2**(hzen - hnum[i]-1)))%Q
        ans = (ans + A*C)%Q
print(int(ans))

Submission status: Wrong Answer

Solution code:
import numpy as np

s = input()

a = np.zeros(len(s))
q = np.zeros(len(s))
ab0 = np.zeros(len(s))
ab1 = np.zeros(len(s))
ab2 = np.zeros(len(s))
abc0 = np.zeros(len(s))
abc1 = np.zeros(len(s))
abc2 = np.zeros(len(s))
abc3 = np.zeros(len(s))

for i in range(len(s)):
    if s[i]=='A':
        a[i] = a[i-1]+1
        q[i] = q[i-1]
        ab0[i] = ab0[i-1]
        ab1[i] = ab1[i-1]
        ab2[i] = ab2[i-1]
        abc0[i] = abc0[i-1]
        abc1[i] = abc1[i-1]
        abc2[i] = abc2[i-1]
        abc3[i] = abc3[i-1]
    elif s[i]=='B':
        a[i] = a[i-1]
        q[i] = q[i-1]
        ab0[i] = ab0[i-1]+a[i-1]
        ab1[i] = ab1[i-1]+q[i-1]
        ab2[i] = ab2[i-1]
        abc0[i] = abc0[i-1]
        abc1[i] = abc1[i-1]
        abc2[i] = abc2[i-1]
        abc3[i] = abc3[i-1]
    elif s[i]== 'C':
        a[i] = a[i-1]
        q[i] = q[i-1]
        ab0[i] = ab0[i-1]
        ab1[i] = ab1[i-1]
        ab2[i] = ab2[i-1]
        abc0[i] = abc0[i-1]+ab0[i-1]
        abc1[i] = abc1[i-1]+ab1[i-1]
        abc2[i] = abc2[i-1]+ab2[i-1]
        abc3[i] = abc3[i-1]
    else:
        a[i] = a[i-1]
        q[i] = q[i-1]+1
        ab0[i] = ab0[i-1]
        ab1[i] = ab1[i-1]+a[i-1]
        ab2[i] = ab2[i-1]+q[i-1]
        abc0[i] = abc0[i-1]
        abc1[i] = abc1[i-1]+ab0[i-1]
        abc2[i] = abc2[i-1]+ab1[i-1]
        abc3[i] = abc3[i-1]+ab2[i-1]
        
m = int(q[len(s)-1])        
p = 1000000007
l3 = 1
l2 = 1
l1 = 1
l0 = 1
for i in range(m):
    l0 *= 3
    l0 %= p
    if i<m-1:
        l1 *= 3
        l1 %= p
    if i<m-2:
        l2 *= 3
        l2 %= p
    if i<m-3:
        l3 *= 3
        l3 %= p


n = abc0[len(s)-1] * (l0)
n %= 1000000007
n += abc1[len(s)-1] * (l1)
n %= 1000000007
n += abc2[len(s)-1] * (l2)
n %= 1000000007
n += abc3[len(s)-1] * (l3)
n %= 1000000007
print(int(n))

Submission status: Wrong Answer

Solution code:
s=input()

a=0
ab=0
abc=0
q=0
m=10**9+7

for i in range(len(s)):
  if s[i]=="A":
    a=(a+3**q)%m
  elif s[i]=="B":
    ab=ab+a
  elif s[i]=="C":
    abc=abc+ab
  elif s[i]=="?":
    abc=(abc*3+ab)%m
    ab=(ab*3+a)%m
    a=(a*3+3**q)%m
    q+=1
print(abc)

Submission status: Wrong Answer

Solution code:
mod = 1000000007


s = raw_input()
n_a = n_ab = n_abc = 0
p = 1

for c in s:
    if c == "A":
        n_a = (n_a + 1) % mod
    elif c == "B":
        n_ab = (n_ab + n_a) % mod
    elif c == "C":
        n_abc = (n_abc + n_ab) % mod
    elif c == "?":
        n_abc = (n_abc * 3 + n_ab) % mod
        n_ab = (n_ab * 3 + n_a) % mod
        n_a = (n_a * 3 + p) % mod
        p = (p * 3) % mod

    # print n_a, n_ab, n_abc

print n_abc % mod

Submission status: Wrong Answer

Solution code:
import numpy as p
s=input()
A=B=C=p.array([0,0,0,0])
t=0
for c in s:
	if c=="A":
		A[0]+=1
	if c=="B":
		B+=A
	if c=='C':
		C+=B
	if c=='?':
		C+=p.roll(B,1)
		B[1]+=A[0]
		B[2]+=A[1]
		A[1]+=1
		t+=1
ans=0
for i in range(4):
	ans+=pow(3,t-i)*C[i]
print(int(ans%1000000007))

Submission status: Wrong Answer

Solution code:
S=input()
N=len(S)
Q=S.count("?")
P=10**9+7
M=[0 for i in range(Q+1)]
M[0]=1
for i in range(1,Q+1):
    M[i]=(M[i-1]*3)%P
A=[0 for i in range(N)]
C=[0 for i in range(N)]
AQ=[0 for i in range(N)]
CQ=[0 for i in range(N)]
ans=0
cnt=0
for i in range(N):
    if S[i]=="A":
        cnt+=1
    A[i]=cnt
cnt=0
for i in range(N)[::-1]:
    if S[i]=="C":
        cnt+=1
    C[i]=cnt
cnt=0
for i in range(N):
    if S[i]=="?":
        cnt+=1
    AQ[i]=cnt
cnt=0
for i in range(N)[::-1]:
    if S[i]=="?":
        cnt+=1
    CQ[i]=cnt
for i in range(N):
    if S[i]=="B":
        delta=(((A[i]+(M[AQ[i]]*AQ[i])%P)%P)*((C[i]+(M[CQ[i]]*CQ[i])%P)%P))%P
        ans=(ans+delta)%P
    if S[i]=="?":
        delta=(((A[i]+(M[AQ[i]-1]*(AQ[i]-1))%P)%P)*((C[i]+(M[CQ[i]-1]*(CQ[i]-1))%P)%P))%P
        ans=(ans+delta)%P
print(ans)

Submission status: Wrong Answer

Solution code:
s=input()

a=0
ab=0
abc=0
q=0

#if s[0]=="A" :
#  a=1
#elif s[0]=="?":
#  a=1
#  q=1
#print(str(a)+" "+str(ab)+" "+str(abc)+" "+str(q))

for i in range(len(s)):
  if s[i]=="A":
    a=a+3**q
  elif s[i]=="B":
    ab=ab+a
  elif s[i]=="C":
    abc=abc+ab
  elif s[i]=="?":
    abc=(abc*3+ab)%(10**9+7)
    
    ab=ab*3+a
    a=a*3
    
    a=a+3**q
    q+=1
  #print(str(a)+" "+str(ab)+" "+str(abc)+" "+str(q))
    
print(abc)

Submission status: Wrong Answer

Solution code:
S=input()

emp=1
A=0
AB=0
ABC=0

big = 10**9+7



for a in S:
    if a == 'A':
        (emp,A,AB,ABC)=(emp,emp+A,AB,ABC)
    if a == 'B':
        (emp,A,AB,ABC)=(emp,A,A+AB,ABC)
    if a == 'C':
        (emp,A,AB,ABC)=(emp,A,AB,AB + ABC)
    if a == '?':
        (emp,A,AB,ABC)=(3*emp%big, (emp+ 3*A) %big, (A+ 3*AB)%big,(AB + 3*ABC)%big)
    print(emp,A,AB,ABC)

print(ABC%big)

Submission status: Wrong Answer

Solution code:
import numpy as np
s=input()
A=np.array([0,0,0,0])
B=np.array([0,0,0,0])
C=np.array([0,0,0,0])
t=0
for c in s:
	if c=="A":
		A[0]+=1
	if c=="B":
		B+=A
	if c=='C':
		C+=B
	if c=='?':
		C+=np.roll(B,1)
		B+=np.roll(A,1)
		A[1]+=1
		t+=1
ans=0
for i in range(4):
	ans+=pow(3,t-i)*C[i]
print(str(int(ans%1000000007))+".0")

Submission status: Wrong Answer

Solution code:
import numpy as np
s=input()
A=np.array([0,0,0,0])
B=np.array([0,0,0,0])
C=np.array([0,0,0,0])
t=0
for c in s:
	if c=="A":
		A[0]+=1
	if c=="B":
		B+=A
	if c=='C':
		C+=B
	if c=='?':
		C+=np.roll(B,1)
		B+=np.roll(A,1)
		A[1]+=1
		t+=1
ans=0
for i in range(4):
	ans+=pow(3,t-i)*C[i]
print(ans%1000000007)

Submission status: Wrong Answer

Solution code:
string = '????C?????B??????A???????'
#string = 'A??C'
ac = 0
bc = 0
cc = 0
ac2 = 0
bc2 = 0
bc3 = 0
bc4 = 0
cc2 = 0
cc3 = 0
cc4 = 0
cc5 = 0
cc6 = 0
cc7 = 0
cc8 = 0
for s in string:
    if s == 'A':
        ac += 1
    elif s == 'B':
        bc += ac
        bc2 += ac2
    elif s == 'C':
        cc += bc
        cc2 += bc2
        cc3 += bc3
        cc4 += bc4
    elif s == '?':
        cc5 += bc2
        cc6 += bc3
        cc7 += bc4
        cc8 += bc

        bc3 += ac
        bc4 += ac2

        ac2 += 1

#print(cc)
#print(cc3)
result = (cc7) + ((cc4+cc5+cc6) * 3) + ((cc2+cc3+cc8)*9) + (cc*27)
#print(ac2)
result *= pow(3, ac2-3)
print(result%(pow(10,9)+7))

Submission status: Wrong Answer

Solution code:
import numpy as np
s=input()
A=np.array([0,0,0,0])
B=np.array([0,0,0,0])
C=np.array([0,0,0,0])
t=0
for c in s:
	if c=="A":
		A[0]+=1
	if c=="B":
		B+=A
	if c=='C':
		C+=B
	if c=='?':
		C[1]+=B[0]
		C[2]+=B[1]
		C[3]+=B[2]
		B[1]+=A[0]
		B[2]+=A[1]
		A[1]+=1
		t+=1
ans=0
for i in range(4):
	ans+=pow(3,t-i)*C[i]
print(ans%1000000007)

Submission status: Wrong Answer

Solution code:
import numpy as np
s=input()
wayA=np.array([0,0,0,0])
wayB=np.array([0,0,0,0])
wayC=np.array([0,0,0,0])
hatena=0
for c in s:
	if c=="A":
		wayA[0]+=1
	if c=="B":
		wayB+=wayA
	if c=='C':
		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+=1
ans=0
for i in range(0,4):
	ans=ans+pow(3,hatena-i)*wayC[i]
print(ans%1000000007)