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):
s = input()
mod = 1000000007
dp = [1, 0, 0, 0]
for c in s:
    newdp = [n for n in dp]
    if c == 'A':
        newdp[1] = (newdp[1] + dp[0]) % mod
    if c == 'B':
        newdp[2] = (newdp[2] + dp[1]) % mod
    if c == 'C':
        newdp[3] = (newdp[3] + dp[2]) % mod
    if c == '?':
        newdp[0] = (newdp[0] * 3) % mod
        newdp[1] = (newdp[1] * 3 + dp[0]) % mod
        newdp[2] = (newdp[2] * 3 + dp[1]) % mod
        newdp[3] = (newdp[3] * 3 + dp[2]) % mod
    dp = newdp
print(dp[3])

Solution (Python):
S = input()
MOD = 10**9+7
DP = [0]*14 
for i in range(len(S)):
    if S[i] == "A":
        DP[0] += 1
    elif S[i] == "B":
        for i in range(2,5,2):
            DP[i] += DP[i//2-1] 
            DP[i] %= MOD
    elif S[i] == "C":
        for i in range(6,13,2):
            DP[i] += DP[i//2-1]
            DP[i] %= MOD
    elif S[i] == "?":
        for i in range(6,13,2):
            DP[i+1] += DP[i//2-1]
            DP[i+1] %= MOD
        for i in range(2,5,2):
            DP[i+1] += DP[i//2-1] 
            DP[i+1] %= MOD    
        DP[1] += 1
q = DP[1]
Q0 = 3**q % MOD
Q1 = int(3**(q-1) % MOD)
Q2 = int(3**(q-2) % MOD)
Q3 = int(3**(q-3) % MOD)
Q = [0,0,0,0,0,0,Q0,Q1,Q1,Q2,Q1,Q2,Q2,Q3]
ans = 0
for i in range(14):
    ans += DP[i]*Q[i] % MOD
print(ans%MOD)

Solution (Python):
S = input()

MOD = 1000000007


count = [[0, 0, 0] for _ in range(8)]
hatena_count = 0

for c in S:
    if c == 'A':
        nums = [0,1,2,3]
        for num in nums:
            count[num][0] += 1
    elif c == 'B':
        nums = [0,1,4,5]
        for num in nums:
            count[num][1] += count[num][0]
    elif c == 'C':
        nums = [0,2,4,6]
        for num in nums:
            count[num][2] += count[num][1]
    elif c == '?':
        
        nums = [1,3,5,7]
        for num in nums:
            count[num][2] += count[num][1]
        
        
        nums = [2,3,6,7]
        for num in nums:
            count[num][1] += count[num][0]

        
        nums = [4,5,6,7]
        for num in nums:
            count[num][0] += 1
        
        hatena_count += 1

total = 0
coef = [0, 1, 1, 2, 1, 2, 2, 3]
for i in range(8):
    total += count[i][2] * 3**(hatena_count - coef[i])

print(int(total % MOD))

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

A_cum = [0] * N
C_cum = [0] * N
q_sum_left = [0] * N
q_sum_right = [0] * N
for i in range(N - 1):
    s = S[i]
    if s == 'A':
        A_cum[i + 1] = A_cum[i] + 1
    else:
        A_cum[i + 1] = A_cum[i]
    if s == '?':
        q_sum_left[i + 1] = q_sum_left[i] + 1
    else:
        q_sum_left[i + 1] = q_sum_left[i]
for i in range(N - 1, 0, -1):
    s = S[i]
    if s == 'C':
        C_cum[i - 1] = C_cum[i] + 1
    else:
        C_cum[i - 1] = C_cum[i]
    if s == '?':
        q_sum_right[i - 1] = q_sum_right[i] + 1
    else:
        q_sum_right[i - 1] = q_sum_right[i]
ans = 0
for i in range(N):
    if S[i] == 'B' or S[i] == '?':
        ans = (ans + (A_cum[i] * pow(3, q_sum_left[i], mod) + q_sum_left[i] * pow(3, max(0, q_sum_left[i] - 1), mod))
               * (C_cum[i] * pow(3, q_sum_right[i], mod) + q_sum_right[i] * pow(3, max(0, q_sum_right[i] - 1), mod))) % mod

print(ans)

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

n = len(s)
o = [1] * (n+1)
a = [0] * (n+1)
b = [0] * (n+1)
c = [0] * (n+1)

for i in range(n):
    if s[i] == '?':
        o[i+1] = o[i] * 3
        a[i+1] = a[i] * 3 + o[i]
        b[i+1] = b[i] * 3 + a[i]
        c[i+1] = c[i] * 3 + b[i]
    else:
        o[i+1] = o[i]
        a[i+1] = a[i]
        b[i+1] = b[i]
        c[i+1] = c[i]
        if s[i] == 'A':
            a[i+1] += o[i]
        if s[i] == 'B':
            b[i+1] += a[i]
        if s[i] == 'C':
            c[i+1] += b[i]
    o[i+1] = o[i+1] % MOD
    a[i+1] = a[i+1] % MOD
    b[i+1] = b[i+1] % MOD
    c[i+1] = c[i+1] % MOD
print(c[n])

Solution (Python):

import sys, math, fractions, itertools

MOD = 1000000007  


def solve(S: str):
    dp = [[0 for _ in range(4)] for _ in range(len(S)+1)]
    for i in reversed(range(len(S)+1)):
        for j in reversed(range(4)):
            if i == len(S) and j == 3:
                dp[i][j] = 1
            if j < 3 and i == len(S):
                dp[i][j] = 0
            if i < len(S):
                if j == 3:
                    if S[i] == '?':
                        m = 3
                    else:
                        m = 1
                    dp[i][3] = m * dp[i+1][3]
                if j < 3:
                    if S[i] == '?':
                        m1 = 3
                    else:
                        m1 = 1
                    if S[i] == '?' or S[i] == list('ABC')[j]:
                        m2 = 1
                    else:
                        m2 = 0
                    dp[i][j] = m1 * dp[i+1][j] + m2 * dp[i+1][j+1]
            dp[i][j] %= MOD
    print(dp[0][0])
    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):
from functools import reduce

S = input()

MOD = 10**9 + 7


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

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

    __repr__ = __str__

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

    def __radd__(self, other):
        return ModInt(other + self.x)

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

    def __rmul__(self, other):
        return ModInt(other * self.x)

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

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





_, _, _, ans = reduce(
    lambda acc, c: (
        (
            3 * acc[0] if c == '?' else
            acc[0]
        ),
        (
            acc[0] + acc[1] if c == 'A' else
            3 * acc[1] + acc[0] if c == '?' else
            acc[1]
        ),
        (
            acc[1] + acc[2] if c == 'B' else
            3 * acc[2] + acc[1] if c == '?' else
            acc[2]
        ),
        (
            acc[2] + acc[3] if c == 'C' else
            3 * acc[3] + acc[2] if c == '?' else
            acc[3]
        ),
    ),
    S,
    (ModInt(1), ModInt(0), ModInt(0), ModInt(0))
)

print(ans)

Solution (Python):
S = list(input())
N = len(S)
mod = int(1E9+7)

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

dp[N][3] = 1
for i in range(N-1, -1, -1):
    m = 3 if S[i] == '?' else 1
    dp[i][3] = m*dp[i+1][3]
    if S[i] == '?':
        dp[i][0] = m*dp[i+1][0] + dp[i+1][1]
        dp[i][1] = m*dp[i+1][1] + dp[i+1][2]
        dp[i][2] = m*dp[i+1][2] + dp[i+1][3]
    if S[i] == 'A':
        dp[i][0] = m*dp[i+1][0] + dp[i+1][1]
        dp[i][1] = m*dp[i+1][1]
        dp[i][2] = m*dp[i+1][2]
    if S[i] == 'B':
        dp[i][0] = m*dp[i+1][0]
        dp[i][1] = m*dp[i+1][1] + dp[i+1][2]
        dp[i][2] = m*dp[i+1][2]
    if S[i] == 'C':
        dp[i][0] = m*dp[i+1][0]
        dp[i][1] = m*dp[i+1][1]
        dp[i][2] = m*dp[i+1][2] + dp[i+1][3]
    dp[i][0] %= mod
    dp[i][1] %= mod
    dp[i][2] %= mod
    dp[i][3] %= mod
    
print(dp[0][0])

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

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

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

o = 1
a = 0
b = 0
c = 0

for i in s:
    if i == "A":
        a += o
    elif i == "B":
        b += a
    elif i == "C":
        c += b
    else:
        o, a, b, c = o*3, o+a*3, a+b*3, b+c*3

    o %= MOD
    a %= MOD
    b %= MOD
    c %= MOD

print(c)

Solution (Python):
S = input()

MOD = 10 ** 9 + 7
N = len(S)
dp = [[0] * 4 for _ in range(N + 1)]
dp[-1][-1] = 1

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

Solution (Python):
S = input()

MOD = 10 ** 9 + 7
N = len(S)
dp = [[0] * 4 for _ in range(N + 1)]
dp[-1][-1] = 1

for i in reversed(range(N)):
    m = 3 if S[i] == '?' else 1
    for j in reversed(range(3)):
        dp[i][j] = m * dp[i + 1][j]
        if S[i] == '?' or S[i] == 'ABC'[j]:
            dp[i][j] += dp[i + 1][j + 1]
        dp[i][j] %= MOD
    
    
    dp[i][3] = m * dp[i + 1][3] % MOD
            
print(dp[0][0] % MOD)

Solution (Python):
import numpy as np


dp = np.zeros((2, 4), dtype=np.int64)
mod = int(1e9+7)
dp[0][0] = 1
for s in input():
    if s == '?':
        dp[1] = dp[0]*3
        dp[1][1:] += dp[0][:3]
    else:
        dp[1] = dp[0]
        if s == 'A':
            dp[1][1] += dp[0][0]
        elif s == 'B':
            dp[1][2] += dp[0][1]
        elif s == 'C':
            dp[1][3] += dp[0][2]
    dp[0] = np.remainder(dp[1], mod)
print(dp[0][3])

Solution (Python):
import numpy as np


dp = np.zeros((2, 4), dtype=np.int64)
mod = 1e9+7
dp[0][0] = 1
for s in input():
    if s == '?':
        dp[1] = dp[0]*3
        dp[1][1:] += dp[0][:3]
        dp[1] = np.remainder(dp[1], mod)
    else:
        dp[1] = dp[0]
        if s == 'A':
            dp[1][1] += dp[0][0]
            dp[1][1] = np.remainder(dp[1][1], mod)
        elif s == 'B':
            dp[1][2] += dp[0][1]
            dp[1][2] = np.remainder(dp[1][2], mod)
        elif s == 'C':
            dp[1][3] += dp[0][2]
            dp[1][3] = np.remainder(dp[1][3], mod)
    dp[0] = dp[1]
print(dp[0][3])

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



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

for i in range(len(S)):
    if S[i] == '?':
        for j in range(4):
            dp[i + 1][j] = dp[i][j] * 3 % MOD
    else:
        for j in range(4):
            dp[i + 1][j] = dp[i][j]
    if S[i] in ['A', '?']:
        dp[i + 1][1] += dp[i][0]
    if S[i] in ['B', '?']:
        dp[i + 1][2] += dp[i][1]
    if S[i] in ['C', '?']:
        dp[i + 1][3] += dp[i][2]

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

Solution (Python):
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import math
Mod = 1000000007



def main(): 
    S = input()
    N = len(S)
    p = [0,0,0,1]
    for i in range(N):
        if S[i] == "A":
            p[0] += p[3]
            p[0] %= Mod
        elif S[i] == "B":
            p[1] += p[0]
            p[1] %= Mod
        elif S[i] == "C":
            p[2] += p[1]
            p[2] %= Mod
        elif S[i] == "?":
            p[2] = p[2]*3 + p[1]
            p[1] = p[1]*3 + p[0]
            p[0] = p[0]*3 + p[3]
            p[3] *= 3
            for l in range(4):
                p[l] %= Mod

    print(p[2])
if __name__ == "__main__":
    main() 




def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n < 2 is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))):
        if prime[i] == 1:
            for j in range(2*i,n):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n):
        if prime[i] == 1:
            res.append(i)
    return res

class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py

    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)

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

a = b = ans = 0
a_old = b_old = ans_old = 0

q = 1 
for s in S:
    if s == "A":
        a = (a_old + q) % mod
        b = b_old
        ans = ans_old
    elif s == "B":
        a = a_old
        b = (b_old + a_old) % mod
        ans = ans_old
    elif s == "C":
        a = a_old
        b = b_old
        ans = (ans_old + b_old) % mod
    else:
        a = (3 * a_old + q) % mod
        b = (3 * b_old + a_old) % mod
        ans = (3 * ans_old + b_old) % mod
        q = q * 3 % mod
    a_old = a
    b_old = b
    ans_old = ans
    

print(ans)

Solution (Python):
s=input()
l=len(s)
mod=10**9+7
dp=[[0,0,0,0] for _ in range(l+1)]
for i in range(l,-1,-1):
  for j in range(3,-1,-1):
    if i==l:
      if j==3:
        dp[i][j]=1
      else:
        dp[i][j]=0
    else:
      if s[i]=='?':
        dp[i][j]=dp[i+1][j]*3
      else:
        dp[i][j]=dp[i+1][j]
      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):
def makelist(n, m):
    return [[0 for _ in range(m)] for _ in range(n)]

S = "0" + input()
l = len(S) - 1


MOD = int(1e9) + 7
dp = makelist(l+1, 4)

def toInt(c):
    return [ord(c) - 65]

dp[0][-1] = 1

for i in range(1, l+1):
    if S[i] == 'A':
        dp[i][-1] = dp[i-1][-1]
        dp[i][0] = (dp[i-1][0] + dp[i-1][-1]) % MOD
        dp[i][1] = dp[i-1][1]
        dp[i][2] = dp[i-1][2]
    elif S[i] == 'B':
        dp[i][-1] = dp[i-1][-1]
        dp[i][0] = dp[i-1][0]
        dp[i][1] = (dp[i-1][1] + dp[i-1][0]) % MOD
        dp[i][2] = dp[i-1][2]
    elif S[i] == 'C':
        dp[i][-1] = dp[i-1][-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]) % MOD
    elif S[i] == '?':
        dp[i][-1] = (dp[i-1][-1] * 3) % MOD
        dp[i][0] = ((dp[i-1][0] * 3) % MOD + dp[i-1][-1])  % MOD
        dp[i][1] = ((dp[i-1][1] * 3) % MOD + dp[i-1][0]) % MOD
        dp[i][2] = ((dp[i-1][2] * 3) % MOD + dp[i-1][1]) % MOD

print(dp[l][2])

Solution (Python):
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque

from itertools import product

from itertools import permutations

from itertools import combinations

from itertools import accumulate
from bisect import bisect_left, bisect_right

import re





dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
INF = int(1e18)
MOD = int(1e9)+7 

def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def init_dp_table(i, j, init=INF):
  return [[ init for _ in range(j)] for _ in range(i)]



S = input()

dp = init_dp_table(len(S)+1, 4, 0)
dp[0][0] = 1

for i in range(len(S)):
    Si = S[i]
    if Si == "A" or Si == "?":
        dp[i+1][0] += dp[i][0] % MOD
        dp[i+1][1] += dp[i][1] % MOD
        dp[i+1][2] += dp[i][2] % MOD
        dp[i+1][3] += dp[i][3] % MOD
        dp[i+1][1] += dp[i][0] % MOD
    if Si == "B" or Si == "?":
        dp[i+1][0] += dp[i][0] % MOD
        dp[i+1][1] += dp[i][1] % MOD
        dp[i+1][2] += dp[i][2] % MOD
        dp[i+1][3] += dp[i][3] % MOD
        dp[i+1][2] += dp[i][1] % MOD
    if Si == "C" or Si == "?":
        dp[i+1][0] += dp[i][0] % MOD
        dp[i+1][1] += dp[i][1] % MOD
        dp[i+1][2] += dp[i][2] % MOD
        dp[i+1][3] += dp[i][3] % MOD
        dp[i+1][3] += dp[i][2] % MOD

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

Solution (Python):



def ri():
    return int(input())

def rl():
    return list(input().split())

def rli():
    return list(map(int, input().split()))

MOD = 10**9+7

def main():
    s = input()
    dp = [[0 for _ in range(4)] for _ in range(len(s)+1)]
    dp[0][0] = 1
    for i, c in enumerate(s):
        if c == '?':
            for j in range(4):
                dp[i+1][j] = 3*dp[i][j]
        else:
            for j in range(4):
                dp[i+1][j] = dp[i][j]
        if c == 'A' or c == '?':
            dp[i+1][1] += dp[i][0]
        if c == 'B' or c == '?':
            dp[i+1][2] += dp[i][1]
        if c == 'C' or c == '?':
            dp[i+1][3] += dp[i][2]
        if i & 1:
            for j in range(4):
                dp[i+1][j] %= MOD

    print(dp[len(s)][3]%MOD)


if __name__ == '__main__':
    main()

Solution (Python):



import sys
import math
import bisect
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter


mod = 10**9 + 7

s = list(input())
n = len(s)








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] = 3*dp[i][j] % mod
    else:
        for j in range(4):
            dp[i+1][j] = dp[i][j]
    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
    elif s[i] == '?':
        
        for j in range(3):
            dp[i+1][j+1] += dp[i][j]
            dp[i+1][j+1] %= mod
print(dp[n][3])

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

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

for i in range(N, -1, -1) :
    for j in range(4) :
        if i == N :
            if j == 3 :
                dp[i][j] = 1
            else :
                dp[i][j] = 0
        else :
            if j == 3 :
                weight = 3 if S[i] == '?' else 1
                dp[i][j] = weight * dp[i+1][j]
            else :
                weight = 3 if S[i] == '?' else 1
                able = 1 if (S[i] == mask[j] or S[i] == '?') else 0
                dp[i][j] = weight * dp[i+1][j] + able * dp[i+1][j+1]
            dp[i][j] %= MOD


print(dp[0][0] % MOD)

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

dp[0][0] = 1

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

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

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

dp = [[0]*5 for _ in range(ls+1)]

dp[0][0] = 1

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

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

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


for i, ss in enumerate(s):
    for j in range(4):
        dp[i + 1][j] += dp[i][j] * (1 if ss != '?' else 3)
        

    if ss == 'A':
        dp[i + 1][1] += dp[i][0]
    elif ss == 'B':
        dp[i + 1][2] += dp[i][1]
    elif ss == 'C':
        dp[i + 1][3] += dp[i][2]
    elif ss == '?':
        dp[i + 1][1] += dp[i][0]  
        dp[i + 1][2] += dp[i][1]  
        dp[i + 1][3] += dp[i][2]  
    

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

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

"""
i文字目の文字で処理を場合分け
それぞれ、取る場合と取らない場合の処理を書く
'?'のときで、文字を取らない場合、
ABCに変える3パターンそれぞれで取らない処理を行うので、3倍になる
"""

Solution (Python):


MOD = 1000000007


def main():
  S = str(input())
  dp = [[0 for _ in range(3)] for _ in range(len(S)+1)]
  A,AB,ABC = [0,1,2]
  wc_num = 1
  for i,s in enumerate(S):
    if s in "A?":
      dp[i+1][A] = (dp[i+1][A]+dp[i][A]+wc_num) % MOD
      dp[i+1][AB] = (dp[i+1][AB]+dp[i][AB]) % MOD
      dp[i+1][ABC] = (dp[i+1][ABC]+dp[i][ABC]) % MOD
    if s in "B?":
      dp[i+1][A] = (dp[i+1][A]+dp[i][A]) % MOD
      dp[i+1][AB] = (dp[i+1][AB]+dp[i][AB]+dp[i][A]) % MOD
      dp[i+1][ABC] = (dp[i+1][ABC]+dp[i][ABC]) % MOD
    if s in "C?":
      dp[i+1][A] = (dp[i+1][A]+dp[i][A]) % MOD
      dp[i+1][AB] = (dp[i+1][AB]+dp[i][AB]) % MOD
      dp[i+1][ABC] = (dp[i+1][ABC]+dp[i][ABC]+dp[i][AB]) % MOD
    if s == "?":
      wc_num = (wc_num*3) % MOD
  print(dp[len(S)][ABC])



if __name__ == "__main__":
  main()

Solution (Python):
mod = 10**9+7
S = list(input())
Thankyou = 1
DP=[]


if S[0] == "A" or S[0]=="?":
    DP.append([1,0,0])
    if S[0]=="?":
        Thankyou = 3
else:
    DP.append([0,0,0])
for i,s in enumerate(S):

    if i==0:continue
    a,b,c = DP[i-1]
    if s=="A":
        DP.append([(a+Thankyou)%mod,b,c])
    elif s=="B":
        DP.append([a,(a+b)%mod,c])
    elif s=="C":
        DP.append([a,b,(b+c)%mod])
    else:
        DP.append([(Thankyou+3*a)%mod,(a+3*b)%mod,(b+3*c)%mod])
        Thankyou *= 3
        Thankyou %= mod
print(DP[len(S)-1][2]%mod)

Solution (Python):
mod = 10**9+7
S = list(input())
Thankyou = 1
DP=[]


if S[0] == "A" or S[0]=="?":
    DP.append([1,0,0])
    if S[0]=="?":
        Thankyou = 3
else:
    DP.append([0,0,0])
for i,s in enumerate(S):

    if i==0:continue
    a,b,c = DP[i-1]
    if s=="A":
        DP.append([(a+Thankyou)%mod,b,c])
    elif s=="B":
        DP.append([a,(a+b)%mod,c])
    elif s=="C":
        DP.append([a,b,(b+c)%mod])
    else:
        DP.append([(Thankyou+3*a)%mod,(a+3*b)%mod,(b+3*c)%mod])
        Thankyou *= 3
        Thankyou %= mod
print(DP[len(S)-1][2]%mod)

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

dp = [[0] * 4 for _ 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 + 1][j] + dp[i][j] * 3) % MOD
        else:
            dp[i + 1][j] = (dp[i + 1][j] + dp[i][j]) % MOD
    
    if S[i] == 'A' or S[i] == '?': dp[i + 1][1] = (dp[i + 1][1] + dp[i][0]) % MOD
    if S[i] == 'B' or S[i] == '?': dp[i + 1][2] = (dp[i + 1][2] + dp[i][1]) % MOD
    if S[i] == 'C' or S[i] == '?': dp[i + 1][3] = (dp[i + 1][3] + dp[i][2]) % MOD

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

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

s = [0]*4

s[0] = 1

for c in S:
    if c == "?":
        s = [s[0]*3,s[1]*3+s[0],s[2]*3+s[1],s[3]*3+s[2]]
        for i in range(4):
            s[i] %= MOD
    else:
        i = "ABC".find(c)
        s[i+1] += s[i] % MOD
print(s[3]%MOD)

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

dp=[[0]*3 for i in range(l)]
mod=10**9+7
c=0

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

print(dp[-1][2])

Solution (Python):
s=input()
l=len(s)
dp=[[0]*4 for i in range(l+1)]
dp[0][0]=1
mod=10**9+7
for i in range(l):
    c = s[i]
    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] 
    if c=="A":
        dp[i+1][1]+=dp[i][0]
    if c=="B":
        dp[i+1][2]=dp[i][2]+dp[i][1] 
    if c=="C":
        dp[i+1][3]=dp[i][3]+dp[i][2]
    if c=="?":
        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[-1][3]%mod)

Solution (Python):
mod=10**9+7
S=input()
N=len(S)
Acnt=[[0,0] for i in range(N+2)]
Ccnt=[[0,0] for i in range(N+2)]
for i in range(N):
    Acnt[i+1]=Acnt[i].copy()
    Ccnt[-i-2]=Ccnt[-i-1].copy()
    if S[i]=="A":
        Acnt[i+1][0]+=1
    if S[i]=="?":
        Acnt[i+1][1]+=1
    if S[-i-1]=="C":
        Ccnt[-i-2][0]+=1
    if S[-i-1]=="?":
        Ccnt[-i-2][1]+=1
Acnt[N+1]=Acnt[N]
Ccnt[-N-2]=Ccnt[-N-1]
ans=0
ruijo=[1]*(N+1)
for i in range(N):
    ruijo[i+1]=ruijo[i]*3%mod
ruijo.append(0)
for i in range(N):
    if S[i]=="B" or S[i]=="?":
        a,b,c,d=0,0,0,0
        a=Acnt[i][0]*Ccnt[i+2][0]*ruijo[Acnt[i][1]+Ccnt[i+2][1]]%mod
        if Ccnt[i+2][1]>0:
            b=Acnt[i][0]*Ccnt[i+2][1]*ruijo[Acnt[i][1]+Ccnt[i+2][1]-1]%mod
        if Acnt[i][1]>0:
            c=Acnt[i][1]*Ccnt[i+2][0]*ruijo[Acnt[i][1]+Ccnt[i+2][1]-1]%mod
        if Acnt[i][1]>0 and Ccnt[i+2][1]>0:
            d=Acnt[i][1]*Ccnt[i+2][1]*ruijo[Acnt[i][1]+Ccnt[i+2][1]-2]%mod
        ans=(ans+a+b+c+d)%mod
print(ans)

Solution (Python):
mo=10**9+7
s=input()
n=len(s)
dp=[[0]*(1+n) for i in range(3)]
cc=0
for i in range(n):
    c=s[i]
    if c=='A':
        da,db,dc,dd=1,0,0,1
    elif c=='B':
        da,db,dc,dd=0,1,0,1
    elif c=='C':
        da,db,dc,dd=0,0,1,1
    elif c=='?':
        da,db,dc,dd=1,1,1,3
        
    dp[0][i+1]=dp[0][i]*dd+da*pow(3,cc,mo)
    dp[1][i+1]=dp[1][i]*dd+dp[0][i]*db
    dp[2][i+1]=dp[2][i]*dd+dp[1][i]*dc
    dp[0][i+1]%=mo
    dp[1][i+1]%=mo
    dp[2][i+1]%=mo
    if c=='?':
        cc+=1

print(dp[2][n]%mo)

Solution (Python):
mo=10**9+7
s=input()
n=len(s)
dp=[[0]*(1+n) for i in range(3)]
cc=0
for i in range(n):
    c=s[i]
    if c=='A':
        da=1
        db=0
        dc=0
        dd=1
    elif c=='B':
        da=0
        db=1
        dc=0
        dd=1
    elif c=='C':
        da=0
        db=0
        dc=1
        dd=1
    elif c=='?':
        da=1
        db=1
        dc=1
        dd=3
        
    dp[0][i+1]=dp[0][i]*dd+da*pow(3,cc,mo)
    dp[1][i+1]=dp[1][i]*dd+dp[0][i]*db
    dp[2][i+1]=dp[2][i]*dd+dp[1][i]*dc
    dp[0][i+1]%=mo
    dp[1][i+1]%=mo
    dp[2][i+1]%=mo
    if c=='?':
        cc+=1

print(dp[2][n]%mo)

Solution (Python):
M = 10 ** 9 + 7
S = input()
A = 0
AB = 0
ABC = 0
X = 1
for c in S:
    if c == 'C':
        ABC = (ABC + AB) % M
    elif c == 'B':
        AB = (AB + A) % M
    elif c == 'A':
        A = (A + X) % M
    elif c == '?':
        ABC = (3 * ABC + AB) % M
        AB = (3 * AB + A) % M
        A = (3 * A + X) % M
        X = (3 * X) % M
print(ABC)

Solution (Python):
MOD = 10 ** 9 + 7
s = input()
n = len(s)
dp = [[0] * 4 for _ in range(n + 1)]
dp[0][0] = 1
for i in range(n):
  if s[i] == '?':
    dp[i + 1][0] += dp[i][0] * 3
    dp[i + 1][0] %= MOD
  else:
    dp[i + 1][0] += dp[i][0]
  for j in range(3):
    if s[i] == 'ABC'[j] or s[i] == '?':
      dp[i + 1][j + 1] += dp[i][j]
    dp[i + 1][j + 1] += dp[i][j + 1] * (3 if s[i] == '?' else 1)
    dp[i + 1][j + 1] %= MOD
print(dp[n][3] % MOD)

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

list_=[[0,0,0,0]]*(N+1)
for cur in range(N,-1,-1):
    for i in range(4):
        if cur==N:
            if i==3:
                list_[N][i]=1
            else:
                list_[N][i]=0
        else:
            if S[cur]=='ABCD'[i]:
                list_[cur][i]=(list_[cur+1][i+1]+list_[cur+1][i])%mod
            elif S[cur]=='?' and i!=3:
                list_[cur][i]=(list_[cur+1][i+1]+3*list_[cur+1][i])%mod
            elif S[cur]=='?':
                list_[cur][i]=3*list_[cur+1][i]%mod
            else:
                list_[cur][i]=list_[cur+1][i]%mod

print(list_[0][0]%mod)