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:
s = input()

dp_prev = [1, 0, 0, 0]

MOD_BASE = 1000000007

for c in s:
    dp_new = [dp_prev[i] for i in range(0, 4)]
    for i in range(0, 4):
        if c == "A":
            dp_new[1] = dp_prev[0] + dp_prev[1]

        elif c == "B":
            dp_new[2] = dp_prev[1] + dp_prev[2]

        elif c == "C":
            dp_new[3] = dp_prev[2] + dp_prev[3]

        else:
            dp_new[0] = dp_prev[0] * 3
            dp_new[1] = dp_prev[0] + dp_prev[1] * 3
            dp_new[2] = dp_prev[1] + dp_prev[2] * 3
            dp_new[3] = dp_prev[2] + dp_prev[3] * 3
            
    dp_prev = [x % MOD_BASE for x in dp_new]

ans = dp_prev[3]
print(ans)

Submission status: Accepted

Solution code:
s = input()

dp_prev = [1, 0, 0, 0]

MODE_BASE = 1000000007

for c in s:
    dp_new = [dp_prev[i] for i in range(0, 4)]
    for i in range(0, 4):
        if c == "A":
            dp_new[1] = (dp_prev[0] + dp_prev[1]) % MODE_BASE

        elif c == "B":
            dp_new[2] = (dp_prev[1] + dp_prev[2]) % MODE_BASE

        elif c == "C":
            dp_new[3] = (dp_prev[2] + dp_prev[3]) % MODE_BASE

        else:
            dp_new[0] = (dp_prev[0] * 3) % MODE_BASE
            dp_new[1] = (dp_prev[0] + dp_prev[1] * 3) % MODE_BASE
            dp_new[2] = (dp_prev[1] + dp_prev[2] * 3) % MODE_BASE
            dp_new[3] = (dp_prev[2] + dp_prev[3] * 3) % MODE_BASE

    dp_prev = dp_new

ans = dp_prev[3]
print(ans)

Submission status: Accepted

Solution code:
S = input()
N = len(S)
ans = 0
MOD = 10**9+7
dp = [[0]*4 for _ in range(2)]
dp[0][0] = 1

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

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

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

Submission status: Accepted

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


S = sys.stdin.buffer.readline().decode().rstrip()

a = 0
ab = 0
abc = 0
q = 0
for i, s in enumerate(S):
    if s == 'C':
        abc += ab
    if s == 'B':
        ab += a
    if s == 'A':
        a += pow(3, q, MOD)
    if s == '?':
        abc = abc * 3 + ab
        ab = ab * 3 + a
        a = a * 3 + pow(3, q, MOD)
        q += 1
    a %= MOD
    ab %= MOD
    abc %= MOD
    # print(s, a, ab, abc)
print(abc)

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
#mint
class ModInt:
    def __init__(self, x):
        self.x = x % mod
    
    def __str__(self):
        return str(self.x)
    
    __repr__ = __str__

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

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

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

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

    __rmul__ = __mul__

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

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

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

def main():
    S=ST()
    N=len(S)
    dp = [[ModInt(0)]*4 for _ in range(N)] #dp[i][j]:=i番目までで、ABCのj文字目まで完成している場合の数
    dp[0][0]+=1
    for i,s in enumerate(S):
        if i==0:
            if s in "A?":
                dp[0][1]+=1
                if s == "?":
                    dp[0][0]*=3
            continue

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

    print(dp[-1][-1])
if __name__ == '__main__':
    main()

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

S = input()
N = len(S)

# dp[i][j] := i文字目まで見て、ABCのうちj文字目まで選んだ状態の通り数
dp = list2d(N+1, 4, 0)
dp[0][0] = 1
for i in range(N):
    s = S[i]
    for j in range(4):
        # 今回の文字を選ばない
        if s == '?':
            # ?は3通り遷移させる
            dp[i+1][j] += dp[i][j] * 3
            dp[i+1][j] %= MOD
        else:
            dp[i+1][j] += dp[i][j]
            dp[i+1][j] %= MOD
        # 今回の文字を選ぶ
        if j < 3:
            # 条件に合わせて次の文字へ進む
            if s == '?' or s == 'A' and j == 0 \
                        or s == 'B' and j == 1 \
                        or s == 'C' and j == 2:
                dp[i+1][j+1] += dp[i][j]
                dp[i+1][j+1] %= MOD
# N文字目まで見て、3文字選び終わっている通り数
print(dp[N][3])

Submission status: Accepted

Solution code:
S = input()
mod = 10**9 + 7
dic = {'': 1, 'A': 0, 'B': 0, 'C': 0}
for s in S:
    if s == 'A':
        dic[s] += dic['']

    elif s == 'B':
        dic[s] += dic['A']

    elif s == 'C':
        dic[s] += dic['B']

    elif s == '?':
        dic['C'] = dic['C'] * 3 + dic['B']
        dic['B'] = dic['B'] * 3 + dic['A']
        dic['A'] = dic['A'] * 3 + dic['']
        dic[''] *= 3

    dic[''] %= mod
    dic['A'] %= mod
    dic['B'] %= mod
    dic['C'] %= mod

print(dic['C']%mod)

Submission status: Accepted

Solution code:
import numpy as np
MOD = 10**9 + 7
def solve(s):
    a = np.zeros(4, dtype=int)
    a[0] = 1
    for c in s:
        t = 2 * int(c == "?") + 1
        b = t * a % MOD
        if c == "A":
            b[1] += a[0]
        elif c == "B":
            b[2] += a[1]
        elif c == "C":
            b[3] += a[2]
        else:
            b[1:] += a[:-1]
        a = b
    return a[3] % MOD

s = input()
print(solve(s))

Submission status: Accepted

Solution code:
import numpy as np
MOD = 10**9 + 7
def solve(s):
    n = len(s)
    a = np.zeros(4, dtype=int)
    b = a.copy()
    a[0] = 1
    for c in s:
        t = 2 * int(c == "?") + 1
        b = t * a % MOD
        if c == "A":
            b[1] += a[0]
        elif c == "B":
            b[2] += a[1]
        elif c == "C":
            b[3] += a[2]
        else:
            b[1:] += a[:-1]
        a = b
    return a[3] % MOD

s = input()
print(solve(s))

Submission status: Accepted

Solution code:
import numpy as np
MOD = 10**9 + 7
def solve(s):
    n = len(s)
    dp = np.zeros((n+1, 4), dtype=int)
    dp[0,0] = 1
    for i in range(n):
        t = 2 * int(s[i] == "?") + 1
        dp[i+1] = t * dp[i] % MOD
        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,1:] += dp[i,:-1]
    return dp[n][3] % MOD

s = input()
print(solve(s))

Submission status: Accepted

Solution code:
s=input()
l=len(s)
dp=[4*[0]for _ in range(l+1)]
dp[0][0]=1
for i in range(1,l+1):
  si=s[i-1]
  for j in range(4):dp[i][j]=dp[i-1][j]*((si=="?")*2+1)
  if si=="A":dp[i][1]+=dp[i-1][0]
  if si=="B":dp[i][2]+=dp[i-1][1]
  if si=="C":dp[i][3]+=dp[i-1][2]
  if si=="?":
    dp[i][1]+=dp[i-1][0]
    dp[i][2]+=dp[i-1][1]
    dp[i][3]+=dp[i-1][2]
  for j in range(4):dp[i][j]%=10**9+7
print(dp[-1][-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
limit = 100000
mod = 10**9+7
lpow = [False] * (limit+1)
lpow[0] = 1
def pow(n,p):
    if p<0:return 0
    if lpow[p]:
        return lpow[p]
    else:
        if p % 2 == 0:
            ret = (pow(n,p//2)**2) % mod
        else:
            ret = ((pow(n,p//2)**2)*n) % mod
        lpow[p] = ret
        return ret

def main():
    s=input()
    res = 0
    ca = 0
    cc = s.count("C")
    cw = 0
    aw = s.count("?")
    for c in s:
        if c == "A":
            ca += 1
        elif c == "C":
            cc -= 1
        elif c == "B":
            res += ca*cc*pow(3,aw)+ca*(aw-cw)*pow(3,aw-1)+cw*cc*pow(3,aw-1)+cw*(aw-cw)*pow(3,aw-2)
            res %= mod
        elif c == "?":
            res += ca*cc*pow(3,aw-1)+ca*(aw-cw-1)*pow(3,aw-2)+cw*cc*pow(3,aw-2)+cw*(aw-cw-1)*pow(3,aw-3)
            res %= mod
            cw += 1

    print(res)

main()

Submission status: Accepted

Solution code:
mod = 10**9+7
def pow(n,p):
    res=1
    while p >0:
        if p%2==0:
            n = n**2 % mod
            p //= 2
        else:
            res = res * n % mod
            p -= 1
    return res % mod

def main():
    s=input()
    res = 0
    ca = 0
    cc = s.count("C")
    cw = 0
    aw = s.count("?")
    for c in s:
        if c == "A":
            ca += 1
        elif c == "C":
            cc -= 1
        elif c == "B":
            res += ca*cc*pow(3,aw)+ca*(aw-cw)*pow(3,aw-1)+cw*cc*pow(3,aw-1)+cw*(aw-cw)*pow(3,aw-2)
            res %= mod
        elif c == "?":
            res += ca*cc*pow(3,aw-1)+ca*(aw-cw-1)*pow(3,aw-2)+cw*cc*pow(3,aw-2)+cw*(aw-cw-1)*pow(3,aw-3)
            res %= mod
            cw += 1

    print(res)

main()

Submission status: Accepted

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

A = 0
AB = 0
Q = 1
ans = 0

for s in S:
    if s == '?':
        ans = (3 * ans + AB) % MOD
        AB = (3 * AB + A) % MOD
        A = (3 * A + Q) % MOD
        Q = Q * 3 % MOD
    elif s == 'A':
        A = (A + Q) % MOD
    elif s == 'B':
        AB = (AB + A) % MOD
    elif s == 'C':
        ans = (ans + AB) % MOD

print(ans)

Submission status: Accepted

Solution code:
def main():
    S = input()
    dp = [[0] * 4 for _ in range(len(S) + 5)]
    dp[0][0] = 1
    MOD = 10 ** 9 + 7

    for i in range(len(S)):
        for j in range(4):
            if S[i] == '?':
                dp[i+1][j] += dp[i][j] * 3
            else:
                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[len(S)][3])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

S = input().rstrip()
N = len(S)
mod = 10**9+7

# dp[i][0] -> A
# dp[i][1] -> AB
# dp[i][2] -> ABC
dp = [0, 0, 0]
k = 1
for i in range(N):
    if S[i] == "A":
        dp[0] += k
    elif S[i] == "B":
        dp[1] += dp[0]
    elif S[i] == "C":
        dp[2] += dp[1]
    else:
        dp[2] = 3*dp[2] + dp[1]
        dp[1] = 3*dp[1] + dp[0]
        dp[0] = 3*dp[0] + k
        k = k*3%mod
    
    dp[0] %= mod
    dp[1] %= mod
    dp[2] %= mod

print(dp[2])

Submission status: Accepted

Solution code:
S = input()
INF = 10**9+7
dp = [0,0,0]
N = 1
for i in range(len(S)):
  if S[i]=='A':
    dp[0] += N
    dp[0] %= INF
  elif S[i]=='B':
    dp[1] += dp[0]
    dp[1] %= INF
  elif S[i]=='C':
    dp[2] += dp[1]
    dp[2] %= INF
  else:
    a = dp[0]
    b = dp[1]
    dp[0] = N + dp[0]*3
    dp[1] = a + dp[1]*3
    dp[2] = b + dp[2]*3
    dp[0] %= INF
    dp[1] %= INF
    dp[2] %= INF
    N = (3*N)%INF
print(dp[2]%INF)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int


def solve(S: str):
    N = len(S)
    # 0:文字列の総数 1:Aの数  2:ABの数 3:ABCの数
    ## dp[i][j] = i文字目まで見たときに状態jの数
    ## answer: dp[N][3]

    dp = [[0]*4 for _ in range(N+1)]
    dp[0][0] = 1
    for i in range(N):
        for j in (0,1,2,3):
            if S[i] == "?":
                dp[i+1][j] += dp[i][j]*3
            else:
                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]%MOD)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int


def solve(S: str):
    N = len(S)
    # 0:文字列の総数 1:Aの数  2:ABの数 3:ABCの数
    ## dp[i][j] = i文字目まで見たときに状態jの数
    ## answer: dp[N][3]

    dp = [[0]*4 for _ in range(N+1)]
    dp[0][0] = 1
    for i in range(N):
        for j in (0,1,2,3):
            if S[i] == "?":
                dp[i+1][j] += dp[i][j]*3
            else:
                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]%MOD)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
S = input()
N = len(S)
MOD = 10**9 + 7
DP = [[1] * 4 for _ in range(N + 1)]
# initialize
DP[N][3] = 1
DP[N][0] = 0
DP[N][1] = 0
DP[N][2] = 0

for i in range(N-1, -1, -1):
    for j in range(3, -1, -1):
        DP[i][j] = DP[i+1][j] * (3 if S[i]=='?' else 1)
        if j<3:
            DP[i][j] += DP[i + 1][j + 1] * (1 if (S[i]=='ABC'[j] or S[i]=='?') else 0)
        DP[i][j] %= MOD

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

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7
sl = list(input())

a = 0
ab = 0
abc = 0
p = 1
for s in sl:
    if s == "A":
        a += p
        a %= mod
    elif s == "B":
        ab += a
        ab %= mod
    elif s == "C":
        abc += ab
        abc %= mod
    elif s == "?":
        abc = 3*abc + ab
        abc %= mod
        ab = 3*ab + a
        ab %= mod
        a = 3*a + p
        a %= mod
        p *= 3
        p %= mod
print(abc)

Submission status: Accepted

Solution code:
S = input()
MOD = 10**9 + 7
dp = [0] * 3  # num of ..A, ..AB, ..ABC
pp = [0] * 3
nq = 0
for s in S:
    pp = dp
    dp = pp.copy()
    if s == 'A':
        dp[0] += pow(3, nq, MOD)
    elif s == 'B':
        dp[1] += pp[0]
    elif s == 'C':
        dp[2] += pp[1]
    else:
        dp[0] += pp[0]*2 + pow(3, nq, MOD)
        dp[1] += pp[1]*2 + pp[0]
        dp[2] += pp[2]*2 + pp[1]
        nq += 1
    dp[0] %= MOD
    dp[1] %= MOD
    dp[2] %= MOD
print(dp[2])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    S=input()
    n=len(S)
    dp=[0]*4
    dp[0]=1
    for s in S:
        ndp=dp[:] if(s!='?') else [3*d%MOD for d in dp]
        if(s=='A' or s=='?'):
            ndp[1]+=dp[0]
            ndp[1]%=MOD
        if(s=='B' or s=='?'):
            ndp[2]+=dp[1]
            ndp[2]%=MOD
        if(s=='C' or s=='?'):
            ndp[3]+=dp[2]
            ndp[3]%=MOD
        dp=ndp
    print(dp[3])
resolve()

Submission status: Accepted

Solution code:
#0:09
"""
ABC数
遷移を考える問題
dp[どこまでみたか][その時の状態] = になりうる場合の数
"""
S = input()
n = len(S)

dp = [[0]*3 for i in range(n+1)]
cnt = 0 #はてなの数
#初期は後で構築
mod = 10**9 + 7 

X = 1
for i in range(n):
    if S[i] == "A":
        dp[i+1][0] = dp[i][0] + X
        dp[i+1][1] = dp[i][1]
        dp[i+1][2] = dp[i][2]
    elif S[i] == "B":
        dp[i+1][0] = dp[i][0]
        dp[i+1][1] = (dp[i][0] + dp[i][1]) % mod
        dp[i+1][2] = dp[i][2]
    elif S[i] == "C":
        dp[i+1][0] = dp[i][0]
        dp[i+1][1] = dp[i][1]
        dp[i+1][2] = (dp[i][1] + dp[i][2]) % mod
    elif S[i] == "?":
        dp[i+1][0] = (dp[i][0] * 3 + X) % mod
        dp[i+1][1] = (dp[i][1] * 3)%mod + (dp[i][0]) % mod
        dp[i+1][2] = (dp[i][2] * 3)%mod + (dp[i][1]) % mod        
        X = (X*3)%mod
print(dp[n][2]%mod)

Submission status: Accepted

Solution code:
S = input()
dp = [[1, 0, 0, 0] for _ in range(len(S))]
if S[0] == 'A':
    dp[0][1] = 1
if S[0] == '?':
    dp[0][1] = 1
    dp[0][0] *= 3

for i, v in enumerate(S):
    if i == 0:
        continue
    if v == '?':
        dp[i][0] = dp[i-1][0] * 3 % 1000000007
        dp[i][1] = (dp[i-1][1] * 3 + dp[i-1][0]) % 1000000007
        dp[i][2] = (dp[i-1][2] * 3 + dp[i-1][1]) % 1000000007
        dp[i][3] = (dp[i-1][3] * 3 + dp[i-1][2]) % 1000000007
        continue

    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]
    if v == 'A':
        dp[i][1] += dp[i-1][0]
        dp[i][1] %= 1000000007
    if v == 'B':
        dp[i][2] += dp[i-1][1]
        dp[i][2] %= 1000000007
    if v == 'C':
        dp[i][3] += dp[i-1][2]
        dp[i][3] %= 1000000007

print(dp[-1][3])

Submission status: Accepted

Solution code:
S = input()
N = len(S)
A = [0] * (N+1)
C = [0] * (N+1)
X = [0] * (N+1)
Y = [0] * (N+1)

for i in range(N):
    A[i+1] = A[i] + (1 if S[i] == "A" else 0)
    X[i+1] = X[i] + (1 if S[i] == "?" else 0)
for i in range(N)[::-1]:
    C[i] = C[i+1] + (1 if S[i] == "C" else 0)
    Y[i] = Y[i+1] + (1 if S[i] == "?" else 0)

P = 10**9 + 7
POW = [1]
for i in range(2*N+10):
    POW.append(POW[-1]*3%P)
    
ans = 0
for i in range(N):
    if S[i] == "B" or S[i] == "?":
        a, x, c, y = A[i], X[i], C[i+1], Y[i+1]
        ans += a * c * POW[x+y]
        if x: ans += x * c * POW[x+y-1]
        if y: ans += a * y * POW[x+y-1]
        if x and y: ans += x * y * POW[x+y-2]
        ans %= P
print(ans)

Submission status: Accepted

Solution code:
# D - We Love ABC

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

n_possible = 1 # その場所以前の文字列としてあり得るパターン
A = 0 # その場所以前の文字列におけるA数
B = 0
C = 0

for s in S:
    if s == "A":
        A += n_possible
    elif s == "B":
        B += A
    elif s == "C":
        C += B
    else:
        # X = 3*X + Y
        # この場所の？を (AorABorABCの一部に含めない場合) + (AorABorABCの一部に含める場合)
        C = 3*C + B
        B = 3*B + A
        A = 3*A + n_possible
        n_possible *= 3
    n_possible %= MOD
    A %= MOD
    B %= MOD
    C %= MOD
        
print(C)

Submission status: Accepted

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

n = 1
a = 0
ab = 0
abc = 0
for s in S:
    if s == 'A':
        a += n
    elif s == 'B':
        ab += a
    elif s == 'C':
        abc += ab
    else: #s == '?'
        abc = 3 * abc + ab
        ab = 3 * ab + a
        a = 3 * a + n
        n *= 3
    abc %= MOD
    ab %= MOD
    a %= MOD
    n %= MOD
    # print (a, ab, abc)
# print (a)
# print (ab)
print (abc)

Submission status: Accepted

Solution code:
s=input()
n=len(s)
mod=10**9+7
dp=[[0]*3 for i in range(n)]
data=[0]*(n)
data[0]=1
for i in range(1,n):
    data[i]=data[i-1]*3%mod
count=0
if s[0]=="A":
    dp[0][0]=1
if s[0]=="?":
    dp[0][0]=1
    count+=1
for i in range(1,n):
    if s[i]=="A":
        dp[i][0]=(dp[i-1][0]+data[count])%mod
        dp[i][1]=dp[i-1][1]
        dp[i][2]=dp[i-1][2]
    elif s[i]=="B":
        dp[i][0]=dp[i-1][0]
        dp[i][1]=(dp[i-1][1]+dp[i-1][0])%mod
        dp[i][2]=dp[i-1][2]
    elif s[i]=="C":
        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])%mod
    else:
        dp[i][0]=(3*dp[i-1][0]+data[count])%mod
        dp[i][1]=(3*dp[i-1][1]+dp[i-1][0])%mod
        dp[i][2]=(3*dp[i-1][2]+dp[i-1][1])%mod
        count+=1
print(dp[n-1][2])

Submission status: Accepted

Solution code:
s=input()
n=len(s)
dp=[4*[0]for i in range(n+1)]
dp[0][0]=1
for i in range(1,n+1):
  for j in range(4):
    dp[i][j]+=dp[i-1][j]*((s[i-1]=="?")*2+1)
  if s[i-1] in "A?":dp[i][1]+=dp[i-1][0]
  if s[i-1] in "B?":dp[i][2]+=dp[i-1][1]
  if s[i-1] in "C?":dp[i][3]+=dp[i-1][2]
  for j in range(4):dp[i][j]%=10**9+7
#for i in range(n+1):print(dp[i],(" "+s)[i])
print(dp[-1][-1])

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7


def add(x, y):
    ret = x + y
    if ret >= MOD:
        ret -= MOD
    return ret


S = input().strip()

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

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

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

print(dp[-1][3])

Submission status: Accepted

Solution code:
s=input()
a=[1,0,0,0]
for i in s:
    if i=="A": a[1]+=a[0]
    elif i=="B": a[2]+=a[1]
    elif i=="C": a[3]+=a[2]
    else: a=[ a[0]*3 ] + [ a[j+1]*3+a[j] for j in range(3) ]

    a=[a[i]%1000000007 for i in range(4)]
print(a[3])

Submission status: Accepted

Solution code:
from sys import stdin

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

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

for k in range(len(S) - 1, -1, -1):
    if S[k] == '?':
        dp[k][3] = 3 * dp[k + 1][3]
    else:
        dp[k][3] = dp[k + 1][3]
    dp[k][3] %= inf

for i in range(len(S) - 1, -1, -1):
    for j in range(2, -1, -1):
        if S[i] == '?':
            dp[i][j] += 3 * dp[i + 1][j]
        else:
            dp[i][j] += dp[i + 1][j]
        s = 'ABC'
        if S[i] == '?' or S[i] == s[j]:
            dp[i][j] += dp[i + 1][j + 1]
        dp[i][j] %= inf

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

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
S = input()
N = len(S)
target = 'ABC'
n = len(target)
cur = [0]*(n+1)
cur[0] = 1
for s in S:
    for w in range(n):
        if s == target[w]:
            cur[w+1] += cur[w]
            cur[w+1] %= MOD
            break
    else: # case of '?'
        for w in range(n-1,-1,-1):
            cur[w+1] = (cur[w+1]*3 + cur[w]) % MOD
        cur[0] *= 3
        cur[0] %= MOD
print(cur[-1])

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

S = input()

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

for i in reversed(range(N)):
    for j in reversed(range(4)):
        dp[i][j] = dp[i + 1][j] * (3 if S[i] == "?" else 1)
        if j < 3 and (S[i] == "?" or S[i] == "ABC"[j]):
            dp[i][j] += dp[i + 1][j + 1]
        dp[i][j] %= MOD

print(dp[0][0])

Submission status: Accepted

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

    S = input()

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

    for i in reversed(range(N + 1)):
        for j in reversed(range(4)):
            if i == N:
                dp[i][j] = int(j == 3)
            else:
                dp[i][j] = dp[i + 1][j] * (3 if S[i] == "?" else 1)
                if j < 3 and (S[i] == "?" or S[i] == "ABC"[j]):
                    dp[i][j] += dp[i + 1][j + 1]
                dp[i][j] %= MOD

    print(dp[0][0])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

S = input()

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

for i in reversed(range(N + 1)):
    for j in reversed(range(4)):
        if i == N:
            dp[i][j] = int(j == 3)
        else:
            dp[i][j] = dp[i + 1][j] * (3 if S[i] == "?" else 1)
            if j < 3 and (S[i] == "?" or S[i] == "ABC"[j]):
                dp[i][j] += dp[i + 1][j + 1]
            dp[i][j] %= MOD

print(dp[0][0])

Submission status: Accepted

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

a = [0]*n
b = [0]*n
c = [0]*n
d = [0]*n

x = 0
y = 0
for i in range(n):
    a[i] = x
    b[i] = y
    if s[i] == 'A':
        x += 1
    elif s[i] == '?':
        y += 1

x = 0
y = 0
for i in range(n-1,-1,-1):
    c[i] = x
    d[i] = y
    if s[i] == 'C':
        x += 1
    elif s[i] == '?':
        y += 1

def f(A,B,C,D):
    if B+D == 0:
        return pow(3,B+D,mod)*A*C%mod
    if B+D == 1:
        return pow(3,B+D,mod)*A*C%mod + pow(3,B+D-1,mod)*B*C%mod + pow(3,B+D-1,mod)*A*D%mod

    return pow(3,B+D,mod)*A*C%mod + pow(3,B+D-1,mod)*B*C%mod + pow(3,B+D-1,mod)*A*D%mod + pow(3,B+D-2,mod)*B*D%mod

res = 0
for i in range(1,n-1):
    if s[i] == 'B' or s[i]=='?':
        res = (res+f(a[i],b[i],c[i],d[i]))%mod
print(res%mod)

Submission status: Accepted

Solution code:
s = input()

dp = [[0 for j in range(4)] for i in range(len(s)+1)]
dp[0][0] = 1
mod = 10**9+7
for i in range(len(s)):
    for j in range(4):
        dp[i+1][j] = dp[i][j]
        dp[i+1][j] %= mod
        dp[i][j] %= mod
    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] * 2
        dp[i+1][1] += dp[i][1] * 2 + dp[i][0]
        dp[i+1][2] += dp[i][2] * 2 + dp[i][1]
        dp[i+1][3] += dp[i][3] * 2 + dp[i][2]

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

Submission status: Accepted

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

ret = 0
la, rc = 0, S.count('C')
lq, rq = 0, S.count('?')

def comb(ac, q) :
    if q == 0 :
        return ac * pow(3, q, mod) % mod
    else :
        p = pow(3, q - 1, mod)
        return (q * p + ac * p * 3) % mod

for s in S :
    if s == '?' :
        rq -= 1
        ret += comb(la, lq) * comb(rc, rq)
        ret %= mod
        lq += 1
    elif s == 'A' :
        la += 1
    elif s == 'B' :
        ret += comb(la, lq) * comb(rc, rq)
        ret %= mod
    elif s == 'C' :
        rc -= 1
    
print(ret)