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

from pprint import pprint

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

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

dp[len(S)][0] = 0
dp[len(S)][1] = 0
dp[len(S)][2] = 0
dp[len(S)][3] = 1

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

    dp[i][3] %= MOD
    dp[i][2] %= MOD
    dp[i][1] %= MOD
    dp[i][0] %= MOD



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

Solution (Python):
S=input()
N=len(S)
O=1
A=[0]*(N+1)
AB=[0]*(N+1)
ABC=[0]*(N+1)
for i in range(1,N+1):
  A[i]=A[i-1]
  AB[i]=AB[i-1]
  ABC[i]=ABC[i-1]
  if S[i-1] is "A":
    A[i]+=O
  elif S[i-1] is "B":
    AB[i]+=A[i-1]
  elif S[i-1] is "C":
    ABC[i]+=AB[i-1]
  elif S[i-1] is "?":
    A[i]*=3
    A[i]+=O
    AB[i]*=3
    AB[i]+=A[i-1]
    ABC[i]*=3
    ABC[i]+=AB[i-1]
    O*=3
  A[i]=A[i]%(10**9+7)
  AB[i]=AB[i]%(10**9+7)
  ABC[i]=ABC[i]%(10**9+7)
  O=O%(10**9+7)
print(int(ABC[N]%(10**9+7)))

Solution (Python):
s = input()
MOD = 10 ** 9 + 7
n = len(s)
ABC = 'ABC'

dp = [[0] * 4 for i 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 s[i] == '?':
                dp[i][j] = 3 * dp[i+1][j]
            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):
Mod = 10**9+7
S = input()
N = len(S)
O = 1
A = [0]*N
AB = [0]*N
ABC = [0]*N

for i in range(N):
    A[i] = A[i-1]
    AB[i] = AB[i-1]
    ABC[i] = ABC[i-1]
    if S[i] == 'A':
        A[i] += O
    if S[i] == 'B':
        AB[i] += A[i-1]
    if S[i] == 'C':
        ABC[i] += AB[i-1]
    if S[i] == '?':
        A[i] *= 3
        A[i] += O
        AB[i] *= 3
        AB[i] += A[i-1]
        ABC[i] *= 3
        ABC[i] += AB[i-1]
        O *= 3
    A[i] %= Mod
    AB[i] %= Mod
    ABC[i] %= Mod
    O %= Mod
print(ABC[-1])

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

    for i in range(n + 1)[::-1]:
        for j in range(4)[::-1]:
            if i == n:
                if j == 3:
                    dp[i][j] = 1
                else:
                    dp[i][j] = 0
            else:
                is_wildcard = s[i] == '?'
                if j == 3:
                    m = 3 if is_wildcard else 1
                    dp[i][j] = m * dp[i + 1][3] % modulus

                else:
                    m1 = 3 if is_wildcard else 1
                    m2 = 1 if is_wildcard or s[i] == 'ABC'[j] else 0

                    dp[i][j] = (m1 * dp[i + 1][j] + m2 * dp[i + 1][j + 1]) % modulus
            
    print(dp[0][0])

Solution (Python):
p = 1000000007
s = input()
n = len(s)
e,a,b,c = 1,0,0,0
for i in range(n):
  if s[i] == "A":
    a = (e+a)%p
  elif s[i] == "B":
    b = (a+b)%p
  elif s[i] == "C":
    c = (b+c)%p
  else:
    e,a,b,c = (3*e)%p,(e+3*a)%p,(a+3*b)%p,(b+3*c)%p
print(c)

Solution (Python):
p = 1000000007
s = input()
n = len(s)
e,a,b,c = 1,0,0,0
for i in range(n):
  if s[i] == "A":
    e,a,b,c = e,(e+a)%p,b,c
  elif s[i] == "B":
    e,a,b,c = e,a,(a+b)%p,c
  elif s[i] == "C":
    e,a,b,c = e,a,b,(b+c)%p
  else:
    e,a,b,c = (3*e)%p,(e+3*a)%p,(a+3*b)%p,(b+3*c)%p
print(c)

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

for j in range(1,len_s+1):
    if(s[j-1]=="?"):
        dp[0][j]=3*dp[0][j-1]
    else:
        dp[0][j]=dp[0][j-1]
    
    if(s[j-1]=="?"):
        dp[1][j]=dp[0][j-1] + 3*dp[1][j-1]
    elif(s[j-1]=="A"):
        dp[1][j]=dp[0][j-1] + dp[1][j-1]
    else:
        dp[1][j]=dp[1][j-1]

    if(s[j-1]=="?"):
        dp[2][j]=dp[1][j-1] + 3*dp[2][j-1]
    elif(s[j-1]=="B"):
        dp[2][j]=dp[1][j-1] + dp[2][j-1]
    else:
        dp[2][j]=dp[2][j-1]

    if(s[j-1]=="?"):
        dp[3][j]=dp[2][j-1] + 3*dp[3][j-1]
    elif(s[j-1]=="C"):
        dp[3][j]=dp[2][j-1] + dp[3][j-1]
    else:
        dp[3][j]=dp[3][j-1]

    for k in range(4):
        dp[k][j]%=10**9+7

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

Solution (Python):
S = input()

ZABC = [[0 for i in range(4)] for j in range(len(S))]
if S[0] == '?':  
    ZABC[0][0] = 3
else:
    ZABC[0][0] = 1
if S[0] == '?' or S[0] == 'A':  
    ZABC[0][1] = 1
else:
    ZABC[0][1] = 0
for i in range(2):
    ZABC[0][i+2] = 0

for i in range(1,len(S)):
    if S[i] == '?':
        q = 3
    else:
        q = 1
    ZABC[i][0] = (ZABC[i-1][0]*q)%1000000007
for i in range(1,len(S)):
    if S[i] == '?':
        q = 3
    else:
        q = 1
    if S[i] == '?' or S[i] == 'A':
        r = 1
    else:
        r = 0
    ZABC[i][1] = (ZABC[i-1][1]*q+ZABC[i-1][0]*r)%1000000007
for i in range(1,len(S)):
    if S[i] == '?':
        q = 3
    else:
        q = 1
    if S[i] == '?' or S[i] == 'B':
        r = 1
    else:
        r = 0
    ZABC[i][2] = (ZABC[i-1][2]*q+ZABC[i-1][1]*r)%1000000007
for i in range(1,len(S)):
    if S[i] == '?':
        q = 3
    else:
        q = 1
    if S[i] == '?' or S[i] == 'C':
        r = 1
    else:
        r = 0
    ZABC[i][3] = (ZABC[i-1][3]*q+ZABC[i-1][2]*r)%1000000007
print(ZABC[len(S)-1][3])

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

for s in S:
    if s == "A":
        A = (A + ALL) % mod

    if s == "B":
        AB = (AB + A) % mod

    if s == "C":
        ABC = (ABC + AB) % mod

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

print(ABC % mod)

Solution (Python):

from sys import stdin

s_in = lambda: stdin.readline()[:-1] 
d_in = lambda: int(stdin.readline()) 
ds_in = lambda: list(map(int, stdin.readline().split())) 

S = s_in()
Mod = 10**9 + 7

dp = [0] * 4 
dp[0] = 1

for s in S:
    if s == 'A':
        dp[1] += dp[0]
    elif s == 'B':
        dp[2] += dp[1]
    elif s == 'C':
        dp[3] += dp[2]
    else:
        temp = dp.copy()
        for i in range(4):
            dp[i] *= 3
        dp[1] += temp[0]
        dp[2] += temp[1]
        dp[3] += temp[2]
    for i in range(4):
        dp[i] %= Mod

print(dp[3])

Solution (Python):
s = input()

MOD = 10 ** 9 + 7


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

for i in range(1, len(s) + 1):
    
    dp[i][0] += dp[i - 1][0] * (3 if s[i - 1] == '?' else 1)
    dp[i][1] += dp[i - 1][1] * (3 if s[i - 1] == '?' else 1)
    dp[i][2] += dp[i - 1][2] * (3 if s[i - 1] == '?' else 1)
    dp[i][3] += dp[i - 1][3] * (3 if s[i - 1] == '?' else 1)

    
    if s[i - 1] == 'A':
        dp[i][1] += dp[i - 1][0]
    elif s[i - 1] == 'B':
        dp[i][2] += dp[i - 1][1]
    elif s[i - 1] == 'C':
        dp[i][3] += dp[i - 1][2]
    elif s[i - 1] == '?':
        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(3 + 1):
        dp[i][j] %= MOD

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

Solution (Python):


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


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


S = input()

A = [-INF for _ in range(len(S))]
C = A[:]
Q = A[:]

A[0] = 1 if S[0] == 'A' else 0
C[0] = 1 if S[0] == 'C' else 0
Q[0] = 1 if S[0] == '?' else 0

for i in range(1, len(S)):
    A[i] = A[i - 1] + 1 if S[i] == 'A' else A[i - 1]
    C[i] = C[i - 1] + 1 if S[i] == 'C' else C[i - 1]
    Q[i] = Q[i - 1] + 1 if S[i] == '?' else Q[i - 1]


pow_three = [1]
for i in range(Q[-1]):
    tmp = pow_three[-1] * 3
    tmp %= MOD
    pow_three.append(tmp)

ans = 0
for i in range(1, len(S) - 1):
    if S[i] == 'A' or S[i] == 'C':
        continue

    
    tmp = Q[i - 1] + Q[-1] - Q[i]
    if tmp < 0: tmp = 0
    ans += A[i - 1] * (C[-1] - C[i]) * pow_three[tmp]
    
    tmp = Q[i - 1] - 1 + Q[-1] - Q[i]
    if tmp < 0: tmp = 0
    ans += Q[i - 1] * (C[-1] - C[i]) * pow_three[tmp]
    
    tmp = Q[i - 1] + Q[-1] - Q[i] - 1
    if tmp < 0: tmp = 0
    ans += A[i - 1] * (Q[-1] - Q[i]) * pow_three[tmp]
    
    tmp = Q[i - 1] + Q[-1] - Q[i] - 2
    if tmp < 0: tmp = 0
    ans += Q[i - 1] * (Q[-1] - Q[i]) * pow_three[tmp]

    ans %= MOD

print(ans)

Solution (Python):


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


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




def pow_mod(a, p):
    if p == 0: return 1
    if p < 0: return 0

    if p % 2 == 0:
        half_p = p // 2
        half = pow_mod(a, half_p)
        return half * half % MOD
    else:
        return a * pow_mod(a, p - 1) % MOD


S = input()






A = [-INF for _ in range(len(S))]
C = A[:]
Q = A[:]

A[0] = 1 if S[0] == 'A' else 0
C[0] = 1 if S[0] == 'C' else 0
Q[0] = 1 if S[0] == '?' else 0

for i in range(1, len(S)):
    A[i] = A[i - 1] + 1 if S[i] == 'A' else A[i - 1]
    C[i] = C[i - 1] + 1 if S[i] == 'C' else C[i - 1]
    Q[i] = Q[i - 1] + 1 if S[i] == '?' else Q[i - 1]

pow_three = [1]
for i in range(Q[-1]):
    tmp = pow_three[-1] * 3
    tmp %= MOD
    pow_three.append(tmp)

ans = 0
for i in range(1, len(S) - 1):
    if S[i] == 'A' or S[i] == 'C':
        continue

    
    tmp = Q[i - 1] + Q[-1] - Q[i]
    if tmp < 0: tmp = 0
    ans += A[i - 1] * (C[-1] - C[i]) * pow_three[tmp]
    
    tmp = Q[i - 1] - 1 + Q[-1] - Q[i]
    if tmp < 0: tmp = 0
    ans += Q[i - 1] * (C[-1] - C[i]) * pow_three[tmp]
    
    tmp = Q[i - 1] + Q[-1] - Q[i] - 1
    if tmp < 0: tmp = 0
    ans += A[i - 1] * (Q[-1] - Q[i]) * pow_three[tmp]
    
    tmp = Q[i - 1] + Q[-1] - Q[i] - 2
    if tmp < 0: tmp = 0
    ans += Q[i - 1] * (Q[-1] - Q[i]) * pow_three[tmp]

    ans %= MOD

print(ans)

Solution (Python):
MOD=10**9+7
def func(s):
    abc="ABC"
    n = len(s)
    dp=[[0 for _ in range(3+1)] for _ in range(n+1)]
    dp[n][3]=1

    for i in range(n-1,-1,-1):
        for j in range(3,-1,-1):
            if j==3:
                if s[i]=='?':
                    dp[i][j]=(dp[i+1][j]*3)%MOD
                else:
                    dp[i][j]=dp[i+1][j]
            else:
                m1=3 if s[i]=='?' else 1
                m2=1 if s[i]=='?' or s[i]==abc[j] else 0
                dp[i][j]=((m1*dp[i+1][j])%MOD +(m2*dp[i+1][j+1])%MOD)%MOD
    return dp[0][0]
print(func(input()))

Solution (Python):

import unittest

MOD = 10**9 + 7

def func(s):
    abc = "ABC"
    n = len(s)
    dp =[[0 for _ in range(3+1)] for _ in range(n+1)]
    dp[n][3] = 1

    for i in range(n-1,-1,-1):
        for j in range(3,-1,-1):
            if j==3:
                if s[i]=="?":
                    dp[i][j] = (dp[i+1][j]*3)%MOD
                else:
                    dp[i][j] = dp[i+1][j]
            else:
                m1 = 3 if s[i]=="?" else 1
                m2 = 1 if s[i]=="?" or s[i]==abc[j] else 0
                dp[i][j] = ((m1*dp[i+1][j])%MOD + (m2*dp[i+1][j+1])%MOD)%MOD
    return dp[0][0]

class Test(unittest.TestCase):
    def test(self):
        self.assertEqual(func("A??C"), 8)
        self.assertEqual(func("ABCBC"), 3)
        self.assertEqual(func("????C?????B??????A???????"), 979596887
)

if __name__ == '__main__':
    print(func(input()))

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

Solution (Python):
s = input()

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

n = 10 ** 9 + 7

for i in reversed(range((len(s)))):
    if s[i] == '?':
        m = 3
    else:
        m = 1

    if s[i] == '?':
        m1 = 3
    else:
        m1 = 1

    if s[i] == '?' or s[i] == 'C':
        m2 = 1
    else:
        m2 = 0

    if s[i] == '?' or s[i] == 'B':
        m3 = 1
    else:
        m3 = 0

    if s[i] == '?' or s[i] == 'A':
        m4 = 1
    else:
        m4 = 0

    t_dp3 = (m * dp3) % n
    t_dp2 = (m1 * dp2 + m2 * dp3) % n
    t_dp1 = (m1 * dp1 + m3 * dp2) % n
    t_dp0 = (m1 * dp0 + m4 * dp1) % n
    dp3 = t_dp3
    dp2 = t_dp2
    dp1 = t_dp1
    dp0 = t_dp0

ans = dp0
print(ans)

Solution (Python):
s = input()

dp = [[0 for _ in range(4)] for _ in range(len(s) + 1)]
dp[len(s)][3] = 1
n = 10 ** 9 + 7

for i in reversed(range((len(s)))):
    m = 1
    m1 = 1
    m2 = 0
    m3 = 0
    m4 = 0
    if s[i] == '?':
        m = 3
        m1 = 3
        m2 = 1
        m3 = 1
        m4 = 1

    if s[i] == 'C':
        m2 = 1

    if s[i] == 'B':
        m3 = 1

    if s[i] == 'A':
        m4 = 1

    dp[i][3] = (m * dp[i+1][3]) % n
    dp[i][2] = (m1 * dp[i+1][2] + m2 * dp[i+1][3]) % n
    dp[i][1] = (m1 * dp[i+1][1] + m3 * dp[i+1][2]) % n
    dp[i][0] = (m1 * dp[i+1][0] + m4 * dp[i+1][1]) % n

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

Solution (Python):
import numpy as np

A = np.array([[1,0,0,0], [1,1,0,0], [0,0,1,0], [0,0,0,1]])
B = np.array([[1,0,0,0], [0,1,0,0], [0,1,1,0], [0,0,0,1]])
C = np.array([[1,0,0,0], [0,1,0,0], [0,0,1,0], [0,0,1,1]])
Q = A + B + C

x = np.array([1,0,0,0])

for ch in raw_input().rstrip():
    if ch == 'A':
        x = np.dot(A, x) 
    elif ch == 'B':
        x = np.dot(B, x) 
    elif ch == 'C':
        x = np.dot(C, x) 
    elif ch == '?':
        x = np.dot(Q, x) 

    x %= 1000000007

print x[3]

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

num=[ [ 0 for i in range(4) ] for j in range(N) ]		

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

ans=0

for i in range(1,N):
	if S[i]=="B" or S[i]=="?":
		a=num[i-1][0]
		c=num[N-1][2]-num[i][2]
		ql=num[i-1][3]
		qr=num[N-1][3]-num[i][3]

		
		ans+=a*pow(3,ql,mod)*c*pow(3,qr,mod)

		
		if qr>0:
			ans+=a*pow(3,ql,mod)*pow(3,(qr-1),mod )*qr

		
		if ql>0:
			ans+=pow(3,(ql-1),mod )*ql*c*pow(3,qr,mod)

		
		if ql>0 and qr>0:
			ans+=pow(3,(ql-1),mod )*ql*pow(3,(qr-1),mod )*qr

print ans%mod

Solution (Python):
def main():
	s = input()
	md = 10 ** 9 + 7

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

	d_q = {"?":3, "A":1, "B":1, "C":1}
	
	d_abc = [
	{"?":1, "A":1, "B":0, "C":0},
	{"?":1, "A":0, "B":1, "C":0},
	{"?":1, "A":0, "B":0, "C":1},
	]

	for i in reversed(range(0, len(s))):
		dp[i][3] = (dp[i + 1][3] * d_q[s[i]]) % md

	for j in reversed(range(3)):
		dp[len(s) - 1][j] = 0
		for i in reversed(range(0, len(s))):
			dp[i][j] = (dp[i + 1][j] * d_q[s[i]] + dp[i + 1][j + 1] * d_abc[j][s[i]]) % md
		
	print(dp[0][0] % md)

if __name__ == '__main__':
	main()

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

moji = [[0,0,0,0] for _ in range(n+1)]

for i in range(1,n+1):
    for k in range(4):
        moji[i][k] += moji[i-1][k]
    if s[i-1] == 'A':
        moji[i][0] += 1
        continue
    elif s[i-1] == 'B':
        moji[i][1] += 1
        continue
    elif s[i-1] == 'C':
        moji[i][2] += 1
        continue
    else:
        moji[i][3] += 1

h = s.count('?')
mt = [1]
for i in range(h+1):
    mt.append(mt[-1]*3 % mod)
mt += [1/9,1/3]
ans = 0
for i in range(n):
    al,cr,hl,hr = moji[i][0], moji[n][2]-moji[i+1][2], moji[i][3], moji[n][3]-moji[i+1][3]
    if s[i] == 'B' or s[i] == '?':
        k = (al*3 + hl) * (cr*3 + hr) * mt[hr+hl-2]
        ans += int(k) % mod
print(ans%mod)

Solution (Python):
s=input()
l=len(s)
a=[[0,0,0] for i in range(l)]
num=1
for i in range(l):
    if s[i]=='A':
        a[i][0]=a[i-1][0]+1*num
        a[i][1]=a[i-1][1]
        a[i][2]=a[i-1][2]
    elif s[i]=='B':
        a[i][0]=a[i-1][0]
        a[i][1]=a[i-1][1]+a[i-1][0]
        a[i][2]=a[i-1][2]
    elif s[i]=='C':
        a[i][0]=a[i-1][0]
        a[i][1]=a[i-1][1]
        a[i][2]=a[i-1][2]+a[i-1][1]
    elif s[i]=='?':
        
        a[i][0]=a[i-1][0]*3+1*num
        a[i][1]=a[i-1][1]*3+a[i-1][0]
        a[i][2]=a[i-1][2]*3+a[i-1][1]
        
        num=(num*3)%1000000007


    a[i][0]=a[i][0]%1000000007
    a[i][1]=a[i][1]%1000000007
    a[i][2]=a[i][2]%1000000007
print(a[-1][2])

Solution (Python):
s=input()
l=len(s)
a=[[0,0,0] for i in range(l)]
num=1
for i in range(l):
    if s[i]=='A':
        a[i][0]=a[i-1][0]+1*num
        a[i][1]=a[i-1][1]
        a[i][2]=a[i-1][2]
    if s[i]=='B':
        a[i][0]=a[i-1][0]
        a[i][1]=a[i-1][1]+a[i-1][0]
        a[i][2]=a[i-1][2]
    if s[i]=='C':
        a[i][0]=a[i-1][0]
        a[i][1]=a[i-1][1]
        a[i][2]=a[i-1][2]+a[i-1][1]
    if s[i]=='?':
        
        a[i][0]=a[i-1][0]*3+1*num
        a[i][1]=a[i-1][1]*3+a[i-1][0]
        a[i][2]=a[i-1][2]*3+a[i-1][1]
        
        num=(num*3)%1000000007


    a[i][0]=a[i][0]%1000000007
    a[i][1]=a[i][1]%1000000007
    a[i][2]=a[i][2]%1000000007
print(a[-1][2])

Solution (Python):
mod = 1000000007
s = input()
ans = [0,1,0,0,0]
for c in s:
    if c == "?":
        for i in range(4,0,-1):
            ans[i] *= 3
            ans[i] += ans[i-1]
            ans[i] %= mod
    else:
        i = "00ABC".index(c)
        ans[i] += ans[i-1]
        ans[i] %= mod
print(ans[-1])

Solution (Python):
s=input()
dp=[[-1 for _ in range(4)] for _ in range(len(s)+1)]
dp[len(s)][3]=1
for i in range(len(s),-1,-1):
    for j in range(3,-1,-1):
        if j<3:
            dp[len(s)][j]=0
        if i<len(s):
            dp[i][3]=3*dp[i+1][3] if s[i]=='?' else dp[i+1][3]
            dp[i][3]%=1e9+7
        if i<len(s) and j<3:
            m1=3 if s[i]=='?' else 1
            m2=1 if s[i]=='?' or s[i]==list('ABC')[j] else 0
            dp[i][j]=m1*dp[i+1][j]+m2*dp[i+1][j+1]
            dp[i][j]%=1e9+7
print(int(dp[0][0]))

Solution (Python):
S = input().replace("A","1").replace("B","2").replace("C","3").replace("?","0")









front = [0,0,0,0]
back = []
for i in range(4):
    back.append(S.count(str(i)))
Q = back[0]
q3s = [(3**t)%1000000007 for t in [Q-3,Q-2,Q-1,Q]]

ans = 0

for i in range(len(S)):
    num = S[i:i+1]
    back[int(num)] -= 1
    if num == "2":
        ans += front[1]*back[3]*q3s[3] 
        ans += front[1]*back[0]*q3s[2] 
        ans += front[0]*back[3]*q3s[2] 
        ans += front[0]*back[0]*q3s[1] 
    elif num == "0":
        ans += front[1]*back[3]*q3s[2] 
        ans += front[1]*back[0]*q3s[1] 
        ans += front[0]*back[3]*q3s[1] 
        ans += front[0]*back[0]*q3s[0] 
    front[int(num)] += 1
    ans = int(ans)%1000000007

print(ans)

Solution (Python):
def ary(r, c, v): return [[v for _ in range(c)] for _ in range(r)]

s = input()
ls = len(s)
dp = ary(ls + 1, 4, 0)
dp[0][0] = 1
mod = 10 ** 9 + 7

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

       
        if j > 0:
            if s[i - 1] == '?' or s[i - 1] == 'ABC'[j - 1]:
                dp[i][j] += dp[i - 1][j - 1]
        dp[i][j] %= mod
print(dp[ls][3])

Solution (Python):
from itertools import accumulate as ac
s=input()
n=len(s)
mod=int(1e9)+7

*aca,=ac([0]+[1 if i=="A" else 0 for i in s])
*acc,=ac([0]+[1 if i=="C" else 0 for i in s])
*acq,=ac([0]+[1 if i=="?" else 0 for i in s])

v=0
for i in range(1,n-1):
  if s[i]=="B" or s[i]=="?":
    a=aca[i]
    l=acq[i]
    c=acc[n]-acc[i+1]
    r=acq[n]-acq[i+1]
    v+=(a*c*pow(3,l+r,mod))
    if l+r-1>=0:
      v+=(a*r*pow(3,l+r-1,mod))+(l*c*pow(3,l+r-1,mod))
    if l+r-2>=0:
      v+=(l*r*pow(3,l+r-2,mod))
    v%=mod
print(v)

Solution (Python):
s=input()
abc="ABCD"
n=len(s)
mod=10**9+7
dp=[[0]*4 for i in range(n+1)]
dp[n][3]=1
for i in range(n-1,-1,-1):
    for j in range(4):
        if s[i]=='?' :
            if j==3:
                dp[i][j]=3*dp[i+1][j]
            else :
                dp[i][j]=3*dp[i+1][j]+dp[i+1][j+1]
        elif s[i]==abc[j]:
            if j!=3:
                dp[i][j]=dp[i+1][j]+dp[i+1][j+1]
            else :
                dp[i][j]=dp[i+1][j]
        else :
            dp[i][j]=dp[i+1][j]
        dp[i][j]%=mod
print(dp[0][0])

Solution (Python):
S = input()
MOD = 10**9+7
A = 0
C = S.count('C')
Q = 0
QMAX = S.count('?')

ans = 0

b = 3 ** (QMAX-2) % MOD
q = 3 ** (QMAX-3) % MOD

for s in S:
    if s == 'A':
        A += 1
    elif s == 'C':
        C -= 1
    elif s == 'B':
        ans = (ans + (3*A+Q) * b * (3*C+QMAX-Q))%MOD
    else:
        ans = (ans + (3*A+Q) * q * (3*C+QMAX-Q-1))%MOD
        Q += 1

print(int(ans))

Solution (Python):
M = 10**9 + 7
N, A, AB, ABC = 1, 0, 0, 0
idx = {'A': 1, 'B': 2, 'C': 3}
for c in input():
    if c == '?':
        N, A, AB, ABC = (N*3)%M, (A*3+N)%M, (AB*3+A)%M, (ABC*3+AB)%M
    elif c == 'A':
        A = (A+N)%M
    elif c == 'B':
        AB = (AB+A)%M
    else:
        ABC = (ABC+AB)%M
print(ABC)

Solution (Python):
M = 10**9 + 7
N, A, AB, ABC = 1, 0, 0, 0
idx = {'A': 1, 'B': 2, 'C': 3}
for c in input():
    if c == '?':
        ABC = (ABC * 3 + AB) % M
        AB = (AB * 3 + A) % M
        A = (A * 3 + N) % M
        N = (N * 3) % M
    elif c == 'A':
        A += N
    elif c == 'B':
        AB += A
    else:
        ABC += AB
print(ABC % M)

Solution (Python):
M = 10**9 + 7
N, A, AB, ABC = 1, 0, 0, 0
idx = {'A': 1, 'B': 2, 'C': 3}
for c in input():
    if c == '?':
        N, A, AB, ABC = (N * 3) % M, (A * 3 + N) % M, (AB * 3 + A) % M, (ABC * 3 + AB) % M
    elif c == 'A':
        A += N
    elif c == 'B':
        AB += A
    else:
        ABC += AB
print(ABC % M)

Solution (Python):
M = 10**9 + 7
N, A, AB, ABC = 1, 0, 0, 0
idx = {'A': 1, 'B': 2, 'C': 3}
for c in input():
    if c == '?':
        N, A, AB, ABC = (N * 3) % M, (A * 3 + N) % M, (AB * 3 + A) % M, (ABC * 3 + AB) % M
    else:
        dp = [N, A, AB, ABC]
        dp[idx[c]] += dp[idx[c] - 1]
        N, A, AB, ABC = dp
print(ABC % M)

Solution (Python):
M = 10**9 + 7
dp = [0] * 4
dp[0] = 1
idx = {'A': 1, 'B': 2, 'C': 3}
m = lambda x: x % M if x > M else x
for c in input():
    if c == '?':
        N, A, AB, ABC = dp
        dp = [m(N * 3), m(A * 3 + N), m(AB * 3 + A), m(ABC * 3 + AB)]
    else:
        dp[idx[c]] += dp[idx[c] - 1]
print(dp[3] % M)

Solution (Python):
M = 10**9 + 7
dp = [0] * 4
dp[0] = 1
idx = {'A': 1, 'B': 2, 'C': 3}
for c in input():
    if c == '?':
        N, A, AB, ABC = dp
        dp = [(N * 3) % M, (A * 3 + N) % M, (AB * 3 + A) % M, (ABC * 3 + AB) % M]
    else:
        dp[idx[c]] += dp[idx[c] - 1]
        dp[idx[c]] %= M
print(dp[3] % M)

Solution (Python):
M = 10**9 + 7
dp = [0] * 4
dp[0] = 1
idx = {'A': 1, 'B': 2, 'C': 3}
for c in input():
    if c == '?':
        N, A, AB, ABC = dp
        dp = [(N * 3) % M, (A * 3 + N) % M, (AB * 3 + A) % M, (ABC * 3 + AB) % M]
    else:
        dp[idx[c]] += dp[idx[c] - 1]
print(dp[3] % M)

Solution (Python):
mod = 1000000007
s = input()
n = len(s)
c = [0 for i in range(n)] 
d = [0 for i in range(n)] 
bc = [0 for i in range(n)] 
bd = [0 for i in range(n)] 
dc = [0 for i in range(n)] 
dd = [0 for i in range(n)] 


if s[-1] == "C":
    c[-1] = 1
if s[-1] == "?":
    d[-1] = 1
for i in range(-2, -n-1, -1): 
    c[i] = c[i+1]
    d[i] = d[i+1]
    bc[i] = bc[i+1]
    bd[i] = bd[i+1]
    dc[i] = dc[i+1]
    dd[i] = dd[i+1]
    if s[i] == "B":
        bc[i] += c[i+1] 
        bd[i] += d[i+1]
    elif s[i] == "C":
        c[i] += 1
    elif s[i] == "?":
        d[i] += 1
        dc[i] += c[i+1]
        dd[i] += d[i+1]


if d[0] == 0: 
    mul = [0, 0, 0, 1]
elif d[0] == 1:
    mul = [0, 0, 1, 3]
elif d[0] == 2:
    mul = [0, 1, 3, 9]
else:
    mul = [1, 1, 1, 1] 
    for i in range(d[0]-3): 
        mul[0] *= 3
        mul[0] %= mod
    for i in range(3): 
        mul[i+1] = (mul[i]*3) % mod

res = 0
for i in range(n-2): 
    if s[i] == "A":
        res += bc[i+1]*mul[3]+(dc[i+1]+bd[i+1])*mul[2]+dd[i+1]*mul[1]
    if s[i] == "?":
        res += bc[i+1]*mul[2]+(dc[i+1]+bd[i+1])*mul[1]+dd[i+1]*mul[0]
    res %= 1000000007
print(res)

Solution (Python):
mod = 1000000007
s = input()
n = len(s)
c = [0 for i in range(n)]
d = [0 for i in range(n)]
bc = [0 for i in range(n)]
bd = [0 for i in range(n)]
dc = [0 for i in range(n)]
dd = [0 for i in range(n)]


if s[-1] == "C":
    c[-1] = 1
if s[-1] == "?":
    d[-1] = 1
for i in range(-2, -n-1, -1):
    c[i] = c[i+1]
    d[i] = d[i+1]
    bc[i] = bc[i+1]
    bd[i] = bd[i+1]
    dc[i] = dc[i+1]
    dd[i] = dd[i+1]
    if s[i] == "B":
        bc[i] += c[i+1]
        bd[i] += d[i+1]
    elif s[i] == "C":
        c[i] += 1
    elif s[i] == "?":
        d[i] += 1
        dc[i] += c[i+1]
        dd[i] += d[i+1]


if d[0] == 0:
    mul = [0, 0, 0, 1]
elif d[0] == 1:
    mul = [0, 0, 1, 3]
elif d[0] == 2:
    mul = [0, 1, 3, 9]
else:
    mul = [1, 1, 1, 1]
    for i in range(d[0]-3):
        mul[0] *= 3
        mul[0] %= mod
    for i in range(3):
        mul[i+1] = (mul[i]*3) % mod

res = 0
for i in range(n-2):
    if s[i] == "A":
        res += bc[i+1]*mul[3]+(dc[i+1]+bd[i+1])*mul[2]+dd[i+1]*mul[1]
    if s[i] == "?":
        res += bc[i+1]*mul[2]+(dc[i+1]+bd[i+1])*mul[1]+dd[i+1]*mul[0]
    res %= 1000000007
print(res)

Solution (Python):
mod = 1000000007
s = input()[-1::-1] 
n = len(s)
dp = [[0]*4 for i in range(n+1)]
dp[0][0] = 1 
for i in range(n):
    for j in range(4):
        dp[i+1][j] = dp[i][j] % mod 
    if s[i] == "?":
        dp[i+1][0] += (2*dp[i][0]) % mod 
        for j in range(1, 4):
            dp[i+1][j] += (2*dp[i][j]+dp[i][j-1]) % mod
    else:
        index = "CBA".find(s[i])+1 
        dp[i+1][index] += dp[i][index-1] % mod
print(dp[n][3] % mod)

Solution (Python):
def main():
    S = input()
    mod = 10**9+7
    dp0 = 1
    dp1 = 0
    dp2 = 0
    dp3 = 0

    for s in S:
        tmp0 = dp0
        tmp1 = dp1
        tmp2 = dp2
        tmp3 = dp3

        if s == '?':
            tmp0 += 2*dp0 % mod
            tmp1 += (2*dp1 + dp0) % mod
            tmp2 += (2*dp2 + dp1) % mod
            tmp3 += (2*dp3 + dp2) % mod
        elif s == 'A':
            tmp1 += dp0 % mod
        elif s == 'B':
            tmp2 += dp1 % mod
        elif s == 'C':
            tmp3 += dp2 % mod
        dp0 = tmp0
        dp1 = tmp1
        dp2 = tmp2
        dp3 = tmp3

    print(dp3%(mod))
if __name__ == '__main__':
    main()

Solution (Python):
S = input()
l = len(S)
A,B,C,q = [0]*l,[0]*l,[0]*l,[0]*l
inf = 1000000007
for i in range(l):
    if S[i] == 'A':
        A[i] = 1
    elif S[i] == 'B':
        B[i] = 1
    elif S[i] == 'C':
        C[i] = 1
    else:
        q[i] = 1

for i in range(l-1):
    A[i+1] += A[i]
    B[i+1] += B[i]
    C[i+1] += C[i]
    q[i+1] += q[i]

ans = 0
for i in range(1,l-1):
    if S[i] == 'B':
        ans += (A[i-1]) * (C[-1]-C[i]) * pow(3,q[-1],inf)
        ans %= inf
        if q[-1] >= 1:
            ans += (q[i-1]) * (C[-1] - C[i]) * pow(3,q[-1]-1,inf)
            ans %= inf
            ans += (A[i-1]) * (q[-1] - q[i]) * pow(3,q[-1]-1,inf)
            ans %= inf
        if q[-1] >= 2:
            ans += (q[i-1]) * (q[-1] - q[i]) * pow(3,q[-1]-2,inf)
            ans %= inf

    elif S[i] == '?':
        ans += (A[i-1]) * (C[-1]-C[i]) * pow(3,q[-1]-1,inf)
        ans %= inf
        if q[-1] >= 2:
            ans += (q[i-1]) * (C[-1] - C[i]) * pow(3,q[-1]-2,inf)
            ans %= inf
            ans += (A[i-1]) * (q[-1] - q[i]) * pow(3,q[-1]-2,inf)
            ans %= inf
        if q[-1] >= 3:
            ans += (q[i-1]) * (q[-1] - q[i]) * pow(3,q[-1]-3,inf)
            ans %= inf

print(ans%inf)

Solution (Python):
S = input()
m = 10**9+7
d = "ABC".index

dp = [0]*4
dp[0] = 1

for c in S:
	if(c == '?'):
		dp = [(3*dp[0])%m, (3*dp[1]+dp[0])%m, (3*dp[2]+dp[1])%m, (3*dp[3]+dp[2])%m]
	else:
		i = d(c)
		dp[i+1] += dp[i]%m 
print(dp[3]%m)

Solution (Python):
S = input()
dp = [[0,0,0,0] for k in range(len(S)+1)]
dp[0][0] = 1
m = 1000000007

for k in range(len(S)):
    if S[k] == "?":
        dp[k+1][0] += (dp[k][0]*3)%m
        dp[k+1][1] += (dp[k][1]*3)%m
        dp[k+1][2] += (dp[k][2]*3)%m
        dp[k+1][3] += (dp[k][3]*3)%m
    else:
        dp[k+1][0] += dp[k][0]
        dp[k+1][1] += dp[k][1]
        dp[k+1][2] += dp[k][2]
        dp[k+1][3] += dp[k][3]
    if S[k] == "A" or S[k] == "?":
        dp[k+1][1] += dp[k][0]
    if S[k] == "B" or S[k] == "?":
        dp[k+1][2] += dp[k][1]
    if S[k] == "C" or S[k] == "?":
        dp[k+1][3] += dp[k][2]
    dp[k+1][0] %= m
    dp[k+1][1] %= m
    dp[k+1][2] %= m
    dp[k+1][3] %= m

print(dp[-1][3])

Solution (Python):
s = input()
q = s.count('?')
res = 0
mod = 10**9+7

""" 前処理 """

bp_A,bp_Q,ap_C,ap_Q = [0],[0],[0],[0]
for c in s:
    bp_A.append(bp_A[-1]+(c=='A'))
    bp_Q.append(bp_Q[-1]+(c=='?'))
for c in s[::-1]:
    ap_C.append(ap_C[-1]+(c=='C'))
    ap_Q.append(ap_Q[-1]+(c=='?'))

three = [3]
i = 1
while i<q:
    three.append((three[-1]**2)%mod)
    i *= 2
""" ここまで """


def pow(num):
    if num<0:
        return 0
    elif num==0:
        return 1
    else:
        ans = 1
        for i,j in enumerate(three):
            if num&(1<<i):
                ans *= j
                ans %= mod
        return ans

for pivot in range(1,len(s)-1):
    if s[pivot]=='B' or s[pivot]=='?':
        tmp = q - (s[pivot]=='?')
        s1_a,s1_q = bp_A[pivot],bp_Q[pivot]
        s2_c,s2_q = ap_C[-pivot-2],ap_Q[-pivot-2]
        res += (s1_a*s2_c)%mod * pow(tmp)
        res += (s1_a*s2_q)%mod * pow(tmp-1)
        res += (s1_q*s2_c)%mod * pow(tmp-1)
        res += (s1_q*s2_q)%mod * pow(tmp-2)

print(int(res)%mod)