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):
inf = 1000000007
 
a = 0
ab = 0
abc = 0
r = 1
 
s = input()
 
for c in s:
    if c == "A":
        a += r
    elif c == "B":
        ab += a
    elif c == "C":
        abc += ab
    else:
        abc = abc * 3 + ab
        ab = ab * 3 + a
        a = a * 3 + r
        r *= 3
        
    a %= inf
    ab %= inf
    abc %= inf
    r %= inf

print(abc)

Solution (Python):
p = [1, 0, 0, 0]
m = 1e9 + 7
def mod(x):
    return int(x % m)

for s in input():
    if s == 'A' :
        p[1] = mod(p[0] + p[1])
    if s == 'B' :
        p[2] = mod(p[1] + p[2])
    if s == 'C' :
        p[3] = mod(p[2] + p[3])
    if s == '?':
        p[3] = mod(p[2] + p[3] * 3)
        p[2] = mod(p[1] + p[2] * 3)
        p[1] = mod(p[0] + p[1] * 3)
        p[0] = mod(p[0] * 3)
        
print(int(p[3] % m))

Solution (Python):

def inpl(): return list(map(int, input().split()))
MOD = 10**9 + 7
S = input()
A, B, C = 0, 0, 0
q = 0

for i, s in enumerate(S, start=1):
    if s == "A":
        A = (A + pow(3, q, MOD))%MOD
    elif s == "B":
        B = (B + A)%MOD
    elif s == "C":
        C = (C + B)%MOD
    elif s == "?":
        A, B, C = (3*A + pow(3, q, MOD))%MOD, (3*B + A)%MOD, (3*C + B)%MOD
        q += 1

print(C)

Solution (Python):
def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y



def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

S = input()
a = 0
c = S.count("C")
ql = 0
qr = S.count("?")
ans = 0
mod = 10**9 + 7
ql3 = 1
qr3 = 1
for i in range(qr):
    qr3 *= 3
    qr3 %= mod
for s in S:
    if s == "C":
        c -= 1
    elif s == "?":
        qr -= 1
        qr3 *= modinv(3, mod)
        qr3 %= mod

    if s == "B" or s == "?":
        ans += ((ql * ql3 * modinv(3, mod) + a * ql3) % mod) * ((qr * qr3 * modinv(3, mod) + c * qr3) % mod)
        ans %= mod

    if s == "A":
        a += 1
    elif s == "?":
        ql += 1
        ql3 *= 3
        ql3 %= mod

print(ans)

Solution (Python):
s = input()

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

for c in s:
  if c=='A':
    dp[1] += dp[0]
  elif c=='B':
    dp[2] += dp[1]
  elif c=='C':
    dp[3] += dp[2]
  elif c=='?':
    dp = [(dp[0]*3)%m, (dp[0]+dp[1]*3)%m, (dp[1]+dp[2]*3)%m, (dp[2]+dp[3]*3)%m]

print(dp[3]%m)

Solution (Python):
from collections import Counter
S = input()
MOD = 10 ** 9 + 7
ans = 0
front = [0, 0, 0, 0]
back = [0, 0, 0, 0]
m = { 'A': 0, 'B': 1, 'C': 2, '?': 3 }
for c in S:
  back[m[c]] += 1

pow3 = [1]
for i in range(max(3, back[3])):
  pow3.append((pow3[-1] * 3) % MOD)

for i in range(len(S)):
  c = S[i]
  back[m[c]] -= 1
  
  if c == 'B' or c == '?':
    fbsum = front[3] + back[3]
    
    ans += front[0] * back[2] * (pow3[fbsum])
    
    ans += front[3] * back[2] * (pow3[fbsum - 1])
    
    ans += front[0] * back[3] * (pow3[fbsum - 1])
    
    ans += front[3] * back[3] * (pow3[fbsum - 2])
    ans %= MOD
  front[m[c]] += 1

print(int(ans))

Solution (Python):
S=input()
N=len(S)
mod=pow(10,9)+7
dpa=[0]*N
dpl=[0]*N
dpc=[0]*N
dpr=[0]*N
for i in range(1,N):
    if S[i-1]=='A':
        dpa[i]=dpa[i-1]+1
        dpl[i]=dpl[i-1]
    elif S[i-1]=='?':
        dpa[i]=dpa[i-1]
        dpl[i]=dpl[i-1]+1
    else:
        dpa[i]=dpa[i-1]
        dpl[i]=dpl[i-1]
for i in range(N-2,-1,-1):
    if S[i+1]=='C': 
        dpc[i]=dpc[i+1]+1
        dpr[i]=dpr[i+1]
    elif S[i+1]=='?': 
        dpc[i]=dpc[i+1]
        dpr[i]=dpr[i+1]+1
    else: 
        dpc[i]=dpc[i+1]
        dpr[i]=dpr[i+1]
ans=0 
for i in range(1,N-1):
    if S[i]=='?' or S[i]=='B':
        x=pow(3,dpl[i],mod)
        y=pow(3,max(dpl[i]-1,0),mod)
        z=pow(3,dpr[i],mod)
        w=pow(3,max(dpr[i]-1,0),mod)
        x=(x*dpa[i])%mod
        y=(y*dpl[i])%mod
        z=(z*dpc[i])%mod
        w=(w*dpr[i])%mod
        s=(x+y)%mod
        u=(z+w)%mod
        t=(s*u)%mod
        ans = (ans+t)%mod
print(ans)

Solution (Python):
s=input()

a=0
ab=0
abc=0
q=1
m=10**9+7

for i in range(len(s)):
  if s[i]=="A":
    a=(a+q)%m
  elif s[i]=="B":
    ab=(ab+a)%m
  elif s[i]=="C":
    abc=(abc+ab)%m
  else:
    abc=(abc*3+ab)%m
    ab=(ab*3+a)%m
    a=(a*3+q)%m
    q=(q*3)%m
print(abc)

Solution (Python):
import sys
sys.setrecursionlimit(int(1e9))
mod = int((1e9) + 7)

S = input()
N = len(S)

mem = [[0] * 4 for _ in range(N)]
used = [[0] * 4 for _ in range(N)]
ch = ['A', 'B', 'C']

def dfs(idx, num):
    
    if idx == N:
        return (num == 3)
    
    if used[idx][num]:
        return mem[idx][num]
    used[idx][num] = 1

    a, b = (0, 0);
    if S[idx] == '?':
        if(num < 3):
            a = dfs(idx + 1, num + 1)    
        b = 3 * dfs(idx + 1, num)
    else:
        if num < 3 and S[idx] == ch[num]:
            a = dfs(idx + 1, num + 1)
        b = dfs(idx + 1, num)
        
    res = (a + b) % mod
    mem[idx][num] = res
    return res

ans = dfs(0, 0)
print (ans)

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

dp = [[0] * 4] * (lenS + 1)
dp[0] = [1, 0, 0, 0]

for i in range(1, lenS + 1):
    if s[i - 1] == 'A':
        l = dp[i-1]
        dp[i] = [l[0], l[0] + l[1], l[2], l[3]]
    if s[i - 1] == 'B':
        l = dp[i-1]
        dp[i] = [l[0], l[1], l[1] + l[2], l[3]]
    if s[i - 1] == 'C':
        l = dp[i-1]
        dp[i] = [l[0], l[1], l[2], l[2] + l[3]]
    if s[i - 1] == '?':
        l = dp[i-1]
        dp[i] = [(l[0] * 3) % MOD, (l[0] + l[1] * 3) %MOD, (l[1] + l[2] * 3) % MOD, (l[2] + l[3] * 3) % MOD]
    
print(dp[lenS][3] % MOD)

Solution (Python):
mod = 1000000007


s = raw_input()
n_a = n_ab = n_abc = 0
p = 1

for c in s:
    if c == "A":
        n_a = (n_a + p) % mod
    elif c == "B":
        n_ab = (n_ab + n_a) % mod
    elif c == "C":
        n_abc = (n_abc + n_ab) % mod
    elif c == "?":
        n_abc = (n_abc * 3 + n_ab) % mod
        n_ab = (n_ab * 3 + n_a) % mod
        n_a = (n_a * 3 + p) % mod
        p = (p * 3) % mod

    

print n_abc % mod

Solution (Python):
import sys
sys.setrecursionlimit(int(1e9))
mod = int((1e9) + 7)

S = input()
N = len(S)

p = [1] * (N+1)
for i in range(1, N+1):
    p[i] = p[i-1]
    if S[N-i] == '?':
        p[i] = p[i] * 3 % mod
p.reverse()

mem = [[0] * 3 for _ in range(N)]
used = [[0] * 3 for _ in range(N)]
ch = ['A', 'B', 'C']



def dfs(idx, num):
    if num == 3:
        return 1 * p[idx]
    
    if idx == N:
        return 0
    
    if used[idx][num]:
        return mem[idx][num]
    used[idx][num] = 1

    a, b = (0, 0);
    if S[idx] == '?':
        a = dfs(idx + 1, num + 1)    
        b = 3 * dfs(idx + 1, num)
    else:
        if S[idx] == ch[num]:
            a = dfs(idx + 1, num + 1)
        b = dfs(idx + 1, num)
        
    res = (a + b) % mod
    mem[idx][num] = res
    return res

ans = dfs(0, 0) % mod
print (ans)

Solution (Python):
from collections import defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
AtoZ = [chr(i) for i in range(65,65+26)]
atoz = [chr(i) for i in range(97,97+26)]

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


def ex_square(n,k): 
	if k == 0:
		ans = 1
	elif k % 2 == 0:
		ans = ex_square(n, k//2) ** 2
	else:
		ans = ex_square(n,k-1) * n
	ans %= mod
	return ans

S = list(input())

aa = [0]
bb = [0]
cc = [0]
qq = [0]
Sa = Sb =Sc = Sq = 0
for s in S:
	if s == 'A':
		Sa += 1
	elif s == 'B':
		Sb += 1
	elif s == 'C':
		Sc += 1
	elif s == '?':
		Sq += 1
	aa.append(Sa)
	bb.append(Sb)
	cc.append(Sc)
	qq.append(Sq)

ans = 0
for i,s in enumerate(S):
	if s == 'B':
		SUMq = Sq
	elif s == '?':
		SUMq = Sq-1
	elif s == 'A' or s == 'C':
		continue

	Lq = qq[i]
	Rq = SUMq-Lq
	La = aa[i]
	Rc = Sc - cc[i]

	if SUMq == 0:
		ex = 1
		exx = exxx = 0
	elif SUMq == 1:
		ex = 3
		exx = 1
		exxx = 0
	else:
		exxx= ex_square(3,SUMq-2)
		exx = exxx*3%mod
		ex = exx*3%mod

	ans1 = (ex  * (La*Rc)%mod)%mod
	ans2 = (exx * (Lq*Rc)%mod)%mod
	ans3 = (exx * (La*Rq)%mod)%mod
	ans4 = (exxx * (Lq*Rq)%mod)%mod
	ans += (ans1+ans2+ans3+ans4)%mod
	ans %= mod

print(ans)

Solution (Python):
S=input()

emp=1
A=0
AB=0
ABC=0

big = 10**9+7



for a in S:
    if a == 'A':
        (emp,A,AB,ABC)=(emp,emp+A,AB,ABC)
    if a == 'B':
        (emp,A,AB,ABC)=(emp,A,A+AB,ABC)
    if a == 'C':
        (emp,A,AB,ABC)=(emp,A,AB,AB + ABC)
    if a == '?':
        (emp,A,AB,ABC)=(3*emp%big, (emp+ 3*A) %big, (A+ 3*AB)%big,(AB + 3*ABC)%big)

print(ABC%big)

Solution (Python):


S=input()

e=1
a=0
ab=0
abc=0
M=10**9+7
for i in S:
    if i == "A":
        a=(a+e)%M
    if i == "B":
        ab = (ab+a)%M
    if i == "C":
        abc=(abc+ab)%M
    if i == "?":
        abc=(3*abc+ab)%M
        ab = (3*ab+a)%M
        a=(3*a+e)%M
        e=e*3%M


print(abc)

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

def ad(x, y):
	return int((x + y) % MOD)


a = s[:2].count("A")
b = s[:2].count("B")
c = s[:2].count("C")
q = s[:2].count("?")


qq = 0
aq = 0
qb = 0
ab = 0

if s[:2] == "??":
	qq += 1
elif s[:2] == "A?":
	aq += 1
elif s[:2] == "?B":
	qb += 1
elif s[:2] == "AB":
	ab += 1

if s[2] == "A":
	a += 1
elif s[2] == "B":
	qb += q
	ab += a
	b += 1
elif s[2] == "C":
	c += 1
elif s[2] == "?":
	qq += q
	aq += a
	q += 1

three = 0
two = 0
one = 0
zero = 0

if s[:3] == "???":
	three += 1
elif s[:3] == "A??" or s[:3] == "?B?" or s[:3] == "??C":
	two += 1
elif s[:3] == "AB?" or s[:3] == "A?C" or s[:3] == "?BC":
	one += 1
elif s[:3] == "ABC":
	zero += 1




for i in range(3, len(s)):
	if s[i] == "A":
		a += 1
	elif s[i] == "B":
		qb = ad(qb, q)
		ab = ad(ab, a)
		b += 1
	elif s[i] == "C":
		two = ad(two, qq)
		one = ad(one, qb)
		one = ad(one, aq)
		zero = ad(zero, ab)
		c += 1
	elif s[i] == "?":
		three = ad(three, qq)
		two = ad(two, aq)
		two = ad(two, qb)
		one = ad(one, ab)
		qq = ad(qq, q)
		aq = ad(aq, a)
		q += 1

ans = 0
ans = ad(ans, (3 ** (q - 3)) * three)
ans = ad(ans, (3 ** (q - 2)) * two)
ans = ad(ans, (3 ** (q - 1)) * one)
ans = ad(ans, (3 ** q) * zero)

print(ans)

Solution (Python):
string = input().strip()
ac = 0
bc = 0
cc = 0
ac2 = 0
bc2 = 0
bc3 = 0
bc4 = 0
cc2 = 0
cc3 = 0
cc4 = 0
cc5 = 0
cc6 = 0
cc7 = 0
cc8 = 0
for s in string:
    if s == 'A':
        ac += 1
    elif s == 'B':
        bc += ac
        bc2 += ac2
    elif s == 'C':
        cc += bc
        cc2 += bc2
        cc3 += bc3
        cc4 += bc4
    elif s == '?':
        cc5 += bc2
        cc6 += bc3
        cc7 += bc4
        cc8 += bc

        bc3 += ac
        bc4 += ac2

        ac2 += 1



result = (cc7) + ((cc4+cc5+cc6) * 3) + ((cc2+cc3+cc8)*9) + (cc*27)

result *= pow(3, ac2-3)
print(int(result%(pow(10,9)+7)))

Solution (Python):
import numpy as np
s=input()
A=np.array([0,0,0,0])
B=np.array([0,0,0,0])
C=np.array([0,0,0,0])
t=0
for c in s:
	if c=="A":
		A[0]+=1
	if c=="B":
		B+=A
	if c=='C':
		C+=B
	if c=='?':
		C+=np.roll(B,1)
		B[1]+=A[0]
		B[2]+=A[1]
		A[1]+=1
		t+=1
ans=0
for i in range(4):
	ans+=pow(3,t-i)*C[i]
print(int(ans%1000000007))

Solution (Python):
import numpy as np
s=input()
A=np.array([0,0,0,0])
B=np.array([0,0,0,0])
C=np.array([0,0,0,0])
t=0
for c in s:
	if c=="A":
		A[0]+=1
	if c=="B":
		B+=A
	if c=='C':
		C+=B
	if c=='?':
		C[1]+=B[0]
		C[2]+=B[1]
		C[3]+=B[2]
		B[1]+=A[0]
		B[2]+=A[1]
		A[1]+=1
		t+=1
ans=0
for i in range(4):
	ans+=pow(3,t-i)*C[i]
print(int(ans%1000000007))

Solution (Python):
import numpy as np
s=input()
A=np.array([0,0,0,0])
B=np.array([0,0,0,0])
C=np.array([0,0,0,0])
t=0
for c in s:
	if c=="A":
		A[0]+=1
	if c=="B":
		B+=A
	if c=='C':
		C+=B
	if c=='?':
		C[1]+=B[0]
		C[2]+=B[1]
		C[3]+=B[2]
		B[1]+=A[0]
		B[2]+=A[1]
		A[1]+=1
		t+=1
ans=0
for i in range(4):
	ans+=pow(3,t-i)*C[i]
print(int(ans%1000000007))

Solution (Python):
import numpy as np
s=input()
wayA=np.array([0,0,0,0])
wayB=np.array([0,0,0,0])
wayC=np.array([0,0,0,0])
hatena=0
for c in s:
	if c=="A":
		wayA[0]+=1
	if c=="B":
		wayB+=wayA
	if c=='C':
		wayC+=wayB
	if c=='?':
		wayC[1]+=wayB[0]
		wayC[2]+=wayB[1]
		wayC[3]+=wayB[2]
		wayB[1]+=wayA[0]
		wayB[2]+=wayA[1]
		wayA[1]+=1
		hatena+=1
ans=0
for i in range(4):
	ans+=pow(3,hatena-i)*wayC[i]
print(int(ans%1000000007))

Solution (Python):
import numpy as np
s=input()
n=len(s)
MOD=1000000007
wayA=np.array([0,0,0,0])
wayB=np.array([0,0,0,0])
wayC=np.array([0,0,0,0])
hatena=0
for c in s:
	if c=="A":
		wayA[0]+=1
	if c=="B":
		wayB+=wayA
	if c=='C':
		wayC+=wayB
	if c=='?':
		wayC[1]=wayC[1]+wayB[0]
		wayC[2]=wayC[2]+wayB[1]
		wayC[3]=wayC[3]+wayB[2]
		wayB[1]=wayB[1]+wayA[0]
		wayB[2]=wayB[2]+wayA[1]
		wayA[1]=wayA[1]+1
		hatena+=1
ans=0
for i in range(0,4):
	ans+=pow(3,hatena-i)*wayC[i]
print(int(ans%MOD))

Solution (Python):
mod=1000000007
a=0
ab=0
abc=0
Q=1
S=input()
for i in S:
    if i=="A":
        a+=Q
    elif i=="B":
        ab+=a
    elif i=="C":
        abc+=ab
    else:
        abc=abc*3+ab
        ab=ab*3+a
        a=a*3+Q
        Q=Q*3
    a=a%mod
    ab=ab%mod
    abc=abc%mod
    Q=Q%mod
print(abc)

Solution (Python):
import numpy as np
s=input()
n=len(s)
MOD=1000000007
wayA=np.array([0,0,0,0])
wayB=np.array([0,0,0,0])
wayC=np.array([0,0,0,0])
hatena=0
for c in s:
	if c=="A":
		wayA[0]+=1
	if c=="B":
		wayB+=wayA
	if c=='C':
		wayC+=wayB
	if c=='?':
		wayC[1]=wayC[1]+wayB[0]
		wayC[2]=wayC[2]+wayB[1]
		wayC[3]=wayC[3]+wayB[2]
		wayB[1]=wayB[1]+wayA[0]
		wayB[2]=wayB[2]+wayA[1]
		wayA[1]=wayA[1]+1
		hatena+=1
ans=0
for i in range(0,4):
	ans=ans+pow(3,hatena-i)*wayC[i]
	ans=ans%MOD
print(int(ans))

Solution (Python):
import numpy as np
s=input()
n=len(s)
MOD=1000000007
wayA=np.array([0,0,0,0])
wayB=np.array([0,0,0,0])
wayC=np.array([0,0,0,0])
MOD2=np.array([MOD,MOD,MOD,MOD])
hatena=0
for c in s:
	if c=="A":
		wayA[0]+=1
	if c=="B":
		wayB+=wayA
	if c=='C':
		wayC+=wayB
	if c=='?':
		wayC[1]=wayC[1]+wayB[0]
		wayC[2]=wayC[2]+wayB[1]
		wayC[3]=wayC[3]+wayB[2]
		wayB[1]=wayB[1]+wayA[0]
		wayB[2]=wayB[2]+wayA[1]
		wayA[1]=wayA[1]+1
		hatena+=1
	wayA%=MOD2
	wayB%=MOD2
	wayC%=MOD2
ans=0
for i in range(0,4):
	ans=ans+pow(3,hatena-i)*wayC[i]
	ans=ans%MOD
print(int(ans))

Solution (Python):
import numpy as np
s=input()
n=len(s)
MOD=1000000007
wayA=np.array([0,0,0,0],dtype=np.int64)
wayB=np.array([0,0,0,0],dtype=np.int64)
wayC=np.array([0,0,0,0],dtype=np.int64)
MOD2=np.array([MOD,MOD,MOD,MOD],dtype=np.int32)
hatena=0
for c in s:
	if c=="A":
		wayA[0]+=1
	if c=="B":
		wayB+=wayA
	if c=='C':
		wayC+=wayB
	if c=='?':
		wayC[1]=wayC[1]+wayB[0]
		wayC[2]=wayC[2]+wayB[1]
		wayC[3]=wayC[3]+wayB[2]
		wayB[1]=wayB[1]+wayA[0]
		wayB[2]=wayB[2]+wayA[1]
		wayA[1]=wayA[1]+1
		hatena+=1
	wayA%=MOD2
	wayB%=MOD2
	wayC%=MOD2
ans=0
for i in range(0,4):
	ans=ans+pow(3,hatena-i)*wayC[i]
	ans=ans%MOD
print(int(ans))

Solution (Python):
import numpy as np
s=input()
n=len(s)
MOD=1000000007
wayA=np.array([0,0,0,0],dtype=np.int64)
wayB=np.array([0,0,0,0],dtype=np.int64)
wayC=np.array([0,0,0,0],dtype=np.int64)
MOD2=np.array([MOD,MOD,MOD,MOD],dtype=np.int32)
hatena=0
for c in s:
	if c=="A":
		wayA[0]+=1
	if c=="B":
		wayB+=wayA
	if c=='C':
		wayC+=wayB
	if c=='?':
		wayC[1]=wayC[1]+wayB[0]
		wayC[2]=wayC[2]+wayB[1]
		wayC[3]=wayC[3]+wayB[2]
		wayB[1]=wayB[1]+wayA[0]
		wayB[2]=wayB[2]+wayA[1]
		wayA[1]=wayA[1]+1
		hatena+=1
	wayA%=MOD2
	wayB%=MOD2
	wayC%=MOD2
ans=0
for i in range(0,4):
	p3=1
	for k in range(0,hatena-i):
		p3=p3*3
		p3=p3%MOD
	ans=ans+p3*wayC[i]
	ans=ans%MOD
print(int(ans))

Solution (Python):
import numpy as np
 
s=input()
n=len(s)
MOD=1000000007
wayA=np.array([0,0,0,0],dtype=np.int64)
wayB=np.array([0,0,0,0],dtype=np.int64)
wayC=np.array([0,0,0,0],dtype=np.int64)
MOD2=np.array([MOD,MOD,MOD,MOD],dtype=np.int32)
hatena=0
for c in s:
	if c=="A":
		wayA[0]+=1
	if c=="B":
		wayB+=wayA
	if c=='C':
		wayC+=wayB
	if c=='?':
		wayC[1]=wayC[1]+wayB[0]
		wayC[2]=wayC[2]+wayB[1]
		wayC[3]=wayC[3]+wayB[2]
		wayB[1]=wayB[1]+wayA[0]
		wayB[2]=wayB[2]+wayA[1]
		wayA[1]=wayA[1]+1
		hatena+=1
	wayA%=MOD2
	wayB%=MOD2
	wayC%=MOD2
ans=0
for i in range(0,4):
	p3=1
	if wayC[i]<=0:
		continue
	for k in range(0,hatena-i):
		p3=p3*3
		p3=p3%MOD
	ans=ans+p3*wayC[i]
	ans=ans%MOD
print(int(ans))

Solution (Python):

def solve(s, MOD=int(1e9 + 7)):
    k = 1
    a = 0
    ab = 0
    abc = 0
    for c in s:
        if c == 'A':
            a += k
        elif c == 'B':
            ab += a
        elif c == 'C':
            abc += ab
        else:
            abc = 3 * abc + ab
            ab = 3 * ab + a
            a = 3 * a + k
            k *= 3
        k, a, ab, abc = map(lambda x: x % MOD, [ k, a, ab, abc ])
    return abc % MOD
print(solve(input()))

Solution (Python):

import numpy as np
 
s=input()
n=len(s)
wayA=np.array([0,0,0,0],dtype=np.int64)
wayB=np.array([0,0,0,0],dtype=np.int64)
wayC=np.array([0,0,0,0],dtype=np.int64)
hatena=0
MOD=1000000007
for c in s:
	if c=="A":
		wayA[0]=wayA[0]+1
	if c=="B":
		wayB+=wayA;
	if c=='C':
		wayC=wayC+wayB
	if c=='?':
		wayC[1]=wayC[1]+wayB[0]
		wayC[2]=wayC[2]+wayB[1]
		wayC[3]=wayC[3]+wayB[2]
		wayB[1]=wayB[1]+wayA[0]
		wayB[2]=wayB[2]+wayA[1]
		wayA[1]=wayA[1]+1
		hatena=hatena+1
	for z in range(0,4):
		wayA[z]=wayA[z]%MOD
		wayB[z]=wayB[z]%MOD
		wayC[z]=wayC[z]%MOD
ans=0
for i in range(0,4):
	p3=1
	if wayC[i]<=0:
		continue
	for k in range(0,hatena-i):
		p3=p3*3
		p3=p3%MOD
	ans=ans+p3*wayC[i]
	ans=ans%MOD
print(ans)

Solution (Python):

s=input()
n=len(s)
wayA=[0,0,0,0]
wayB=[0,0,0,0]
wayC=[0,0,0,0]
hatena=0
MOD=1000000007
for c in s:
	if c=="A":
		wayA[0]=wayA[0]+1
	if c=="B":
		wayB[0]=wayB[0]+wayA[0]
		wayB[1]=wayB[1]+wayA[1]
	if c=='C':
		wayC[0]=wayC[0]+wayB[0]
		wayC[1]=wayC[1]+wayB[1]
		wayC[2]=wayC[2]+wayB[2]
	if c=='?':
		wayC[1]=wayC[1]+wayB[0]
		wayC[2]=wayC[2]+wayB[1]
		wayC[3]=wayC[3]+wayB[2]
		wayB[1]=wayB[1]+wayA[0]
		wayB[2]=wayB[2]+wayA[1]
		wayA[1]=wayA[1]+1
		hatena=hatena+1
	for z in range(0,4):
		wayA[z]=wayA[z]%MOD
		wayB[z]=wayB[z]%MOD
		wayC[z]=wayC[z]%MOD
ans=0
for i in range(0,4):
	p3=1
	for k in range(0,hatena-i):
		p3=p3*3
		p3=p3%MOD
	ans=ans+p3*wayC[i]
ans = ans%1000000007
print(int(ans))

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

make = [[0 for i in range(4)] for j in range(n + 1)]

make[n][3] = 1

mod = 10**9 + 7

for i in range(n - 1, -1, -1):
	if s[i] == '?':
		make[i][0] += make[i + 1][0] * 3 + make[i + 1][1]
		make[i][1] += make[i + 1][1] * 3 + make[i + 1][2]
		make[i][2] += make[i + 1][2] * 3 + make[i + 1][3]
		make[i][3] += make[i + 1][3] * 3
	elif s[i] == 'A':
		make[i][0] += make[i + 1][0] + make[i + 1][1]
		make[i][1] += make[i + 1][1]
		make[i][2] += make[i + 1][2]
		make[i][3] += make[i + 1][3]
	elif s[i] == 'B':
		make[i][0] += make[i + 1][0]
		make[i][1] += make[i + 1][1] + make[i + 1][2]
		make[i][2] += make[i + 1][2]
		make[i][3] += make[i + 1][3]
	elif s[i] == 'C':
		make[i][0] += make[i + 1][0]
		make[i][1] += make[i + 1][1]
		make[i][2] += make[i + 1][2] + make[i + 1][3]
		make[i][3] += make[i + 1][3]

	make[i][0] %= mod
	make[i][1] %= mod
	make[i][2] %= mod
	make[i][3] %= mod

print(make[0][0])

Solution (Python):

import numpy as np

s=input()
n=len(s)
wayA=np.array([0,0,0,0],dtype=np.int64)
wayB=np.array([0,0,0,0],dtype=np.int64)
wayC=np.array([0,0,0,0],dtype=np.int64)
hatena=0
MOD=1000000007
for c in s:
	if c=="A":
		wayA[0]=wayA[0]+1
	if c=="B":
		wayB+=wayA;
	if c=='C':
		wayC=wayC+wayB
	if c=='?':
		wayC[1]=wayC[1]+wayB[0]
		wayC[2]=wayC[2]+wayB[1]
		wayC[3]=wayC[3]+wayB[2]
		wayB[1]=wayB[1]+wayA[0]
		wayB[2]=wayB[2]+wayA[1]
		wayA[1]=wayA[1]+1
		hatena=hatena+1
	for z in range(0,4):
		wayA[z]=wayA[z]%MOD
		wayB[z]=wayB[z]%MOD
		wayC[z]=wayC[z]%MOD
ans=0
for i in range(0,4):
	p3=1
	if wayC[i]<=0:
		continue
	for k in range(0,hatena-i):
		p3=p3*3
		p3=p3%MOD
	ans=ans+p3*wayC[i]
	ans=ans%MOD
print(int(ans))

Solution (Python):
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

mod = 1000000007

s = ns().rstrip()

nums = [0]*4
nums[0] = 1
for c in s:
    if c == 'A':
        nums[1] += nums[0]
        nums[1] %= mod
    elif c == "B":
        nums[2] += nums[1]
        nums[2] %= mod
    elif c == "C":
        nums[3] += nums[2]
        nums[3] %= mod
    else:
        nums[3] = nums[3]*3+nums[2]
        nums[2] = nums[2]*3+nums[1]
        nums[1] = nums[1]*3+nums[0]
        nums[0] = nums[0]*3
        for k in range(4):
            nums[k] %= mod
print(nums[3])

Solution (Python):
S = raw_input()
M = 10**9+7

def count(W):
  N = len(S)
  T1 = [0]*N
  for i in range(N):
    T1[i] = (0 if i==0 else T1[i-1]) + int(S[i]==W[0])
  T2 = [0]*N
  for i in range(N)[::-1]:
    T2[i] = (0 if i==N-1 else T2[i+1]) + int(S[i]==W[2])
  ans = 0
  for i in range(1,N-1):
    if S[i]==W[1]:
      ans += T1[i-1]*T2[i+1]
      ans %= M
  return ans

Q = S.count("?")
print (
  count("ABC")*pow(3,Q,M) +
  count("AB?")*pow(3,max(Q-1,0),M) +
  count("A?C")*pow(3,max(Q-1,0),M) +
  count("A??")*pow(3,max(Q-2,0),M) +
  count("?BC")*pow(3,max(Q-1,0),M) +
  count("?B?")*pow(3,max(Q-2,0),M) +
  count("??C")*pow(3,max(Q-2,0),M) +
  count("???")*pow(3,max(Q-3,0),M))%M

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

d = "ABC".index
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 = d(c)
        s[i+1] += s[i] % MOD
print(s[3] % MOD)

Solution (Python):
def main():
    s = input()
    pa = [0]
    pb = [0]
    pc = [0]
    pd = [0]

    n = len(s)
    for i in range(n):
        pa.append(pa[-1])
        pb.append(pb[-1])
        pc.append(pc[-1])
        pd.append(pd[-1])

        if s[i] == 'A':
            pa[-1] += 1
        elif s[i] == 'B':
            pb[-1] += 1
        elif s[i] == 'C':
            pc[-1] += 1
        elif s[i] == '?':
            pd[-1] += 1

    totq = pd[n]

    MOD = 1000000007
    ans = 0
    for i in range(1, n + 1):
        if s[i - 1] == 'A' or s[i - 1] == 'C':
            continue

        if s[i - 1] == 'B':
            buf = 0
        else:
            buf = 1

        
        a_bef = pa[i - 1]
        d_bef = pd[i - 1]
        c_aft = pc[n] - pc[i]
        d_aft = pd[n] - pd[i]

        if a_bef * c_aft > 0:
            ans += (a_bef * c_aft % MOD) * pow(3, totq - buf, MOD) % MOD
            ans %= MOD

        if d_bef * c_aft > 0:
            ans += (d_bef * c_aft % MOD) * pow(3, totq - buf - 1, MOD) % MOD
            ans %= MOD

        if a_bef * d_aft > 0:
            ans += (a_bef * d_aft % MOD) * pow(3, totq - buf - 1, MOD) % MOD
            ans %= MOD
        
        if d_bef * d_aft > 0:
            ans += (d_bef * d_aft % MOD) * pow(3, totq - buf - 2, MOD) % MOD
            ans %= MOD

    print(ans)

main()