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):
MOD = 10**9 + 7
p3 = [1]

S = input()
n = len(S)

a = []
c = []
q = []
for i in range(n):
  p3.append(int(p3[i] * 3 % MOD))
  if S[i] == 'A':
    a.append(1)
  else:
    a.append(0)
  if S[i] == 'C':
    c.append(1)
  else:
    c.append(0)
  if S[i] == '?':
    q.append(1)
  else:
    q.append(0)

for i in range(1, n):
  a[i] += a[i - 1]
  c[i] += c[i - 1]
  q[i] += q[i - 1]

count = 0
for i in range(1, n - 1):
  if S[i] == 'B' or S[i] == '?':
    bq = 0 if S[i] == 'B' else 1
    count += a[i - 1] * (c[n - 1] - c[i]) * p3[q[n - 1] - bq]
    count += q[i - 1] * (c[n - 1] - c[i]) * p3[q[n - 1] - 1 - bq]
    count += a[i - 1] * (q[n - 1] - q[i]) * p3[q[n - 1] - 1 - bq]
    count += q[i - 1] * (q[n - 1] - q[i]) * p3[q[n - 1] - 2 - bq]

print(int(count % MOD))

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

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

for i in range(1,l+1):
  si = s[i-1]
  if si == "?":
    dp[i][0] = dp[i-1][0] * 3
    dp[i][1] = dp[i-1][1] * 3
    dp[i][2] = dp[i-1][2] * 3
    dp[i][3] = dp[i-1][3] * 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]
    
  if si == "A":
    dp[i][1] = dp[i-1][0] + dp[i][1]
  elif si == "B":
    dp[i][2] = dp[i-1][1] + dp[i][2]
  elif si == "C":
    dp[i][3] = dp[i-1][2] + dp[i][3]
  else:
    dp[i][1] = dp[i-1][0] + dp[i][1]
    dp[i][2] = dp[i-1][1] + dp[i][2]
    dp[i][3] = dp[i-1][2] + dp[i][3]
  
  for j in range(4):
    dp[i][j] = dp[i][j] % 1000000007
  
print(int(dp[-1][-1]))

Solution (Python):
S = 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][0] + dp[i][1]) % 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][1] + dp[i][2]) % 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][2] + dp[i][3]) % MOD
    
    if S[i] == '?':
        dp[i+1][0] = 3 * dp[i][0] % MOD
        dp[i+1][1] = (dp[i][0] + 3 * dp[i][1]) % MOD
        dp[i+1][2] = (dp[i][1] + 3 * dp[i][2]) % MOD
        dp[i+1][3] = (dp[i][2] + 3 * dp[i][3]) % MOD

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

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

l = len(S)
nAB = [0]*(l+1)
nA = [0]*(l+1)
nB = [0]*(l+1)
nC = [0]*(l+1)
nABC = [0]*(l+1)

add = 1
for i,s in enumerate(S):
    if s == '?':
        nA[i+1] = 3*nA[i] + add
        nB[i+1] = 3*nB[i] + add
        nC[i+1] = 3*nC[i] + add
        nAB[i+1] = 3*nAB[i] + nA[i]
        nABC[i+1] = 3*nABC[i] + nAB[i]
        add = (add * 3) % MOD
    if s == 'A':
        nA[i+1] = nA[i] + add
        nB[i+1] = nB[i]
        nC[i+1] = nC[i]
        nAB[i+1] = nAB[i]
        nABC[i+1] = nABC[i]
    if s == 'B':
        nA[i+1] = nA[i]
        nB[i+1] = nB[i] + add
        nC[i+1] = nC[i]
        nAB[i+1] = nAB[i] + nA[i]
        nABC[i+1] = nABC[i]
    if s == 'C':
        nA[i+1] = nA[i]
        nB[i+1] = nB[i]
        nC[i+1] = nC[i] + add
        nAB[i+1] = nAB[i]
        nABC[i+1] = nABC[i] + nAB[i]
    nA[i+1] = nA[i+1] % MOD
    nB[i+1] = nB[i+1] % MOD
    nC[i+1] = nC[i+1] % MOD
    nAB[i+1] = nAB[i+1] % MOD
    nABC[i+1] = nABC[i+1] % MOD

print(nABC[l] % MOD)

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

suma,sumc,sumq=0,0,0
maxC=S.count("C")%mod
maxQ=S.count("?")%mod
ans1,ans2,ans3,ans4=0,0,0,0

for i,s in enumerate(S):
  if s=="A":
    suma+=1
    suma%=mod
  elif s=="C":
    sumc+=1
    sumc%=mod
  elif s=="?":
    sumq+=1
    sumq%=mod
  
  if i==0 or i==len(S):
    continue
  
  if s=="?":
    ans2+=suma    *(maxC-sumc)%mod
    ans3+=(sumq-1)*(maxC-sumc)%mod
    ans3+=suma    *(maxQ-sumq)%mod
    ans4+=(sumq-1)*(maxQ-sumq)%mod
  elif s=="B":
    ans1+=suma*(maxC-sumc)%mod
    ans2+=sumq*(maxC-sumc)%mod
    ans2+=suma*(maxQ-sumq)%mod
    ans3+=sumq*(maxQ-sumq)%mod
    
ans1*=3**maxQ%mod
ans2*=3**(maxQ-1)%mod
ans3*=3**(maxQ-2)%mod
ans4*=3**(maxQ-3)%mod
ans=ans1+ans2+ans3+ans4
print(int(ans%mod))

Solution (Python):
S = input()
nQ_r = S.count('?')
nC_r = S.count('C')
nQ_l = 0
nA_l = 0
N = len(S)
mod = 10**9+7

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

ans = 0
for n, c in enumerate(S):
    if c=='C': nC_r-=1
    if c=='?': nQ_r-=1
    
    if n>0 and n<N-1 and (c=='B' or c=='?'):
        p = ( nQ_l*pow3[max(0, nQ_l-1)] + nA_l*pow3[nQ_l] ) % mod
        q = ( nQ_r*pow3[max(0, nQ_r-1)] + nC_r*pow3[nQ_r] ) % mod
        ans += p * q
        ans %= mod

    if c=='A': nA_l+=1
    if c=='?': nQ_l+=1

print(ans)

Solution (Python):
def examA():
    R = I()
    if R<1200:
        ans = "ABC"
    elif R<2800:
        ans = "ARC"
    else:
        ans = "AGC"
    print(ans)
    return

def examB():
    S = SI(); N = len(S)
    ans = "AC"
    if not S[0]=="A":
        ans = "WA"
    flag = False
    for i in range(2,N-1):
        if S[i]=="C":
            flag = True
    if not flag:
        ans = "WA"
    num = 0
    for i in S:
        if ord("A")<=ord(i)<=ord('Z'):
            num +=1
    if not num==2:
        ans = "WA"
    print(ans)
    return

def examC():
    return

def examD():
    S = SI(); N = len(S)
    dp = [[0]*4 for _ in range(N+1)]
    dp[0][0] = 1
    for i in range(N):
        C = S[i]
        if C=="?":
            dp[i+1][0] = dp[i][0]*3
            dp[i+1][1] = dp[i][1]*3 + dp[i][0]
            dp[i+1][2] = dp[i][2]*3 + dp[i][1]
            dp[i+1][3] = dp[i][3]*3 + dp[i][2]
        elif C=="A":
            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][3] = dp[i][3]
        elif C=="B":
            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][3] = dp[i][3]
        elif C=="C":
            dp[i+1][0] = dp[i][0]
            dp[i+1][1] = dp[i][1]
            dp[i+1][2] = dp[i][2]
            dp[i+1][3] = dp[i][3] + dp[i][2]
        for j in range(4):
            dp[i+1][j] %=mod
    ans = dp[-1][3]
    print(ans)
    return


import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examD()

Solution (Python):
D=[0,0,0,1,0]
for s in input():D=[(D[j]*((s=="?")*2+1)+D[j+1]*(s in t+"?"))%(10**9+7) for j,t in enumerate("CBA.")]+[0]
print(D[0])

Solution (Python):
s = input()

dp_prev = [1, 0, 0, 0]

MOD_BASE = 1000000007

for c in s:
    dp_new = [dp_prev[i] for i in range(0, 4)]
    for i in range(0, 4):
        if c == "A":
            dp_new[1] = dp_prev[0] + dp_prev[1]

        elif c == "B":
            dp_new[2] = dp_prev[1] + dp_prev[2]

        elif c == "C":
            dp_new[3] = dp_prev[2] + dp_prev[3]

        else:
            dp_new[0] = dp_prev[0] * 3
            dp_new[1] = dp_prev[0] + dp_prev[1] * 3
            dp_new[2] = dp_prev[1] + dp_prev[2] * 3
            dp_new[3] = dp_prev[2] + dp_prev[3] * 3
            
    dp_prev = [x % MOD_BASE for x in dp_new]

ans = dp_prev[3]
print(ans)

Solution (Python):
s = input()

dp_prev = [1, 0, 0, 0]

MODE_BASE = 1000000007

for c in s:
    dp_new = [dp_prev[i] for i in range(0, 4)]
    for i in range(0, 4):
        if c == "A":
            dp_new[1] = (dp_prev[0] + dp_prev[1]) % MODE_BASE

        elif c == "B":
            dp_new[2] = (dp_prev[1] + dp_prev[2]) % MODE_BASE

        elif c == "C":
            dp_new[3] = (dp_prev[2] + dp_prev[3]) % MODE_BASE

        else:
            dp_new[0] = (dp_prev[0] * 3) % MODE_BASE
            dp_new[1] = (dp_prev[0] + dp_prev[1] * 3) % MODE_BASE
            dp_new[2] = (dp_prev[1] + dp_prev[2] * 3) % MODE_BASE
            dp_new[3] = (dp_prev[2] + dp_prev[3] * 3) % MODE_BASE

    dp_prev = dp_new

ans = dp_prev[3]
print(ans)

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

for i in range(N):
    if S[i]=='A':
        dp[(i+1)%2][0] = dp[i%2][0]
        dp[(i+1)%2][1] = dp[i%2][0]+dp[i%2][1]
        dp[(i+1)%2][2] = dp[i%2][2]
        dp[(i+1)%2][3] = dp[i%2][3]
    elif S[i]=='B':
        dp[(i+1)%2][0] = dp[i%2][0]
        dp[(i+1)%2][1] = dp[i%2][1]
        dp[(i+1)%2][2] = dp[i%2][1]+dp[i%2][2]
        dp[(i+1)%2][3] = dp[i%2][3]
    elif S[i]=='C':
        dp[(i+1)%2][0] = dp[i%2][0]
        dp[(i+1)%2][1] = dp[i%2][1]
        dp[(i+1)%2][2] = dp[i%2][2]
        dp[(i+1)%2][3] = dp[i%2][2]+dp[i%2][3]
    else:
        dp[(i+1)%2][0] = 3*dp[i%2][0]
        dp[(i+1)%2][1] = dp[i%2][0]+3*dp[i%2][1]
        dp[(i+1)%2][2] = dp[i%2][1]+3*dp[i%2][2]
        dp[(i+1)%2][3] = dp[i%2][2]+3*dp[i%2][3]

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

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

Solution (Python):
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7



S = sys.stdin.buffer.readline().decode().rstrip()

a = 0
ab = 0
abc = 0
q = 0
for i, s in enumerate(S):
    if s == 'C':
        abc += ab
    if s == 'B':
        ab += a
    if s == 'A':
        a += pow(3, q, MOD)
    if s == '?':
        abc = abc * 3 + ab
        ab = ab * 3 + a
        a = a * 3 + pow(3, q, MOD)
        q += 1
    a %= MOD
    ab %= MOD
    abc %= MOD
    
print(abc)

Solution (Python):











import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,hypot,log 
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')

class ModInt:
    def __init__(self, x):
        self.x = x % mod
    
    def __str__(self):
        return str(self.x)
    
    __repr__ = __str__

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

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

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

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

    __rmul__ = __mul__

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

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

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

def main():
    S=ST()
    N=len(S)
    dp = [[ModInt(0)]*4 for _ in range(N)] 
    dp[0][0]+=1
    for i,s in enumerate(S):
        if i==0:
            if s in "A?":
                dp[0][1]+=1
                if s == "?":
                    dp[0][0]*=3
            continue

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

    print(dp[-1][-1])
if __name__ == '__main__':
    main()

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

S = input()
N = len(S)


dp = list2d(N+1, 4, 0)
dp[0][0] = 1
for i in range(N):
    s = S[i]
    for j in range(4):
        
        if s == '?':
            
            dp[i+1][j] += dp[i][j] * 3
            dp[i+1][j] %= MOD
        else:
            dp[i+1][j] += dp[i][j]
            dp[i+1][j] %= MOD
        
        if j < 3:
            
            if s == '?' or s == 'A' and j == 0 \
                        or s == 'B' and j == 1 \
                        or s == 'C' and j == 2:
                dp[i+1][j+1] += dp[i][j]
                dp[i+1][j+1] %= MOD

print(dp[N][3])

Solution (Python):
S = input()
mod = 10**9 + 7
dic = {'': 1, 'A': 0, 'B': 0, 'C': 0}
for s in S:
    if s == 'A':
        dic[s] += dic['']

    elif s == 'B':
        dic[s] += dic['A']

    elif s == 'C':
        dic[s] += dic['B']

    elif s == '?':
        dic['C'] = dic['C'] * 3 + dic['B']
        dic['B'] = dic['B'] * 3 + dic['A']
        dic['A'] = dic['A'] * 3 + dic['']
        dic[''] *= 3

    dic[''] %= mod
    dic['A'] %= mod
    dic['B'] %= mod
    dic['C'] %= mod

print(dic['C']%mod)

Solution (Python):
import numpy as np
MOD = 10**9 + 7
def solve(s):
    a = np.zeros(4, dtype=int)
    a[0] = 1
    for c in s:
        t = 2 * int(c == "?") + 1
        b = t * a % MOD
        if c == "A":
            b[1] += a[0]
        elif c == "B":
            b[2] += a[1]
        elif c == "C":
            b[3] += a[2]
        else:
            b[1:] += a[:-1]
        a = b
    return a[3] % MOD

s = input()
print(solve(s))

Solution (Python):
import numpy as np
MOD = 10**9 + 7
def solve(s):
    n = len(s)
    a = np.zeros(4, dtype=int)
    b = a.copy()
    a[0] = 1
    for c in s:
        t = 2 * int(c == "?") + 1
        b = t * a % MOD
        if c == "A":
            b[1] += a[0]
        elif c == "B":
            b[2] += a[1]
        elif c == "C":
            b[3] += a[2]
        else:
            b[1:] += a[:-1]
        a = b
    return a[3] % MOD

s = input()
print(solve(s))

Solution (Python):
import numpy as np
MOD = 10**9 + 7
def solve(s):
    n = len(s)
    dp = np.zeros((n+1, 4), dtype=int)
    dp[0,0] = 1
    for i in range(n):
        t = 2 * int(s[i] == "?") + 1
        dp[i+1] = t * dp[i] % MOD
        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,:-1]
    return dp[n][3] % MOD

s = input()
print(solve(s))

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

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
limit = 100000
mod = 10**9+7
lpow = [False] * (limit+1)
lpow[0] = 1
def pow(n,p):
    if p<0:return 0
    if lpow[p]:
        return lpow[p]
    else:
        if p % 2 == 0:
            ret = (pow(n,p//2)**2) % mod
        else:
            ret = ((pow(n,p//2)**2)*n) % mod
        lpow[p] = ret
        return ret

def main():
    s=input()
    res = 0
    ca = 0
    cc = s.count("C")
    cw = 0
    aw = s.count("?")
    for c in s:
        if c == "A":
            ca += 1
        elif c == "C":
            cc -= 1
        elif c == "B":
            res += ca*cc*pow(3,aw)+ca*(aw-cw)*pow(3,aw-1)+cw*cc*pow(3,aw-1)+cw*(aw-cw)*pow(3,aw-2)
            res %= mod
        elif c == "?":
            res += ca*cc*pow(3,aw-1)+ca*(aw-cw-1)*pow(3,aw-2)+cw*cc*pow(3,aw-2)+cw*(aw-cw-1)*pow(3,aw-3)
            res %= mod
            cw += 1

    print(res)

main()

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
limit = 100000
mod = 10**9+7
lpow = [False] * (limit+1)
lpow[0] = 1
def pow(n,p):
    if p<0:return 0
    if lpow[p]:
        return lpow[p]
    else:
        if p % 2 == 0:
            ret = (pow(n,p//2)**2) % mod
        else:
            ret = ((pow(n,p//2)**2)*n) % mod
        lpow[p] = ret
        return ret

def main():
    s=input()
    res = 0
    ca = 0
    cc = s.count("C")
    cw = 0
    aw = s.count("?")
    for c in s:
        if c == "A":
            ca += 1
        elif c == "C":
            cc -= 1
        elif c == "B":
            res += ca*cc*pow(3,aw)+ca*(aw-cw)*pow(3,aw-1)+cw*cc*pow(3,aw-1)+cw*(aw-cw)*pow(3,aw-2)
            res %= mod
        elif c == "?":
            res += ca*cc*pow(3,aw-1)+ca*(aw-cw-1)*pow(3,aw-2)+cw*cc*pow(3,aw-2)+cw*(aw-cw-1)*pow(3,aw-3)
            res %= mod
            cw += 1

    print(res)

main()

Solution (Python):
mod = 10**9+7
def pow(n,p):
    res=1
    while p >0:
        if p%2==0:
            n = n**2 % mod
            p //= 2
        else:
            res = res * n % mod
            p -= 1
    return res % mod

def main():
    s=input()
    res = 0
    ca = 0
    cc = s.count("C")
    cw = 0
    aw = s.count("?")
    for c in s:
        if c == "A":
            ca += 1
        elif c == "C":
            cc -= 1
        elif c == "B":
            res += ca*cc*pow(3,aw)+ca*(aw-cw)*pow(3,aw-1)+cw*cc*pow(3,aw-1)+cw*(aw-cw)*pow(3,aw-2)
            res %= mod
        elif c == "?":
            res += ca*cc*pow(3,aw-1)+ca*(aw-cw-1)*pow(3,aw-2)+cw*cc*pow(3,aw-2)+cw*(aw-cw-1)*pow(3,aw-3)
            res %= mod
            cw += 1

    print(res)

main()

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

A = 0
AB = 0
Q = 1
ans = 0

for s in S:
    if s == '?':
        ans = (3 * ans + AB) % MOD
        AB = (3 * AB + A) % MOD
        A = (3 * A + Q) % MOD
        Q = Q * 3 % MOD
    elif s == 'A':
        A = (A + Q) % MOD
    elif s == 'B':
        AB = (AB + A) % MOD
    elif s == 'C':
        ans = (ans + AB) % MOD

print(ans)

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

    for i in range(len(S)):
        for j in range(4):
            if S[i] == '?':
                dp[i+1][j] += dp[i][j] * 3
            else:
                dp[i+1][j] = 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[len(S)][3])

if __name__ == "__main__":
    main()

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

S = input().rstrip()
N = len(S)
mod = 10**9+7




dp = [0, 0, 0]
k = 1
for i in range(N):
    if S[i] == "A":
        dp[0] += k
    elif S[i] == "B":
        dp[1] += dp[0]
    elif S[i] == "C":
        dp[2] += dp[1]
    else:
        dp[2] = 3*dp[2] + dp[1]
        dp[1] = 3*dp[1] + dp[0]
        dp[0] = 3*dp[0] + k
        k = k*3%mod
    
    dp[0] %= mod
    dp[1] %= mod
    dp[2] %= mod

print(dp[2])

Solution (Python):
S = input()
INF = 10**9+7
dp = [0,0,0]
N = 1
for i in range(len(S)):
  if S[i]=='A':
    dp[0] += N
    dp[0] %= INF
  elif S[i]=='B':
    dp[1] += dp[0]
    dp[1] %= INF
  elif S[i]=='C':
    dp[2] += dp[1]
    dp[2] %= INF
  else:
    a = dp[0]
    b = dp[1]
    dp[0] = N + dp[0]*3
    dp[1] = a + dp[1]*3
    dp[2] = b + dp[2]*3
    dp[0] %= INF
    dp[1] %= INF
    dp[2] %= INF
    N = (3*N)%INF
print(dp[2]%INF)

Solution (Python):

import sys

MOD = 1000000007  


def solve(S: str):
    N = len(S)
    
    
    

    dp = [[0]*4 for _ in range(N+1)]
    dp[0][0] = 1
    for i in range(N):
        for j in (0,1,2,3):
            if S[i] == "?":
                dp[i+1][j] += dp[i][j]*3
            else:
                dp[i+1][j] += dp[i][j]

            dp[i+1][j]%=MOD
            
        
        if S[i] == "A" or S[i] == "?":
            dp[i+1][1] += dp[i][0]
            
        
        if S[i] == "B" or S[i] == "?":
            dp[i+1][2] += dp[i][1]
            

        if S[i] == "C" or S[i] == "?":
            dp[i+1][3] += dp[i][2]
            

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


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  
    solve(S)

if __name__ == '__main__':
    main()

Solution (Python):

import sys

MOD = 1000000007  


def solve(S: str):
    N = len(S)
    
    
    

    dp = [[0]*4 for _ in range(N+1)]
    dp[0][0] = 1
    for i in range(N):
        for j in (0,1,2,3):
            if S[i] == "?":
                dp[i+1][j] += dp[i][j]*3
            else:
                dp[i+1][j] += 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)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  
    solve(S)

if __name__ == '__main__':
    main()

Solution (Python):

import sys

MOD = 1000000007  


def solve(S: str):
    N = len(S)
    
    
    

    dp = [[0]*4 for _ in range(N+1)]
    dp[0][0] = 1
    for i in range(N):
        for j in (0,1,2,3):
            if S[i] == "?":
                dp[i+1][j] += dp[i][j]*3
            else:
                dp[i+1][j] += dp[i][j]

            dp[i+1][j]%=MOD
            
        
        if S[i] == "A" or S[i] == "?":
            dp[i+1][1] += dp[i][0]
            
        
        if S[i] == "B" or S[i] == "?":
            dp[i+1][2] += dp[i][1]
            

        if S[i] == "C" or S[i] == "?":
            dp[i+1][3] += dp[i][2]
            

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


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  
    solve(S)

if __name__ == '__main__':
    main()

Solution (Python):
S = input()
N = len(S)
MOD = 10**9 + 7
DP = [[1] * 4 for _ in range(N + 1)]

DP[N][3] = 1
DP[N][0] = 0
DP[N][1] = 0
DP[N][2] = 0

for i in range(N-1, -1, -1):
    for j in range(3, -1, -1):
        DP[i][j] = DP[i+1][j] * (3 if S[i]=='?' else 1)
        if j<3:
            DP[i][j] += DP[i + 1][j + 1] * (1 if (S[i]=='ABC'[j] or S[i]=='?') else 0)
        DP[i][j] %= MOD

ans = DP[0][0]
print(ans)

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

a = 0
ab = 0
abc = 0
p = 1
for s in sl:
    if s == "A":
        a += p
        a %= mod
    elif s == "B":
        ab += a
        ab %= mod
    elif s == "C":
        abc += ab
        abc %= mod
    elif s == "?":
        abc = 3*abc + ab
        abc %= mod
        ab = 3*ab + a
        ab %= mod
        a = 3*a + p
        a %= mod
        p *= 3
        p %= mod
print(abc)

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

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    S=input()
    n=len(S)
    dp=[0]*4
    dp[0]=1
    for s in S:
        ndp=dp[:] if(s!='?') else [3*d%MOD for d in dp]
        if(s=='A' or s=='?'):
            ndp[1]+=dp[0]
            ndp[1]%=MOD
        if(s=='B' or s=='?'):
            ndp[2]+=dp[1]
            ndp[2]%=MOD
        if(s=='C' or s=='?'):
            ndp[3]+=dp[2]
            ndp[3]%=MOD
        dp=ndp
    print(dp[3])
resolve()

Solution (Python):

"""
ABC数
遷移を考える問題
dp[どこまでみたか][その時の状態] = になりうる場合の数
"""
S = input()
n = len(S)

dp = [[0]*3 for i in range(n+1)]
cnt = 0 

mod = 10**9 + 7 

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

Solution (Python):
S = input()
dp = [[1, 0, 0, 0] for _ in range(len(S))]
if S[0] == 'A':
    dp[0][1] = 1
if S[0] == '?':
    dp[0][1] = 1
    dp[0][0] *= 3

for i, v in enumerate(S):
    if i == 0:
        continue
    if v == '?':
        dp[i][0] = dp[i-1][0] * 3 % 1000000007
        dp[i][1] = (dp[i-1][1] * 3 + dp[i-1][0]) % 1000000007
        dp[i][2] = (dp[i-1][2] * 3 + dp[i-1][1]) % 1000000007
        dp[i][3] = (dp[i-1][3] * 3 + dp[i-1][2]) % 1000000007
        continue

    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]
    if v == 'A':
        dp[i][1] += dp[i-1][0]
        dp[i][1] %= 1000000007
    if v == 'B':
        dp[i][2] += dp[i-1][1]
        dp[i][2] %= 1000000007
    if v == 'C':
        dp[i][3] += dp[i-1][2]
        dp[i][3] %= 1000000007

print(dp[-1][3])

Solution (Python):
S = input()
N = len(S)
A = [0] * (N+1)
C = [0] * (N+1)
X = [0] * (N+1)
Y = [0] * (N+1)

for i in range(N):
    A[i+1] = A[i] + (1 if S[i] == "A" else 0)
    X[i+1] = X[i] + (1 if S[i] == "?" else 0)
for i in range(N)[::-1]:
    C[i] = C[i+1] + (1 if S[i] == "C" else 0)
    Y[i] = Y[i+1] + (1 if S[i] == "?" else 0)

P = 10**9 + 7
POW = [1]
for i in range(2*N+10):
    POW.append(POW[-1]*3%P)
    
ans = 0
for i in range(N):
    if S[i] == "B" or S[i] == "?":
        a, x, c, y = A[i], X[i], C[i+1], Y[i+1]
        ans += a * c * POW[x+y]
        if x: ans += x * c * POW[x+y-1]
        if y: ans += a * y * POW[x+y-1]
        if x and y: ans += x * y * POW[x+y-2]
        ans %= P
print(ans)

Solution (Python):


S = list(input())
MOD = 10**9 + 7

n_possible = 1 
A = 0 
B = 0
C = 0

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

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

n = 1
a = 0
ab = 0
abc = 0
for s in S:
    if s == 'A':
        a += n
    elif s == 'B':
        ab += a
    elif s == 'C':
        abc += ab
    else: 
        abc = 3 * abc + ab
        ab = 3 * ab + a
        a = 3 * a + n
        n *= 3
    abc %= MOD
    ab %= MOD
    a %= MOD
    n %= MOD
    


print (abc)