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























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

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

Solution (Python):
MOD = 10**9 +7
S = input().rstrip()
A = 0
B = 0
C = 0
X = 1
for s in S:
    if s=="?":
        C=B + C*3
        B=A + B*3
        A=X + A*3
        X *= 3
    else:
        if s=="A":
            A+=X
        if s=="B":
            B+=A
        if s =="C":
            C+=B
    X %= MOD
    A %= MOD
    B %= MOD
    C %= MOD
print(C)

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

dp0 = 1 
dp1 = 0 
dp2 = 0 
dp3 = 0 

for c in S:
    if c == 'A':
        dp1 = (dp0+dp1)%MOD
    elif c == 'B':
        dp2 = (dp1+dp2)%MOD
    elif c == 'C':
        dp3 = (dp2+dp3)%MOD
    else:
        dp3 = (dp3*3+dp2)%MOD
        dp2 = (dp2*3+dp1)%MOD
        dp1 = (dp1*3+dp0)%MOD
        dp0 = (dp0*3)%MOD
print(dp3)

Solution (Python):
MOD = 10**9 + 7
S = input()
res = 0
dp0 = 1 
dp1 = 0 
dp2 = 0 
dp3 = 0 

for c in S:
    if c == 'A':
        dp1 = (dp0+dp1)%MOD
    elif c == 'B':
        dp2 = (dp1+dp2)%MOD
    elif c == 'C':
        dp3 = (dp2+dp3)%MOD
    else:
        dp3 = (dp3*3+dp2)%MOD
        dp2 = (dp2*3+dp1)%MOD
        dp1 = (dp1*3+dp0)%MOD
        dp0 = (dp0*3)%MOD
print(dp3)

Solution (Python):
MOD = 10**9 + 7
S = input()
res = 0
dp0 = 1 
dp1 = 0 
dp2 = 0 
dp3 = 0 

for c in S:
    if c == 'A':
        dp1 += dp0
    elif c == 'B':
        dp2 += dp1
    elif c == 'C':
        dp3 += dp2
    else:
        dp0,dp1,dp2,dp3 = dp0*3,dp1*3+dp0,dp2*3+dp1,dp3*3+dp2
    dp0 %= MOD
    dp1 %= MOD
    dp2 %= MOD
    dp3 %= MOD
print(dp3)

Solution (Python):
MOD = 10**9 + 7
S = input()
res = 0
dpn = 1
dp0 = 0 
dp1 = 0 

for c in S:
    if c == 'A':
        dp0 += dpn
    elif c == 'B':
        dp1 += dp0
    elif c == 'C':
        res += dp1
    else:
        dp0,dp1,res = dp0*3+dpn,dp1*3+dp0,res*3+dp1
        dpn *= 3
    dpn %= MOD
    dp0 %= MOD
    dp1 %= MOD
    res %= MOD
print(res)

Solution (Python):
S=input()
N=len(S)
A=[0]
B=[0]
C=[0]
X=[0]
for i in range(N):
  A.append(A[i])
  B.append(B[i])
  C.append(C[i])
  X.append(X[i])
  if S[i]=='A':
    A[-1]+=1
  elif S[i]=='B':
    B[-1]+=1
  elif S[i]=='C':
    C[-1]+=1
  else:
    X[-1]+=1
P=0
mod=10**9+7
for i in range(N):
  if S[i]=='B':
    P=(P+pow(3,X[N],mod)*A[i]*(C[N]-C[i+1]))%mod
    if X[i]:
      P=(P+pow(3,X[N]-1,mod)*X[i]*(C[N]-C[i+1]))%mod
    if X[N]-X[i+1]:
      P=(P+pow(3,X[N]-1,mod)*A[i]*(X[N]-X[i+1]))%mod
    if X[i] and X[N]-X[i+1]:
      P=(P+pow(3,X[N]-2,mod)*X[i]*(X[N]-X[i+1]))%mod
  if S[i]=='?':
    P=(P+pow(3,X[N]-1,mod)*A[i]*(C[N]-C[i+1]))%mod
    if X[i]:
      P=(P+pow(3,X[N]-2,mod)*X[i]*(C[N]-C[i+1]))%mod
    if X[N]-X[i+1]:
      P=(P+pow(3,X[N]-2,mod)*A[i]*(X[N]-X[i+1]))%mod
    if X[i] and X[N]-X[i+1]:
      P=(P+pow(3,X[N]-3,mod)*X[i]*(X[N]-X[i+1]))%mod
print(P)

Solution (Python):


s = str(input())

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

    if s[i-1] == "A":
        dp[i][1] += (dp[i-1][0]) % mod
    elif s[i-1] == "B":
        dp[i][2] += (dp[i-1][1]) % mod
    elif s[i-1] == "C":
        dp[i][3] += (dp[i-1][2]) % mod
    else:
        dp[i][1] += (dp[i-1][0]) % mod
        dp[i][2] += (dp[i-1][1]) % mod
        dp[i][3] += (dp[i-1][2]) % mod


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

Solution (Python):
mod=10**9+7
s=list(input())
s=['-']+s

l=len(s)
dp=[[0 for j in range(4)] for i in range(l)]
dp[0][0]=1
for i in range(1,l):
    for j in range(4):
        dp[i][j]=dp[i-1][j]
        if s[i]=='?':
            dp[i][j]*=3;
        if (j  > 0) and (s[i]=='?' or 'ABC'[j-1]==s[i]):
            dp[i][j] += dp[i-1][j-1]
        dp[i][j] %= mod
        
print(dp[-1][3])

Solution (Python):
mod=10**9+7
s=list(input())
s=['-']+s
l=len(s)
dp=[[0 for j in range(4)] for i in range(l)]
dp[0][0]=1
for i in range(1,l):
    for j in range(4):
        dp[i][j]=dp[i-1][j]
        if s[i]=='?':
            dp[i][j]*=3;
        if j and (s[i]=='?' or 'ABC'[j-1]==s[i]):
            dp[i][j]+=dp[i-1][j-1]
        dp[i][j]%=mod
print(dp[-1][3])

Solution (Python):
mod=10**9+7
s=list(input())
s=['-']+s
l=len(s)
dp=[[0 for j in range(4)] for i in range(l)]
dp[0][0]=1
for i in range(1,l):
    for j in range(4):
        dp[i][j]=dp[i-1][j]
        if s[i]=='?':
            dp[i][j]*=3;
        if j and (s[i]=='?' or 'ABC'[j-1]==s[i]):
            dp[i][j]+=dp[i-1][j-1]
        dp[i][j]%=mod
print(dp[-1][3])

Solution (Python):


import math

import itertools
from collections import deque
from collections import Counter
import heapq
from fractions  import gcd


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

Solution (Python):
S=input()
MOD=pow(10,9)+7
dp=[0]*4
dp[0]=1
for s in S:
  if s=='A':
    dp[1]+=dp[0]
  elif s=='B':
    dp[2]+=dp[1]
  elif s=='C':
    dp[3]+=dp[2]
  else:
    tmp3=dp[2]
    tmp2=dp[1]
    tmp1=dp[0]
    dp[3]*=3
    dp[3]+=tmp3
    dp[2]*=3
    dp[2]+=tmp2
    dp[1]*=3
    dp[1]+=tmp1
    dp[0]*=3
  dp[3]%=MOD
  dp[2]%=MOD
  dp[1]%=MOD
  dp[0]%=MOD
print(dp[3])

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
from math import sqrt, pi
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
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):
        
        if S[i] != '?':
            
            dp[i + 1][j] += dp[i][j]
            dp[i + 1][j] %= mod
        
        else:
            
            dp[i + 1][j] += 3 * dp[i][j]
            dp[i + 1][j] %= mod
    
    
    if S[i] == 'A' or S[i] == '?':
        dp[i + 1][1] += dp[i][0]
        dp[i + 1][1] %= mod
    if S[i] == 'B' or S[i] == '?':
        dp[i + 1][2] += dp[i][1]
        dp[i + 1][2] %= mod
    if S[i] == 'C' or S[i] == '?':
        dp[i + 1][3] += dp[i][2]
        dp[i + 1][3] %= mod
print(dp[N][3] % mod)

Solution (Python):
MOD = 10 ** 9 + 7
s = input()
a = 0
ql = 0
c = s.count('C')
qr = s.count('?')
ans = 0 
for si in s:
    if si == '?':
        qr -= 1
    if si in 'B?':
        ans = (ans + pow(3,ql+qr,MOD)*a*c 
             + (pow(3,ql+qr-1,MOD)*(ql*c+a*qr) if ql + qr - 1 >= 0 else 0)
             + (pow(3,ql+qr-2,MOD)*ql*qr if ql + qr - 2 >= 0 else 0)) % MOD
    if si == '?':
        ql += 1
    elif si == 'A':
        a += 1
    elif si == 'C':
        c -= 1
print(ans)

Solution (Python):
MOD = 10 ** 9 + 7
dp = [0, 0]
ans = 0
t = 1
for c in input():
    ndp = dp.copy()
    if c in 'A':
        ndp[0] = (dp[0] + t) % MOD
    elif c in 'B':
        ndp[1] = (ndp[1] + dp[0]) % MOD
    elif c in 'C':
        ans = (ans + dp[1]) % MOD
    else:
        ndp[0] = (3 * dp[0] + t) % MOD
        ndp[1] = (3 * dp[1] + dp[0]) % MOD
        ans = (3 * ans + dp[1]) % MOD
        t = (t * 3) % MOD
    
    dp = ndp
print(ans)

Solution (Python):
S = input()
ans = 0
MOD = 10 ** 9 + 7
la = 0
lp = 0
rc = 0
rp = 0
for c in S:
    if c == 'C':
        rc += 1
    if c == '?':
        rp += 1
for c in S:
    if c == 'C':
        rc -= 1
    if c == '?':
        rp -= 1
    if c == '?' or c == 'B':
        if lp == 0:
            l = la * pow(3, lp, MOD)
        else:
            l = la * pow(3, lp, MOD) + lp * pow(3, lp-1, MOD)
        if rp == 0:
            r = rc * pow(3, rp, MOD)
        else:
            r = rc * pow(3, rp, MOD) + rp * pow(3, rp-1, MOD)
        ans += l*r
        ans %= MOD
    if c == 'A':
        la += 1
    if c == '?':
        lp += 1
print(ans)

Solution (Python):
S = input()
MOD = 10**9 + 7
dp = [[0]*4 for _ in range(100005)]
dp[0][0] = 1
for i in range(len(S)):
    for j in range(4):
        if S[i] != '?':
            dp[i+1][j] += dp[i][j]
            dp[i+1][j] %= MOD
        else:
            dp[i+1][j] += 3*dp[i][j] % MOD
            dp[i+1][j] %= MOD
    if S[i] == 'A' or S[i] == '?':
        dp[i+1][1] += dp[i][0]
        dp[i+1][1] %= MOD
    if S[i] == 'B' or S[i] == '?':
        dp[i+1][2] += dp[i][1]
        dp[i+1][2] %= MOD
    if S[i] == 'C' or S[i] == '?':
        dp[i+1][3] += dp[i][2]
        dp[i+1][3] %= MOD
print(dp[len(S)][3])

Solution (Python):
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))


def main():
    S=["D"] + list(input())
    N=len(S)
    MOD=10**9+7

    A = [0] * (N+1)
    C = [0] * (N+1)
    Q = [0] * (N+1)

    for i in range(1,N+1):
        s = S[i-1]
        A[i] = A[i-1]
        C[i] = C[i-1]
        Q[i] = Q[i-1]
        if s == "A":
            A[i] += 1
        elif s == "C":
            C[i] += 1
        elif s == "?":
            Q[i] += 1
    
    
    ans = 0
    for i in range(1,N+1):
        s = S[i-1]
        if s == "?" or s == "B":
            l_A = A[i-1]
            l_Q = Q[i-1]
            r_Q = Q[-1] - Q[i]
            r_C = C[-1] - C[i]

    
            left = pow(2,l_Q,MOD) * l_A % MOD 
            if l_Q > 0:
                left += l_Q * pow((1+pow(2,MOD-2,MOD)), l_Q-1,MOD) * pow(2,l_Q-1,MOD) % MOD 
                left %= MOD
                left += l_A * (pow(3,l_Q,MOD)-pow(2,l_Q,MOD)) % MOD 


            right = pow(2,r_Q,MOD) * r_C % MOD 
            if r_Q > 0:
                right += r_Q * pow((1+pow(2,MOD-2,MOD)), r_Q-1,MOD) * pow(2,r_Q-1,MOD) % MOD 
                right %= MOD
                right += r_C * (pow(3,r_Q,MOD)-pow(2,r_Q,MOD)) % MOD 

            ans += left * right % MOD
            ans %= MOD


            
    ans %= MOD
    print(ans)






if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))


def main():
    S=["D"] + list(input())
    N=len(S)
    MOD=10**9+7

    A = [0] * (N+1)
    C = [0] * (N+1)
    Q = [0] * (N+1)

    for i in range(1,N+1):
        s = S[i-1]
        A[i] = A[i-1]
        C[i] = C[i-1]
        Q[i] = Q[i-1]
        if s == "A":
            A[i] += 1
        elif s == "C":
            C[i] += 1
        elif s == "?":
            Q[i] += 1
    
    
    ans = 0
    for i in range(1,N+1):
        s = S[i-1]
        if s == "?" or s == "B":
            l_A = A[i-1]
            l_Q = Q[i-1]
            r_Q = Q[-1] - Q[i]
            r_C = C[-1] - C[i]

            
            
            
            

            left = pow(2,l_Q,MOD) * l_A % MOD
            if l_Q > 0:
                left += l_Q * pow((1+pow(2,MOD-2,MOD)), l_Q-1,MOD) * pow(2,l_Q-1,MOD) % MOD 
                
                left %= MOD
                left += l_A * (pow(3,l_Q,MOD)-pow(2,l_Q,MOD)) % MOD 
                
                

            right = pow(2,r_Q,MOD) * r_C % MOD 
            
            if r_Q > 0:
                right += r_Q * pow((1+pow(2,MOD-2,MOD)), r_Q-1,MOD) * pow(2,r_Q-1,MOD) % MOD 
                
                right %= MOD
                right += r_C * (pow(3,r_Q,MOD)-pow(2,r_Q,MOD)) % MOD 
                
                

            
            ans += left * right % MOD
            ans %= MOD
            

            
    ans %= MOD
    print(ans)






if __name__ == "__main__":
    main()

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





S = S()
N = len(S)
dp = [[0,0,0,0] for i in range(N+1)]
dp[0][0] = 1
for i in range(1,N+1):
  if S[i-1] == "A" or S[i-1] == "?":
    dp[i][0] += dp[i-1][0]
    dp[i][1] += dp[i-1][1]+dp[i-1][0]
    dp[i][2] += dp[i-1][2]
    dp[i][3] += dp[i-1][3]
  if S[i-1] == "B" or S[i-1] == "?":
    dp[i][0] += dp[i-1][0]
    dp[i][1] += dp[i-1][1]
    dp[i][2] += dp[i-1][2]+dp[i-1][1]
    dp[i][3] += dp[i-1][3]
  if S[i-1] == "C" or S[i-1] == "?":
    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]
  dp[i][0] %= MOD
  dp[i][1] %= MOD
  dp[i][2] %= MOD
  dp[i][3] %= MOD  
print(dp[-1][-1])

Solution (Python):
import numpy as np

MOD = 10 ** 9 + 7

S = input()

n = len(S)
dp = np.zeros((n+1, 4), np.int64)
dp[0, 0] = 1
for i, c in enumerate(S):
    if c == 'A' or c == '?':
        dp[i+1] += dp[i]
        dp[i+1, 1] += dp[i, 0]
    if c == 'B' or c == '?':
        dp[i+1] += dp[i]
        dp[i+1, 2] += dp[i, 1]
    if c == 'C' or c == '?':
        dp[i+1] += dp[i]
        dp[i+1, 3] += dp[i, 2]
    dp[i+1] %= MOD

print(dp[n, 3])

Solution (Python):
from collections import Counter
s = list(input())
n = len(s)
c = Counter(s)
mod = 10**9+7


left_a  = 0
left_b  = 0
left_c  = 0
left_q  = 0
right_a = c['A']
right_b = c['B']
right_c = c['C']
right_q = c['?']

def add_ans():
    lhs = left_a * pow(3, left_q, mod) + left_q*pow(3, left_q-1, mod)
    rhs = right_c * pow(3, right_q, mod) + right_q*pow(3, right_q-1, mod)
    return  (lhs * rhs)%mod

ans = 0
for i in range(n):
    if s[i] == 'A':
        left_a  += 1
    if s[i] == 'B':
        ans = (ans+ add_ans())%mod
    if s[i] == 'C':
        right_c -= 1
    if s[i] == '?':
        right_q -= 1
        ans = (ans+ add_ans())%mod
        left_q  += 1
print(ans)

Solution (Python):

printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

s = ins()
n = len(s)
a = ab = abc = 0
z = 1
for i in range(n):
    ss = s[i]
    if ss=='A':
        a += z
    elif ss=='B':
        ab = (ab+a)%R
    elif ss=='C':
        abc = (abc+ab)%R 
    else:
        abc = (abc*3+ab)%R 
        ab = (ab*3+a)%R
        a = (a*3+z)%R
        z = (z*3)%R
    
print(abc)

Solution (Python):
s=input()
mod=pow(10,9)+7
dp=[0]*4
dp[0]=1
for si in s:
  if si=='A':
    dp[1]+=dp[0]
  elif si=='B':
    dp[2]+=dp[1]
  elif si=='C':
    dp[3]+=dp[2]
  else:
    dp[3]*=3
    dp[3]+=dp[2]
    dp[2]*=3
    dp[2]+=dp[1]
    dp[1]*=3
    dp[1]+=dp[0]
    dp[0]*=3
  dp[3]%=mod
  dp[2]%=mod
  dp[1]%=mod
  dp[0]%=mod
print(dp[3])

Solution (Python):
s=input()
mod=pow(10,9)+7
dp=[0]*4
dp[0]=1
for si in s:
  if si=='A':
    dp[1]+=dp[0]
  elif si=='B':
    dp[2]+=dp[1]
  elif si=='C':
    dp[3]+=dp[2]
  else:
    tmp3=dp[2]
    tmp2=dp[1]
    tmp1=dp[0]
    dp[3]*=3
    dp[3]+=tmp3
    dp[2]*=3
    dp[2]+=tmp2
    dp[1]*=3
    dp[1]+=tmp1
    dp[0]*=3
  dp[3]%=mod
  dp[2]%=mod
  dp[1]%=mod
  dp[0]%=mod
print(dp[3])

Solution (Python):


S = list(str(input()))
MOD = 10**9 + 7
a = 0
ab = 0
abc = 0
pat = 1
for s in S:
    if s == 'A':
        a = (a + pat) % MOD
    elif s == 'B':
        ab = (ab + a) % MOD
    elif s == 'C':
        abc = (abc + ab) % MOD
    else: 
        tmpa = a
        tmpab = ab
        a = (3*a + pat) % MOD
        ab = (3*ab + tmpa) % MOD
        abc = (3*abc + tmpab) % MOD
        pat = (pat*3) % MOD

print(abc)

Solution (Python):

import sys
readline = sys.stdin.readline

S = list(str(readline().rstrip()))
MOD = 10**9 + 7
a = 0
ab = 0
abc = 0
pat = 1
for s in S:
    if s == 'A':
        a = (a + pat) % MOD
    elif s == 'B':
        ab = (ab + a) % MOD
    elif s == 'C':
        abc = (abc + ab) % MOD
    else: 
        tmpa = a
        tmpab = ab
        a = (3*a + pat) % MOD
        ab = (3*ab + tmpa) % MOD
        abc = (3*abc + tmpab) % MOD
        pat = (pat*3) % MOD

print(abc)

Solution (Python):
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
	S = SI()
	N = len(S)
	dp = make_grid(N+1, 4, 0)
	dic = {"A": [0], "B": [1], "C": [2], "?": [0,1,2]}
	dp[0][0] = 1
	for i, s in enumerate(S):
		if s == "?":
			for j in range(4):
				if j in dic[s]:
					dp[i+1][j+1] += dp[i][j] % MOD
				dp[i+1][j] += dp[i][j] * 3 % MOD
		else:
			for j in range(4):
				if j in dic[s]:
					dp[i+1][j+1] += dp[i][j] % MOD

				dp[i+1][j] += dp[i][j] % MOD

	print(dp[N][3] % MOD)



if __name__ == "__main__":
	main()

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

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


class ModInt:
    MOD = 10 ** 9 + 7

    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    def __repr__(self):
        return str(self.x)

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )

    def set_mod_divisor(self, divisor):
        ModInt.MOD = divisor


def main():
    s = input()
    n = len(s)
    dp_t = [ModInt(0)] * (n + 1)
    dp_a = [ModInt(0)] * (n + 1)
    dp_ab = [ModInt(0)] * (n + 1)
    dp_abc = [ModInt(0)] * (n + 1)

    dp_t[0] = ModInt(1)
    dp_a[0] = ModInt(0)
    dp_ab[0] = ModInt(0)
    dp_abc[0] = ModInt(0)

    for i, char in enumerate(s, 1):
        if char == "?":
            dp_t[i] = 3 * dp_t[i - 1]
            dp_a[i] = 3 * dp_a[i - 1] + dp_t[i - 1]
            dp_ab[i] += 3 * dp_ab[i - 1] + dp_a[i - 1]
            dp_abc[i] += 3 * dp_abc[i - 1] + dp_ab[i - 1]
        else:
            dp_t[i] = dp_t[i - 1]
            dp_a[i] += dp_a[i - 1]
            dp_ab[i] += dp_ab[i - 1]
            dp_abc[i] += dp_abc[i - 1]
            if char == "A":
                dp_a[i] += dp_t[i - 1]
            if char == "B":
                dp_ab[i] += dp_a[i - 1]
            if char == "C":
                dp_abc[i] += dp_ab[i - 1]

    print(dp_abc[-1])


if __name__ == '__main__':
    main()

Solution (Python):
s=input()
n=len(s)
mod=10**9+7
dp=[[0]*4 for _ in range(n+1)]
dp[n][3]=1
for i in reversed(range(n)):
    for j in reversed(range(4)):
        if j==3:
            if s[i]=="?":
                m=3
            else:
                m=1
            dp[i][j]+=m*dp[i+1][j]
        else:
            if s[i]=="?":
                m1=3
            else:
                m1=1
            if j==0:
                if s[i]=="A" or s[i]=="?":
                    m2=1
                else:
                    m2=0
            elif j==1:
                if s[i]=="B" or s[i]=="?":
                    m2=1
                else:
                    m2=0
            else:
                if s[i]=="C" or s[i]=="?":
                    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]%mod)

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
mod = 10**9+7

def main():
    S = input()
    L = len(S)
    """
    dpなんですか、そうですか。。。（眼中になかった）
    '?'を総当たりで埋めてから考えるのではなく、
    i文字目までの問題の解を考えるのがミソ。具体的には
        dp[i][""]    = (i文字目まで見たときにまだどの文字も選んでいない方法)
        dp[i]["A"]   = (i文字目まで見たときに"A  "の１文字まで選んでいる方法)
        dp[i]["AB"]  = (i文字目まで見たときに"AB "の２文字まで選んでいる方法)
        dp[i]["ABC"] = (i文字目まで見たときに"ABC"の３文字まで選んでいる方法)
    をキーとする遷移を考える。

    （注意）この遷移を例えば
        dp[i]["A"] = (i文字目まで見たときに"A"の１文字を選ぶ方法)
    のようにすると、それまでにどの文字を選んできたかの情報が抜け落ちるのでダメ。
    """
    dp = [1, 0, 0, 0]
    if S[0] == "A": dp = [1, 1, 0, 0]
    if S[0] == '?': dp = [3, 1, 0, 0]
    
    for i in range(1, L):
        if S[i] == 'A':
            dp = [dp[0], dp[1] + dp[0], dp[2], dp[3]]
        elif S[i] == 'B':
            dp = [dp[0], dp[1], dp[2] + dp[1], dp[3]]
        elif S[i] == 'C':
            dp = [dp[0], dp[1], dp[2], dp[3] + dp[2]]
        else: 
            
            
            dp = [dp[0] * 3, dp[1] * 3 + dp[0], dp[2] * 3 + dp[1], dp[3] * 3 + dp[2]]
        dp = [dp[0] % mod, dp[1] % mod, dp[2] % mod, dp[3] % mod]
        
    print(dp[3])


if __name__ == "__main__":
    main()

Solution (Python):
mod = 10**9+7
S = input()
s = len(S)
dp = [[0 for i in range(4)]for j in range(s+1)]
mod = 10**9+7
 
dp[0][0] = 1
 
for j in range(4):
    for i in range(s):
        dp[i+1][j] = dp[i][j]%mod
        if S[i] == "?":
            dp[i+1][j] = dp[i][j]*3%mod
            if j > 0:
                dp[i+1][j] += dp[i][j-1]%mod
        else:
            if "ABC".index(S[i])+1 == j:
                dp[i+1][j] += dp[i][j-1]%mod
print(dp[s][3]%mod)

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


la = [0 for _ in range(n)]
rc = [0 for _ in range(n)]
lq = [0 for _ in range(n)]
rq = [0 for _ in range(n)]

for i in range(n-1):
    if s[i] == 'A':
        la[i+1] = 1
    if s[i] == '?':
        lq[i+1] = 1
    if s[i+1] == '?':
        rq[i] = 1
    if s[i+1] == 'C':
        rc[i] = 1

for i in range(n-1):
    la[i+1] += la[i]
    lq[i+1] += lq[i]

for i in range(n-1, 0, -1):
    rc[i-1] += rc[i]
    rq[i-1] += rq[i]

ans = 0
mod = 10 ** 9 + 7

for i in range(n):
    if s[i] in ['B', '?']:
        l = la[i] * pow(3, lq[i], mod)
        if lq[i] > 0:
            l += lq[i] * pow(3, lq[i]-1, mod)
            l %= mod

        r = rc[i] * pow(3, rq[i], mod)
        if rq[i] > 0:
            r += rq[i] * pow(3, rq[i]-1, mod)
            r %= mod
        ans += l * r
        ans %= mod


print(ans)

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

    S = input()
    z, a, b, c = 1, 0, 0, 0

    for x in S:
        if x == 'C':
            c = (c + b) % MOD
        elif x == 'B':
            b = (b + a) % MOD
        elif x == 'A':
            a = (a + z) % MOD
        elif x == '?':
            z, a, b, c = z * 3 % MOD, (a * 3 + z) % MOD, (b * 3 + a) % MOD, (c * 3 + b) % MOD
    print(c)


if __name__ == '__main__':
    main()

Solution (Python):
s = input()
a, d = [0], [0]
for char in s[:-1]:
    if char == 'A':
        a.append(a[-1] + 1)
    else:
        a.append(a[-1])
    if char == '?':
        d.append(d[-1] + 1)
    else:
        d.append(d[-1])

c, e = [0], [0]
for char in s[::-1][:-1]:
    if char == 'C':
        c.append(c[-1] + 1)
    else:
        c.append(c[-1])
    if char == '?':
        e.append(e[-1] + 1)
    else:
        e.append(e[-1])
c = c[::-1]
e = e[::-1]

ret = 0
mod = 10 ** 9 + 7
for char, aa, dd, cc, ee in zip(s, a, d, c, e):
    if char in 'B?':
        tmp1 = aa * pow(3, dd, mod)
        if dd != 0:
            tmp1 += dd * pow(3, dd - 1, mod)

        tmp2 = cc * pow(3, ee, mod)
        if ee != 0:
            tmp2 += ee * pow(3, ee - 1, mod)

        ret += tmp1 * tmp2
        ret %= mod

print(ret)

Solution (Python):
s = input()
S = len(s)


dp = [[0 for i in range(4)]for j in range(S+1)]
mod = 10**9+7

dp[0][0] = 1

for j in range(4):
    for i in range(S):
        dp[i+1][j] = dp[i][j]%mod
        if s[i] == "?":
            dp[i+1][j] = dp[i][j]*3%mod
            if j > 0:
                dp[i+1][j] += dp[i][j-1]%mod
        else:
            if "ABC".index(s[i])+1 == j:
                dp[i+1][j] += dp[i][j-1]%mod

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