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):
def main():
    """
    1 <= i < j < k <= |T|
    Ti = A
    Tj = B
    Tk = C
    """
    S = input()
    ans2 = dp_simple(S)
    print(ans2)


def dp_simple(S):
    n = len(S)
    MOD = 10 ** 9 + 7
    dp = [[0] * (3+1) for _ in range(n+1)]
    
    dp[0][0] = 1

    for i in range(n):
        
        for j in range(3+1):
            
            m = 1
            if S[i] == "?":
                
                m = 3
            dp[i+1][j] += dp[i][j] * m
            dp[i+1][j] %= MOD

            
            if j < 3 and (S[i] == "?" or S[i] == "ABC"[j]):
                dp[i+1][j+1] += dp[i][j]
                dp[i+1][j+1] %= MOD

    ans = dp[n][3]
    return ans


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    """
    1 <= i < j < k <= |T|
    Ti = A
    Tj = B
    Tk = C
    """
    S = input()
    ans = editorial(S)

    print(ans)


def editorial(S):
    MOD = 10 ** 9 + 7
    n = len(S)
    dp = [[0] * (3+1) for _ in range(n+1)]

    for i in range(n, -1, -1):
        for j in range(3, -1, -1):
            if i == n:
                x = int(j == 3)
                
                
                dp[i][j] = x
            else:
                m1 = 1
                if S[i] == "?":
                    m1 = 3

                if j == 3:
                    
                    dp[i][j] = m1 * dp[i+1][j]
                else:
                    m2 = int(S[i] == "?" or S[i] == "ABC"[j])
                    
                    dp[i][j] = m1 * dp[i+1][j] + m2 * dp[i+1][j+1]

                dp[i][j] %= MOD

    ans = dp[0][0]
    return ans


if __name__ == '__main__':
    main()

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

MOD = 10 ** 9 + 7

def nLeftA(S, A):
    """(S[:i]の'A'の選び方, S[:i]の'?'の埋め方)"""
    l = [(0, 1)]
    for s in S:
        a, q = l[-1]
        if s == A:
            a = q + a      
        elif s == '?':
            a = q + a * 3  
            q = q * 3
        l.append((a % MOD, q % MOD))
    return l

l = nLeftA(S, 'A')
r = nLeftA(reversed(S), 'C')
r.reverse()
r = r[1:]

n = 0
for i in range(N):
    if S[i] in 'B?':
        n += l[i][0] * r[i][0] % MOD

print(n % MOD)

Solution (Python):
S=input()
N=len(S)
MOD=10**9+7
res=0
dp = [[0]*4 for _ in range(100001)]
for i in reversed(range(N + 1)):
    for j in reversed(range(4)):
        if i == N:
            dp[i][j] = int(j == 3)
        else:
            dp[i][j] = dp[i+1][j] * (3 if S[i] == '?' else 1)
            if(j < 3 and (S[i] == '?' or S[i] == "ABC"[j])): dp[i][j] += dp[i+1][j+1]
            dp[i][j] %= MOD

print(dp[0][0])

Solution (Python):
S = input()

dp = [[0]*(len(S)+1) for i in range(4)]
dp[0][0] = 1

for i in range(4):
    for j in range(1, len(S)+1):
        if S[j-1] == '?':
            dp[i][j] = 3 * dp[i][j-1]
        else:
            dp[i][j] = dp[i][j-1]
        if i > 0:
            if S[j-1] == '?' or 'ABC'.find(S[j-1]) == i-1:
                dp[i][j] += dp[i-1][j-1]
        dp[i][j] %= 10**9+7

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

Solution (Python):
from itertools import product

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

dp = {i: {j: 0 for j in range(3+1)} for i in range(N+1)}
for i, j in reversed(list(product(range(N+1), range(3+1)))):
    if i < N and j < 3:
        m1 = 3 if S[i] == '?' else 1
        m2 = 1 if S[i] == '?' or S[i] == ['A', 'B', 'C'][j] else 0
        dp[i][j] = m1*dp[i+1][j] + m2*dp[i+1][j+1]
    elif i < N and j == 3:
        dp[i][j] = 3*dp[i+1][j] if S[i] == '?' else dp[i+1][j]
    elif i == N and j == 3:
        dp[i][j] = 1
    dp[i][j] %= MOD
print(dp[0][0])

Solution (Python):
mod=10**9+7
s=input()
n=len(s)
Sum_A=[0]*(n+1)
Sum_B=[0]*(n+1)
Sum_C=[0]*(n+1)
Sum_q=[0]*(n+1)
for i in range(1, n+1):
    Sum_A[i]=Sum_A[i-1]
    Sum_C[i]=Sum_C[i-1]
    Sum_q[i]=Sum_q[i-1]
    if s[i-1]=='A':
        Sum_A[i]+=1
    elif s[i-1]=='C':
        Sum_C[i]+=1
    elif s[i-1]=='?':
        Sum_q[i]+=1
ans=0
def count(x, q):
    return int(x*pow(3, q, mod)+q*pow(3, (q-1), mod)) if q>0 else int(x*pow(3, q, mod))
for i in range(n):
    if s[i]=='B' or s[i]=='?':
        ans+=count(Sum_A[i], Sum_q[i])*count(Sum_C[n]-Sum_C[i+1], Sum_q[n]-Sum_q[i+1])
        ans%=mod
print(ans)

Solution (Python):
S=input()
N=len(S)
INF=1e9+7
dp=[[0]*4 for _ in range(N+1)]
dp[0][0]=1
for i in range(N):
    if S[i]=="?":
        for j in range(4):
            dp[i+1][j]+=dp[i][j]*3%INF
    else:
        for j in range(4):
            dp[i+1][j]+=dp[i][j]%INF
    if S[i]=="A" or S[i]=="?":
        dp[i+1][1]+=dp[i][0]%INF
    if S[i]=="B" or S[i]=="?":
        dp[i+1][2]+=dp[i][1]%INF
    if S[i]=="C" or S[i]=="?":
        dp[i+1][3]+=dp[i][2]%INF
print(int(dp[N][3]%INF))

Solution (Python):
import functools
import os
import sys

sys.setrecursionlimit(10000)
INF = float('inf')


def debug(fn):
    if not os.getenv('LOCAL'):
        return fn

    @functools.wraps(fn)
    def wrapper(*args, **kwargs):
        ret = fn(*args, **kwargs)
        print('DEBUG: {}({}) -> '.format(
            fn.__name__,
            ', '.join(
                list(map(str, args)) +
                ['{}={}'.format(k, str(v)) for k, v in kwargs.items()]
            )
        ), end='')
        print(ret)
        return ret

    return wrapper





























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



























dp = [0] * 4
dp[0] = 1
for i in range(len(S)):
    c = S[i]
    for abc in [3, 2, 1]:
        if c == '0ABC'[abc]:
            dp[abc] = (dp[abc] + dp[abc - 1]) % MOD
        elif c == '?':
            dp[abc] = (dp[abc] * 3 + dp[abc - 1]) % MOD
    if c == '?':
        dp[0] = dp[0] * 3 % MOD
print(int(dp[3]))

Solution (Python):

import sys

MOD = 1000000007  


def solve(S: str):
    dp = [[0 for j in range(4)] for i in range(len(S) + 1)]
    STR = "XABC"
    dp[0][0] = 1
    for i in range(len(S)):
        c = S[i]
        for j in range(4):
            next = dp[i][j]
            if c == "?":
                next *= 3
                if j > 0:
                    next += dp[i][j-1]
            if STR[j] == c:  
                next += dp[i][j-1]
            dp[i+1][j] = next % MOD
    
    print(dp[len(S)][3])
    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()
MOD = 10 ** 9 + 7

dp = [1,0,0,0]


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]
    elif s == '?':
        dp[3] *= 3
        dp[3] += dp[2]
        dp[2] *= 3
        dp[2] += dp[1]
        dp[1] *= 3
        dp[1] += dp[0]
        dp[0] *= 3

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


print(dp[3])

Solution (Python):
s=input()
a=[1,0,0,0]
for i in s:
    if i=="A": a[1]+=a[0]
    elif i=="B": a[2]+=a[1]
    elif i=="C": a[3]+=a[2]
    else: a=[ a[0]*3 ] + [ a[j+1]*3+a[j] for j in range(3) ]

    a=[a[i]%1000000007 for i in range(4)]
print(a[3])

Solution (Python):
s=input()

a=[1,0,0,0]

for i in range(len(s)):
    c=s[i]
    if c=="A":
        a[1]+=a[0]
    elif c=="B":
        a[2]+=a[1]
    elif c=="C":
        a[3]+=a[2]
    else:
        a=[ a[0]*3 ] + [ a[j+1]*3+a[j] for j in range(3) ]

    a=[a[i]%1000000007 for i in range(4)]

print(a[3])

Solution (Python):
s=input()

a=[1,0,0,0]

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

    a=[a[i]%1000000007 for i in range(4)]

print(a[3])

Solution (Python):
s=input()

a=[1,0,0,0]

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

    a=[a[i]%1000000007 for i in range(4)]
    
print(a[3])

Solution (Python):
s=input()

a=[1,0,0,0]

for i in range(len(s)):
    c=s[i]
    if c=="A":
        a[1]=(a[1]+a[0])%1000000007
    elif c=="B":
        a[2]=(a[2]+a[1])%1000000007
    elif c=="C":
        a[3]=(a[3]+a[2])%1000000007
    elif c=="?":
        tmp=[a[i] for i in range(4)]
        a[0]=tmp[0]*3
        for j in range(3):
            a[j+1]=tmp[j+1]*3+tmp[j]
        a=list(map(lambda x: x%1000000007,a))

    
print(a[3]%1000000007)

Solution (Python):
s=input()

a=[1,0,0,0]

for i in range(len(s)):
    c=s[i]
    if c=="A":
        a[1]+=a[0]
    elif c=="B":
        a[2]+=a[1]
    elif c=="C":
        a[3]+=a[2]
    elif c=="?":
        tmp=[a[i] for i in range(4)]
        a[0]=tmp[0]*3
        for j in range(3):
            a[j+1]=tmp[j+1]*3+tmp[j]

    a=[a[i]%1000000007 for i in range(4)]

print(a[3])

Solution (Python):

import sys
import itertools
import collections
import functools
import math
from queue import Queue
INF = float("inf")

MOD = 1000000007  

d = {}


def thpow(q):
    if q < 0:
        return 0
    if q == 0:
        return 1
    if q in d:
        return d[q]
    else:
        d[q] = (3*thpow(q-1)) % MOD
        return d[q]


def solve(S: str):
    dp = [0, 0, 0]
    q = 0
    for ch in S:
        a, b, c = dp
        if ch == "A":
            dp = [(a+thpow(q)) % MOD, b, c]
        elif ch == "B":
            dp = [a, (b+a) % MOD, c]
        elif ch == "C":
            dp = [a, b, (c+b) % MOD]
        elif ch == "?":
            dp = [((a*3 % MOD)+thpow(q)) % MOD,
                  ((b*3) % MOD+a) % MOD,
                  ((c*3)+b) % MOD]
            q += 1
        
    

    
    print(dp[2])
    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=raw_input()
l=len(S)

mod=10**9+7

all_strings=1
a=0
ab=0
abc=0

for i,s in enumerate(S):
	if s =="A":
		a+=all_strings
	elif s=="B":
		ab+=a
	elif s=="C":
		abc+=ab
	elif s=="?":
		abc*=3
		abc+=ab
		ab*=3
		ab+=a
		a*=3
		a+=all_strings
	if s == "?":
		all_strings*=3

	all_strings%=mod
	a%=mod
	ab%=mod
	abc%=mod

print abc

Solution (Python):
s=input()
d=[[0]*(len(s)+1)for i in range(4)]
d[3][-1]+=1
e="ABC"
for i in range(len(s)-1,-1,-1):
    for j in range(3,-1,-1):
        if j==3:
            if s[i]=="?":
                d[3][i]=(d[3][i+1]*3)%(10**9+7)
            else:
                d[3][i]=d[3][i+1]%(10**9+7)
        else:
            if s[i]=="?":
                d[j][i]=(3*d[j][i+1]+d[j+1][i+1])%(10**9+7)
            else:
                d[j][i]=d[j][i+1]
                if e[j]==s[i]:
                    d[j][i]=(d[j][i]+d[j+1][i])%(10**9+7)
print(d[0][0]%(10**9+7))

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007


def A():
    return


def B():
    return


def C():
    def dfs(i,k):
        if i == d:
            l.append(k)
        else:
            for j in range(2):
                dfs(i+1,k+[j])
    d,g = LI()
    p = LIR(d)
    ans = float("inf")
    l = []
    dfs(0,[])
    for k in l:
        m = 0
        o = 0
        q = [[p[i][0],p[i][1]] for i in range(d)]
        for i in range(d):
            if k[i]:
                o += q[i][0]
                m += q[i][0]*(i+1)*100+q[i][1]
                q[i][0] = 0
        while m < g:
            for i in range(d)[::-1]:
                for j in range(q[i][0]):
                    m += (i+1)*100
                    o += 1
                    if m >= g:break
                if m >= g:break
        ans = min(ans,o)
    print(ans)

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

def E():
    return


def F():
    return


def G():
    return


def H():
    return


if __name__ == "__main__":
    D()

Solution (Python):
def main():
    s = input()
    N = len(s)

    dp = [[-1]*4 for n in range(N)]
    for i in reversed(list(range(N))):
        for j in range(4):
            if i == N-1:
                if j == 3:
                    dp[i][j] = 3 if s[i] == "?" else 1
                elif j == 2:
                    dp[i][j] = 1 if s[i] in ("?", "C") else 0
                else:
                    dp[i][j] = 0
            else:
                if j == 3:
                    dp[i][j] = (3 if s[i] == "?" else 1) * dp[i+1][j]
                elif s[i] == "?":
                    dp[i][j] = 3 * dp[i+1][j] + dp[i+1][j+1]
                elif s[i] == "ABC"[j]:
                    dp[i][j] = dp[i+1][j+1] + dp[i+1][j]
                else:
                    dp[i][j] = dp[i+1][j]
            dp[i][j] %= 10 ** 9 + 7
    print(dp[0][0])


if __name__ == "__main__":
    main()

Solution (Python):
S = input()

dp = [ [ 0 for _ in range(4)] for _ in range(len(S)+10) ]
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]
            dp[i+1][j] %= mod
        else:
            dp[i+1][j] += dp[i][j]*3
            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):
S = str(input())
mod = 10 ** 9 + 7
L = len(S)
d = "ABC".index
dp = [[0 for _ in range(4)] for _ in range(L+1)]
dp[0][0] = 1
for i in range(len(S)):
    if S[i] == '?':
        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]
        for j in range(4):
            dp[i+1][j] %= mod
    else:
        dp[i+1] = dp[i]
        j = d(S[i])
        dp[i+1][j+1] += dp[i][j] % mod

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

Solution (Python):
S = str(input())
mod = 10 ** 9 + 7
L = len(S)
d = "ABC".index
dp = [0 for _ in range(4)]
dp[0] = 1
for i in range(len(S)):
    if S[i] == '?':
        dp = [dp[0]*3, dp[1]*3+dp[0], dp[2]*3+dp[1], dp[3]*3+dp[2]]
        for j in range(4):
            dp[j] %= mod
    else:
        j = d(S[i])
        dp[j+1] += dp[j] % mod

print(dp[-1]%mod)

Solution (Python):
s = input()

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

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

Solution (Python):
s = input()
dp = [[0]*4 for i in range(len(s)+1)]

dp[0][3] = 1
mod = 1000000007

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

print(dp[len(s)][2])

Solution (Python):
mod = 1000000007

S = input()
n = 1
a = 0
ab = 0
abc = 0
for s in S:
    if s in "A":
        a += n
    if s in "B":
        ab += a
    if s == "C":
        abc += ab
    if s in "?":
        n, a, ab, abc = 3 * n, 3 * a + n, 3 * ab + a, 3 * abc + ab
    n %= mod
    a %= mod
    ab %= mod
    abc %= mod

print(abc % mod)

Solution (Python):
mod = 1000000007

S = input()
n = 1
a = 0
ab = 0
abc = 0
for s in S:
    if s in "A":
        a += n
    if s in "B":
        ab += a
    if s == "C":
        abc += ab
    if s in "?":
        n, a, ab, abc = 3 * n, 3 * a + n, 3 * ab + a, 3 * abc + ab
    n %= mod
    a %= mod
    ab %= mod
    abc %= mod

print(abc % mod)

Solution (Python):
a=[1]+[0]*4
m=10**9+7
for s in input():
 i=ord(s)-64
 if i>0:a[i]+=a[i-1]
 else:a=[a[i]*3%m+a[i-1]for i in range(4)]+[0]
print(a[3]%m)

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

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] * 3 % mod
        else:
            dp[i + 1][j] = dp[i][j]
            
    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[len(S)][3] % mod)

Solution (Python):
X = list(input())

q_num = X.count("?")
a_num = 0
c_num = X.count("C")
left_q_num = 0
right_q_num = q_num
ans = 0
len_x = len(X)
q_dict = []
b_ans = 0
q_ans = 0
q_dict = {}
q_dict[q_num - 1] = (3 ** (q_num - 1)) % (10 ** 9 + 7)
q_dict[q_num - 2] = (3 ** (q_num - 2)) % (10 ** 9 + 7)
q_dict[q_num - 3] = (3 ** (q_num - 3)) % (10 ** 9 + 7)
q_dict[q_num] = (3 ** (q_num)) % (10 ** 9 + 7)

if X[0] == "?":
    right_q_num -= 1
elif X[0] == "C":
    c_num -= 1
for i, x in enumerate(X):
    if x == "B" or x == "?":
        ans += (a_num * c_num)  * (q_dict[(left_q_num + right_q_num)])
        if left_q_num + right_q_num >= 2:
            ans += (right_q_num * left_q_num  + 3*(left_q_num * c_num) + 3*(right_q_num * a_num)) * (q_dict[(left_q_num + right_q_num - 2)])
        elif left_q_num + right_q_num == 1:
            ans += ((left_q_num * c_num) + (right_q_num * a_num)) * (q_dict[(left_q_num + right_q_num - 1)])
        ans = ans % (10 ** 9 + 7)
    if  i == len_x - 1:
        break
    if x == "A":
        a_num += 1
    elif x == "?":
        left_q_num += 1
    if X[i + 1] == "C":
        c_num -= 1
    elif X[i + 1] == "?":
        right_q_num -= 1

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

Solution (Python):
X = list(input())

q_num = X.count("?")
a_num = 0
c_num = X.count("C")
left_q_num = 0
right_q_num = q_num
ans = 0
len_x = len(X)
q_dict = []
b_ans = 0
q_ans = 0
q_dict = {}
q_dict[q_num - 1] = (3 ** (q_num - 1)) % (10 ** 9 + 7)
q_dict[q_num - 2] = (3 ** (q_num - 2)) % (10 ** 9 + 7)
q_dict[q_num - 3] = (3 ** (q_num - 3)) % (10 ** 9 + 7)
q_dict[q_num] = (3 ** (q_num)) % (10 ** 9 + 7)

if X[0] == "?":
    right_q_num -= 1
elif X[0] == "C":
    c_num -= 1
for i, x in enumerate(X):
    if x == "B" or x == "?":
        ans += (a_num * c_num)  * (q_dict[(left_q_num + right_q_num)])
        if left_q_num + right_q_num >= 2:
            ans += (right_q_num * left_q_num  + 3*(left_q_num * c_num) + 3*(right_q_num * a_num)) * (q_dict[(left_q_num + right_q_num - 2)])
        elif left_q_num + right_q_num == 1:
            ans += ((left_q_num * c_num) + (right_q_num * a_num)) * (q_dict[(left_q_num + right_q_num - 1)])
        ans = ans % (10 ** 9 + 7)
    if  i == len_x - 1:
        break
    if x == "A":
        a_num += 1
    elif x == "?":
        left_q_num += 1
    if X[i + 1] == "C":
        c_num -= 1
    elif X[i + 1] == "?":
        right_q_num -= 1

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

Solution (Python):
s=input()

n=len(s)
dc=dict()
dc['A']=0
dc['B']=1
dc['C']=2
dc['?']=3
dp=[[0 for i in range(4)] for j in range(n+1)]
dp[0][0]=1
mo=10**9+7
for i in range(n):
    for t in range(4):
        ch=s[i]
        m = 1 if dc[ch]==t-1 or dc[ch]==3 else 0
        if t!=0:
            dp[i+1][t]+=(dp[i][t-1]*m)%mo
        dp[i+1][t]+=(dp[i][t]*(3 if dc[ch]==3 else 1))%mo

ans=dp[n][3]
print(ans%mo)

Solution (Python):
import sys
sys.setrecursionlimit(1000000)



'''
n=int(input())
for i in range(n):
    a[i]=int(input())
    a[i],b[i]=map(int,input().split())
a=[int(x) for x in input().split()]
n,m=map(int,input.split())
from operator import itemgetter
a = [(1, "c", 1), (1, "b", 3), (2, "a", 0), (1, "a", 2)]
print(sorted(a))  
print(sorted(a, key=itemgetter(0)))  
print(sorted(a, key=itemgetter(0, 2)))  
print(sorted(a, key=lambda x: x[0] * x[2]))  
print(sorted(a, reverse=True))  
a.sort()  
try: 
    for i in range():
        k=b[i]
except IndexError as e:
    print(i)
'''

test_data1 = '''\
A??C
'''

test_data2 = '''\
ACACAC
'''

test_data3 = '''\
????C?????B??????A???????
'''

test_data4 = '''\
?AC?AC
'''
td_num=3

def GetTestData(index):
    if index==1:
        return test_data1
    if index==2:
        return test_data2
    if index==3:
        return test_data3
    if index==4:
        return test_data4
    
if False:
    with open("../test.txt", mode='w') as f:
        f.write(GetTestData(td_num))
    with open("../test.txt") as f:
        
        s=f.readline()
        
else:
    
    s=input()
    
n=len(s)
dc=dict()
dc['A']=0
dc['B']=1
dc['C']=2
dc['?']=3
dp=[[0 for i in range(4)] for j in range(n+1)]
dp[0][0]=1
mo=10**9+7
for i in range(n):
    for t in range(4):
        ch=s[i]
        if dc[ch]==t-1 or dc[ch]==3:
            m=1
        else:
            m=0
        if t!=0:
            dp[i+1][t]+=(dp[i][t-1]*m)%mo
        dp[i+1][t]+=(dp[i][t]*max(int(dc[ch]/3)*3,1))%mo

ans=dp[n][3]



    

print(ans%mo)

Solution (Python):
import sys
sys.setrecursionlimit(1000000)



'''
n=int(input())
for i in range(n):
    a[i]=int(input())
    a[i],b[i]=map(int,input().split())
a=[int(x) for x in input().split()]
n,m=map(int,input.split())
from operator import itemgetter
a = [(1, "c", 1), (1, "b", 3), (2, "a", 0), (1, "a", 2)]
print(sorted(a))  
print(sorted(a, key=itemgetter(0)))  
print(sorted(a, key=itemgetter(0, 2)))  
print(sorted(a, key=lambda x: x[0] * x[2]))  
print(sorted(a, reverse=True))  
a.sort()  
try: 
    for i in range():
        k=b[i]
except IndexError as e:
    print(i)
'''

test_data1 = '''\
A??C
'''

test_data2 = '''\
ACACAC
'''

test_data3 = '''\
????C?????B??????A???????
'''

test_data4 = '''\
?AC?AC
'''
td_num=3

def GetTestData(index):
    if index==1:
        return test_data1
    if index==2:
        return test_data2
    if index==3:
        return test_data3
    if index==4:
        return test_data4
    
if False:
    with open("../test.txt", mode='w') as f:
        f.write(GetTestData(td_num))
    with open("../test.txt") as f:
        
        s=f.readline()
        
else:
    
    s=input()
    
n=len(s)
lc_a=[0]*n
lc_c=[0]*n
lc_w=[0]*n
rc_a=[0]*n
rc_c=[0]*n
rc_w=[0]*n
rc_a0=s.count('A')
rc_c0=s.count('C')
rc_w0=s.count('?')
c_a=0
c_c=0
c_w=0
for i in range(n-1):
    ch=s[i]
    if ch=='A':
        c_a+=1
    if ch=='C':
        c_c+=1        
    if ch=='?':
        c_w+=1
    lc_a[i+1]=c_a
    
    lc_w[i+1]=c_w
    
    rc_c[i]=rc_c0-c_c
    rc_w[i]=rc_w0-c_w
      
ans=0
mo=10**9+7


for i in range(1,n-1):
    ch=s[i]
    if ch=='B' or ch=='?':
        ans+=(lc_a[i]*pow(3,lc_w[i],mo)+pow(3,max(0,lc_w[i]-1),mo)*lc_w[i])*(rc_c[i]*pow(3,rc_w[i],mo)+pow(3,max(0,rc_w[i]-1),mo)*rc_w[i])%mo
    

print(ans%mo)

Solution (Python):
S = input()

dp = [[None] * 4 for _ in range(len(S))]
dp.append([0, 0, 0, 1])
next_str = ["A", "B", "C"]
MOD = 10**9 + 7

for i, s in enumerate(reversed(S)):
    i = len(S) - i - 1
    for j in range(4):
        if j == 3:
            if s == "?":
                dp[i][j] = (3 * dp[i + 1][j]) % MOD
            else:
                dp[i][j] = dp[i + 1][j] % MOD
        else:
            if s == "?":
                m_1 = 3
                m_2 = 1
            else:
                m_1 = 1
                if s == next_str[j]:
                    m_2 = 1
                else:
                    m_2 = 0
            dp[i][j] = (m_1 * dp[i + 1][j] + m_2 * dp[i + 1][j + 1]) % MOD


print(dp[0][0])

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

print(dp[3][SLen])

Solution (Python):
s = input()

a = [0] * len(s)
b = [0] * len(s)
c = [0] * len(s)
q = 0
m = 10**9 + 7

if s[0] == "A":
    a[0] = 1
elif s[0] == "?":
    a[0] = 1
    q = 1

for i in range(1, len(s)):
    if s[i] == "A":
        a[i] = (a[i - 1] + pow(3, q, m)) % m
        b[i] = b[i - 1] % m
        c[i] = c[i - 1] % m
    elif s[i] == "B":
        a[i] = a[i - 1] % m
        b[i] = (b[i - 1] + a[i - 1]) % m
        c[i] = c[i - 1] % m
    elif s[i] == "C":
        a[i] = a[i - 1] % m
        b[i] = b[i - 1] % m
        c[i] = (c[i - 1] + b[i - 1]) % m
    else:
        a[i] = (3 * a[i - 1] + pow(3, q, m)) % m
        b[i] = (3 * b[i - 1] + a[i - 1]) % m
        c[i] = (3 * c[i - 1] + b[i - 1]) % m
        q += 1
        
print(c[len(s) - 1] % m)

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

MOD = 10**9+7

S = input()[:-1]
N = len(S)

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

for i in reversed(range(N+1)):
    for j in reversed(range(4)):
        if i == N:
            dp[i][j] = 1 if j == 3 else 0
        else:
            if j == 3:
                m1 = 3 if S[i] == "?" else 1
                dp[i][j] = m1*dp[i+1][j]
            else:
                m2 = 1 if S[i] == "?" or S[i] == "ABC"[j] else 0
                m1 = 3 if S[i] == "?" else 1
                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()

A = [1,0]
AB = 0
ABC = 0
D = 10**9 + 7
for c in s:
    if c == 'A':
        A[1] += A[0]
    elif c == 'B':
        AB += A[1]
    elif c == 'C':
        ABC += AB
    elif c == '?':
        ABC = (((ABC%D) *3)%D + (AB)%D)%D
        AB = (((AB%D) *3)%D + (A[1])%D)%D
        A[1] = (((A[1]%D)*3)%D + A[0]%D)%D
        A[0] = ((A[0]%D) * 3)%D

print(ABC%D)

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

dp = [0, 0, 0, 0]
dp[0] = 1

for s in S:
    factor = 3 if s == '?' else 1
    for j, c in zip([2, 1, 0], 'CBA'):
        dp[j + 1] = dp[j + 1] * factor % MOD
        if s == c or s == '?':
            dp[j + 1] += dp[j]
    if s == '?':
        dp[0] = (dp[0] * 3) % MOD

ans = dp[-1] % MOD

print(ans)

Solution (Python):
def we_love_abc(S: str)->int:
    ABC = 'ABC'
    MOD = 1000000007

    dp = [0, 0, 0, 0]
    dp[3] = 1

    for c in reversed(S):
        for j in range(3):
            m1 = 3 if c == '?' else 1
            m2 = 1 if c == '?' or c == ABC[j] else 0
            dp[j] = (m1 * dp[j] + m2 * dp[j+1]) % MOD
        dp[3] = (3 if c == '?' else 1) * dp[3]
        dp[3] %= MOD

    return dp[0] % MOD


if __name__ == "__main__":
    S = input()
    ans = we_love_abc(S)
    print(ans)

Solution (Python):
a = list(input())

dp = [[0]*3 for i in range(len(a)+1)]

ppp = 1
for i in range(len(a))[::-1]:
	if a[i] == "A":
		dp[i][0] += dp[i+1][0] + dp[i+1][1]
		dp[i][1] += dp[i+1][1]
		dp[i][2] += dp[i+1][2]
	elif a[i] == "B":
		dp[i][0] += dp[i+1][0]
		dp[i][1] += dp[i+1][1] + dp[i+1][2]
		dp[i][2] += dp[i+1][2]
	elif a[i] == "C":
		dp[i][0] += dp[i+1][0]
		dp[i][1] += dp[i+1][1]
		dp[i][2] += dp[i+1][2] + ppp
	else:
		dp[i][0] += 3 * dp[i+1][0] + dp[i+1][1]
		dp[i][1] += 3 * dp[i+1][1] + dp[i+1][2]
		dp[i][2] += 3 * dp[i+1][2] + ppp
		ppp *= 3
		ppp %= 10**9+7
	for j in range(3):
		dp[i][j] %= (10**9 + 7)
print(dp[0][0] % (10**9 + 7))

Solution (Python):
S = input()
mod = 10 ** 9 + 7
A, AB, ABC, ALL = 0, 0, 0, 1

for s in S:
    if s == 'A':
        A += ALL
        A %= mod

    if s == 'B':
        AB += A
        AB %= mod

    if s == 'C':
        ABC += AB
        ABC %= mod

    if s == '?':
        ABC = (3 * ABC + AB) % mod
        AB = (3 * AB + A) % mod
        A = (3 * A + ALL) % mod
        ALL *= 3
        ALL %= mod

print(ABC)