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):
import sys
input = sys.stdin.readline
MOD = 10 ** 9 + 7

def main():
    string = input().strip()
    n = len(string)
    dp = [[0, 0, 0, 0] for _ in range(n + 1)]
    dp[0][0] = 1
    for i, s in enumerate(string):
        if s == "A":
            dp[i + 1][0] = dp[i][0]
            dp[i + 1][1] = dp[i][1] + dp[i][0]
            dp[i + 1][2] = dp[i][2]
            dp[i + 1][3] = dp[i][3]
        elif s == "B":
            dp[i + 1][0] = dp[i][0]
            dp[i + 1][1] = dp[i][1]
            dp[i + 1][2] = dp[i][2] + dp[i][1]
            dp[i + 1][3] = dp[i][3]
        elif s == "C":
            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] + dp[i][2]
        else:
            dp[i + 1][0] = 3 * dp[i][0]
            dp[i + 1][1] = 3 * dp[i][1] + dp[i][0]
            dp[i + 1][2] = 3 * dp[i][2] + dp[i][1]
            dp[i + 1][3] = 3 * dp[i][3] + dp[i][2]
        for j in range(4):
            dp[i + 1][j] %= MOD
    print(dp[-1][-1] % MOD)
    
main()

Solution (Python):


s = input()

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

power_3 = 1
for idx, letter in enumerate(s):
    dp[idx] = dp[idx-1].copy()

    if letter == 'A':
        dp[idx][1] += power_3
    elif letter == 'B':
        dp[idx][2] += dp[idx-1][1]
    elif letter == 'C':
        dp[idx][3] += dp[idx-1][2]
    elif letter == '?':
        dp[idx][1] *= 3
        dp[idx][2] *= 3
        dp[idx][3] *= 3
        dp[idx][1] += power_3 
        power_3 *= 3
        power_3 %= mod
        dp[idx][2] += dp[idx-1][1]
        dp[idx][3] += dp[idx-1][2]
        dp[idx][1] %= mod
        dp[idx][2] %= mod
        dp[idx][3] %= mod


print(dp[len(s)-1][3] % mod)

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

dpa = [0]*(10**5+10)
dpc = [0]*(10**5+10)

hatena_count = 0
pow3 = [1]*(10**5+10)

for i in range(1, 10**5+10):
    pow3[i] = pow3[i-1]*3 % mod

for i in range(n):
    if S[i] == "A":
        dpa[i+1] = (dpa[i] + pow3[hatena_count]) % mod
    elif S[i] == "?":
        dpa[i+1] = (3*dpa[i] + pow3[hatena_count]) % mod
        hatena_count += 1
    else:
        dpa[i+1] = dpa[i]

S.reverse()

hatena_count = 0
for i in range(n):
    if S[i] == "C":
        dpc[i+1] = (dpc[i] + pow3[hatena_count]) % mod
    elif S[i] == "?":
        dpc[i+1] = (3*dpc[i] + pow3[hatena_count]) % mod
        hatena_count += 1
    else:
        dpc[i+1] = dpc[i]

ans = 0
for i in range(1, n - 1):
    if S[i] == "B" or S[i] == "?":
        ans += dpa[n-1-i]*dpc[i]
        ans %= mod
print(ans)

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

dp_a = 0
dp_ab = 0
dp_abc = 0
hatena = 1

mod = 10**9 + 7

for i in range(n):
    if s[i]=="a":
        dp_a = (dp_a + hatena) % mod
    elif s[i]=="b":
        dp_ab = (dp_a + dp_ab) % mod
    elif s[i]=="c":
        dp_abc = (dp_ab + dp_abc) % mod
    else:
        dp_abc = (dp_ab + 3 * dp_abc) % mod
        dp_ab = (3 * dp_ab + dp_a) % mod
        dp_a = (3 * dp_a + hatena) % mod
        hatena = (hatena * 3) % mod

print(dp_abc)

Solution (Python):
def pow3(a):
    return 0 if a == -1 else p[a]

s = list(input())
n = len(s)
mod = pow(10, 9) + 7
x = [[0] * 2 for _ in range(n - 1)]
y = [[0] * 2 for _ in range(n - 1)]
p = [1] * n
ans = 0
for i in range(1, n):
    p[i] = 3 * p[i - 1] % mod
for i in range(n - 2):
    if s[i] == "A":
        x[i + 1][0] = 1
    elif s[i] == "?":
        x[i + 1][1] = 1
    for j in range(2):
        x[i + 1][j] += x[i][j]
    k = n - i - 1
    if s[k] == "C":
        y[i + 1][0] = 1
    elif s[k] == "?":
        y[i + 1][1] = 1
    for j in range(2):
        y[i + 1][j] += y[i][j]
for i in range(n - 2):
    j, k = i + 1, n - i - 2
    if s[j] == "B" or s[j] == "?":
        c1 = (x[j][0] * pow3(x[j][1]) + x[j][1] * pow3(x[j][1] - 1)) % mod
        c2 = (y[k][0] * pow3(y[k][1]) + y[k][1] * pow3(y[k][1] - 1)) % mod
        ans += c1 * c2
        ans %= mod
print(ans)

Solution (Python):
def getval():
    s = input()
    return s
    
def main(s):
    
    mod = 10**9 + 7
    dp = [0,0,0,0]
    p3 = [1]
    for i in range(len(s)):
        p3.append((3*p3[i])%mod)
    for i in s:
        if i=="A":
            dp[0] += p3[dp[3]]
            dp[0] %= mod
        elif i=="B":
            dp[1] += dp[0]
            dp[1] %= mod
        elif i=="C":
            dp[2] += dp[1]
            dp[2] %= mod
        else:
            temp1 = dp[0]*2
            temp2 = dp[1]*2
            temp3 = dp[2]*2
            dp[2] += dp[1]
            dp[1] += dp[0]
            dp[0] += p3[dp[3]]
            dp[2] += temp3
            dp[1] += temp2
            dp[0] += temp1
            dp[3] += 1
            for j in range(3):
                dp[j] %= mod
            
    print(dp[2])

if __name__=="__main__":
    s = getval()
    main(s)

Solution (Python):
S = input()
lct_A = 0
lct_q = 0
rct_C = S.count("C")
rct_q = S.count("?")

MOD = 10**9 + 7

ans = 0
for s in S:
  if s == "C":
    rct_C -= 1
  elif s == "?":
    rct_q -= 1
  
    
  if s == "B" or s == "?":
    ans += (lct_A * rct_C * pow(3, lct_q+rct_q, MOD)) % MOD
    if lct_q > 0:
      ans += (lct_q * rct_C * pow(3, lct_q+rct_q-1, MOD) ) % MOD
    if rct_q > 0:
      ans += (rct_q * lct_A * pow(3, lct_q+rct_q-1, MOD) ) % MOD
    if lct_q > 0 and rct_q > 0:
      ans += (lct_q * rct_q * pow(3, lct_q+rct_q-2, MOD) ) % MOD   
    ans %= MOD
    
    
  if s == "A":
    lct_A += 1
  elif s == "?":
    lct_q += 1
    
print(ans % MOD)

Solution (Python):
s=input()
mod=10**9+7
n,a,b,c=1,0,0,0
for i in s:
  if i=="A":
    a+=n
  if i=="B":
    b+=a
  if i=="C":
    c+=b
  if i=="?":
    n,a,b,c=3*n,3*a+n,3*b+a,3*c+b
  n%=mod
  a%=mod
  b%=mod
  c%=mod
print(c)

Solution (Python):
MOD=10**9+7
dp=[[0]*5 for _ in range(210000)]

def add(a,b):
  ret_val=a+b
  if ret_val>=MOD:
    ret_val-=MOD
  return ret_val

S=input()

dp[0][0]=1
for i in range(len(S)):
  for j in range(5):
    if S[i]!="?":
      temp=add(dp[i+1][j],dp[i][j])
      dp[i+1][j]=temp
    else:
      temp=add(dp[i+1][j],dp[i][j]*3%MOD)
      dp[i+1][j]=temp

  if S[i]=="A" or S[i]=="?":
    temp=add(dp[i+1][1],dp[i][0])
    dp[i+1][1]=temp
  if S[i]=="B" or S[i]=="?":
    temp=add(dp[i+1][2],dp[i][1])
    dp[i+1][2]=temp
  if S[i]=="C" or S[i]=="?":
    temp=add(dp[i+1][3],dp[i][2])
    dp[i+1][3]=temp
print(dp[len(S)][3])

Solution (Python):
N=input()
DP=[[0]*(len(N)+1) for i in range(4)]
DP[0][0]=1
mod=10**9+7
for i in range(len(N)):
   if N[i]=="A":
      DP[0][i+1]=DP[0][i]%mod
      DP[1][i+1]=(DP[1][i]+DP[0][i])%mod
      DP[2][i+1]=DP[2][i]%mod
      DP[3][i+1]=DP[3][i]%mod
   elif N[i]=="B":
      DP[0][i+1]=DP[0][i]%mod
      DP[1][i+1]=DP[1][i]%mod
      DP[2][i+1]=(DP[2][i]+DP[1][i])%mod
      DP[3][i+1]=DP[3][i]%mod
   elif N[i]=="C":
      DP[0][i+1]=DP[0][i]%mod
      DP[1][i+1]=DP[1][i]%mod
      DP[2][i+1]=DP[2][i]%mod
      DP[3][i+1]=(DP[3][i]+DP[2][i])%mod
   else:
      DP[3][i+1]=(3*DP[3][i]+DP[2][i])%mod
      DP[0][i+1]=(DP[0][i]*3)%mod
      DP[1][i+1]=(DP[1][i]*3+DP[0][i])%mod
      DP[2][i+1]=(DP[2][i]*3+DP[1][i])%mod
print(DP[3][-1]%mod)

Solution (Python):
MOD=10**9+7
S=input()
N=len(S)
Acum,Ccum,Qcum=[0]*(N+1),[0]*(N+1),[0]*(N+1)

for i in range(N):
    Acum[i+1]=Acum[i]+1 if S[i]=='A' else Acum[i]
    Ccum[i+1]=Ccum[i]+1 if S[i]=='C' else Ccum[i]
    Qcum[i+1]=Qcum[i]+1 if S[i]=='?' else Qcum[i]
ans=0
for i in range(N):
    if S[i]!='B' and S[i]!='?':
        continue
    a,c,l,r=Acum[i],Ccum[N]-Ccum[i+1],Qcum[i],Qcum[N]-Qcum[i+1]
    res=pow(3,l+r-2,MOD)*(3*a+l)%MOD*(3*c+r)%MOD
    ans=(ans+res)%MOD
print(ans)

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

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

dp[0][0]=1

for i in range(N):
    dp[i+1][0]=dp[i][0] if (S[i]!='?') else dp[i][0]*3%MOD
    dp[i+1][1]=dp[i][1] if (S[i]!='A' and S[i]!='?') else (dp[i][1]+dp[i][0])%MOD if (S[i]=='A') else (dp[i][0]+dp[i][1]*3)%MOD
    dp[i+1][2]=dp[i][2] if (S[i]!='B' and S[i]!='?') else (dp[i][2]+dp[i][1])%MOD if (S[i]=='B') else (dp[i][1]+dp[i][2]*3)%MOD
    dp[i+1][3]=dp[i][3] if (S[i]!='C' and S[i]!='?') else (dp[i][3]+dp[i][2])%MOD if (S[i]=='C') else (dp[i][2]+dp[i][3]*3)%MOD

print(dp[N][3])

Solution (Python):
s=input()
n=len(s)
q=s.count('?')

mod=10**9+7

target='ABC'
ans=0
for i in range(2**3):
    bdp=[1]*(n+1)
    cnt=0
    for j in range(2,-1,-1):
        if (i>>j)&1==1:
            c='?'
            cnt+=1
        else:
            c=target[j]
        
        cdp=[0]*(n+1)
        for k in range(n):
            if s[k]==c:
                cdp[k]=bdp[k+1]
        
        for k in range(n,0,-1):
            cdp[k-1]+=cdp[k]
            cdp[k-1]%=mod
        
        bdp=cdp
    
    if q>=cnt:
        ans+=bdp[0]*pow(3,q-cnt,mod)
        ans%=mod

print(ans)

Solution (Python):
s=input()
mod=10**9+7
n,a,b,c=1,0,0,0
for i in s:
  if i=="A":
    a+=n
  if i=="B":
    b+=a
  if i=="C":
    c+=b
  if i=="?":
    n,a,b,c=3*n,3*a+n,3*b+a,3*c+b
  n%=mod
  a%=mod
  b%=mod
  c%=mod
print(c)

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

    a_num = 0
    c_num = s.count('C')
    q_num = 0
    q_cnt = s.count('?')

    pow3, pow2, pow1, pow0 = 0, 0, 0, 0
    if q_cnt >= 3:
        pow3 = pow(3, q_cnt-3, mod)
        pow2 = pow3 * 3 % mod
        pow1 = pow2 * 3 % mod
        pow0 = pow1 * 3 % mod
    elif q_cnt == 2:
        pow2 = 1
        pow1 = 3
        pow0 = 9
    elif q_cnt == 1:
        pow1 = 1
        pow0 = 3
    else:
        pow0 = 1

    ans = 0
    for x in s:
        if x == 'A':
            a_num += 1
        elif x == 'B':
            ans += pow0 * a_num * c_num
            ans += pow1 * (q_num * c_num + a_num * (q_cnt - q_num))
            ans += pow2 * (q_num) * (q_cnt - q_num)
            ans %= mod
        elif x == 'C':
            c_num -= 1
        else:
            ans += pow1 * a_num * c_num
            ans += pow2 * (q_num * c_num + a_num * (q_cnt - q_num - 1))
            ans += pow3 * (q_num) * (q_cnt - q_num - 1)
            ans %= mod
            q_num += 1

    print(ans)

main()

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

    a_num = 0
    c_num = s.count('C')
    q_num = 0
    q_cnt = s.count('?')

    pow3, pow2, pow1, pow0 = 0, 0, 0, 0
    if q_cnt >= 3:
        pow3 = pow(3, q_cnt-3, mod)
        pow2 = pow3 * 3 % mod
        pow1 = pow2 * 3 % mod
        pow0 = pow1 * 3 % mod
    elif q_cnt == 2:
        pow2 = 1
        pow1 = 3
        pow0 = 9
    elif q_cnt == 1:
        pow1 = 1
        pow0 = 3
    else:
        pow0 = 1

    ans = 0
    for x in s:
        if x == 'A':
            a_num += 1
        elif x == 'B':
            ans += pow0 * a_num * c_num
            ans += pow1 * (q_num * c_num + a_num * (q_cnt - q_num))
            ans += pow2 * (q_num) * (q_cnt - q_num)
            ans %= mod
        elif x == 'C':
            c_num -= 1
        else:
            ans += pow1 * a_num * c_num
            ans += pow2 * (q_num * c_num + a_num * (q_cnt - q_num - 1))
            ans += pow3 * (q_num) * (q_cnt - q_num - 1)
            ans %= mod
            q_num += 1

    print(ans)

main()

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

    a_num = 0
    c_num = s.count('C')
    q_num = 0
    q_cnt = s.count('?')

    pows = [0] * 4
    if q_cnt >= 3:
        pows[3] = pow(3, q_cnt-3, mod)
        pows[2] = pows[3] * 3 % mod
        pows[1] = pows[2] * 3 % mod
        pows[0] = pows[1] * 3 % mod
    elif q_cnt == 2:
        pows[2] = 1
        pows[1] = 3
        pows[0] = 9
    elif q_cnt == 1:
        pows[1] = 1
        pows[0] = 3
    else:
        pows[0] = 1

    ans = 0
    for x in s:
        if x == 'A':
            a_num += 1
        elif x == 'B':
            ans += pows[0] * a_num * c_num
            ans += pows[1] * (q_num * c_num + a_num * (q_cnt - q_num))
            ans += pows[2] * (q_num) * (q_cnt - q_num)
            ans %= mod
        elif x == 'C':
            c_num -= 1
        else:
            ans += pows[1] * a_num * c_num
            ans += pows[2] * (q_num * c_num + a_num * (q_cnt - q_num - 1))
            ans += pows[3] * (q_num) * (q_cnt - q_num - 1)
            ans %= mod
            q_num += 1

    print(ans)

main()

Solution (Python):
S = input()
a = [1,0,0,0]

for s in S:
  if s=="A":
    a[1]+=a[0]
  elif s=="B":
    a[2]+=a[1]
  elif s=="C":
    a[3]+=a[2]
  else:
    a=[3*a[0]]+[3*a[n+1]+a[n] for n in range(3)]
  a=[a[n]%1000000007 for n in range(4)]

print(a[3])

Solution (Python):
mod = 10**9+7
S = input()
l = len(S)
dp = [0,0,1]
ans = 0
for i in range(l):
    if S[i] == 'A':
        dp[0] += dp[2]
        dp[0] %= mod
    if S[i] == 'B':
        dp[1] += dp[0]
        dp[1] %= mod
    if S[i] == 'C':
        ans += dp[1]
        ans %= mod
    if S[i] == '?':
        dp1 = dp[:]
        dp2 = dp[:]
        dp3 = dp[:]
        dp1[0] += dp1[2]
        dp2[1] += dp2[0]
        ans *= 3
        ans += dp3[1]
        ans %= mod
        dp[0] = (dp1[0]+dp2[0]+dp3[0]) % mod
        dp[1] = (dp1[1]+dp2[1]+dp3[1]) % mod
        dp[2]*= 3
        dp[2] %= mod
print(ans)

Solution (Python):
S = input()
s = 'ABC'
N = len(S)
C = 10**9+7
dp = [[0]*4 for _ in range(N+1)]
dp[N][3] = 1
for i in reversed(range(N)):
    for j in range(3):
        if i < j:
            continue
        dp[i][j] = ((1+(S[i] == '?')*2)*dp[i+1][j] +
                    (S[i] in {s[j], '?'})*dp[i+1][j+1]) % C
    if i>=3:
        dp[i][3] = ((1+(S[i] == '?')*2)*dp[i+1][3]) % C
print(dp[0][0])

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

S = readline().rstrip()
DIV = 10 ** 9 + 7

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

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

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

S = readline().rstrip()
DIV = 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] == "?":
    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] 
    dp[i + 1][1] += dp[i][0] 
    
  if S[i] == "B" or 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] 
    dp[i + 1][2] += dp[i][1] 
  
  if S[i] == "C" or 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] 
    dp[i + 1][3] += dp[i][2] 
    
  for j in range(4):
    dp[i + 1][j] %= DIV
    

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

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


def main():
    S = input()
    N = len(S)
    pre_hatena = S[:1].count("?")
    a = S[:1].count("A")
    post_hatena = S[2:].count("?")
    c = S[2:].count("C")

    rev_3 = pow(3, MOD-2, MOD)
    ans = 0
    for i in range(1, N-1):
        if S[i] == "?" or S[i] == "B":
            pre_pow = pow(3, pre_hatena, MOD)
            pre = pre_pow * a + ((pre_pow * rev_3) % MOD) * pre_hatena
            post_pow = pow(3, post_hatena, MOD)
            post = post_pow * c + ((post_pow * rev_3) % MOD) * post_hatena
            ans += pre * post
            ans %= MOD
        if S[i] == "?":
            pre_hatena += 1
        if S[i] == "A":
            a += 1
        if S[i+1] == "?":
            post_hatena -= 1
        if S[i+1] == "C":
            c -= 1
    print(ans)


if __name__ == '__main__':
    main()

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


def main():
    S = input()
    N = len(S)
    pre_hatena = S[:1].count("?")
    a = S[:1].count("A")
    post_hatena = S[2:].count("?")
    c = S[2:].count("C")

    ans = 0
    for i in range(1, N-1):
        if S[i] == "?" or S[i] == "B":
            pre_pow = pow(3, pre_hatena-1, MOD)
            pre = ((pre_pow * 3) % MOD) * a + pre_pow * pre_hatena
            post_pow = pow(3, post_hatena-1, MOD)
            post = ((post_pow * 3) % MOD) * c + post_pow * post_hatena
            ans += pre * post
            ans %= MOD
        if S[i] == "?":
            pre_hatena += 1
        if S[i] == "A":
            a += 1
        if S[i+1] == "?":
            post_hatena -= 1
        if S[i+1] == "C":
            c -= 1
    print(ans)


if __name__ == '__main__':
    main()

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

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

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

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

Solution (Python):
S=input()
N=len(S)
As=[0]*N
ABs=[0]*N
ABCs=[0]*N
p=10**9+7

if S[0]=="A":
    As[0]=1

now=1
if S[0]=="?":
    now=3
    As[0]=1
for i in range(1,N):
    s=S[i]
    if s=="A":
        As[i]=(As[i-1]+now)%p
        ABs[i]=ABs[i-1]
        ABCs[i]=ABCs[i-1]
    elif s=="B":
        As[i]=As[i-1]
        ABs[i]=(ABs[i-1]+As[i-1])%p
        ABCs[i]=ABCs[i-1]

    elif s=="C":
        As[i]=As[i-1]
        ABs[i]=ABs[i-1]
        ABCs[i]=(ABCs[i-1]+ABs[i-1])%p

    else:
        
        As[i]=(3*As[i-1]+now)%p
        ABs[i]=(3*ABs[i-1]+As[i-1])%p
        ABCs[i]=(3*ABCs[i-1]+ABs[i-1])%p
        now*=3
        now%=p

print(ABCs[-1])

Solution (Python):
s = input()

MOD = 10**9 + 7

a, ab, abc, q = 0, 0, 0, 1

for x in s:
    
    if x == "A":
        a += q
        a %= MOD
    
    elif x == "B":
        ab += a
        ab %= MOD
    
    elif x == "C":
        abc += ab
        abc %= MOD
    
    else:
        
        abc = (abc * 3 + ab) % MOD
        ab = (ab * 3 + a) % MOD
        a = (a * 3 + q) % MOD
        q = q * 3 % MOD

print(abc % MOD)

Solution (Python):
s = input().rstrip()
dp = [0] * 4
dp[0] = 1

for i in range(len(s)):
    if s[i] == 'A':
        dp[1] += dp[0]
    elif s[i] == 'B':
        dp[2] += dp[1]
    elif s[i] == 'C':
        dp[3] += dp[2]
    else:
        dp = [dp[0]*3, dp[1]*3+dp[0], dp[2]*3+dp[1], dp[3]*3+dp[2]]
    dp = list(map(lambda x: x % (10**9+7), dp))
print(dp[3])

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

s = input()
n = len(s)
dp = [[0] * 4 for _ in range(n+1)]
dp[0][0] = 1
for i,x in enumerate(s):
    for j in range(4):
        if x == '?':
            dp[i+1][j] = dp[i][j] * 3
        else:
            dp[i+1][j] = dp[i][j]
    if x == 'A' or x == '?':
        dp[i+1][1] += dp[i][0]
    if x == 'B' or x == '?':
        dp[i+1][2] += dp[i][1]
    if x == 'C' or x == '?':
        dp[i+1][3] += dp[i][2]
    for j in range(4):
        dp[i+1][j] %= mod
print(dp[-1][-1])

Solution (Python):
import sys

def LS2(): return list(sys.stdin.readline().rstrip())  

S = [0] + LS2()
n = len(S)
mod = 10**9+7

a,c,d = [0]*n,[0]*n,[0]*n  
for i in range(1,n):
    a[i] = a[i-1]
    c[i] = c[i-1]
    d[i] = d[i-1]
    if S[i] == 'A':
        a[i] += 1
    elif S[i] == 'C':
        c[i] += 1
    elif S[i] == '?':
        d[i] += 1

X = [1]  
for _ in range(n):
    X.append((X[-1]*3) % mod)

hatena = d[n-1]  

ans = 0
for i in range(1,n):
    if S[i] == 'B':
        ans += a[i-1]*(c[n-1]-c[i])*X[max(hatena,0)]
        ans %= mod
        ans += a[i-1]*(d[n-1]-d[i])*X[max(hatena-1,0)]
        ans %= mod
        ans += d[i-1]*(c[n-1]-c[i])*X[max(hatena-1,0)]
        ans %= mod
        ans += d[i-1]*(d[n-1]-d[i])*X[max(hatena-2,0)]
        ans %= mod
    elif S[i] == '?':
        ans += a[i-1]*(c[n-1]-c[i])*X[max(hatena-1,0)]
        ans %= mod
        ans += a[i-1]*(d[n-1]-d[i])*X[max(hatena-2,0)]
        ans %= mod
        ans += d[i-1]*(c[n-1]-c[i])*X[max(hatena-2,0)]
        ans %= mod
        ans += d[i-1]*(d[n-1]-d[i])*X[max(hatena-3,0)]
        ans %= mod

print(ans)

Solution (Python):
s = input().rstrip()
n = len(s)
mod = 10**9 + 7
dp = [0] * 4
dp[0] = 1

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

    for j in range(4):
        next[j] %= mod
    dp = next
print(dp[3])

Solution (Python):
s=input()
all_hatena = s.count('?')

a_cnt = 0
ab_cnt = 0
hatena_cnt = 0
ans = 0

MOD = 10**9+7
for si in s:
    if si == 'A':
        a_cnt += 1
    elif si == 'B':
        ab_cnt += a_cnt*pow(3,all_hatena,MOD)
        if all_hatena >= 1: ab_cnt += hatena_cnt*pow(3,all_hatena-1,MOD)
    elif si == 'C':
        ans += ab_cnt
    else:
        ans += ab_cnt*333333336 
        ab_cnt += a_cnt*pow(3,all_hatena-1,MOD)
        if all_hatena >= 2: ab_cnt += hatena_cnt*pow(3,all_hatena-2,MOD)
        hatena_cnt += 1
    ab_cnt%=MOD
    ans%=MOD
print(ans)

Solution (Python):
def modinv(a,m):
    b, u, v = m, 1, 0
    while b:
        t = a//b
        a -= t*b
        a,b = b,a
        u -= t * v
        u,v = v,u
    u %= m
    return u

s=input()
all_hatena = s.count('?')

a_cnt = 0
ab_cnt = 0
hatena_cnt = 0
ans = 0

MOD = 10**9+7
for si in s:
    if si == 'A':
        a_cnt += 1
    elif si == 'B':
        ab_cnt += a_cnt*pow(3,all_hatena,MOD)
        if all_hatena >= 1: ab_cnt += hatena_cnt*pow(3,all_hatena-1,MOD)
    elif si == 'C':
        ans += ab_cnt
    else:
        ans += ab_cnt*modinv(3,MOD)
        ab_cnt += a_cnt*pow(3,all_hatena-1,MOD)
        if all_hatena >= 2: ab_cnt += hatena_cnt*pow(3,all_hatena-2,MOD)
        hatena_cnt += 1
    ab_cnt%=MOD
    ans%=MOD
print(ans)

Solution (Python):
def modinv(a,m):
    b, u, v = m, 1, 0
    while b:
        t = a//b
        a -= t*b
        a,b = b,a
        u -= t * v
        u,v = v,u
    u %= m
    return u

s=input()
all_hatena = s.count('?')

a_cnt = 0
ab_cnt = 0
hatena_cnt = 0
ans = 0

MOD = 10**9+7
for si in s:
    if si == 'A':
        a_cnt += 1
    elif si == 'B':
        ab_cnt += a_cnt*pow(3,all_hatena,MOD)
        if all_hatena >= 1:
            ab_cnt += hatena_cnt*pow(3,all_hatena-1,MOD)
    elif si == 'C':
        ans += ab_cnt
    else:
        ans += ab_cnt*modinv(3,MOD)
        ab_cnt += a_cnt*pow(3,all_hatena-1,MOD)
        if all_hatena >= 2:
            ab_cnt += hatena_cnt*pow(3,all_hatena-2,MOD)
        hatena_cnt += 1
    ab_cnt%=MOD
    ans%=MOD
    
print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(10**7)
def LS2(): return list(sys.stdin.readline().rstrip())  

S = [0] + LS2()
n = len(S)
mod = 10**9+7

a,c,d = [0]*(n+1),[0]*(n+1),[0]*(n+1)
for i in range(1,n):
    a[i] = a[i-1]
    c[i] = c[i-1]
    d[i] = d[i-1]
    if S[i] == 'A':
        a[i] += 1
    elif S[i] == 'C':
        c[i] += 1
    elif S[i] == '?':
        d[i] += 1

X = [1]
for _ in range(n):
    X.append((X[-1]*3) % mod)

ans = 0
for i in range(1,n):
    if S[i] == 'B':
        ans += a[i-1]*(c[n-1]-c[i])*X[max(d[n-1],0)]
        ans %= mod
        ans += a[i-1]*(d[n-1]-d[i])*X[max(d[n-1]-1,0)]
        ans %= mod
        ans += d[i-1]*(c[n-1]-c[i])*X[max(d[n-1]-1,0)]
        ans %= mod
        ans += d[i-1]*(d[n-1]-d[i])*X[max(d[n-1]-2,0)]
        ans %= mod
    elif S[i] == '?':
        ans += a[i-1]*(c[n-1]-c[i])*X[max(d[n-1]-1,0)]
        ans %= mod
        ans += a[i-1]*(d[n-1]-d[i])*X[max(d[n-1]-2,0)]
        ans %= mod
        ans += d[i-1]*(c[n-1]-c[i])*X[max(d[n-1]-2,0)]
        ans %= mod
        ans += d[i-1]*(d[n-1]-d[i])*X[max(d[n-1]-3,0)]
        ans %= mod

print(ans)

Solution (Python):



def main():
    S = input()
    N = len(S)
    m = 10**9 + 7
    
    dp = [[0]*4 for _ 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] = dp[i+1][j] * 3 % m
                else:
                    dp[i][j] = dp[i+1][j]
                
                if j < 3:
                    if S[i] == '?' or S[i] == 'ABC'[j]:
                        dp[i][j] += dp[i+1][j+1]
                        dp[i][j] %= m

    print(dp[0][0])


if __name__ == "__main__":
    main()

Solution (Python):
s = str(input());MOD = pow(10,9)+7
n = len(s)
dp = [[0,0,0,0]  for _ in range(n+1)]

dp[0][0] = 1
for i in range(n):
  if s[i] == "A":
    dp[i+1][0] = dp[i][0]
    dp[i+1][1] = dp[i][0]+dp[i][1]
    dp[i+1][2] = dp[i][2]
    dp[i+1][3] = dp[i][3]
  if s[i] == "B":
    dp[i+1][0] = dp[i][0]
    dp[i+1][1] = dp[i][1]
    dp[i+1][2] = dp[i][2]+dp[i][1]
    dp[i+1][3] = dp[i][3]
  if s[i] == "C":
    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]+dp[i][2]
  if s[i] == "?":
    dp[i+1][0] = dp[i][0]*3
    dp[i+1][1] = dp[i][1]*3+dp[i][0]
    dp[i+1][2] = dp[i][2]*3+dp[i][1]
    dp[i+1][3] = dp[i][3]*3+dp[i][2]
  for j in range(4):
    dp[i+1][j] %= MOD
    
ans = dp[n][3]

print(ans)

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(1,n+1):
    dp[i][0]=dp[i-1][0]*((s[i-1]=="?")*2+1)
    dp[i][1]=dp[i-1][1]*((s[i-1]=="?")*2+1)
    dp[i][2]=dp[i-1][2]*((s[i-1]=="?")*2+1)
    dp[i][3]=dp[i-1][3]*((s[i-1]=="?")*2+1)
    if s[i-1]=="A" or s[i-1]=="?":
        dp[i][1]+=dp[i-1][0]
    if s[i-1]=="B" or s[i-1]=="?":
        dp[i][2]+=dp[i-1][1]
    if s[i-1]=="C" or s[i-1]=="?":
        dp[i][3]+=dp[i-1][2]
    dp[i][0]%=mod
    dp[i][1]%=mod
    dp[i][2]%=mod
    dp[i][3]%=mod
print(dp[n][3])

Solution (Python):
S = input()

MOD = 10 ** 9 + 7
dp, dp_a, dp_ab, dp_abc = 1, 0, 0, 0

for s in S:
    if s == 'A':
        dp_a += dp
    elif s == 'B':
        dp_ab += dp_a
    elif s == 'C':
        dp_abc += dp_ab
    else:
        dp, dp_a, dp_ab, dp_abc = dp * 3, dp_a * 3 + dp, dp_ab * 3 + dp_a, dp_abc * 3 + dp_ab
    dp %= MOD
    dp_a %= MOD
    dp_ab %= MOD
    dp_abc %= MOD
print(dp_abc)

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




def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))



def main():
	s=RD()
	n=len(s)

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


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

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


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











if __name__ == "__main__":
	main()

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




def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))



def main():
	s=RD()
	n=len(s)

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


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

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


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











if __name__ == "__main__":
	main()