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 .

Solution (Python):

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)
    if q-1>=0:
        pow3q_1=pow(3,q-1,MOD)
    else:
        pow3q_1=0
    if q-2>=0:
        pow3q_2=pow(3,q-2,MOD)
    else:
        pow3q_2=0
    if q-3>=0:
        pow3q_3=pow(3,q-3,MOD)
    else:
        pow3q_3=0
    
    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()

Solution (Python):
data = input()
MOD = 10**9 + 7
SLen = len(data)
targets = "ABC"
array = [[0 for i in range(SLen + 1)] for _ in range(4)]
array[0][0] = 1
for i in range(SLen):
    for j in range(4):
        if data[i] == '?':
            if j < 3:
                array[j + 1][i + 1] = (array[j + 1][i + 1] + array[j][i]) % MOD
            array[j][i + 1] = (array[j][i + 1] + array[j][i] * 3) % MOD
        else:
            if j < 3 and data[i] == targets[j]:
                array[j + 1][i + 1] = (array[j + 1][i + 1] + array[j][i]) % MOD
            array[j][i + 1] = (array[j][i + 1] + array[j][i]) % MOD

print(array[3][SLen])

Solution (Python):
import sys
input = sys.stdin.readline

S = input().rstrip()
N = len(S)
mod = 10**9 + 7
cnt = 0
A = B = C = 0
for c in S:
    if c == 'A':
        A += pow(3, cnt, mod)
    if c == 'B':
        B += A
    if c == 'C':
        C += B
    if c == '?':
        C = C * 3 + B
        B = B * 3 + A
        A = A * 3 + pow(3, cnt, mod)
        cnt += 1
    A %= mod
    B %= mod
    C %= mod
print(C)

Solution (Python):
s = input()
n = len(s)
mod = 10**9+7
dp = [[0]*4 for i in range(n+1)]
dp[0][0] = 1
for i in range(n):
  l = s[i]
  for j in range(4):
    if l == "?":
      dp[i+1][j] = (dp[i][j]*3)%mod
    else:
      dp[i+1][j] = dp[i][j] % mod
  if l == "A" or l == "?":
    dp[i+1][1] += dp[i][0] % mod
  if l == "B" or l == "?":
    dp[i+1][2] += dp[i][1] % mod
  if l == "C" or l == "?":
    dp[i+1][3] += dp[i][2] % mod
print(dp[n][3]%mod)

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






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

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

print(dp[n][3])

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

q = s.count('?')
l_a = [0] * n  
l_x = [0] * n  
r_c = [0] * n  
r_x = [0] * n  

for i in range(1, n):  
    l_a[i] = l_a[i - 1] + int(s[i - 1] == 'A')
    l_x[i] = l_x[i - 1] + int(s[i - 1] == '?')
    r_c[n - i - 1] = r_c[n - i] + int(s[n - i] == 'C')
    r_x[n - i - 1] = r_x[n - i] + int(s[n - i] == '?')

ans = 0
pow_q = []
for i in range(0, 4):
    pow_q.append(max(1, 3 ** (q - i) % p))

for i in range(n):
    if s[i] == 'B':
        ans += (l_a[i] * r_c[i] % p) * pow_q[0] % p  
        ans += (l_x[i] * r_c[i] % p) * pow_q[1] % p 
        ans += (l_a[i] * r_x[i] % p) * pow_q[1] % p 
        ans += (l_x[i] * r_x[i] % p) * pow_q[2] % p 
        ans %= p
    elif s[i] == '?':
        ans += (l_a[i] * r_c[i] % p) * pow_q[1] % p 
        ans += (l_x[i] * r_c[i] % p) * pow_q[2] % p 
        ans += (l_a[i] * r_x[i] % p) * pow_q[2] % p 
        ans += (l_x[i] * r_x[i] % p) * pow_q[3] % p 
        ans %= p

print(ans)

Solution (Python):
def main():
    S = input()
    mod = 10 ** 9 + 7
    A = AB = ABC = 0
    n = 1
    for i in S:
        if i == '?':
            ABC = ABC * 3 + AB
            AB = AB * 3 + A
            A = A * 3 + n
            n = n * 3 % mod
        if i == 'C':
            ABC = ABC + AB
        if i == 'B':
            AB = AB + A
        if i == 'A':
            A += n
    print(ABC % mod)

main()

Solution (Python):
from functools import lru_cache
class cmbs(object):
    def __init__(self, mod):
        self.mod = mod
        self.g1 = [1, 1]
        self.g2 = [1, 1]
        inverse = [0, 1]
        for i in range(2, 10 ** 6 + 1):
            self.g1.append((self.g1[-1] * i) % mod)
            inverse.append((-inverse[mod % i] * (mod // i)) % mod)
            self.g2.append((self.g2[-1] * inverse[-1]) % mod)
    @lru_cache(maxsize=None)
    def cmb(self, n, r):
        if n > 10 ** 6:
            return self.cmbl(n, r)
        return self.cmbr(n, r)

    def cmbr(self, n, r):
        if r < 0 or r > n:
            return 0
        r = min(r, n - r)
        return self.g1[n] * self.g2[r] * self.g2[n-r] % self.mod

    def cmbl(self, n, r):
        t = 1
        r = min(r, n-r)
        for i in range(n - r + 1, n + 1):
            t = t * i % self.mod
        return t * self.g2[r] % self.mod
def main():
    S = input()
    mod = 10**9 + 7
    n = len(S)
    A = [0] * n
    B = [0] * n
    C = [0] * n
    Q = [0] * n
    d = {'A':0, 'B':0, 'C':0, '?':0}
    for i, v in enumerate(S):
        d[v] += 1
        A[i] = d['A']
        B[i] = d['B']
        C[i] = d['C']
        Q[i] = d['?']
    r = 0
    c = cmbs(mod)
    t = d['?']
    
    if t >= 3:
        r += c.cmb(t, 3) * pow(3, t - 3)
        r %= mod
    if t >= 2:
        r2 = 0
        for i in range(n):
            p = t - Q[i]
            
            if S[i] == 'A' and p >= 2:
                r2 += c.cmb(p, 2)
            
            if S[i] == 'B' and Q[i] >= 1 and p >= 1:
                r2 += Q[i] * p
            
            if S[i] == 'C' and Q[i] >= 2:
                r2 += c.cmb(Q[i], 2)
        r2 *= pow(3, t-2)
        r += r2
        r %= mod
    if t >= 1:
        r1 = 0
        for i in range(n):
            if S[i] == 'B':
                
                r1 += A[i] * (t - Q[i])
                
                r1 += Q[i] * (d['C']-C[i])
            if S[i] == '?':
                
                r1 += A[i] * (d['C']-C[i])
        r1 *=  pow(3, t-1)
        r += r1
        r %= mod
    r0 = 0
    for i in range(n):
        if S[i] == 'B':
            r0 += A[i] * (d['C'] - C[i])
    r0 *= pow(3, t)
    r += r0
    r %= mod
    return r
print(main())

Solution (Python):
s=input()
mod=10**9+7
a=0
ab=0
abc=0
q=1
for i in s:
    if i=="?":
        abc*=3
        abc+=ab
        ab*=3
        ab+=a
        a*=3
        a+=q
        q*=3
        q%=mod
    elif i=="A":
        a+=q
    elif i=="B":
        ab+=a
    else:
        abc+=ab
    abc%=mod
    ab%=mod
    a%=mod
print(abc)

Solution (Python):
s=input()
n=len(s)
mod=10**9+7
dp=[ [0]*3 for _ in range(n)]



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

print(dp[-1][2]%mod)

Solution (Python):
MOD=10**9+7
S=input()

dp=[]
for i in range(len(S)+1):
  dp.append([0,0,0,0])
  
dp[-1][3]=1
for i in reversed(range(len(S))):
  if S[i]=="?":
    m1=3
  else:
    m1=1        
  dp[i][3]=m1*dp[i+1][3]
  dp[i][3]%=MOD
  
  for j in range(3):
    if S[i]=="?":
      m2=1
    else:
      if S[i]==["A","B","C"][j]:
        m2=1
      else:
        m2=0    
    dp[i][j]=m1*dp[i+1][j]+m2*dp[i+1][j+1]
    dp[i][j]%=MOD
    
print(dp[0][0])

Solution (Python):
S = input()
MOD = 10**9 + 7
dp = [[0, 0, 0] for i in range(len(S)+1)]

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

print(dp[-1][2])

Solution (Python):
s=input()
mod=10**9+7
a,ab,abc=0,0,0
q=0
for c in s:
  if c=='A':
    a=(a+pow(3,q,mod))%mod
  elif c=='B':
    ab=(a+ab)%mod
  elif c=='C':
    abc=(ab+abc)%mod
  else:
    a,ab,abc=(3*a+pow(3,q,mod))%mod,(3*ab+a)%mod,(3*abc+ab)%mod
    q+=1
print(abc)

Solution (Python):
S=list(input())
n=len(S)
mod=10**9+7
dp=[[0]*4 for i in range(n+1)]
dp[0][0]=1
for i in range(1,n+1):
  if S[i-1]=="A":
    dp[i][0]=dp[i-1][0]%mod
    dp[i][1]=(dp[i-1][0]+dp[i-1][1])%mod
    dp[i][2]=dp[i-1][2]%mod
    dp[i][3]=dp[i-1][3]%mod
  elif S[i-1]=="B":
    dp[i][0]=dp[i-1][0]%mod
    dp[i][1]=dp[i-1][1]%mod
    dp[i][2]=(dp[i-1][1]+dp[i-1][2])%mod
    dp[i][3]=dp[i-1][3]%mod
  elif S[i-1]=="C":
    dp[i][0]=dp[i-1][0]%mod
    dp[i][1]=dp[i-1][1]%mod
    dp[i][2]=dp[i-1][2]%mod
    dp[i][3]=(dp[i-1][2]+dp[i-1][3])%mod
  else:
    dp[i][0]=dp[i-1][0]*3%mod
    dp[i][1]=(dp[i-1][0]+dp[i-1][1]*3)%mod
    dp[i][2]=(dp[i-1][1]+dp[i-1][2]*3)%mod
    dp[i][3]=(dp[i-1][2]+dp[i-1][3]*3)%mod
print(dp[n][3])

Solution (Python):
s = input()
mod = 10**9+7

dp = [[0]*4 for i in range(len(s)+1)]
dp[0][0] = 1
for i in range(len(s)):
    
    if s[i] == "A":
        dp[i+1][1] += dp[i][0]
    elif s[i] =="B":
        dp[i+1][2] += dp[i][1]
    elif s[i] == "C":
        dp[i+1][3] += dp[i][2]
    else:
        dp[i+1][1] += dp[i][0]
        dp[i+1][2] += dp[i][1]
        dp[i+1][3] += dp[i][2]
    for j in range(4):
        if s[i] == "?":
            dp[i+1][j] = (dp[i+1][j]+dp[i][j]*3)%mod
        else:
            dp[i+1][j] = (dp[i+1][j]+dp[i][j])%mod


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

Solution (Python):
import sys


def main():
    S = input()
    l = len(S)
    MOD = 10**9+7
    dp = [[0 for _ in range(3)] for _ in range(2)]
    cq = 1
    for st in S:
        if st == "A":
            dp[1][0] = dp[0][0]+cq
            dp[1][1] = dp[0][1]
            dp[1][2] = dp[0][2]
        elif st == "B":
            dp[1][0] = dp[0][0]
            dp[1][1] = dp[0][0]+dp[0][1]
            dp[1][2] = dp[0][2]
        elif st == "C":
            dp[1][0] = dp[0][0]
            dp[1][1] = dp[0][1]
            dp[1][2] = dp[0][1]+dp[0][2]
        else:
            dp[1][0] = dp[0][0]*3+cq
            dp[1][1] = dp[0][1]*3+dp[0][0]
            dp[1][2] = dp[0][2]*3+dp[0][1]
            cq *= 3
            cq %= MOD
        for i in range(3):
            dp[0][i] = dp[1][i]%MOD
    
    print(dp[0][-1])

if __name__ == "__main__":
    main()

Solution (Python):
MOD = 10 ** 9 + 7
S = input()
N = len(S)

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

for i in range(N):
    for j in range(4):
        s = S[i]
        m1 = 3 if s == '?' else 1
        m2 = 1 if j != 0 and (s == '?' or s == 'ABC'[j - 1]) else 0
        dp[i + 1][j] = (m1 * dp[i][j] + m2 * dp[i][j - 1]) % MOD

print(dp[N][3])

Solution (Python):
from collections import Counter


MOD = 10 ** 9 + 7
S = input()
N = len(S)

cnt = Counter()

for s in S:
    if s == 'B':
        cnt['?B'] += cnt['?']
        cnt['AB'] += cnt['A']
    elif s == 'C':
        cnt['ABC'] += cnt['AB']
        cnt['A?C'] += cnt['A?']
        cnt['?BC'] += cnt['?B']
        cnt['??C'] += cnt['??']
    elif s == '?':
        for t in ['??', 'A?', '?B', 'AB']:
            cnt[t + '?'] += cnt[t]
        for t in ['A', '?']:
            cnt[t + '?'] += cnt[t]
    cnt[s] += 1

q = cnt['?']
ans = 0
for key in [x for x in list(cnt.keys()) if len(x) == 3]:
    if cnt[key]:
        ans += cnt[key] * pow(3, q - key.count('?'), MOD)
        ans %= MOD

print(ans)

Solution (Python):
s = input()
n = len(s)
mod = 10**9+7
cnt = 0
dp = [[0 for i in range(4)] for j in range(n+1)]
dp[0][0] = 1
for i in range(1,n+1):
  if s[i-1] in "A?":
    dp[i][1] += dp[i-1][0]
  if s[i-1] in "B?":
    dp[i][2] += dp[i-1][1]
  if s[i-1] in "C?":
    dp[i][3] += dp[i-1][2]
  for j in range(4):
    if s[i-1] == "?":
      dp[i][j] += dp[i-1][j]*3
    else:
      dp[i][j] += dp[i-1][j]
    dp[i][j] %= mod
print(dp[-1][-1])

Solution (Python):
S=str(input())
N=len(S)
dp=[[0 for _ in range(4)] for _ in range(N+1)]
dp[0][0]=1
mod=10**9+7
for i in range(N):
  if S[i]=='A':
    dp[i+1][0]+=dp[i][0]%mod
    dp[i+1][1]+=dp[i][1]%mod+dp[i][0]%mod
    dp[i+1][2]+=dp[i][2]%mod
    dp[i+1][3]+=dp[i][3]%mod
  if S[i]=='B':
    dp[i+1][0]+=dp[i][0]%mod
    dp[i+1][1]+=dp[i][1]%mod
    dp[i+1][2]+=dp[i][2]%mod+dp[i][1]%mod
    dp[i+1][3]+=dp[i][3]%mod
  if S[i]=='C':
    dp[i+1][0]+=dp[i][0]%mod
    dp[i+1][1]+=dp[i][1]%mod
    dp[i+1][2]+=dp[i][2]%mod
    dp[i+1][3]+=dp[i][3]%mod+dp[i][2]%mod
  if S[i]=='?':
    dp[i+1][0]+=3*dp[i][0]%mod
    dp[i+1][1]+=(3*dp[i][1])%mod+dp[i][0]%mod
    dp[i+1][2]+=(3*dp[i][2])%mod+dp[i][1]%mod
    dp[i+1][3]+=(3*dp[i][3])%mod+dp[i][2]%mod
print(dp[N][3]%mod)

Solution (Python):
MOD = 10**9+7

s=input()
Anum = 0
ABnum = 0
ABCnum = 0
q = 0
for c in s:
    if c == 'A':
        Anum = (Anum+pow(3,q,MOD))%MOD
    elif c == 'B':
        ABnum = (ABnum+Anum)%MOD
    elif c == 'C':
        ABCnum = (ABCnum+ABnum)%MOD
    else:
        Anum,ABnum,ABCnum = 3*Anum+pow(3,q,MOD),3*ABnum+Anum,3*ABCnum+ABnum
        Anum,ABnum,ABCnum = Anum%MOD,ABnum%MOD,ABCnum%MOD
        q += 1
print(ABCnum)

Solution (Python):
S=input()
mod=10**9+7
La,Lq,Rc,Rq=0,0,S.count("C"),S.count("?")
ans=0
f=lambda x,y:pow(x,y,mod) if y>=0 else 0
for s in S:
	Rc-=s=="C";Rq-=s=="?"
	if s=="B" or s=="?":
		ans+=(La*f(3,Lq)+Lq*f(3,Lq-1))*(Rc*f(3,Rq)+Rq*f(3,Rq-1))
		ans%=mod
	La+=s=="A";Lq+=s=="?"
print(ans)

Solution (Python):
s = input()
mod = 10 ** 9 + 7

l = len(s)
dp = [[0] * 4 for _ in range(l + 1)]
dp[0][0] = 1

for i, e in enumerate(s, 1):
	
	for j in range(4):
		if e == "?":
			dp[i][j] += dp[i-1][j] * 3
		else:
			dp[i][j] += dp[i-1][j]

	
	if e == "A" or e == "?":
		dp[i][1] += dp[i-1][0]
	if e == "B" or e == "?":
		dp[i][2] += dp[i-1][1]
	if e == "C" or e == "?":
		dp[i][3] += dp[i-1][2]

	for j in range(4):
		dp[i][j] %= mod


ans = dp[l][3]
print(ans)

Solution (Python):

s=input()
mod=10**9+7
dpa=[[0,0] for i in range(len(s)+1)]
dpc=[[0,0] for i in range(len(s)+1)]
power3=[1 for i in range(10**5+100)]
for i in range(10**5+3):
    power3[i+1]=(power3[i]*3)%mod
for i in range(len(s)):
    if s[i]=="A":
        dpa[i+1][0]=(dpa[i][0]+power3[dpa[i][1]])%mod
        dpa[i+1][1]=dpa[i][1]  
    elif s[i]=="?":
        dpa[i+1][0]=(3*dpa[i][0]+power3[dpa[i][1]])%mod
        dpa[i+1][1]=dpa[i][1]+1   
    else:
        dpa[i+1]=dpa[i]
for i in range(len(s)):
    if s[len(s)-1-i]=="C":
        dpc[i+1][0]=(dpc[i][0]+power3[dpc[i][1]])%mod
        dpc[i+1][1]=dpc[i][1]  
    elif s[len(s)-1-i]=="?":
        dpc[i+1][0]=(3*dpc[i][0]+power3[dpc[i][1]])%mod
        dpc[i+1][1]=dpc[i][1]+1   
    else:
        dpc[i+1]=dpc[i]    
ans=0
for i in range(1,len(s)-1):
    if s[i]=="B" or s[i]=="?":
        ans+=dpa[i][0]*dpc[len(s)-1-i][0]
        ans=ans%mod
print(ans)

Solution (Python):
S=input()
pr=10**9+7
a1,a2,a3=0,0,0
c=0
for i in S:
    if i=="A":
        a1=(a1+pow(3,c,pr))%pr
    elif i=="B":
        a2=(a2+a1)%pr
    elif i=="C":
        a3=(a3+a2)%pr
    else:
        a1,a2,a3=(3*a1+pow(3,c,pr))%pr,(3*a2+a1)%pr,(3*a3+a2)%pr
        c+=1
print(a3)

Solution (Python):
s= list(input())
n=len(s)

mod=10**9+7

ans=0
dp=[[0,0,0] for i in range(n+1)]
cnt=1

for i in range(n):
    if s[i]=='A':
        dp[i+1][0]=dp[i][0]+cnt
        dp[i+1][1]=dp[i][1]
        dp[i+1][2]=dp[i][2]
        dp[i+1][0]%=mod
    elif s[i]=='B':
        dp[i+1][0]=dp[i][0]
        dp[i+1][1]=dp[i][1]+dp[i][0]
        dp[i+1][2]=dp[i][2]
        dp[i+1][1]%=mod
    elif 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]
        dp[i+1][2]%=mod
    else:
        dp[i+1][0]=3*dp[i][0]+cnt
        dp[i+1][1]=3*dp[i][1]+dp[i][0]
        dp[i+1][2]=3*dp[i][2]+dp[i][1]
        cnt*=3
        cnt%=mod
        dp[i+1][0]%=mod
        dp[i+1][1]%=mod
        dp[i+1][2]%=mod

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

Solution (Python):
s = input()
n = len(s)
MOD = 10 ** 9 + 7
dp = [[0] * 4 for _ in range(n + 1)]
dp[0][0] = 1

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

    for j in range(4):
        dp[i + 1][j] %= MOD

print(dp[n][3])

Solution (Python):
s = input()
MOD = 10 ** 9 + 7
dp = [1, 0, 0, 0]

for x in s:
    emp, a, b, c = dp
    if x == 'A':
        dp[1] += emp
    if x == 'B':
        dp[2] += a
    if x == 'C':
        dp[3] += b
    if x == '?':
        dp = [v * 3 for v in dp]
        dp[1] += emp
        dp[2] += a
        dp[3] += b

    dp = [v % MOD for v in dp]

print(dp[3])

Solution (Python):
s = list(str(input()))
n = len(s)

dl = {'A':0, 'C':0, '?':0}
dr = {'A':0, 'C':0, '?':0}

dls = []
drs = []

import copy

for i in range(n):
    if s[i] == 'A' or s[i] == 'C':
        dl[s[i]] += 1
    elif s[i] == 'B':
        dl_ = copy.copy(dl)
        dls.append(dl_)
    else:
        dl_ = copy.copy(dl)
        dls.append(dl_)
        dl[s[i]] += 1
    j = n - 1- i
    if s[j] == 'A' or s[j] == 'C':
        dr[s[j]] += 1
    elif s[j] == 'B':
        dr_ = copy.copy(dr)
        drs.append(dr_)
    else:
        dr_ = copy.copy(dr)
        drs.append(dr_)
        dr[s[j]] += 1

drs = list(reversed(drs))



ans = 0
mod = 10**9+7

def power(a, n, mod):
  bi=str(format(n,"b")) 
  res=1
  for i in range(len(bi)):
    res=(res*res) %mod
    if bi[i]=="1":
      res=(res*a) %mod
  return res

for i in range(len(dls)):
    a = (dls[i]['A']*power(3, dls[i]['?'], mod) + dls[i]['?']*power(3, max(0, dls[i]['?']-1), mod))%mod
    b = (drs[i]['C']*power(3, drs[i]['?'], mod) + drs[i]['?']*power(3, max(0, drs[i]['?']-1), mod))%mod
    ans += (a*b)%mod
    
ans %=mod
print(ans)

Solution (Python):
import sys
s = input()
mod = 10**9+7
memo_ls = [[0 for j in range(4)] for i in range(len(s) + 1)]
memo_ls[0][0] = 1
for i, _s in enumerate(s, 1):
    memo_ls[i][0] = memo_ls[i-1][0]
    memo_ls[i][1] = memo_ls[i-1][1]
    memo_ls[i][2] = memo_ls[i-1][2]
    memo_ls[i][3] = memo_ls[i - 1][3]
    if _s == "A":
        memo_ls[i][1] += memo_ls[i-1][0]
    elif _s == "B":
        memo_ls[i][2] += memo_ls[i-1][1]
    elif _s == "C":
        memo_ls[i][3] += memo_ls[i-1][2]
    else:
        memo_ls[i][0] *= 3
        memo_ls[i][1] *= 3
        memo_ls[i][2] *= 3
        memo_ls[i][3] *= 3
        memo_ls[i][1] += memo_ls[i - 1][0]
        memo_ls[i][2] += memo_ls[i - 1][1]
        memo_ls[i][3] += memo_ls[i - 1][2]
    memo_ls[i][0] %= mod
    memo_ls[i][1] %= mod
    memo_ls[i][2] %= mod
    memo_ls[i][3] %= mod
print(memo_ls[-1][-1] % mod)

Solution (Python):
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

S = sr()[::-1]
MOD = 10 ** 9 + 7
answer = 0
dp = [0, 0, 1] 
for i in range(len(S)):
    s = S[i]
    if s == 'A':
        answer += dp[1]
    elif s == 'B':
        dp[1] += dp[0]
    elif s == 'C':
        dp[0] += dp[2]
    elif s == '?':
        answer *= 3
        answer += dp[1]
        dp[1] *= 3
        dp[1] += dp[0]
        dp[0] *= 3
        dp[0] += dp[2]
        dp[2] *= 3
    answer %= MOD
    dp[0] %= MOD; dp[1] %= MOD; dp[2] %= MOD
print(answer)

Solution (Python):
def main():
    S=input()
    N=len(S)
    abccounter=0
    abcounter=0
    acounter=0
    for i in range(0,N):
        if S[i]=='A':
            acounter+=1
        elif S[i]=='B':
            abcounter+=acounter
        elif S[i]=='C':
            abccounter+=abcounter
    hbccounter=0
    hbcounter=0
    hcounter=0
    for i in range(0,N):
        if S[i]=='?':
            hcounter+=1
        elif S[i]=='B':
            hbcounter+=hcounter
        elif S[i]=='C':
            hbccounter+=hbcounter
    ahccounter=0
    ahcounter=0
    acounter=0
    for i in range(0,N):
        if S[i]=='A':
            acounter+=1
        elif S[i]=='?':
            ahcounter+=acounter
        elif S[i]=='C':
            ahccounter+=ahcounter
    abhcounter=0
    abcounter=0
    acounter=0
    for i in range(0,N):
        if S[i]=='A':
            acounter+=1
        elif S[i]=='B':
            abcounter+=acounter
        elif S[i]=='?':
            abhcounter+=abcounter
    ahhcounter=0
    ahcounter=0
    acounter=0
    for i in range(0,N):
        if S[i]=='A':
            acounter+=1
        elif S[i]=='?':
            ahhcounter+=ahcounter
            ahcounter+=acounter
    hbhcounter=0
    hbcounter=0
    hcounter=0
    for i in range(0,N):
        if S[i]=='B':
            hbcounter+=hcounter
        elif S[i]=='?':
            hbhcounter+=hbcounter
            hcounter+=1
    hhccounter=0
    hhcounter=0
    hcounter=0
    for i in range(0,N):
        if S[i]=='C':
            hhccounter+=hhcounter
        elif S[i]=='?':
            hhcounter+=hcounter
            hcounter+=1
    Q=hcounter
    if Q>=3:
        ans=abccounter*3**Q+(hbccounter+ahccounter+abhcounter)*3**(Q-1)+(ahhcounter+hbhcounter+hhccounter)*3**(Q-2)+(Q*(Q-1)*(Q-2)//6)*3**(Q-3)
    elif Q==2:
        ans=abccounter*3**Q+(hbccounter+ahccounter+abhcounter)*3**(Q-1)+(ahhcounter+hbhcounter+hhccounter)*3**(Q-2)
    elif Q==1:
        ans=abccounter*3**Q+(hbccounter+ahccounter+abhcounter)*3**(Q-1)
    else:
        ans=abccounter*3**Q
    print(ans%(10**9+7))
if __name__ == '__main__':
    main()

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

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


for i, s in enumerate(S):
    if s == '?':
        dp[i][0] = dp[i - 1][0] * 3 % mod
        dp[i][1] = (dp[i - 1][0] + dp[i - 1][1] * 3) % mod
        dp[i][2] = (dp[i - 1][1] + dp[i - 1][2] * 3) % mod
        dp[i][3] = (dp[i - 1][2] + dp[i - 1][3] * 3) % mod
    elif s == 'A':
        dp[i][0] = dp[i - 1][0]
        dp[i][1] = (dp[i - 1][1] + dp[i - 1][0]) % mod
        dp[i][2] = dp[i - 1][2]
        dp[i][3] = dp[i - 1][3]
    elif s == 'B':
        dp[i][0] = dp[i - 1][0]
        dp[i][1] = dp[i - 1][1]
        dp[i][2] = (dp[i - 1][1] + dp[i - 1][2]) % mod
        dp[i][3] = dp[i - 1][3]
    else:
        dp[i][0] = dp[i - 1][0]
        dp[i][1] = dp[i - 1][1]
        dp[i][2] = dp[i - 1][2]
        dp[i][3] = (dp[i - 1][3] + dp[i - 1][2]) % mod

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

Solution (Python):
S = input()
MOD = 10 ** 9 + 7

A = 0
AB = 0
ABC = 0
cnt = 1

for s in S:
    if s == "A":
        A = (A + cnt) % MOD
    elif s == "B":
        AB = (A + AB) % MOD
    elif s == "C":
        ABC = (AB + ABC) % MOD
    else:
        A, AB, ABC = (A * 3 + cnt) % MOD, (AB * 3 + A) % MOD, (ABC * 3 + AB) % MOD
        cnt = (cnt * 3) % MOD
    
    
print(ABC)

Solution (Python):
S = input()

dp = [[0] * 4 for _ in range(len(S) + 1)]
dp[0][0] = 1
W = 'ABC'

MOD = 10 ** 9 + 7


def update1(i):
    for j in range(4):
        dp[i + 1][j] += dp[i][j] % MOD


def update2(i, c):
    ic = W.index(c)
    dp[i + 1][ic + 1] += dp[i][ic] % MOD


for i in range(len(S)):
    if S[i] == '?':
        for c in W:
            update1(i)
            update2(i, c)
    else:
        update1(i)
        update2(i, S[i])
print(dp[len(S)][-1] % MOD)

Solution (Python):
import sys
from bisect import bisect_left as bl
from collections import defaultdict as dd
input = sys.stdin.readline
S = list(input())[: -1]
d = dd(list)
mod = 10 ** 9 + 7
res = 0
for i in range(len(S)):
  d[S[i]].append(i)
for i in range(len(S)):
  if S[i] == "B":
    l = bl(d["A"], i)
    m = bl(d["?"], i)
    r = bl(d["C"], i)
    res += l * (len(d["C"]) - r) * pow(3, len(d["?"]), mod)
    res %= mod
    res += m * (len(d["C"]) - r) * pow(3, max(len(d["?"]) - 1, 0), mod) * (len(d["?"]) > 0)
    res %= mod
    res += l * (len(d["?"]) - m) * pow(3, max(len(d["?"]) - 1, 0), mod) * (len(d["?"]) > 0)
    res %= mod
    res += m * (len(d["?"]) - m) * pow(3, max(len(d["?"]) - 2, 0), mod) * (len(d["?"]) > 1)
    res %= mod
  elif S[i] == "?":
    l = bl(d["A"], i)
    m = bl(d["?"], i)
    r = bl(d["C"], i)
    res += l * (len(d["C"]) - r) * pow(3, len(d["?"]) - 1, mod)
    res %= mod
    res += m * (len(d["C"]) - r) * pow(3, max(len(d["?"]) - 2, 0), mod) * (len(d["?"]) > 1)
    res %= mod
    res += l * (len(d["?"]) - m - 1) * pow(3, max(len(d["?"]) - 2, 0), mod) * (len(d["?"]) > 1)
    res %= mod
    res += m * (len(d["?"]) - m - 1) * pow(3, max(len(d["?"]) - 3, 0), mod) * (len(d["?"]) > 2)
    res %= mod
  
print(res)

Solution (Python):


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

Solution (Python):


S=input()
N=len(S)
dp=[0,0,0]

mod=10**9+7

p=[1]*(N+1)
for i in range(N):
    p[i+1]=(p[i]*3)%mod


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

Solution (Python):


S=input()
N=len(S)
dp=[0,0,0]

mod=10**9+7

p=[1]*(N+1)
for i in range(N):
    p[i+1]=(p[i]*3)%mod


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

Solution (Python):
S = input()

mod = 10**9+7
A = 0
AB = 0
ABC = 0
cnt = 0
for i in range(len(S)):
    if S[i] == "A":
        A += pow(3, cnt, mod)
        A %= mod
    elif S[i] == "B":
        AB += A
        AB %= mod
    elif S[i] == "C":
        ABC += AB
        ABC %= mod
    else:
        ABC = (3*ABC + AB) % mod
        AB = (3*AB + A) % mod
        A = (3*A + pow(3, cnt, mod)) % mod
        cnt += 1
        
        
print(ABC)

Solution (Python):
from collections import *
from itertools import *
import copy
from heapq import *

S=input()
mod=10**9+7


"""def mpow(x,n):
    num=1
    while n > 0:
        if n&1:
            num=num*x%mod
        x=x*x%mod
        n=n>>1
    return(num)"""

A=0
AB=0
ABC=0
count=0
for s in S:
    if s=="A":
        A+=pow(3,count,mod)
    elif s=="B":
        AB+=A
    elif s=="C":
        ABC+=AB
    else:
        ABC=(ABC*3+AB)%mod
        AB=(AB*3+A)%mod
        A=(A*3+pow(3,count,mod) )%mod
        count+=1
print(ABC%mod)

Solution (Python):
S = input(); N = len(S)
a,b,c,d = 0,0,0,1
mod = 10**9+7
for x in reversed(S):
  if x == "?":
    a,b,c,d = (3*a+b)%mod, (3*b+c)%mod, (3*c+d)%mod, 3*d%mod
  elif x == "A": a = (a+b)%mod
  elif x == "B": b = (b+c)%mod
  elif x == "C": c = (c+d)%mod
print(a)

Solution (Python):
S = input()
N = len(S)
a,b,c,d = 0,0,0,1
mod = 10**9+7
for x in reversed(S):
  if x == "?":
    a,b,c,d = 3*a+b, 3*b+c, 3*c+d, 3*d
  elif x == "A":
    a += b
  elif x == "B":
    b += c
  elif x == "C":
    c += d
  a %= mod; b %= mod; c %= mod; d %= mod
print(a)

Solution (Python):
S = input()
N = len(S)
mod = 10**9+7
numofA = 0
numofAB = 0
numofABC = 0
numofquestion = 1
for i in range(N):
    if S[i] == "?":
        numofABC = (numofABC*3+numofAB) % mod
        numofAB = (numofAB*3+numofA) % mod
        numofA = (numofquestion + numofA*3) % mod
        numofquestion = (numofquestion * 3) % mod
    elif S[i] == "C":
        numofABC = (numofAB+numofABC) % mod
    elif S[i] == "B":
        numofAB = (numofAB + numofA) % mod
    else:
        numofA = (numofquestion + numofA) % mod
print(numofABC)