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()
mod = 1000000007
dp = [1, 0, 0, 0]
for c in s:
    newdp = [n for n in dp]
    if c == 'A':
        newdp[1] = (newdp[1] + dp[0]) % mod
    if c == 'B':
        newdp[2] = (newdp[2] + dp[1]) % mod
    if c == 'C':
        newdp[3] = (newdp[3] + dp[2]) % mod
    if c == '?':
        newdp[0] = (newdp[0] * 3) % mod
        newdp[1] = (newdp[1] * 3 + dp[0]) % mod
        newdp[2] = (newdp[2] * 3 + dp[1]) % mod
        newdp[3] = (newdp[3] * 3 + dp[2]) % mod
    dp = newdp
print(dp[3])

Submission status: Accepted

Solution code:
S = input()
MOD = 10**9+7
DP = [0]*14 # A,AB,ABC,AB?,A?,A?C,A??,?,?B,?BC,?B?,??,??C,???
for i in range(len(S)):
    if S[i] == "A":
        DP[0] += 1
    elif S[i] == "B":
        for i in range(2,5,2):
            DP[i] += DP[i//2-1] 
            DP[i] %= MOD
    elif S[i] == "C":
        for i in range(6,13,2):
            DP[i] += DP[i//2-1]
            DP[i] %= MOD
    elif S[i] == "?":
        for i in range(6,13,2):
            DP[i+1] += DP[i//2-1]
            DP[i+1] %= MOD
        for i in range(2,5,2):
            DP[i+1] += DP[i//2-1] 
            DP[i+1] %= MOD    
        DP[1] += 1
q = DP[1]
Q0 = 3**q % MOD
Q1 = int(3**(q-1) % MOD)
Q2 = int(3**(q-2) % MOD)
Q3 = int(3**(q-3) % MOD)
Q = [0,0,0,0,0,0,Q0,Q1,Q1,Q2,Q1,Q2,Q2,Q3]
ans = 0
for i in range(14):
    ans += DP[i]*Q[i] % MOD
print(ans%MOD)

Submission status: Accepted

Solution code:
S = input()

MOD = 1000000007

# a_b_c, a_b_hc, a_hb_c, a_hb_hc, ha_b_c, ha_b_hc, ha_hb_c, ha_hb_hc
count = [[0, 0, 0] for _ in range(8)]
hatena_count = 0

for c in S:
    if c == 'A':
        nums = [0,1,2,3]
        for num in nums:
            count[num][0] += 1
    elif c == 'B':
        nums = [0,1,4,5]
        for num in nums:
            count[num][1] += count[num][0]
    elif c == 'C':
        nums = [0,2,4,6]
        for num in nums:
            count[num][2] += count[num][1]
    elif c == '?':
        # hc
        nums = [1,3,5,7]
        for num in nums:
            count[num][2] += count[num][1]
        
        # hb
        nums = [2,3,6,7]
        for num in nums:
            count[num][1] += count[num][0]

        # ha
        nums = [4,5,6,7]
        for num in nums:
            count[num][0] += 1
        
        hatena_count += 1

total = 0
coef = [0, 1, 1, 2, 1, 2, 2, 3]
for i in range(8):
    total += count[i][2] * 3**(hatena_count - coef[i])

print(int(total % MOD))

Submission status: Accepted

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

A_cum = [0] * N
C_cum = [0] * N
q_sum_left = [0] * N
q_sum_right = [0] * N
for i in range(N - 1):
    s = S[i]
    if s == 'A':
        A_cum[i + 1] = A_cum[i] + 1
    else:
        A_cum[i + 1] = A_cum[i]
    if s == '?':
        q_sum_left[i + 1] = q_sum_left[i] + 1
    else:
        q_sum_left[i + 1] = q_sum_left[i]
for i in range(N - 1, 0, -1):
    s = S[i]
    if s == 'C':
        C_cum[i - 1] = C_cum[i] + 1
    else:
        C_cum[i - 1] = C_cum[i]
    if s == '?':
        q_sum_right[i - 1] = q_sum_right[i] + 1
    else:
        q_sum_right[i - 1] = q_sum_right[i]
ans = 0
for i in range(N):
    if S[i] == 'B' or S[i] == '?':
        ans = (ans + (A_cum[i] * pow(3, q_sum_left[i], mod) + q_sum_left[i] * pow(3, max(0, q_sum_left[i] - 1), mod))
               * (C_cum[i] * pow(3, q_sum_right[i], mod) + q_sum_right[i] * pow(3, max(0, q_sum_right[i] - 1), mod))) % mod

print(ans)

Submission status: Accepted

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

n = len(s)
o = [1] * (n+1)
a = [0] * (n+1)
b = [0] * (n+1)
c = [0] * (n+1)

for i in range(n):
    if s[i] == '?':
        o[i+1] = o[i] * 3
        a[i+1] = a[i] * 3 + o[i]
        b[i+1] = b[i] * 3 + a[i]
        c[i+1] = c[i] * 3 + b[i]
    else:
        o[i+1] = o[i]
        a[i+1] = a[i]
        b[i+1] = b[i]
        c[i+1] = c[i]
        if s[i] == 'A':
            a[i+1] += o[i]
        if s[i] == 'B':
            b[i+1] += a[i]
        if s[i] == 'C':
            c[i+1] += b[i]
    o[i+1] = o[i+1] % MOD
    a[i+1] = a[i+1] % MOD
    b[i+1] = b[i+1] % MOD
    c[i+1] = c[i+1] % MOD
print(c[n])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, fractions, itertools

MOD = 1000000007  # type: int


def solve(S: str):
    dp = [[0 for _ in range(4)] for _ in range(len(S)+1)]
    for i in reversed(range(len(S)+1)):
        for j in reversed(range(4)):
            if i == len(S) and j == 3:
                dp[i][j] = 1
            if j < 3 and i == len(S):
                dp[i][j] = 0
            if i < len(S):
                if j == 3:
                    if S[i] == '?':
                        m = 3
                    else:
                        m = 1
                    dp[i][3] = m * dp[i+1][3]
                if j < 3:
                    if S[i] == '?':
                        m1 = 3
                    else:
                        m1 = 1
                    if S[i] == '?' or S[i] == list('ABC')[j]:
                        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])
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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:
from functools import reduce

S = input()

MOD = 10**9 + 7


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

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

    __repr__ = __str__

    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))
        )

    def __radd__(self, other):
        return ModInt(other + self.x)

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

    def __rmul__(self, other):
        return ModInt(other * self.x)

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

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


# 動的計画法による。すなわち、
# i文字目までのA数, AB数, ABC数を求め、それらを用いて
# N文字目までのABC数を求める
_, _, _, ans = reduce(
    lambda acc, c: (
        (
            3 * acc[0] if c == '?' else
            acc[0]
        ),
        (
            acc[0] + acc[1] if c == 'A' else
            3 * acc[1] + acc[0] if c == '?' else
            acc[1]
        ),
        (
            acc[1] + acc[2] if c == 'B' else
            3 * acc[2] + acc[1] if c == '?' else
            acc[2]
        ),
        (
            acc[2] + acc[3] if c == 'C' else
            3 * acc[3] + acc[2] if c == '?' else
            acc[3]
        ),
    ),
    S,
    (ModInt(1), ModInt(0), ModInt(0), ModInt(0))
)

print(ans)

Submission status: Accepted

Solution code:
S = list(input())
N = len(S)
mod = int(1E9+7)

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

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

Submission status: Accepted

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

Submission status: Accepted

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

o = 1
a = 0
b = 0
c = 0

for i in s:
    if i == "A":
        a += o
    elif i == "B":
        b += a
    elif i == "C":
        c += b
    else:
        o, a, b, c = o*3, o+a*3, a+b*3, b+c*3

    o %= MOD
    a %= MOD
    b %= MOD
    c %= MOD

print(c)

Submission status: Accepted

Solution code:
S = input()

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

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

Submission status: Accepted

Solution code:
S = input()

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

for i in reversed(range(N)):
    m = 3 if S[i] == '?' else 1
    for j in reversed(range(3)):
        dp[i][j] = m * dp[i + 1][j]
        if S[i] == '?' or S[i] == 'ABC'[j]:
            dp[i][j] += dp[i + 1][j + 1]
        dp[i][j] %= MOD
    
    # j == 3
    dp[i][3] = m * dp[i + 1][3] % MOD
            
print(dp[0][0] % MOD)

Submission status: Accepted

Solution code:
import numpy as np


dp = np.zeros((2, 4), dtype=np.int64)
mod = int(1e9+7)
dp[0][0] = 1
for s in input():
    if s == '?':
        dp[1] = dp[0]*3
        dp[1][1:] += dp[0][:3]
    else:
        dp[1] = dp[0]
        if s == 'A':
            dp[1][1] += dp[0][0]
        elif s == 'B':
            dp[1][2] += dp[0][1]
        elif s == 'C':
            dp[1][3] += dp[0][2]
    dp[0] = np.remainder(dp[1], mod)
print(dp[0][3])

Submission status: Accepted

Solution code:
import numpy as np


dp = np.zeros((2, 4), dtype=np.int64)
mod = 1e9+7
dp[0][0] = 1
for s in input():
    if s == '?':
        dp[1] = dp[0]*3
        dp[1][1:] += dp[0][:3]
        dp[1] = np.remainder(dp[1], mod)
    else:
        dp[1] = dp[0]
        if s == 'A':
            dp[1][1] += dp[0][0]
            dp[1][1] = np.remainder(dp[1][1], mod)
        elif s == 'B':
            dp[1][2] += dp[0][1]
            dp[1][2] = np.remainder(dp[1][2], mod)
        elif s == 'C':
            dp[1][3] += dp[0][2]
            dp[1][3] = np.remainder(dp[1][3], mod)
    dp[0] = dp[1]
print(dp[0][3])

Submission status: Accepted

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

# dp[i]['A' or 'AB' or 'ABC'] := 先頭からi桁までに含まれる φ数、A数、AB数、ABC数 の数
# 便宜上 φ: 0, 'A': 1, 'AB': 2, 'ABC': 3と表現する
dp = [[0 for _ in range(4)] for _ in range(len(S) + 1)]
dp[0][0] = 1

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

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

Submission status: Accepted

Solution code:
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import math
Mod = 1000000007



def main(): #startline-------------------------------------------
    S = input()
    N = len(S)
    p = [0,0,0,1]
    for i in range(N):
        if S[i] == "A":
            p[0] += p[3]
            p[0] %= Mod
        elif S[i] == "B":
            p[1] += p[0]
            p[1] %= Mod
        elif S[i] == "C":
            p[2] += p[1]
            p[2] %= Mod
        elif S[i] == "?":
            p[2] = p[2]*3 + p[1]
            p[1] = p[1]*3 + p[0]
            p[0] = p[0]*3 + p[3]
            p[3] *= 3
            for l in range(4):
                p[l] %= Mod

    print(p[2])
if __name__ == "__main__":
    main() #endline===============================================




def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n < 2 is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))):
        if prime[i] == 1:
            for j in range(2*i,n):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n):
        if prime[i] == 1:
            res.append(i)
    return res

class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py

    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)

Submission status: Accepted

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

a = b = ans = 0
a_old = b_old = ans_old = 0

q = 1 
for s in S:
    if s == "A":
        a = (a_old + q) % mod
        b = b_old
        ans = ans_old
    elif s == "B":
        a = a_old
        b = (b_old + a_old) % mod
        ans = ans_old
    elif s == "C":
        a = a_old
        b = b_old
        ans = (ans_old + b_old) % mod
    else:
        a = (3 * a_old + q) % mod
        b = (3 * b_old + a_old) % mod
        ans = (3 * ans_old + b_old) % mod
        q = q * 3 % mod
    a_old = a
    b_old = b
    ans_old = ans
    # print(a, b, ans)

print(ans)

Submission status: Accepted

Solution code:
s=input()
l=len(s)
mod=10**9+7
dp=[[0,0,0,0] for _ in range(l+1)]
for i in range(l,-1,-1):
  for j in range(3,-1,-1):
    if i==l:
      if j==3:
        dp[i][j]=1
      else:
        dp[i][j]=0
    else:
      if s[i]=='?':
        dp[i][j]=dp[i+1][j]*3
      else:
        dp[i][j]=dp[i+1][j]
      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 makelist(n, m):
    return [[0 for _ in range(m)] for _ in range(n)]

S = "0" + input()
l = len(S) - 1


MOD = int(1e9) + 7
dp = makelist(l+1, 4)

def toInt(c):
    return [ord(c) - 65]

dp[0][-1] = 1

for i in range(1, l+1):
    if S[i] == 'A':
        dp[i][-1] = dp[i-1][-1]
        dp[i][0] = (dp[i-1][0] + dp[i-1][-1]) % MOD
        dp[i][1] = dp[i-1][1]
        dp[i][2] = dp[i-1][2]
    elif S[i] == 'B':
        dp[i][-1] = dp[i-1][-1]
        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][-1] = dp[i-1][-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]) % MOD
    elif S[i] == '?':
        dp[i][-1] = (dp[i-1][-1] * 3) % MOD
        dp[i][0] = ((dp[i-1][0] * 3) % MOD + dp[i-1][-1])  % MOD
        dp[i][1] = ((dp[i-1][1] * 3) % MOD + dp[i-1][0]) % MOD
        dp[i][2] = ((dp[i-1][2] * 3) % MOD + dp[i-1][1]) % MOD

print(dp[l][2])

Submission status: Accepted

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

import re
# import numpy as np
# from scipy.misc import perm
# from scipy.misc import comb

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
INF = int(1e18)
MOD = int(1e9)+7 # 10^9 + 7

def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# dp[i][j]
def init_dp_table(i, j, init=INF):
  return [[ init for _ in range(j)] for _ in range(i)]

########

S = input()

dp = init_dp_table(len(S)+1, 4, 0)
dp[0][0] = 1

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

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8

def ri():
    return int(input())

def rl():
    return list(input().split())

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

MOD = 10**9+7

def main():
    s = input()
    dp = [[0 for _ in range(4)] for _ in range(len(s)+1)]
    dp[0][0] = 1
    for i, c in enumerate(s):
        if c == '?':
            for j in range(4):
                dp[i+1][j] = 3*dp[i][j]
        else:
            for j in range(4):
                dp[i+1][j] = dp[i][j]
        if c == 'A' or c == '?':
            dp[i+1][1] += dp[i][0]
        if c == 'B' or c == '?':
            dp[i+1][2] += dp[i][1]
        if c == 'C' or c == '?':
            dp[i+1][3] += dp[i][2]
        if i & 1:
            for j in range(4):
                dp[i+1][j] %= MOD

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#ABC104 D

import sys
import math
import bisect
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter


mod = 10**9 + 7

s = list(input())
n = len(s)
#見るA,B,Cを仮定して
#dp[i][j] := i文字までみたとき、
#            j = 0 := A,B,C全部入っていない
#            j = 1 := Aだけ入っている
#            j = 2 := A,Bだけ入っている
#            j = 3 := A,B,C全て入っている
#           状態のABC数

dp = [[0]*4 for _ in range(n+1)]
dp[0][0] = 1
for i in range(n):
    if s[i] == '?':
        for j in range(4):
            #A,B,Cそれぞれに変換して進めることができるため3倍
            #jの状態変化なし
            dp[i+1][j] = 3*dp[i][j] % mod
    else:
        for j in range(4):
            dp[i+1][j] = dp[i][j]
    if s[i] == 'A':
        #状態0→1に変えることができる
        dp[i+1][1] += dp[i][0]
        dp[i+1][1] %= mod
    elif s[i] == 'B':
        #状態1→2に変えることができる
        dp[i+1][2] += dp[i][1]
        dp[i+1][2] %= mod
    elif s[i] == 'C':
        #状態2→3に変えることができる
        dp[i+1][3] += dp[i][2]
        dp[i+1][3] %= mod
    elif s[i] == '?':
        #状態0→1,1→2,2→3に変えることができる
        for j in range(3):
            dp[i+1][j+1] += dp[i][j]
            dp[i+1][j+1] %= mod
print(dp[n][3])

Submission status: Accepted

Solution code:
S = input()
N = len(S)
MOD = 10**9 + 7
mask = 'ABC'

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

for i in range(N, -1, -1) :
    for j in range(4) :
        if i == N :
            if j == 3 :
                dp[i][j] = 1
            else :
                dp[i][j] = 0
        else :
            if j == 3 :
                weight = 3 if S[i] == '?' else 1
                dp[i][j] = weight * dp[i+1][j]
            else :
                weight = 3 if S[i] == '?' else 1
                able = 1 if (S[i] == mask[j] or S[i] == '?') else 0
                dp[i][j] = weight * dp[i+1][j] + able * dp[i+1][j+1]
            dp[i][j] %= MOD


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

Submission status: Accepted

Solution code:
INF = 10**9+7
s = input()
dp = [[0,0,0,0] for _ in range(len(s) + 10)]

dp[0][0] = 1

for i in range(len(s)):
    for j in range(4):
        if s[i] != '?':
            dp[i+1][j] = (dp[i+1][j]+dp[i][j]) % INF
        else:
            dp[i+1][j] = (dp[i+1][j]+dp[i][j] * 3) % INF
    if s[i] == 'A' or s[i] == '?':
        dp[i+1][1] = (dp[i+1][1]+dp[i][0]) % INF
    if s[i] == 'B' or s[i] == '?':
        dp[i+1][2] = (dp[i+1][2]+dp[i][1]) % INF
    if s[i] == 'C' or s[i] == '?':
        dp[i+1][3] = (dp[i+1][3]+dp[i][2]) % INF

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

Submission status: Accepted

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

dp = [[0]*5 for _ in range(ls+1)]

dp[0][0] = 1

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

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

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7
s = input()
dp = [[0] * 4 for _ in range(len(s) + 1)]
dp[0][0] = 1
# dp[sの何文字目まで見たか][未取得0->A取得1->B取得2->C取得3]

for i, ss in enumerate(s):
    for j in range(4):
        dp[i + 1][j] += dp[i][j] * (1 if ss != '?' else 3)
        # i文字目を取らないケース

    if ss == 'A':
        dp[i + 1][1] += dp[i][0]
    elif ss == 'B':
        dp[i + 1][2] += dp[i][1]
    elif ss == 'C':
        dp[i + 1][3] += dp[i][2]
    elif ss == '?':
        dp[i + 1][1] += dp[i][0]  # Aに変えた
        dp[i + 1][2] += dp[i][1]  # Bに変えた
        dp[i + 1][3] += dp[i][2]  # Cに変えた
    # i文字目を取るケース

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

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

"""
i文字目の文字で処理を場合分け
それぞれ、取る場合と取らない場合の処理を書く
'?'のときで、文字を取らない場合、
ABCに変える3パターンそれぞれで取らない処理を行うので、3倍になる
"""

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
MOD = 1000000007


def main():
  S = str(input())
  dp = [[0 for _ in range(3)] for _ in range(len(S)+1)]
  A,AB,ABC = [0,1,2]
  wc_num = 1
  for i,s in enumerate(S):
    if s in "A?":
      dp[i+1][A] = (dp[i+1][A]+dp[i][A]+wc_num) % MOD
      dp[i+1][AB] = (dp[i+1][AB]+dp[i][AB]) % MOD
      dp[i+1][ABC] = (dp[i+1][ABC]+dp[i][ABC]) % MOD
    if s in "B?":
      dp[i+1][A] = (dp[i+1][A]+dp[i][A]) % MOD
      dp[i+1][AB] = (dp[i+1][AB]+dp[i][AB]+dp[i][A]) % MOD
      dp[i+1][ABC] = (dp[i+1][ABC]+dp[i][ABC]) % MOD
    if s in "C?":
      dp[i+1][A] = (dp[i+1][A]+dp[i][A]) % MOD
      dp[i+1][AB] = (dp[i+1][AB]+dp[i][AB]) % MOD
      dp[i+1][ABC] = (dp[i+1][ABC]+dp[i][ABC]+dp[i][AB]) % MOD
    if s == "?":
      wc_num = (wc_num*3) % MOD
  print(dp[len(S)][ABC])



if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
mod = 10**9+7
S = list(input())
Thankyou = 1
DP=[]
#DP[x][y] x+1文字目までを見たときの、
#y=0,1,2 : A,AB,ABCの登場回数
if S[0] == "A" or S[0]=="?":
    DP.append([1,0,0])
    if S[0]=="?":
        Thankyou = 3
else:
    DP.append([0,0,0])
for i,s in enumerate(S):

    if i==0:continue
    a,b,c = DP[i-1]
    if s=="A":
        DP.append([(a+Thankyou)%mod,b,c])
    elif s=="B":
        DP.append([a,(a+b)%mod,c])
    elif s=="C":
        DP.append([a,b,(b+c)%mod])
    else:
        DP.append([(Thankyou+3*a)%mod,(a+3*b)%mod,(b+3*c)%mod])
        Thankyou *= 3
        Thankyou %= mod
print(DP[len(S)-1][2]%mod)

Submission status: Accepted

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

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

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

Submission status: Accepted

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

s = [0]*4

s[0] = 1

for c in S:
    if c == "?":
        s = [s[0]*3,s[1]*3+s[0],s[2]*3+s[1],s[3]*3+s[2]]
        for i in range(4):
            s[i] %= MOD
    else:
        i = "ABC".find(c)
        s[i+1] += s[i] % MOD
print(s[3]%MOD)

Submission status: Accepted

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

dp=[[0]*3 for i in range(l)]
mod=10**9+7
c=0

for i in range(l):
    if s[i]=="A":
        dp[i][0]=dp[i-1][0]+pow(3,c,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]
        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]
    else:
        dp[i][0]=dp[i-1][0]*3+pow(3,c,mod)
        dp[i][1]=dp[i-1][1]*3+dp[i-1][0]
        dp[i][2]=dp[i-1][2]*3+dp[i-1][1]
        c+=1
    dp[i][0]=dp[i][0]%mod
    dp[i][1]=dp[i][1]%mod
    dp[i][2]=dp[i][2]%mod

print(dp[-1][2])

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
mod=10**9+7
S=input()
N=len(S)
Acnt=[[0,0] for i in range(N+2)]
Ccnt=[[0,0] for i in range(N+2)]
for i in range(N):
    Acnt[i+1]=Acnt[i].copy()
    Ccnt[-i-2]=Ccnt[-i-1].copy()
    if S[i]=="A":
        Acnt[i+1][0]+=1
    if S[i]=="?":
        Acnt[i+1][1]+=1
    if S[-i-1]=="C":
        Ccnt[-i-2][0]+=1
    if S[-i-1]=="?":
        Ccnt[-i-2][1]+=1
Acnt[N+1]=Acnt[N]
Ccnt[-N-2]=Ccnt[-N-1]
ans=0
ruijo=[1]*(N+1)
for i in range(N):
    ruijo[i+1]=ruijo[i]*3%mod
ruijo.append(0)
for i in range(N):
    if S[i]=="B" or S[i]=="?":
        a,b,c,d=0,0,0,0
        a=Acnt[i][0]*Ccnt[i+2][0]*ruijo[Acnt[i][1]+Ccnt[i+2][1]]%mod
        if Ccnt[i+2][1]>0:
            b=Acnt[i][0]*Ccnt[i+2][1]*ruijo[Acnt[i][1]+Ccnt[i+2][1]-1]%mod
        if Acnt[i][1]>0:
            c=Acnt[i][1]*Ccnt[i+2][0]*ruijo[Acnt[i][1]+Ccnt[i+2][1]-1]%mod
        if Acnt[i][1]>0 and Ccnt[i+2][1]>0:
            d=Acnt[i][1]*Ccnt[i+2][1]*ruijo[Acnt[i][1]+Ccnt[i+2][1]-2]%mod
        ans=(ans+a+b+c+d)%mod
print(ans)

Submission status: Accepted

Solution code:
mo=10**9+7
s=input()
n=len(s)
dp=[[0]*(1+n) for i in range(3)]
cc=0
for i in range(n):
    c=s[i]
    if c=='A':
        da,db,dc,dd=1,0,0,1
    elif c=='B':
        da,db,dc,dd=0,1,0,1
    elif c=='C':
        da,db,dc,dd=0,0,1,1
    elif c=='?':
        da,db,dc,dd=1,1,1,3
        
    dp[0][i+1]=dp[0][i]*dd+da*pow(3,cc,mo)
    dp[1][i+1]=dp[1][i]*dd+dp[0][i]*db
    dp[2][i+1]=dp[2][i]*dd+dp[1][i]*dc
    dp[0][i+1]%=mo
    dp[1][i+1]%=mo
    dp[2][i+1]%=mo
    if c=='?':
        cc+=1

print(dp[2][n]%mo)

Submission status: Accepted

Solution code:
mo=10**9+7
s=input()
n=len(s)
dp=[[0]*(1+n) for i in range(3)]
cc=0
for i in range(n):
    c=s[i]
    if c=='A':
        da=1
        db=0
        dc=0
        dd=1
    elif c=='B':
        da=0
        db=1
        dc=0
        dd=1
    elif c=='C':
        da=0
        db=0
        dc=1
        dd=1
    elif c=='?':
        da=1
        db=1
        dc=1
        dd=3
        
    dp[0][i+1]=dp[0][i]*dd+da*pow(3,cc,mo)
    dp[1][i+1]=dp[1][i]*dd+dp[0][i]*db
    dp[2][i+1]=dp[2][i]*dd+dp[1][i]*dc
    dp[0][i+1]%=mo
    dp[1][i+1]%=mo
    dp[2][i+1]%=mo
    if c=='?':
        cc+=1

print(dp[2][n]%mo)

Submission status: Accepted

Solution code:
M = 10 ** 9 + 7
S = input()
A = 0
AB = 0
ABC = 0
X = 1
for c in S:
    if c == 'C':
        ABC = (ABC + AB) % M
    elif c == 'B':
        AB = (AB + A) % M
    elif c == 'A':
        A = (A + X) % M
    elif c == '?':
        ABC = (3 * ABC + AB) % M
        AB = (3 * AB + A) % M
        A = (3 * A + X) % M
        X = (3 * X) % M
print(ABC)