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 getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))

s = input()
n = len(s)
xc, yc, zc, wc = 1,0,0,0

for c in s:
    if c == "?":
        x = xc*3
        y = xc + yc * 3
        z = yc + zc * 3
        w = zc + wc * 3

    elif c == "A":
        x = xc
        y= yc + xc
        z = zc
        w = wc

    elif c == "B":
        x = xc
        y = yc
        z = zc + yc
        w = wc

    else:
        x = xc
        y = yc
        z = zc
        w = wc + zc

    xc,yc,zc,wc = [cur%1000000007 for cur in [x,y,z,w]]

print(wc)

Solution (Python):
s = list(input())
law = 10 ** 9 + 7
l = len(s)
dp = [[0 for _ in range(4)] for _ in range(l+1)]
dp[0][0] = 1
for i in range(l):
    dp[i+1][0] = (1 + 2 * int(s[i] == '?')) * dp[i][0]
    dp[i+1][1] = int(s[i] in ('A', '?')) * dp[i][0] + dp[i][1] * (1 + 2 * int(s[i] == '?'))
    dp[i+1][2] = int(s[i] in ('B', '?')) * dp[i][1] + dp[i][2] * (1 + 2 * int(s[i] == '?'))
    dp[i+1][3] = int(s[i] in ('C', '?')) * dp[i][2] + dp[i][3] * (1 + 2 * int(s[i] == '?'))
    dp[i+1][0] %= law
    dp[i+1][1] %= law
    dp[i+1][2] %= law
    dp[i+1][3] %= law
print(dp[l][3])

Solution (Python):
s = input();n = len(s)
dp = [[0 for i in range(4)] for j in range(len(s)+1)]
dp[0][0] = 1;string = ["A","B","C"];num = 10**9+7
for i in range(n):
    for j in range(4):
        m = 0;b = 1
        if '?' == s[i]:b = 3
        if j == 0:
            if '?' == s[i]:dp[i+1][j] = (dp[i][j] * 3)%num
            else:dp[i+1][j] = (dp[i][j])%num
            continue
        if s[i] == string[j-1]or s[i] == '?':m = 1
        dp[i+1][j] = (m*dp[i][j-1] + b*dp[i][j])%num
print(dp[-1][3])

Solution (Python):
import numpy as np
mod = 10**9 + 7

s = input()[::-1]

n = len(s)
DP = [[0]*3 for i in range(n+1)]

power_three = 1

for i, c in enumerate(list(s)):
    for j in range(3):
        if c == "?":
            DP[i+1][j] = 3*DP[i][j] % mod
        else:
            DP[i+1][j] = DP[i][j] % mod
    if c == "C" or c == "?":
        DP[i+1][0] = (DP[i+1][0] + power_three) % mod
    if c == "B" or c == "?":
        DP[i+1][1] = (DP[i+1][1] + DP[i][0]) % mod
    if c == "A" or c == "?":
        DP[i+1][2] = (DP[i+1][2] + DP[i][1]) % mod
    if c == "?":
        power_three = 3*power_three % mod
print(DP[n][2] % mod)

Solution (Python):
str_num, a,b,c = 1, 0, 0, 0
for i in input():
    if i == 'A':
        a += str_num
    elif i == 'B':
        b += a
    elif i == 'C':
        c += b
    else:
        str_num, a,b,c = (3*str_num) % (10**9+7), (3*a+str_num) % (10**9+7), (a+3*b) % (10**9+7), (b+3*c) % (10**9+7)
print(c % (10**9+7))

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

Solution (Python):
from functools import reduce
M = 10**9 + 7
S = input()
ans = reduce(
    lambda t, s:
        (t[0], t[1] + t[0], t[2], t[3]) if s == 'A' else
        (t[0], t[1], t[1] + t[2], t[3]) if s == 'B' else
        (t[0], t[1], t[2], t[2] + t[3]) if s == 'C' else
        ((3 * t[0]) % M, (3 * t[1] + t[0]) % M, (3 * t[2] + t[1]) % M, (3 * t[3] + t[2]) % M),
    S,
    (1, 0, 0, 0)
)[3] % M
print(ans)

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

Solution (Python):



MOD = int(1e9+7)
S = input()

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

dp[0][0] = 1
for e,s in enumerate(S,1):

    dp[e][0] = dp[e-1][0] * (3 if s == "?" else 1)

    if s == "A" or s == "?":
        dp[e][1] += dp[e-1][0] 
    dp[e][1] += dp[e-1][1] * (3 if s == "?" else 1) 

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

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


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



    
    


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

Solution (Python):


S = input()
from collections import defaultdict
from bisect import bisect_left, bisect_right
a = []
b = []
c = []



q = []

for e,s in enumerate(S):
    if s == "A" :
        a.append(e)
    if s == "B" :
        b.append(e)
    if s == "C" :
        c.append(e)
    if s == "?":
        q.append(e)

ans = 0
MOD = int(1e9+7)

for eb in b:
    range_a = bisect_right(a, eb-1)
    
            
    range_c = len(c) - bisect_left(c, eb+1)
    
    range_cq = len(q) - bisect_left(q, eb+1)
    range_aq = bisect_right(q, eb-1)

    ans += range_a*range_c * pow(3, len(q), MOD) % MOD
    ans %= MOD
    if len(q)>=1:
        ans += range_a*range_cq * pow(3, len(q)-1, MOD)
        ans += range_aq*range_c * pow(3, len(q)-1, MOD)
        ans %= MOD
    if len(q)>=2:
        ans += range_aq*range_cq * pow(3, len(q)-2, MOD)
        ans %= MOD
for eq in q:
    
            
    range_a = bisect_right(a, eq-1)
    range_c = len(c) - bisect_left(c, eq+1)
    range_cq = len(q) - bisect_left(q, eq+1)
    range_aq = bisect_right(q, eq-1)

    ans += range_a*range_c * pow(3, len(q)-1, MOD)
    ans %= MOD
    if len(q) >= 2:
        ans += range_a*range_cq * pow(3, len(q)-2, MOD)
        ans += range_aq*range_c * pow(3, len(q)-2, MOD)
        ans %= MOD
    if len(q) >= 3:
        ans += range_aq*range_cq * pow(3, len(q)-3, MOD)
        ans %= MOD
    
print(ans % MOD)

Solution (Python):
S = input()

a=0
ab=0
ans=0
n=1
m=10**9+7
for s in S:
    if s=='A':
        a+=n
    elif s=='B':
        ab+=a
    elif s=='C':
        ans+=ab
    else:
        ans+=2*ans+ab
        ab+=2*ab+a
        a+=2*a+n
        n*=3
        n%=m
    ans%=m
    ab%=m
    a%=m
print(ans)

Solution (Python):
s=input()
a=0
ab=0
abc=0
total=1
mod=10**9+7
for i in range(len(s)):
    if s[i]=='A':
        a+=total
    elif s[i]=='B':
        ab+=a
    elif s[i]=='C':
        abc+=ab
    else:
        abc=3*abc+ab
        ab=3*ab+a
        a=3*a+total
        total*=3
    a%=mod
    ab%=mod
    abc%=mod
    total%=mod
print(abc)

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



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

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


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

Solution (Python):
S = input()

a = 0
ab = 0
abc = 0
all = 1
mod = 10**9 + 7

for i in range(len(S)):
    if S[i] == 'A':
        a += all
    elif S[i] == 'B':
        ab += a
    elif S[i] == 'C':
        abc += ab
    elif S[i] == '?':
        abc = 3*abc + ab
        ab = 3*ab + a
        a = 3*a + all
        all *= 3

    a %= mod
    ab %= mod
    abc %= mod
    all %= mod

print(abc)

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

MOD = 10 ** 9 + 7

S = input()

a, ab, abc = [0] * 3
c = 1

for s in S:
    if s == "A":
        a = (a + c) % MOD
    elif s == "B":
        ab = (ab + a) % MOD
    elif s == "C":
        abc = (abc + ab) % MOD
    elif s == "?":
        abc = (3 * abc + ab) % MOD
        ab = (3 * ab + a) % MOD
        a = (3 * a + c) % MOD
        c = (3 * c) % MOD
print(abc % MOD)

Solution (Python):


def main():
    S = input()

    N = len(S)

    AC = [0] * N
    CC = [0] * N
    QCA = [0] * N
    QCD = [0] * N

    a = 0
    q = 0
    for i in range(N):
        if S[i] == 'A':
            a += 1
        elif S[i] == '?':
            q += 1
        AC[i] = a
        QCA[i] = q

    c = 0
    q = 0
    for i in range(N - 1, -1, -1):
        if S[i] == 'C':
            c += 1
        elif S[i] == '?':
            q += 1
        CC[i] = c
        QCD[i] = q

    qc = q

    t = 0
    tt = 0
    m = 10 ** 9 + 7

    for i in range(1, N - 1):
        if S[i] == 'B':
            t += AC[i - 1] * CC[i + 1]
            t %= m

    if 1 <= qc:
        t *= 3
        t %= m
        for i in range(1, N - 1):
            if S[i] == 'B':
                t += QCA[i - 1] * CC[i + 1]
                t %= m
                t += AC[i - 1] * QCD[i + 1]
                t %= m
            elif S[i] == '?':
                t += AC[i - 1] * CC[i + 1]
                t %= m

    if 2 <= qc:
        t *= 3
        t %= m
        for i in range(1, N - 1):
            if S[i] == 'B':
                t += QCA[i - 1] * QCD[i + 1]
                t %= m
            elif S[i] == '?':
                t += QCA[i - 1] * CC[i + 1]
                t %= m
                t += AC[i - 1] * QCD[i + 1]
                t %= m

    if 3 <= qc:
        t *= 3
        t %= m
        for i in range(1, N - 1):
            if S[i] == '?':
                t += QCA[i - 1] * QCD[i + 1]
                t %= m

    for i in range(3, qc):
        t *= 3
        t %= m


    print(t)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
S = input().strip()
mod = 10**9+7
a = 0
ab = 0
ans = 0
q = 1
for c in S:
    if c == 'A':
        a += q
    elif c == 'B':
        ab += a
    elif c == 'C':
        ans += ab
    elif c == '?':
        a, ab, ans, q = a*3+q, ab*3+a, ans*3+ab, q*3
    a %= mod
    ab %= mod
    ans %= mod
    q %= mod
print(ans % mod)

Solution (Python):
import sys
input = sys.stdin.readline
S = input().strip()
mod = 10**9+7
a = 0
ab = 0
ans = 0
q = 1
for c in S:
    if c == 'A':
        a += q
    elif c == 'B':
        ab += a
    elif c == 'C':
        ans += ab
    elif c == '?':
        a, ab, ans, q = a*3+q, ab*3+a, ans*3+ab, q*3
    a %= mod
    ab %= mod
    ans %= mod
    q %= mod
print(ans % mod)

Solution (Python):
def func(s):
    alpha = [0, 0, 0]
    ques = 0
    nowQues = 1
    ab = 0  
    count = 0
    for _s in s:
        if _s == "?":
            count *= 3  
            count += ab  
            ab *= 3
            
            if ques > 0:
                ab += alpha[0] * nowQues*3  
            else:
                ab += alpha[0]
            
            if ques > 0:
                ab += ques * nowQues  
            ques += 1
            if ques > 1:
                nowQues *= 3
        elif _s == "A":
            alpha[0] += 1
        elif _s == "B":
            
            if ques > 0:
                ab += alpha[0] * nowQues*3  
            else:
                ab += alpha[0]
            if ques > 0:
                ab += ques * nowQues  
            alpha[1] += 1
        elif _s == "C":
            
            count += ab
            alpha[2] += 1
        count %= 10 ** 9 + 7
        ab %= 10 ** 9 + 7
        nowQues %= 10 ** 9 + 7
        
    return count % (10 ** 9 + 7)


"""
print(func("A??C") == 8)
print(func("ABCBC") == 3)
print(func("????C?????B??????A???????") == 979596887)
def listToString(_list, split=""):
    maped_list = map(str, _list)  
    mojiretu = split.join(maped_list)
    return mojiretu
print(func(listToString(["?" for _ in range(10 ** 5)])))
print("finish")
"""
print(func(input()))

Solution (Python):
def index(c):return ord(c)-ord('A')+1
s=' '+input()
m=10**9+7
dp=[[0]*4 for _ in range(len(s))]
dp[0][0]=1
for i in range(1,len(s)):
    for j in range(4):
        dp[i][j]=dp[i-1][j]
    if s[i]=='?':
        dp[i][0]=dp[i-1][0]*3%m
        for j in range(1,4):
            dp[i][j]=(dp[i-1][j-1]+dp[i-1][j]*3)%m
    else:
        k=index(s[i])
        dp[i][k]=(dp[i-1][k-1]+dp[i-1][k])%m
print(dp[-1][3])

Solution (Python):
def index(c):return ord(c)-ord('A')+1
s=' '+input()
m=10**9+7
dp=[[0]*4 for _ in range(len(s))]
dp[0][0]=1
for i in range(1,len(s)):
    for j in range(4):
        dp[i][j]=dp[i-1][j]
    if s[i]=='?':
        dp[i][0]=dp[i-1][0]*3%m
        for j in range(1,4):
            dp[i][j]=(dp[i-1][j-1]+dp[i-1][j]*3)%m
    else:
        k=index(s[i])
        dp[i][k]=(dp[i-1][k-1]+dp[i-1][k])%m
print(dp[-1][3])

Solution (Python):
mod = 10 ** 9 + 7
S = input()
abc = 0
bc = 0
c = 0
q = 0

for i in S[::-1]:
    if i == 'C':
        c = (pow(3, q, mod) + c) % mod
    if i == 'B':
        bc = (bc + c) % mod
    if i == 'A':
        abc = (abc + bc) % mod
    if i == '?':
        abc = (abc * 3 + bc) % mod
        bc = (bc * 3 + c) % mod
        c = (c * 3 + pow(3, q, mod)) % mod
        q += 1
        
print(abc)

Solution (Python):
S = input()
mod = 10 ** 9 + 7
abc = 0
bc = 0
c = 0
q = 0

for i in S[::-1]:
    if i == 'A':
        abc = (bc + abc) % mod
        
    if i == 'B':
        bc = (c + bc) % mod
        
    if i == 'C':
        c = (pow(3, q, mod) + c) % mod
        
    if i == '?':
        abc = (bc + abc * 3) % mod
        bc = (c + bc * 3) % mod
        c = (pow(3, q, mod) + c * 3) % mod
        q += 1
        
print(abc)

Solution (Python):
S = input()
mod = 10 ** 9 + 7
abc = 0
bc = 0
c = 0
q = 0

for i in S[::-1]:
    if i == 'A':
        abc = (bc + abc) % mod
    if i == 'B':
        bc = (c + bc) % mod
    if i == 'C':
        c = (pow(3, q, mod) + c ) % mod
    if i == '?':
        abc = (abc * 3 + bc) % mod
        bc = (bc * 3 + c) % mod
        c = (pow(3, q, mod) + c * 3) % mod
        q += 1
        
print(int(abc))

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

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

Solution (Python):
S = input()
mod = 10**9 + 7
N = len(S)
cA = 0
cAB = 0
cABC = 0
total = 1
for i in range(N):
    if S[i] == 'A':
        cA += total
    elif S[i] == 'B':
        cAB += cA
    elif S[i] == 'C':
        cABC += cAB
    else:
        cABC *= 3
        cABC += cAB
        cAB *= 3
        cAB += cA
        cA *= 3
        cA += total
        total *= 3
    cABC %= mod
    cAB %= mod
    cA %= mod
    total %= mod
print(cABC)

Solution (Python):
S = input()
mod = 10**9 + 7
N = len(S)
cA = 0
cAB = 0
cABC = 0
all = 1
for i in range(N):
    if S[i] == 'A':
        cA += all
    elif S[i] == 'B':
        cAB += cA
    elif S[i] == 'C':
        cABC += cAB
    else:
        cABC *= 3
        cABC += cAB
        cAB *= 3
        cAB += cA
        cA *= 3
        cA += all
        all *= 3
    cABC %= mod
    cAB %= mod
    cA %= mod
    all %= mod
print(cABC)

Solution (Python):
mod = 10 ** 9 + 7
s = input()
n = len(s)
q = s.count('?')
dp = [[0] * (n + 1) for i in range(4)]

for i in range(n, -1, -1):
    for j in range(3, -1, -1):
        if i == n:
            if j == 3:
                dp[j][i] = 1
            else:
                dp[j][i] = 0

        else:
            if s[i] == '?':
                dp[j][i] = 3 * dp[j][i + 1]
            else:
                dp[j][i] = dp[j][i + 1]

            if j < 3 and (s[i] == '?' or s[i] == 'ABC'[j]):
                dp[j][i] += dp[j + 1][i + 1]

            dp[j][i] %= mod

print(dp[0][0])

Solution (Python):
from collections import Counter
mod = 10**9+7
s = input()
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
    a %= mod
    ab %= mod
    abc %= mod
    k %= mod
print(abc%mod)

Solution (Python):
S = input()
dp = list()
for i in range(4):
	dp.append([0] * 4)
dp[0][0] = 1
target = "ABC"
modulo = 1000000007
N = len(S)
for i in range(N):
	for j in range(2, -1, -1):
		if target[j] == S[i] or S[i] == '?':
			for k in range(2, -1, -1):
				tark = k + (1 if S[i] == '?' else 0)
				dp[j + 1][tark] += dp[j][k]
				if dp[j + 1][tark] >= modulo:
					dp[j + 1][tark] -= modulo
numquestion = 0
for i in range(N):
	if S[i] == '?':
		numquestion += 1
ans = 0
for i in range(4):
	if dp[3][i] >= 1:
		delta = dp[3][i] * pow(3, numquestion - i, modulo) % modulo
		ans += delta
		ans %= modulo
print(ans)

Solution (Python):
s = input()
mod = 10**9 + 7
abc = 0
bc = 0
c = 0
q = 0
for i in s[::-1]:
  if i == "A":
    abc = (abc + bc) % mod
  if i == "B":
    bc = (bc + c) % mod
  if i == "C":
    c = (pow(3,q,mod) + c) % mod
  if i == "?":
    abc = (abc*3 + bc) % mod
    bc = (bc*3 + c) % mod 
    c = (pow(3,q,mod) + c*3) % mod
    q += 1
print(int(abc))

Solution (Python):
S = input()

mod = 10 ** 9 + 7
ALL, A, AB, ABC = 1, 0, 0, 0

for s in S:
    if s == 'A':
        A = (A + ALL) % mod
    elif s == 'B':
        AB = (AB + A) % mod
    elif s == 'C':
        ABC = (ABC + AB) % mod
    elif s == '?':
        ABC = (3 * ABC + AB) % mod
        AB = (3 * AB + A) % mod
        A = (3 * A + ALL) % mod
        ALL = 3 * ALL % mod

print(ABC % mod)

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

l_a = [0] * (n + 1)
l_q = [0] * (n + 1)
r_c = [0] * (n + 1)
r_q = [0] * (n + 1)
total = 0

for i in range(1, n):
    l_a[i] = l_a[i - 1] + (1 if t[i - 1] == 'A' else 0)
    l_q[i] = l_q[i - 1] + (1 if t[i - 1] == '?' else 0)
for i in range(n - 1, 0, -1):
    r_c[i - 1] = r_c[i] + (1 if t[i] == 'C' else 0)
    r_q[i - 1] = r_q[i] + (1 if t[i] == '?' else 0)


pow3mod = [1] * (n+1)
for i in range(n):
    pow3mod[i+1] = pow3mod[i] * 3 % mod

for i in range(n):
    if t[i] in 'B?':
        total += l_a[i] * r_c[i] * pow3mod[l_q[i] + r_q[i]] + \
            l_a[i] * r_q[i] * pow3mod[l_q[i] + r_q[i] - 1] +\
            l_q[i] * r_c[i] * pow3mod[l_q[i] + r_q[i] - 1] +\
            l_q[i] * r_q[i] * pow3mod[l_q[i] + r_q[i] - 2]
        total %= mod
print(int(total))

Solution (Python):
S=raw_input()
 
M=10**9+7
 
all=1
abc=0
ab=0
a=0
 
for x in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		abc+=ab
 
	if x=="?":
		abc=abc*3+ab
		ab=ab*3+a
		a= a*3+all
		all*=3
 
	abc%=M
	ab%=M
	a%=M
	all%=M
 
 
print abc%M

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

S = input()
N = len(S)

nums = [1, 0, 0, 0]

for i in range(0, N):
    s = S[i]
    m = 3 if s == "?" else 1
    a = 1 if s == "A" or s == "?" else 0
    b = 1 if s == "B" or s == "?" else 0
    c = 1 if s == "C" or s == "?" else 0

    n0 = (nums[0] * m) % MOD
    n1 = (nums[1] * m + nums[0] * a) % MOD
    n2 = (nums[2] * m + nums[1] * b) % MOD
    n3 = (nums[3] * m + nums[2] * c) % MOD
    nums = [n0, n1, n2, n3]

print(nums[3] % MOD)

Solution (Python):
import gc

MOD = (10 ** 9) + 7

S = input()
N = len(S)

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

dp[0][0] = 1
dp[1][0] = 0
dp[2][0] = 0
dp[3][0] = 0

for i in range(1, N + 1):
    for j in range(4):
        s = S[i - 1]
        m = 3 if s == "?" else 1
        dp[j][i] += m * dp[j][i - 1]
        if j == 1:
            if s == "A" or s == "?":
                dp[j][i] += dp[j - 1][i - 1]
        elif j == 2:
            if s == "B" or s == "?":
                dp[j][i] += dp[j - 1][i - 1]
        elif j == 3:
            if s == "C" or s == "?":
                dp[j][i] += dp[j - 1][i - 1]
        dp[j][i] = dp[j][i] % MOD

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

Solution (Python):


"""
参考：http://tutuz.hateblo.jp/entry/2018/08/06/074104
　　　https://www.hamayanhamayan.com/entry/2018/08/05/232127
・別解
・予め必要なA,C,?の個数は集めておく。
・Bの位置を決めて、4つの選び方パターンを全部数え上げる。
・3べきの計算はpowの第三引数modで高速化
"""

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


A, LQ = [0] * len(S), [0] * len(S)
for i in range(len(S)-1):
    a = lq = 0
    if S[i] == 'A':
        a += 1
    if S[i] == '?':
        lq += 1
    A[i+1] = A[i] + a
    LQ[i+1] = LQ[i] + lq

C, RQ = [0] * len(S), [0] * len(S)
for i in range(len(S)-1, 0, -1):
    c = rq = 0
    if S[i] == 'C':
        c += 1
    if S[i] == '?':
        rq += 1
    C[i-1] = C[i] + c
    RQ[i-1] = RQ[i] + rq

ans = 0
for i in range(len(S)):
    if S[i] == '?' or S[i] == 'B':
        
        case1 = (A[i] * C[i] * pow(3, LQ[i] + RQ[i], MOD)) % MOD
        
        case2 = (A[i] * RQ[i] * pow(3, max(LQ[i] + RQ[i] - 1, 0), MOD)) % MOD
        
        case3 = (LQ[i] * C[i] * pow(3, max(LQ[i] + RQ[i] - 1, 0), MOD)) % MOD
        
        case4 = (LQ[i] * RQ[i] * pow(3, max(LQ[i] + RQ[i] - 2, 0), MOD)) % MOD
        
        ans = (ans + case1 + case2 + case3 + case4) % MOD

print(ans)

Solution (Python):


"""
参考：http://tutuz.hateblo.jp/entry/2018/08/06/074104
・別解
・予め必要なA,C,?の個数は集めておく。
・Bの位置を決めて、4つの選び方パターンを全部数え上げる。
"""

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


A, LQ = [0] * len(S), [0] * len(S)
for i in range(len(S)-1):
    a = lq = 0
    if S[i] == 'A':
        a += 1
    if S[i] == '?':
        lq += 1
    A[i+1] = A[i] + a
    LQ[i+1] = LQ[i] + lq

C, RQ = [0] * len(S), [0] * len(S)
for i in range(len(S)-1, 0, -1):
    c = rq = 0
    if S[i] == 'C':
        c += 1
    if S[i] == '?':
        rq += 1
    C[i-1] = C[i] + c
    RQ[i-1] = RQ[i] + rq

ans = 0
for i in range(len(S)):
    if S[i] == '?' or S[i] == 'B':
        
        case1 = (A[i] * C[i] * pow(3, LQ[i] + RQ[i], MOD)) % MOD
        
        case2 = (A[i] * RQ[i] * pow(3, max(LQ[i] + RQ[i] - 1, 0), MOD)) % MOD
        
        case3 = (LQ[i] * C[i] * pow(3, max(LQ[i] + RQ[i] - 1, 0), MOD)) % MOD
        
        case4 = (LQ[i] * RQ[i] * pow(3, max(LQ[i] + RQ[i] - 2, 0), MOD)) % MOD
        
        ans = (ans + case1 + case2 + case3 + case4) % MOD

print(int(ans))

Solution (Python):


"""
参考：http://drken1215.hatenablog.com/entry/2018/08/05/224100_1
・文字列DP
・こういう、ちょっと状況込み入ったDPがまだ自分でうまく書けない。
・もっと数こなして経験積まなきゃなー。
"""

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

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

Solution (Python):
s=input()
table=[1]+[0 for _ in range(3)] 
abc='ABC'
mod=10**9+7
for i in range(len(s)):
    if s[i]=='?':
        for j in range(3,0,-1):
            table[j]=(3*table[j]+table[j-1])%mod
        table[0]=3*table[0]%mod
    else:
        for j in range(3):
            if s[i]==abc[j]:
                table[j+1]+=table[j]

print(table[3]%mod)

Solution (Python):
s=input()
table=[[0 for _ in range(4)] for _ in range(len(s)+1)]
table[0][0]=1
abc='ABC'
for i in range(len(s)):
    for j in range(4):
        if s[i]=='?' and j!=0:
            table[i+1][j]=(3*table[i][j]+table[i][j-1])%(10**9+7)
        elif s[i]=='?':
            table[i+1][0]=3*table[i][0]%(10**9+7)
        elif s[i]==abc[j-1] and j!=0:
            table[i+1][j]=(table[i][j]+table[i][j-1])%(10**9+7)
        else:
            table[i+1][j]=table[i][j]%(10**9+7)

print(table[i+1][j]%(10**9+7))

Solution (Python):
s = list(input())
mod = 1000000007
c = [1] + [0] * 3
for i in s:
    if i == 'A':
        c[1] = (c[1] + c[0]) % mod
    elif i == 'B':
        c[2] = (c[2] + c[1]) % mod
    elif i == 'C':
        c[3] = (c[3] + c[2]) % mod
    else:
        c[3] = (c[3] * 3 + c[2]) % mod
        c[2] = (c[2] * 3 + c[1]) % mod
        c[1] = (c[1] * 3 + c[0]) % mod
        c[0] = c[0] * 3 % mod
print(c[3])

Solution (Python):
import numpy as np
s = list(input())
count = np.array([1] + [0] * 3).astype("int64")
for i in s:
    if i == 'A':
        count[1] += count[0]
    elif i == 'B':
        count[2] += count[1]
    elif i == 'C':
        count[3] += count[2]
    else:
        count[3] = count[3] * 3 + count[2]
        count[2] = count[2] * 3 + count[1]
        count[1] = count[1] * 3 + count[0]
        count[0] *= 3
    count %= 1000000007
print(count[3])

Solution (Python):


import sys


input = sys.stdin.readline
INF = float('inf')
MOD = 10 ** 9 + 7


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


S = input().rstrip()

na, a, ab, abc = 1, 0, 0, 0
for s in S:
    if s == 'A':
        a = (a + na) % 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 + na) % MOD
        na = (na * 3) % MOD

print(abc)

Solution (Python):


import sys


input = sys.stdin.readline
INF = float('inf')
MOD = 10 ** 9 + 7


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


S = input().rstrip()

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

        if S[i] == 'A':
            dp[i + 1][1] = (dp[i + 1][1] + dp[i][0]) % MOD
        if S[i] == 'B':
            dp[i + 1][2] = (dp[i + 1][2] + dp[i][1]) % MOD
        if S[i] == 'C':
            dp[i + 1][3] = (dp[i + 1][3] + dp[i][2]) % MOD

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

Solution (Python):


import sys


input = sys.stdin.readline
INF = float('inf')
MOD = 10 ** 9 + 7


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


S = input().rstrip()

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][j]
        else:
            dp[i + 1][j] += dp[i][j] * 3

        dp[i + 1][j] %= MOD

    
    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]

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

    

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

Solution (Python):
S = input()

dp = [(-1,-1,-1,-1)] * (len(S) + 1)
dp[0] = (1,0,0,0)
for i in range(len(S)):
    w, x, y, z = dp[i]
    if S[i] == "A":
        x += w
    elif S[i] == "B":
        y += x
    elif S[i] == "C":
        z += y
    else:
        z = 3 * z + y
        y = 3 * y + x
        x = 3 * x + w
        w = 3 * w
    w = w % 1000000007
    x = x % 1000000007
    y = y % 1000000007
    z = z % 1000000007
    dp[i + 1] = (w, x, y, z)

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

Solution (Python):
def calc_ABC(a, c, bq, aq):
    ans = 0
    if aq != 0:
        if bq != 0:
            ans = ans + (a*pow(3, bq, MOD) + bq*pow(3, bq-1, MOD)) \
                 * (c*pow(3, aq, MOD) + aq*pow(3, (aq-1), MOD))
        else:
            ans = ans + (a*pow(3, bq, MOD)) \
                 * (c*pow(3, aq, MOD) + aq*pow(3, (aq-1), MOD))
    else:
        if bq != 0:
            ans = ans + (a*pow(3, bq, MOD) + bq*pow(3, bq-1, MOD)) \
                 * (c*pow(3, aq, MOD))
        else:
            ans = ans + (a*pow(3, bq, MOD)) \
                 * (c*pow(3, aq, MOD))
    return ans % MOD


MOD = 10**9 + 7
S = input()
ans = 0
count_a = 0
count_c = S.count('C')
count_afterq = S.count('?')
count_beforeq = 0

for i in range(len(S)):
    if S[i] == 'A':
        count_a += 1
    elif S[i] == 'B':
        ans += calc_ABC(count_a, count_c, count_beforeq, count_afterq)
        ans = ans % MOD
    elif S[i] == 'C':
        count_c -= 1
    elif S[i] == '?':
        count_afterq -= 1
        ans += calc_ABC(count_a, count_c, count_beforeq, count_afterq)
        ans = ans % MOD
        count_beforeq += 1
print(ans)

Solution (Python):
S = input()
strs = list(S)

m = {}
l_s = len(strs)

for i in range(l_s+1):
    m[i] = {}
    for j in range(4):
        m[i][j] = 0

m[l_s][3] = 1

mod = 10**9+7
for i in range(l_s)[::-1]:
    s = strs[i]
    for j in range(4):
        m[i][j] = m[i+1][j]
    if s == 'A':
        m[i][0] += m[i+1][1]
    elif s == 'B':
        m[i][1] += m[i+1][2]
    elif s == 'C':
        m[i][2] += m[i+1][3]
    else:
        m[i][0] = m[i+1][0] * 3 + m[i+1][1]
        m[i][1] = m[i+1][1] * 3 + m[i+1][2]
        m[i][2] = m[i+1][2] * 3 + m[i+1][3]
        m[i][3] *= 3
    for j in range(4):
        m[i][j] = m[i][j] % mod
print(m[0][0] % mod)

Solution (Python):
MOD = 1000000007

S = input()

a, ab, abc, all_s = 0, 0, 0, 1

for s in S:
    if s == "A":
        a = (a + all_s) % MOD
    elif s == "B":
        ab = (ab + a) % MOD
    elif s == "C":
        abc = (abc + ab) % MOD
    elif s == "?":
        abc = (abc * 3 + ab) % MOD
        ab = (ab * 3 + a) % MOD
        a = (a * 3 + all_s) % MOD
        all_s = (all_s * 3) % MOD

print(abc)

Solution (Python):
mod = int(1e9) + 7


def main():
    S = input()
    a_sum = 0
    ab_sum = 0
    abc_sum = 0
    pattern = 1
    for i in range(len(S)):
        s = S[i]
        if s == "A":
            a_sum = (a_sum + pattern) % mod
        if s == "B":
            ab_sum = (ab_sum + a_sum) % mod
        if s == "C":
            abc_sum = (abc_sum + ab_sum) % mod
        if s == "?":
            abc_sum = (abc_sum * 3 + ab_sum) % mod
            ab_sum = (ab_sum * 3 + a_sum) % mod
            a_sum = (a_sum * 3 + pattern) % mod
            pattern = pattern * 3 % mod
    print(abc_sum)


if __name__ == "__main__":
    main()