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.



Sample input:
A??C


Sample output:
8

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
from math import sqrt, pi
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

S = input()
N = len(S)
# dp[i][j]: i番目にjまで丸をつけ終えている通り
dp = [[0] * 4 for _ in range(N + 1)]
dp[0][0] = 1

for i in range(N):
    for j in range(4):
        # i番目の文字が?でなければ
        if S[i] != '?':
            # 一つ前のものを引き継ぐ
            dp[i + 1][j] += dp[i][j]
            dp[i + 1][j] %= mod
        # ?なら
        else:
            # A, B, C３つ分引き継ぐ
            dp[i + 1][j] += 3 * dp[i][j]
            dp[i + 1][j] %= mod
    # もしS[i]がAか?ならj == 0の場合カウントを一つ増やせる
    # これでABC○A○B○Cと○A○B○CABCは区別される
    if S[i] == 'A' or S[i] == '?':
        dp[i + 1][1] += dp[i][0]
        dp[i + 1][1] %= mod
    if S[i] == 'B' or S[i] == '?':
        dp[i + 1][2] += dp[i][1]
        dp[i + 1][2] %= mod
    if S[i] == 'C' or S[i] == '?':
        dp[i + 1][3] += dp[i][2]
        dp[i + 1][3] %= mod
print(dp[N][3] % mod)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
s = input()
a = 0
ql = 0
c = s.count('C')
qr = s.count('?')
ans = 0 
for si in s:
    if si == '?':
        qr -= 1
    if si in 'B?':
        ans = (ans + pow(3,ql+qr,MOD)*a*c 
             + (pow(3,ql+qr-1,MOD)*(ql*c+a*qr) if ql + qr - 1 >= 0 else 0)
             + (pow(3,ql+qr-2,MOD)*ql*qr if ql + qr - 2 >= 0 else 0)) % MOD
    if si == '?':
        ql += 1
    elif si == 'A':
        a += 1
    elif si == 'C':
        c -= 1
print(ans)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
dp = [0, 0]
ans = 0
t = 1
for c in input():
    ndp = dp.copy()
    if c in 'A':
        ndp[0] = (dp[0] + t) % MOD
    elif c in 'B':
        ndp[1] = (ndp[1] + dp[0]) % MOD
    elif c in 'C':
        ans = (ans + dp[1]) % MOD
    else:
        ndp[0] = (3 * dp[0] + t) % MOD
        ndp[1] = (3 * dp[1] + dp[0]) % MOD
        ans = (3 * ans + dp[1]) % MOD
        t = (t * 3) % MOD
    #print(*ndp, ans)
    dp = ndp
print(ans)

Submission status: Accepted

Solution code:
S = input()
ans = 0
MOD = 10 ** 9 + 7
la = 0
lp = 0
rc = 0
rp = 0
for c in S:
    if c == 'C':
        rc += 1
    if c == '?':
        rp += 1
for c in S:
    if c == 'C':
        rc -= 1
    if c == '?':
        rp -= 1
    if c == '?' or c == 'B':
        if lp == 0:
            l = la * pow(3, lp, MOD)
        else:
            l = la * pow(3, lp, MOD) + lp * pow(3, lp-1, MOD)
        if rp == 0:
            r = rc * pow(3, rp, MOD)
        else:
            r = rc * pow(3, rp, MOD) + rp * pow(3, rp-1, MOD)
        ans += l*r
        ans %= MOD
    if c == 'A':
        la += 1
    if c == '?':
        lp += 1
print(ans)

Submission status: Accepted

Solution code:
S = input()
MOD = 10**9 + 7
dp = [[0]*4 for _ in range(100005)]
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]
            dp[i+1][j] %= MOD
        else:
            dp[i+1][j] += 3*dp[i][j] % MOD
            dp[i+1][j] %= MOD
    if S[i] == 'A' or S[i] == '?':
        dp[i+1][1] += dp[i][0]
        dp[i+1][1] %= MOD
    if S[i] == 'B' or S[i] == '?':
        dp[i+1][2] += dp[i][1]
        dp[i+1][2] %= MOD
    if S[i] == 'C' or S[i] == '?':
        dp[i+1][3] += dp[i][2]
        dp[i+1][3] %= MOD
print(dp[len(S)][3])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))


def main():
    S=["D"] + list(input())
    N=len(S)
    MOD=10**9+7

    A = [0] * (N+1)
    C = [0] * (N+1)
    Q = [0] * (N+1)

    for i in range(1,N+1):
        s = S[i-1]
        A[i] = A[i-1]
        C[i] = C[i-1]
        Q[i] = Q[i-1]
        if s == "A":
            A[i] += 1
        elif s == "C":
            C[i] += 1
        elif s == "?":
            Q[i] += 1
    
    # print(A,C,Q)
    ans = 0
    for i in range(1,N+1):
        s = S[i-1]
        if s == "?" or s == "B":
            l_A = A[i-1]
            l_Q = Q[i-1]
            r_Q = Q[-1] - Q[i]
            r_C = C[-1] - C[i]

            
            
            # print(l_A,l_Q,r_Q,r_C)
            # ans += (l_A+l_Q) * (r_Q+r_C) % MOD

            left = pow(2,l_Q,MOD) * l_A % MOD
            if l_Q > 0:
                left += l_Q * pow((1+pow(2,MOD-2,MOD)), l_Q-1,MOD) * pow(2,l_Q-1,MOD) % MOD # 1個以上使うとき
                # print("r2",r_Q * pow((1+pow(2,MOD-2,MOD)), r_Q-1,MOD) * pow(2,r_Q-1,MOD) % MOD)
                left %= MOD
                left += l_A * (pow(3,l_Q,MOD)-pow(2,l_Q,MOD)) % MOD 
                # print("r3",r_C * (pow(3,r_Q,MOD)-pow(2,r_Q,MOD)) % MOD)
                # print(right)

            right = pow(2,r_Q,MOD) * r_C % MOD # 一個も使わないとき
            # print("r",right)
            if r_Q > 0:
                right += r_Q * pow((1+pow(2,MOD-2,MOD)), r_Q-1,MOD) * pow(2,r_Q-1,MOD) % MOD # 1個以上使うとき
                # print("r2",r_Q * pow((1+pow(2,MOD-2,MOD)), r_Q-1,MOD) * pow(2,r_Q-1,MOD) % MOD)
                right %= MOD
                right += r_C * (pow(3,r_Q,MOD)-pow(2,r_Q,MOD)) % MOD 
                # print("r3",r_C * (pow(3,r_Q,MOD)-pow(2,r_Q,MOD)) % MOD)
                # print(right)

            # exit()
            ans += left * right % MOD
            ans %= MOD
            # if s == "?":

            
    ans %= MOD
    print(ans)






if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

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

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

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

Submission status: Accepted

Solution code:
import numpy as np

MOD = 10 ** 9 + 7

S = input()

n = len(S)
dp = np.zeros((n+1, 4), np.int64)
dp[0, 0] = 1
for i, c in enumerate(S):
    if c == 'A' or c == '?':
        dp[i+1] += dp[i]
        dp[i+1, 1] += dp[i, 0]
    if c == 'B' or c == '?':
        dp[i+1] += dp[i]
        dp[i+1, 2] += dp[i, 1]
    if c == 'C' or c == '?':
        dp[i+1] += dp[i]
        dp[i+1, 3] += dp[i, 2]
    dp[i+1] %= MOD

print(dp[n, 3])

Submission status: Accepted

Solution code:
from collections import Counter
s = list(input())
n = len(s)
c = Counter(s)
mod = 10**9+7


left_a  = 0
left_b  = 0
left_c  = 0
left_q  = 0
right_a = c['A']
right_b = c['B']
right_c = c['C']
right_q = c['?']

def add_ans():
    lhs = left_a * pow(3, left_q, mod) + left_q*pow(3, left_q-1, mod)
    rhs = right_c * pow(3, right_q, mod) + right_q*pow(3, right_q-1, mod)
    return  (lhs * rhs)%mod

ans = 0
for i in range(n):
    if s[i] == 'A':
        left_a  += 1
    if s[i] == 'B':
        ans = (ans+ add_ans())%mod
    if s[i] == 'C':
        right_c -= 1
    if s[i] == '?':
        right_q -= 1
        ans = (ans+ add_ans())%mod
        left_q  += 1
print(ans)

Submission status: Accepted

Solution code:
#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

s = ins()
n = len(s)
a = ab = abc = 0
z = 1
for i in range(n):
    ss = s[i]
    if ss=='A':
        a += z
    elif ss=='B':
        ab = (ab+a)%R
    elif ss=='C':
        abc = (abc+ab)%R #+qb+aq+qq
    else:
        abc = (abc*3+ab)%R #+qb+aq+qq
        ab = (ab*3+a)%R
        a = (a*3+z)%R
        z = (z*3)%R
    #ddprint(f"{i=} {z=} {a=} {ab=} {abc=}")
print(abc)

Submission status: Accepted

Solution code:
s=input()
mod=pow(10,9)+7
dp=[0]*4
dp[0]=1
for si in s:
  if si=='A':
    dp[1]+=dp[0]
  elif si=='B':
    dp[2]+=dp[1]
  elif si=='C':
    dp[3]+=dp[2]
  else:
    dp[3]*=3
    dp[3]+=dp[2]
    dp[2]*=3
    dp[2]+=dp[1]
    dp[1]*=3
    dp[1]+=dp[0]
    dp[0]*=3
  dp[3]%=mod
  dp[2]%=mod
  dp[1]%=mod
  dp[0]%=mod
print(dp[3])

Submission status: Accepted

Solution code:
s=input()
mod=pow(10,9)+7
dp=[0]*4
dp[0]=1
for si in s:
  if si=='A':
    dp[1]+=dp[0]
  elif si=='B':
    dp[2]+=dp[1]
  elif si=='C':
    dp[3]+=dp[2]
  else:
    tmp3=dp[2]
    tmp2=dp[1]
    tmp1=dp[0]
    dp[3]*=3
    dp[3]+=tmp3
    dp[2]*=3
    dp[2]+=tmp2
    dp[1]*=3
    dp[1]+=tmp1
    dp[0]*=3
  dp[3]%=mod
  dp[2]%=mod
  dp[1]%=mod
  dp[0]%=mod
print(dp[3])

Submission status: Accepted

Solution code:
# D - We Love ABC

S = list(str(input()))
MOD = 10**9 + 7
a = 0
ab = 0
abc = 0
pat = 1
for s in S:
    if s == 'A':
        a = (a + pat) % MOD
    elif s == 'B':
        ab = (ab + a) % MOD
    elif s == 'C':
        abc = (abc + ab) % MOD
    else: # s == '?'
        tmpa = a
        tmpab = ab
        a = (3*a + pat) % MOD
        ab = (3*ab + tmpa) % MOD
        abc = (3*abc + tmpab) % MOD
        pat = (pat*3) % MOD

print(abc)

Submission status: Accepted

Solution code:
# D - We Love ABC
import sys
readline = sys.stdin.readline

S = list(str(readline().rstrip()))
MOD = 10**9 + 7
a = 0
ab = 0
abc = 0
pat = 1
for s in S:
    if s == 'A':
        a = (a + pat) % MOD
    elif s == 'B':
        ab = (ab + a) % MOD
    elif s == 'C':
        abc = (abc + ab) % MOD
    else: # s == '?'
        tmpa = a
        tmpab = ab
        a = (3*a + pat) % MOD
        ab = (3*ab + tmpa) % MOD
        abc = (3*abc + tmpab) % MOD
        pat = (pat*3) % MOD

print(abc)

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
	S = SI()
	N = len(S)
	dp = make_grid(N+1, 4, 0)
	dic = {"A": [0], "B": [1], "C": [2], "?": [0,1,2]}
	dp[0][0] = 1
	for i, s in enumerate(S):
		if s == "?":
			for j in range(4):
				if j in dic[s]:
					dp[i+1][j+1] += dp[i][j] % MOD
				dp[i+1][j] += dp[i][j] * 3 % MOD
		else:
			for j in range(4):
				if j in dic[s]:
					dp[i+1][j+1] += dp[i][j] % MOD

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

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



if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
md=10**9+7
s=input()
dp=[[0]*4 for _ in range(3)]
for c in s:
    if c=="A":dp[0][0]=(dp[0][0]+1)%md
    if c=="B":
        for j in range(2):dp[1][j]=(dp[1][j]+dp[0][j])%md
    if c=="C":
        for j in range(3):dp[2][j]=(dp[2][j]+dp[1][j])%md
    if c=="?":
        for j in range(3):dp[2][j+1]=(dp[2][j+1]+dp[1][j])%md
        for j in range(2):dp[1][j+1]=(dp[1][j+1]+dp[0][j])%md
        dp[0][1] = (dp[0][1] + 1) % md
ans=0
q=s.count("?")
for j in range(4):
    if q-j<0:break
    ans+=dp[2][j]*pow(3,q-j,md)
    ans%=md
print(ans)

Submission status: Accepted

Solution code:
import sys

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


class ModInt:
    MOD = 10 ** 9 + 7

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

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

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

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

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

    __rmul__ = __mul__

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

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

    def set_mod_divisor(self, divisor):
        ModInt.MOD = divisor


def main():
    s = input()
    n = len(s)
    dp_t = [ModInt(0)] * (n + 1)
    dp_a = [ModInt(0)] * (n + 1)
    dp_ab = [ModInt(0)] * (n + 1)
    dp_abc = [ModInt(0)] * (n + 1)

    dp_t[0] = ModInt(1)
    dp_a[0] = ModInt(0)
    dp_ab[0] = ModInt(0)
    dp_abc[0] = ModInt(0)

    for i, char in enumerate(s, 1):
        if char == "?":
            dp_t[i] = 3 * dp_t[i - 1]
            dp_a[i] = 3 * dp_a[i - 1] + dp_t[i - 1]
            dp_ab[i] += 3 * dp_ab[i - 1] + dp_a[i - 1]
            dp_abc[i] += 3 * dp_abc[i - 1] + dp_ab[i - 1]
        else:
            dp_t[i] = dp_t[i - 1]
            dp_a[i] += dp_a[i - 1]
            dp_ab[i] += dp_ab[i - 1]
            dp_abc[i] += dp_abc[i - 1]
            if char == "A":
                dp_a[i] += dp_t[i - 1]
            if char == "B":
                dp_ab[i] += dp_a[i - 1]
            if char == "C":
                dp_abc[i] += dp_ab[i - 1]

    print(dp_abc[-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
s=input()
n=len(s)
mod=10**9+7
dp=[[0]*4 for _ in range(n+1)]
dp[n][3]=1
for i in reversed(range(n)):
    for j in reversed(range(4)):
        if j==3:
            if s[i]=="?":
                m=3
            else:
                m=1
            dp[i][j]+=m*dp[i+1][j]
        else:
            if s[i]=="?":
                m1=3
            else:
                m1=1
            if j==0:
                if s[i]=="A" or s[i]=="?":
                    m2=1
                else:
                    m2=0
            elif j==1:
                if s[i]=="B" or s[i]=="?":
                    m2=1
                else:
                    m2=0
            else:
                if s[i]=="C" or s[i]=="?":
                    m2=1
                else:
                    m2=0
            dp[i][j]+=m1*dp[i+1][j]+m2*dp[i+1][j+1]
        dp[i][j]%=mod
print(dp[0][0]%mod)
#print(dp)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
mod = 10**9+7

def main():
    S = input()
    L = len(S)
    """
    dpなんですか、そうですか。。。（眼中になかった）
    '?'を総当たりで埋めてから考えるのではなく、
    i文字目までの問題の解を考えるのがミソ。具体的には
        dp[i][""]    = (i文字目まで見たときにまだどの文字も選んでいない方法)
        dp[i]["A"]   = (i文字目まで見たときに"A  "の１文字まで選んでいる方法)
        dp[i]["AB"]  = (i文字目まで見たときに"AB "の２文字まで選んでいる方法)
        dp[i]["ABC"] = (i文字目まで見たときに"ABC"の３文字まで選んでいる方法)
    をキーとする遷移を考える。

    （注意）この遷移を例えば
        dp[i]["A"] = (i文字目まで見たときに"A"の１文字を選ぶ方法)
    のようにすると、それまでにどの文字を選んできたかの情報が抜け落ちるのでダメ。
    """
    dp = [1, 0, 0, 0]
    if S[0] == "A": dp = [1, 1, 0, 0]
    if S[0] == '?': dp = [3, 1, 0, 0]
    #print("S[0]={}, dp[0]={}".format(S[0], dp))
    for i in range(1, L):
        if S[i] == 'A':
            dp = [dp[0], dp[1] + dp[0], dp[2], dp[3]]
        elif S[i] == 'B':
            dp = [dp[0], dp[1], dp[2] + dp[1], dp[3]]
        elif S[i] == 'C':
            dp = [dp[0], dp[1], dp[2], 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 = [dp[0] % mod, dp[1] % mod, dp[2] % mod, dp[3] % mod]
        #print("S[{}]={}, dp[{}]={}".format(i, S[i], i, dp))
    print(dp[3])


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

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

#iよりleftのA、rightのC, leftの？, rightの?
la = [0 for _ in range(n)]
rc = [0 for _ in range(n)]
lq = [0 for _ in range(n)]
rq = [0 for _ in range(n)]

for i in range(n-1):
    if s[i] == 'A':
        la[i+1] = 1
    if s[i] == '?':
        lq[i+1] = 1
    if s[i+1] == '?':
        rq[i] = 1
    if s[i+1] == 'C':
        rc[i] = 1

for i in range(n-1):
    la[i+1] += la[i]
    lq[i+1] += lq[i]

for i in range(n-1, 0, -1):
    rc[i-1] += rc[i]
    rq[i-1] += rq[i]

ans = 0
mod = 10 ** 9 + 7

for i in range(n):
    if s[i] in ['B', '?']:
        l = la[i] * pow(3, lq[i], mod)
        if lq[i] > 0:
            l += lq[i] * pow(3, lq[i]-1, mod)
            l %= mod

        r = rc[i] * pow(3, rq[i], mod)
        if rq[i] > 0:
            r += rq[i] * pow(3, rq[i]-1, mod)
            r %= mod
        ans += l * r
        ans %= mod


print(ans)

Submission status: Accepted

Solution code:
def main():
    MOD = 10 ** 9 + 7

    S = input()
    z, a, b, c = 1, 0, 0, 0

    for x in S:
        if x == 'C':
            c = (c + b) % MOD
        elif x == 'B':
            b = (b + a) % MOD
        elif x == 'A':
            a = (a + z) % MOD
        elif x == '?':
            z, a, b, c = z * 3 % MOD, (a * 3 + z) % MOD, (b * 3 + a) % MOD, (c * 3 + b) % MOD
    print(c)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
s = input()
a, d = [0], [0]
for char in s[:-1]:
    if char == 'A':
        a.append(a[-1] + 1)
    else:
        a.append(a[-1])
    if char == '?':
        d.append(d[-1] + 1)
    else:
        d.append(d[-1])

c, e = [0], [0]
for char in s[::-1][:-1]:
    if char == 'C':
        c.append(c[-1] + 1)
    else:
        c.append(c[-1])
    if char == '?':
        e.append(e[-1] + 1)
    else:
        e.append(e[-1])
c = c[::-1]
e = e[::-1]

ret = 0
mod = 10 ** 9 + 7
for char, aa, dd, cc, ee in zip(s, a, d, c, e):
    if char in 'B?':
        tmp1 = aa * pow(3, dd, mod)
        if dd != 0:
            tmp1 += dd * pow(3, dd - 1, mod)

        tmp2 = cc * pow(3, ee, mod)
        if ee != 0:
            tmp2 += ee * pow(3, ee - 1, mod)

        ret += tmp1 * tmp2
        ret %= mod

print(ret)

Submission status: Accepted

Solution code:
s = input()
S = len(s)

#i文字目まで見たときj文字目まで確定しているときの組み合わせ
dp = [[0 for i in range(4)]for j in range(S+1)]
mod = 10**9+7

dp[0][0] = 1

for j in range(4):
    for i in range(S):
        dp[i+1][j] = dp[i][j]%mod
        if s[i] == "?":
            dp[i+1][j] = dp[i][j]*3%mod
            if j > 0:
                dp[i+1][j] += dp[i][j-1]%mod
        else:
            if "ABC".index(s[i])+1 == j:
                dp[i+1][j] += dp[i][j-1]%mod

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

Submission status: Accepted

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

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

print(dp[n][3])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from itertools import accumulate

MOD = 10**9+7
S = input()
n = len(S)
acc_A = [0]*n
acc_C = [0]*n
acc_Q_left = [0]*n
acc_Q_right = [0]*n
cnt = 0
for i, s in enumerate(S):
  if s == "A":
    acc_A[i] = 1
  elif s == "C":
    acc_C[i] = 1
  elif s == "?":
    acc_Q_left[i] = 1
    acc_Q_right[i] = 1
    cnt += 1
acc_A = list(accumulate(acc_A))
acc_C = list(accumulate(acc_C[::-1]))[::-1]
acc_Q_left = list(accumulate(acc_Q_left))
acc_Q_right = list(accumulate(acc_Q_right[::-1]))[::-1]
ans = 0
for i, s in enumerate(S):
  if i == 0 or i == n-1:
    continue
  if s == "B":
    ans += acc_A[i-1] * acc_C[i+1] * pow(3, cnt, MOD)
    if cnt >= 1:
      ans += acc_A[i-1] * acc_Q_right[i+1] * pow(3, cnt-1, MOD)
      ans += acc_Q_left[i-1] * acc_C[i+1] * pow(3, cnt-1, MOD)
    if cnt >= 2:
      ans += acc_Q_left[i-1] * acc_Q_right[i+1] * pow(3, cnt-2, MOD)
  elif s == "?":
    ans += acc_A[i-1] * acc_C[i+1] * pow(3, cnt-1, MOD)
    if cnt >= 2:
      ans += acc_A[i-1] * acc_Q_right[i+1] * pow(3, cnt-2, MOD)
      ans += acc_Q_left[i-1] * acc_C[i+1] * pow(3, cnt-2, MOD)
    if cnt >= 3:
      ans += acc_Q_left[i-1] * acc_Q_right[i+1] * pow(3, cnt-3, MOD)
  ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 10**9 + 7
    SI = lambda : sys.stdin.readline().rstrip()
    S = SI()

    dp = [[0] * 4 for _ in range(len(S)+1)]
    dp[0] = [1,0,0,0]
    ans = 0
    for i in range(len(S)):
        rg = [0,1,2] if S[i] == '?' else [ord(S[i])-ord('A')]
        for a in rg:
            for b in range(4):
                if a == b:
                    c = b + 1
                    dp[i + 1][c] = (dp[i + 1][c] + dp[i][b]) % MOD
                dp[i + 1][b] = (dp[i + 1][b] + dp[i][b]) % MOD

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
MOD = 1000000007

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

print(dp[N][3])

Submission status: Accepted

Solution code:
#何も思い浮かばない
#完全に負けた死にたいわかんない
#やっぱりDPだけど式が全く立てれない
#頭悪すぎしね
mod=10**9+7
s=input()
l=len(s)
dp=[[0]*4 for i in range(l)]
for i in range(l):
    if i==0:
        dp[i][3]=1
        if s[i]=="A":
            dp[i][0]=1
        elif s[i]=="?":
            dp[i][0]=1
            dp[i][3]=3
    else:
        if s[i]=="A":
            dp[i]=[(dp[i-1][0]+dp[i-1][3])%mod,dp[i-1][1],dp[i-1][2],dp[i-1][3]]
        elif s[i]=="B":
            dp[i]=[dp[i-1][0],(dp[i-1][0]+dp[i-1][1])%mod,dp[i-1][2],dp[i-1][3]]
        elif s[i]=="C":
            dp[i]=[dp[i-1][0],dp[i-1][1],(dp[i-1][1]+dp[i-1][2])%mod,dp[i-1][3]]
        else:
            dp[i]=[(3*dp[i-1][0]+dp[i-1][3])%mod,(3*dp[i-1][1]+dp[i-1][0])%mod,(3*dp[i-1][2]+dp[i-1][1])%mod,(3*dp[i-1][3])%mod]
print(dp[-1][2])

Submission status: Accepted

Solution code:
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# DP[0, 0], Aの数、ABの数、ABCの数
MOD = 10 ** 9 + 7
S = sr()
dp = [0, 0, 0]
total = 1
for s in S:
    if s == 'A':
        dp[0] += total
    elif s == 'B':
        dp[1] += dp[0]
    elif s == 'C':
        dp[2] += dp[1]
    elif s == '?':
        dp[2] = dp[2]*3 + dp[1]
        dp[1] = dp[1]*3 + dp[0]
        dp[0] = dp[0]*3 + total
        total *= 3
    total %= MOD; dp[0] %= MOD; dp[1] %= MOD; dp[2] %= MOD
    #print(dp, total)

answer = dp[2] % MOD
print(answer)

Submission status: Accepted

Solution code:
S = input()
#dp[i][four] =: i + 1番目まで見たとき,照合したケツがfourとなるものの総数
dp = [[0 for _ in range(4)] for _ in range(len(S)+1 )]
dp[0][0] = 1
mod = 10**9 + 7
for i in range(len(S)):
    if S[i] == 'A' or S[i] == '?':
        dp[i+1][1] += dp[i][0] 
        for k in range(4): dp[i+1][k] += dp[i][k]
    if S[i] == 'B' or S[i] == '?':
        dp[i+1][2] += dp[i][1]
        for k in range(4): dp[i+1][k] += dp[i][k]
    if S[i] == 'C' or S[i] == '?':
        dp[i+1][3] += dp[i][2]
        for k in range(4): dp[i+1][k] += dp[i][k]
    for k in range(4): dp[i+1][k] %= mod
print(dp[len(S)][3])