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()
count = 0
a, c, q = 0, 0, 0
n = len(s)
for i in range(n):
    if s[i] == 'C':
        c += 1
    elif s[i] == '?':
        q += 1
    else:
        continue
c = 3 * c + q
p = pow(3, q-3)
for i in range(n):
    if s[i] == 'A':
        a += 3
    elif s[i] == 'C':
        c -= 3
    elif s[i] == 'B':
        count += 3*a*c
    else:
        c -= 1
        count += a*c
        a += 1
print(int(count*p) % 1000000007)

Submission status: Accepted

Solution code:
s = input()
count = 0
a, c, q = 0, 0, 0
for i in range(len(s)):
    if s[i] == 'C':
        c += 1
    elif s[i] == '?':
        q += 1
    else:
        continue
c = 3 * c + q
p = pow(3, q-3)
for i in range(len(s)):
    if s[i] == 'A':
        a += 3
    elif s[i] == 'C':
        c -= 3
    elif s[i] == 'B':
        count += 3*a*c
    else:
        c -= 1
        count += a*c
        a += 1
print(int(count*p) % 1000000007)

Submission status: Accepted

Solution code:
S = input()

MOD = 10**9 + 7
dp = [[0] * 4 for _ in range(len(S) + 1)]
dp[len(S)][3] = 1
for i in range(len(S))[::-1]:
    dp[i][3] = 3 * dp[i + 1][3] if S[i] == "?" else dp[i + 1][3]
    dp[i][3] %= MOD
    if S[i] == "?":
        dp[i][0] = (3 * dp[i + 1][0] + dp[i + 1][1]) % MOD
        dp[i][1] = (3 * dp[i + 1][1] + dp[i + 1][2]) % MOD
        dp[i][2] = (3 * dp[i + 1][2] + dp[i + 1][3]) % MOD
    else:
        dp[i][0] = (dp[i + 1][0] + int(S[i] == "A") * dp[i + 1][1]) % MOD
        dp[i][1] = (dp[i + 1][1] + int(S[i] == "B") * dp[i + 1][2]) % MOD
        dp[i][2] = (dp[i + 1][2] + int(S[i] == "C") * dp[i + 1][3]) % MOD
print(dp[0][0])

Submission status: Accepted

Solution code:
s = input()

dp1 = {'A': 0, 'AB': 0, 'ABC': 0}
dp2 = {'A': 0, 'AB': 0, 'ABC': 0}

c = 1000000000 + 7
n = len(s)
tmp = [1]*n
for i in range(1, n):
    tmp[i] = (tmp[i-1] * 3)%c

count = 0
for i in range(n):
    if s[i] == '?':
        dp2['A'] = dp1['A']*3 + tmp[count]
        dp2['AB'] = dp1['AB']*3 + dp1['A']
        dp2['ABC'] = dp1['ABC']*3 + dp1['AB']
        count += 1
    elif s[i] == 'A':
        dp2['A'] = dp1['A'] + tmp[count]
        dp2['AB'] = dp1['AB']
        dp2['ABC'] = dp1['ABC']
    elif s[i] == 'B':
        dp2['A'] = dp1['A']
        dp2['AB'] = dp1['AB'] + dp1['A']
        dp2['ABC'] = dp1['ABC']
    elif s[i] == 'C':
        dp2['A'] = dp1['A']
        dp2['AB'] = dp1['AB']
        dp2['ABC'] = dp1['ABC'] + dp1['AB']

    dp1['ABC'] = dp2['ABC'] % c
    dp1['AB'] = dp2['AB'] % c
    dp1['A'] = dp2['A'] % c

    #print(i, dp1)

print(dp1['ABC'])

Submission status: Accepted

Solution code:
s = input()

dp1 = {'A': 0, 'AB': 0, 'ABC': 0}
dp2 = {'A': 0, 'AB': 0, 'ABC': 0}

c = 1000000000 + 7
n = len(s)
tmp = [1]*n
for i in range(1, n):
    tmp[i] = (tmp[i-1] * 3)%c
#print(tmp)

count = 0
for i in range(n):
    #dp2 = {'A': 0, 'AB': 0, 'ABC': 0}

    # if s[i] == '?':
    #     dp2['A'] = dp1['A']*3 + (3**count)
    # elif s[i] == 'A':
    #     dp2['A'] = dp1['A'] + (3**count)
    # else:
    #     dp2['A'] = dp1['A']
    #
    # if s[i] == '?':
    #     dp2['AB'] = dp1['AB']*3 + dp1['A']
    # elif s[i] == 'B':
    #     dp2['AB'] = dp1['AB'] + dp1['A']
    # else:
    #     dp2['AB'] = dp1['AB']
    #
    # if s[i] == '?':
    #     dp2['ABC'] = dp1['ABC']*3 + dp1['AB']
    # elif s[i] == 'C':
    #     dp2['ABC'] = dp1['ABC'] + dp1['AB']
    # else:
    #     dp2['ABC'] = dp1['ABC']
    #
    # if s[i] == '?':
    #     count += 1

    if s[i] == '?':
        dp2['A'] = dp1['A']*3 + tmp[count]
        dp2['AB'] = dp1['AB']*3 + dp1['A']
        dp2['ABC'] = dp1['ABC']*3 + dp1['AB']
        count += 1
    elif s[i] == 'A':
        dp2['A'] = dp1['A'] + tmp[count]
        dp2['AB'] = dp1['AB']
        dp2['ABC'] = dp1['ABC']
    elif s[i] == 'B':
        dp2['A'] = dp1['A']
        dp2['AB'] = dp1['AB'] + dp1['A']
        dp2['ABC'] = dp1['ABC']
    elif s[i] == 'C':
        dp2['A'] = dp1['A']
        dp2['AB'] = dp1['AB']
        dp2['ABC'] = dp1['ABC'] + dp1['AB']

    # for j in dp2.keys():
    #     dp2[j] = dp2[j] % c\
    # dp1 = dp2

    dp1['ABC'] = dp2['ABC'] % c
    dp1['AB'] = dp2['AB'] % c
    dp1['A'] = dp2['A'] % c

    #print(i, dp1)

print(dp1['ABC'])

Submission status: Accepted

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

A1, A2, C1, C2 = [1]*N, [1]*N, [1]*N, [1]*N
a, aa = 0, 0
c, cc = 0, 0
for i in range(1,N):
    if S[i-1] == "A":
        a += 1
    elif S[i-1] == "?":
        aa += 1
    A1[i] = a
    A2[i] = aa

for i in range(1,N):
    if S[N-1-i+1] == "C":
        c += 1
    elif S[N-1-i+1] == "?":
        cc +=1
    C1[N-1-i] = c
    C2[N-1-i] = cc

answer = 0
for i in range(1,N-1):
    if S[i] in ("B", "?"):
        ta = 0
        tc = 0
        if A2[i] == 0:
            ta = A1[i]
        else:
            ta = pow(3, A2[i], mod)*A1[i] +  pow(3,A2[i]-1,mod)*A2[i]
        if C2[i]==0:
            tc = C1[i]
        else:
            tc = pow(3,C2[i],mod)*C1[i] + pow(3,C2[i]-1,mod)*C2[i]
        answer += ta*tc
        answer %= mod


print(answer)

Submission status: Accepted

Solution code:
s = input()
count = 0
a, qa, c, qc = 0, 0, 0, 0
def calc(x, qx, y, qy):
    return ((3*x+qx) * (3*y+qy) * pow3q)
#x*y*pow(3,qx+qy)+qx*y*pow(3,qx+qy-1)+x*qy*pow(3,qx+qy-1)+qx*qy*pow(3,qx+qy-2)
for i in range(len(s)):
    if s[i] == 'C':
        c += 1
    elif s[i] == '?':
        qc += 1
    else:
        continue
pow3q = pow(3, qc-3)
for i in range(len(s)):
    if s[i] == 'A':
        a += 1
    elif s[i] == 'C':
        c -= 1
    elif s[i] == 'B':
        count += 3*calc(a, qa, c, qc)
    else:
        qc -= 1
        count += calc(a, qa, c, qc)
        qa += 1
print(int(count) % 1000000007)

Submission status: Accepted

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

N = len(S)
A1,A2,C1,C2 = [1]*N,[1]*N,[1]*N,[1]*N
a,aa = 0,0
c,cc = 0,0
for i in range(1,N):
    if S[i-1]=="A":
        a += 1
    elif S[i-1]=="?":
        aa += 1
    A1[i],A2[i] = a,aa
for i in range(1,N):
    if S[N-1-i+1]=="C":
        c += 1
    elif S[N-1-i+1]=="?":
        cc += 1
    C1[N-1-i] = c
    C2[N-1-i] = cc

Ans = 0
for i in range(1,N-1):
    if S[i] in ("B","?"):
        ta,tc = 0,0
        if A2[i]==0:
            ta = A1[i]
        else:
            ta = pow(3,A2[i],mod)*A1[i] + pow(3,A2[i]-1,mod)*A2[i]
        if C2[i]==0:
            tc = C1[i]
        else:
            tc = pow(3,C2[i],mod)*C1[i] + pow(3,C2[i]-1,mod)*C2[i]
        Ans += ta*tc
        Ans %= mod

print(Ans)

Submission status: Accepted

Solution code:
S = input()

mod = 1000000007

dp = [[0, 0, 0] for _ in range(len(S))]

mul = 1

if S[0] == "A":
    dp[0][0] = 1
elif S[0] == "?":
    dp[0][0] = 1
    mul *= 3

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

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

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

s = input()
n = len(s)

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

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

for i in range(n, 0, -1):
  sr[i-1] = sr[i][:]
  if s[i-1] == 'A': sr[i-1][0] += 1
  elif s[i-1] == 'B': sr[i-1][1] += 1
  elif s[i-1] == 'C': sr[i-1][2] += 1
  else: sr[i-1][3] += 1

ans = 0
for i in range(n):
  if s[i] == 'B' or s[i] == '?':
    a = c = 0
    a += sl[i][0] * pow(3, sl[i][3], MOD)
    if sl[i][3] > 0: a += sl[i][3] * pow(3, sl[i][3]-1, MOD)
    c += sr[i+1][2] * pow(3, sr[i+1][3], MOD)
    if sr[i+1][3] > 0: c += sr[i+1][3] * pow(3, sr[i+1][3]-1, MOD)
    ans = (ans + a*c) % MOD

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
mod = 1000000007

S = input()
L = len(S)
i = L-1
A = [0 for _ in range(L+1)]
C = [0 for _ in range(L+1)]
Q = [0 for _ in range(L+1)]
while i >= 0:
    Q[i] = Q[i+1]
    A[i] = A[i+1]
    C[i] = C[i+1]

    if S[i] == '?':
        Q[i] = Q[i+1] + 1
    else:
        Q[i] = Q[i+1]

    if S[i] == 'A':
        A[i] = A[i+1] + 1
    else:
        A[i] = A[i+1]
    if S[i] == 'C':
        C[i] = C[i+1] + 1
    else:
        C[i] = C[i+1]
    i -= 1

ans = 0
for i in range(L):
    if S[i] in ('B','?'):
        a = A[0] - A[i]
        qleft = Q[0] - Q[i]
        c = C[i+1]
        qright = Q[i+1]
        if qleft > 0:
            LEFT = a*pow(3,qleft,mod) + qleft*pow(3,qleft-1,mod)
        else: 
            LEFT = a*pow(3,qleft,mod)
        if qright > 0:
            RIGHT = c*pow(3,qright,mod) + qright*pow(3,qright-1,mod)
        else:
            RIGHT = c*pow(3,qright,mod)
        number = (LEFT * RIGHT)%mod
        ans = (ans + number)%mod
print(ans)

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect
 
def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

P = 10**9 + 7

S = input()
N = len(S)

psumA = [0] + list(accumulate(c == 'A' for c in S))
psumC = [0] + list(accumulate(c == 'C' for c in S))
psumX = [0] + list(accumulate(c == '?' for c in S))
Q = psumX[N]

ans = 0
for i in range(1, N-1):
  if S[i] == 'B':
    ans += psumA[i] * (psumC[N] - psumC[i+1]) % P * pow(3, Q, P) % P
    if Q >= 1:
      ans += psumX[i] * (psumC[N] - psumC[i+1]) % P * pow(3, Q-1, P) % P
      ans += psumA[i] * (psumX[N] - psumX[i+1]) % P * pow(3, Q-1, P) % P
    if Q >= 2:
      ans += psumX[i] * (psumX[N] - psumX[i+1]) % P * pow(3, Q-2, P) % P
  if S[i] == '?':
    ans += psumA[i] * (psumC[N] - psumC[i+1]) % P * pow(3, Q-1, P) % P
    if Q >= 2:
      ans += psumX[i] * (psumC[N] - psumC[i+1]) % P * pow(3, Q-2, P) % P
      ans += psumA[i] * (psumX[N] - psumX[i+1]) % P * pow(3, Q-2, P) % P
    if Q >= 3:
      ans += psumX[i] * (psumX[N] - psumX[i+1]) % P * pow(3, Q-3, P) % P

print(ans % P)

Submission status: Accepted

Solution code:
S = input()
def ABC(S):
    N = len(S)
    dp = [[0 for j in range(4)] for i in range(N+1)]
    model = 'ABC'
    p = 10**9 + 7
    for i in range(N, -1, -1):
        for j in range(3,-1,-1):
            if i == N and j == 3:
                dp[i][j] = 1
            elif i == N and j < 3:
                dp[i][j] = 0
            elif i < N and j == 3:
                if S[i] == '?':
                    dp[i][j] = 3 * dp[i+1][j] % p
                else:
                    dp[i][j] = dp[i+1][j] % p
            else:
                if S[i] == '?':
                    m1 = 3
                else:
                    m1 = 1
                if S[i] == '?' or S[i] == model[j]:
                    m2 = 1
                else:
                    m2 = 0
                dp[i][j] = (m1 * dp[i+1][j])%p + m2 * (dp[i+1][j+1])%p
    return dp[0][0] % p
print(ABC(S))

Submission status: Accepted

Solution code:
S = input()
P = 10**9+7
d = [[0 for j in range(4)] for i in range(len(S)+1)]

d[len(S)][3] = 1
#d[len(S)][0--2] = 0
for i in range(len(S)-1,-1,-1):
	d[i][3] = ((3 if S[i] == "?" else 1) * d[i+1][3])%P
	d[i][2] = ((3 if S[i] == "?" else 1) * d[i+1][2])%P
	d[i][2] += (1 if S[i] == "C" or S[i] == "?" else 0) * d[i+1][3]
	d[i][1] = ((3 if S[i] == "?" else 1) * d[i+1][1])%P
	d[i][1] += (1 if S[i] == "B" or S[i] == "?" else 0) * d[i+1][2]
	d[i][0] = ((3 if S[i] == "?" else 1) * d[i+1][0])%P
	d[i][0] += (1 if S[i] == "A" or S[i] == "?" else 0) * d[i+1][1]
print(d[0][0] % P)

Submission status: Accepted

Solution code:

a = 0
_ = 0
ab = 0
a_ = 0
_b = 0
__ = 0
abc = 0
ab_ = 0
a_c = 0
_bc = 0
a__ = 0
_b_ = 0
__c = 0
___ = 0

T = input()

for c in T:
    if c == "A":
        a += 1
    if c == "B":
        ab += a
        _b += _
    if c == "C":
        abc += ab
        a_c += a_
        _bc += _b
        __c += __
    if c == "?":
        ___ += __
        __ += _
        _ += 1
        a__ += a_
        a_ += a
        _b_ += _b
        ab_ += ab

print(sum([
    abc * 3**(max(_ - 0, 0)),
    ab_ * 3**(max(_ - 1, 0)),
    a_c * 3**(max(_ - 1, 0)),
    _bc * 3**(max(_ - 1, 0)),
    a__ * 3**(max(_ - 2, 0)),
    _b_ * 3**(max(_ - 2, 0)),
    __c * 3**(max(_ - 2, 0)),
    ___ * 3**(max(_ - 3, 0)),
]) % (10**9 + 7))

Submission status: Accepted

Solution code:
inf = 1000000007
 
a = 0
ab = 0
abc = 0
r = 1
 
s = input()
 
for c in s:
    if c == "A":
        a += r
    elif c == "B":
        ab += a
    elif c == "C":
        abc += ab
    else:
        abc = abc * 3 + ab
        ab = ab * 3 + a
        a = a * 3 + r
        r *= 3
        
    a %= inf
    ab %= inf
    abc %= inf
    r %= inf

print(abc)

Submission status: Accepted

Solution code:
p = [1, 0, 0, 0]
m = 1e9 + 7
def mod(x):
    return int(x % m)

for s in input():
    if s == 'A' :
        p[1] = mod(p[0] + p[1])
    if s == 'B' :
        p[2] = mod(p[1] + p[2])
    if s == 'C' :
        p[3] = mod(p[2] + p[3])
    if s == '?':
        p[3] = mod(p[2] + p[3] * 3)
        p[2] = mod(p[1] + p[2] * 3)
        p[1] = mod(p[0] + p[1] * 3)
        p[0] = mod(p[0] * 3)
        
print(int(p[3] % m))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
def inpl(): return list(map(int, input().split()))
MOD = 10**9 + 7
S = input()
A, B, C = 0, 0, 0
q = 0

for i, s in enumerate(S, start=1):
    if s == "A":
        A = (A + pow(3, q, MOD))%MOD
    elif s == "B":
        B = (B + A)%MOD
    elif s == "C":
        C = (C + B)%MOD
    elif s == "?":
        A, B, C = (3*A + pow(3, q, MOD))%MOD, (3*B + A)%MOD, (3*C + B)%MOD
        q += 1

print(C)

Submission status: Accepted

Solution code:
def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y


# mを法とするaの乗法的逆元
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

S = input()
a = 0
c = S.count("C")
ql = 0
qr = S.count("?")
ans = 0
mod = 10**9 + 7
ql3 = 1
qr3 = 1
for i in range(qr):
    qr3 *= 3
    qr3 %= mod
for s in S:
    if s == "C":
        c -= 1
    elif s == "?":
        qr -= 1
        qr3 *= modinv(3, mod)
        qr3 %= mod

    if s == "B" or s == "?":
        ans += ((ql * ql3 * modinv(3, mod) + a * ql3) % mod) * ((qr * qr3 * modinv(3, mod) + c * qr3) % mod)
        ans %= mod

    if s == "A":
        a += 1
    elif s == "?":
        ql += 1
        ql3 *= 3
        ql3 %= mod

print(ans)

Submission status: Accepted

Solution code:
s = input()

m = 1000000007
dp = [0] * 4
dp[0] = 1

for c in s:
  if c=='A':
    dp[1] += dp[0]
  elif c=='B':
    dp[2] += dp[1]
  elif c=='C':
    dp[3] += dp[2]
  elif c=='?':
    dp = [(dp[0]*3)%m, (dp[0]+dp[1]*3)%m, (dp[1]+dp[2]*3)%m, (dp[2]+dp[3]*3)%m]

print(dp[3]%m)

Submission status: Accepted

Solution code:
from collections import Counter
S = input()
MOD = 10 ** 9 + 7
ans = 0
front = [0, 0, 0, 0]
back = [0, 0, 0, 0]
m = { 'A': 0, 'B': 1, 'C': 2, '?': 3 }
for c in S:
  back[m[c]] += 1

pow3 = [1]
for i in range(max(3, back[3])):
  pow3.append((pow3[-1] * 3) % MOD)

for i in range(len(S)):
  c = S[i]
  back[m[c]] -= 1
  # Bの位置を固定
  if c == 'B' or c == '?':
    fbsum = front[3] + back[3]
    # ?を使わない
    ans += front[0] * back[2] * (pow3[fbsum])
    # Aだけ?をつかう
    ans += front[3] * back[2] * (pow3[fbsum - 1])
    # Cだけ?をつかう
    ans += front[0] * back[3] * (pow3[fbsum - 1])
    # 両方?をつかう
    ans += front[3] * back[3] * (pow3[fbsum - 2])
    ans %= MOD
  front[m[c]] += 1

print(int(ans))

Submission status: Accepted

Solution code:
S=input()
N=len(S)
mod=pow(10,9)+7
dpa=[0]*N
dpl=[0]*N
dpc=[0]*N
dpr=[0]*N
for i in range(1,N):
    if S[i-1]=='A':
        dpa[i]=dpa[i-1]+1
        dpl[i]=dpl[i-1]
    elif S[i-1]=='?':
        dpa[i]=dpa[i-1]
        dpl[i]=dpl[i-1]+1
    else:
        dpa[i]=dpa[i-1]
        dpl[i]=dpl[i-1]
for i in range(N-2,-1,-1):
    if S[i+1]=='C': 
        dpc[i]=dpc[i+1]+1
        dpr[i]=dpr[i+1]
    elif S[i+1]=='?': 
        dpc[i]=dpc[i+1]
        dpr[i]=dpr[i+1]+1
    else: 
        dpc[i]=dpc[i+1]
        dpr[i]=dpr[i+1]
ans=0 
for i in range(1,N-1):
    if S[i]=='?' or S[i]=='B':
        x=pow(3,dpl[i],mod)
        y=pow(3,max(dpl[i]-1,0),mod)
        z=pow(3,dpr[i],mod)
        w=pow(3,max(dpr[i]-1,0),mod)
        x=(x*dpa[i])%mod
        y=(y*dpl[i])%mod
        z=(z*dpc[i])%mod
        w=(w*dpr[i])%mod
        s=(x+y)%mod
        u=(z+w)%mod
        t=(s*u)%mod
        ans = (ans+t)%mod
print(ans)

Submission status: Accepted

Solution code:
s=input()

a=0
ab=0
abc=0
q=1
m=10**9+7

for i in range(len(s)):
  if s[i]=="A":
    a=(a+q)%m
  elif s[i]=="B":
    ab=(ab+a)%m
  elif s[i]=="C":
    abc=(abc+ab)%m
  else:
    abc=(abc*3+ab)%m
    ab=(ab*3+a)%m
    a=(a*3+q)%m
    q=(q*3)%m
print(abc)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(int(1e9))
mod = int((1e9) + 7)

S = input()
N = len(S)

mem = [[0] * 4 for _ in range(N)]
used = [[0] * 4 for _ in range(N)]
ch = ['A', 'B', 'C']

def dfs(idx, num):
    
    if idx == N:
        return (num == 3)
    
    if used[idx][num]:
        return mem[idx][num]
    used[idx][num] = 1

    a, b = (0, 0);
    if S[idx] == '?':
        if(num < 3):
            a = dfs(idx + 1, num + 1)    
        b = 3 * dfs(idx + 1, num)
    else:
        if num < 3 and S[idx] == ch[num]:
            a = dfs(idx + 1, num + 1)
        b = dfs(idx + 1, num)
        
    res = (a + b) % mod
    mem[idx][num] = res
    return res

ans = dfs(0, 0)
print (ans)

Submission status: Accepted

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

dp = [[0] * 4] * (lenS + 1)
dp[0] = [1, 0, 0, 0]

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

Submission status: Accepted

Solution code:
mod = 1000000007


s = raw_input()
n_a = n_ab = n_abc = 0
p = 1

for c in s:
    if c == "A":
        n_a = (n_a + p) % mod
    elif c == "B":
        n_ab = (n_ab + n_a) % mod
    elif c == "C":
        n_abc = (n_abc + n_ab) % mod
    elif c == "?":
        n_abc = (n_abc * 3 + n_ab) % mod
        n_ab = (n_ab * 3 + n_a) % mod
        n_a = (n_a * 3 + p) % mod
        p = (p * 3) % mod

    # print n_a, n_ab, n_abc

print n_abc % mod

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(int(1e9))
mod = int((1e9) + 7)

S = input()
N = len(S)

p = [1] * (N+1)
for i in range(1, N+1):
    p[i] = p[i-1]
    if S[N-i] == '?':
        p[i] = p[i] * 3 % mod
p.reverse()

mem = [[0] * 3 for _ in range(N)]
used = [[0] * 3 for _ in range(N)]
ch = ['A', 'B', 'C']



def dfs(idx, num):
    if num == 3:
        return 1 * p[idx]
    
    if idx == N:
        return 0
    
    if used[idx][num]:
        return mem[idx][num]
    used[idx][num] = 1

    a, b = (0, 0);
    if S[idx] == '?':
        a = dfs(idx + 1, num + 1)    
        b = 3 * dfs(idx + 1, num)
    else:
        if S[idx] == ch[num]:
            a = dfs(idx + 1, num + 1)
        b = dfs(idx + 1, num)
        
    res = (a + b) % mod
    mem[idx][num] = res
    return res

ans = dfs(0, 0) % mod
print (ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
AtoZ = [chr(i) for i in range(65,65+26)]
atoz = [chr(i) for i in range(97,97+26)]

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


def ex_square(n,k): #n^k
	if k == 0:
		ans = 1
	elif k % 2 == 0:
		ans = ex_square(n, k//2) ** 2
	else:
		ans = ex_square(n,k-1) * n
	ans %= mod
	return ans

S = list(input())

aa = [0]
bb = [0]
cc = [0]
qq = [0]
Sa = Sb =Sc = Sq = 0
for s in S:
	if s == 'A':
		Sa += 1
	elif s == 'B':
		Sb += 1
	elif s == 'C':
		Sc += 1
	elif s == '?':
		Sq += 1
	aa.append(Sa)
	bb.append(Sb)
	cc.append(Sc)
	qq.append(Sq)

ans = 0
for i,s in enumerate(S):
	if s == 'B':
		SUMq = Sq
	elif s == '?':
		SUMq = Sq-1
	elif s == 'A' or s == 'C':
		continue

	Lq = qq[i]
	Rq = SUMq-Lq
	La = aa[i]
	Rc = Sc - cc[i]

	if SUMq == 0:
		ex = 1
		exx = exxx = 0
	elif SUMq == 1:
		ex = 3
		exx = 1
		exxx = 0
	else:
		exxx= ex_square(3,SUMq-2)
		exx = exxx*3%mod
		ex = exx*3%mod

	ans1 = (ex  * (La*Rc)%mod)%mod
	ans2 = (exx * (Lq*Rc)%mod)%mod
	ans3 = (exx * (La*Rq)%mod)%mod
	ans4 = (exxx * (Lq*Rq)%mod)%mod
	ans += (ans1+ans2+ans3+ans4)%mod
	ans %= mod

print(ans)

Submission status: Accepted

Solution code:
S=input()

emp=1
A=0
AB=0
ABC=0

big = 10**9+7



for a in S:
    if a == 'A':
        (emp,A,AB,ABC)=(emp,emp+A,AB,ABC)
    if a == 'B':
        (emp,A,AB,ABC)=(emp,A,A+AB,ABC)
    if a == 'C':
        (emp,A,AB,ABC)=(emp,A,AB,AB + ABC)
    if a == '?':
        (emp,A,AB,ABC)=(3*emp%big, (emp+ 3*A) %big, (A+ 3*AB)%big,(AB + 3*ABC)%big)

print(ABC%big)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
S=input()

e=1
a=0
ab=0
abc=0
M=10**9+7
for i in S:
    if i == "A":
        a=(a+e)%M
    if i == "B":
        ab = (ab+a)%M
    if i == "C":
        abc=(abc+ab)%M
    if i == "?":
        abc=(3*abc+ab)%M
        ab = (3*ab+a)%M
        a=(3*a+e)%M
        e=e*3%M
#    print(e,a,ab,abc)

print(abc)

Submission status: Accepted

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

def ad(x, y):
	return int((x + y) % MOD)


a = s[:2].count("A")
b = s[:2].count("B")
c = s[:2].count("C")
q = s[:2].count("?")


qq = 0
aq = 0
qb = 0
ab = 0

if s[:2] == "??":
	qq += 1
elif s[:2] == "A?":
	aq += 1
elif s[:2] == "?B":
	qb += 1
elif s[:2] == "AB":
	ab += 1

if s[2] == "A":
	a += 1
elif s[2] == "B":
	qb += q
	ab += a
	b += 1
elif s[2] == "C":
	c += 1
elif s[2] == "?":
	qq += q
	aq += a
	q += 1

three = 0
two = 0
one = 0
zero = 0

if s[:3] == "???":
	three += 1
elif s[:3] == "A??" or s[:3] == "?B?" or s[:3] == "??C":
	two += 1
elif s[:3] == "AB?" or s[:3] == "A?C" or s[:3] == "?BC":
	one += 1
elif s[:3] == "ABC":
	zero += 1

#print(zero)


for i in range(3, len(s)):
	if s[i] == "A":
		a += 1
	elif s[i] == "B":
		qb = ad(qb, q)
		ab = ad(ab, a)
		b += 1
	elif s[i] == "C":
		two = ad(two, qq)
		one = ad(one, qb)
		one = ad(one, aq)
		zero = ad(zero, ab)
		c += 1
	elif s[i] == "?":
		three = ad(three, qq)
		two = ad(two, aq)
		two = ad(two, qb)
		one = ad(one, ab)
		qq = ad(qq, q)
		aq = ad(aq, a)
		q += 1

ans = 0
ans = ad(ans, (3 ** (q - 3)) * three)
ans = ad(ans, (3 ** (q - 2)) * two)
ans = ad(ans, (3 ** (q - 1)) * one)
ans = ad(ans, (3 ** q) * zero)

print(ans)

Submission status: Accepted

Solution code:
string = input().strip()
ac = 0
bc = 0
cc = 0
ac2 = 0
bc2 = 0
bc3 = 0
bc4 = 0
cc2 = 0
cc3 = 0
cc4 = 0
cc5 = 0
cc6 = 0
cc7 = 0
cc8 = 0
for s in string:
    if s == 'A':
        ac += 1
    elif s == 'B':
        bc += ac
        bc2 += ac2
    elif s == 'C':
        cc += bc
        cc2 += bc2
        cc3 += bc3
        cc4 += bc4
    elif s == '?':
        cc5 += bc2
        cc6 += bc3
        cc7 += bc4
        cc8 += bc

        bc3 += ac
        bc4 += ac2

        ac2 += 1

#print(cc)
#print(cc3)
result = (cc7) + ((cc4+cc5+cc6) * 3) + ((cc2+cc3+cc8)*9) + (cc*27)
#print(ac2)
result *= pow(3, ac2-3)
print(int(result%(pow(10,9)+7)))

Submission status: Accepted

Solution code:
import numpy as np
s=input()
A=np.array([0,0,0,0])
B=np.array([0,0,0,0])
C=np.array([0,0,0,0])
t=0
for c in s:
	if c=="A":
		A[0]+=1
	if c=="B":
		B+=A
	if c=='C':
		C+=B
	if c=='?':
		C+=np.roll(B,1)
		B[1]+=A[0]
		B[2]+=A[1]
		A[1]+=1
		t+=1
ans=0
for i in range(4):
	ans+=pow(3,t-i)*C[i]
print(int(ans%1000000007))

Submission status: Accepted

Solution code:
import numpy as np
s=input()
A=np.array([0,0,0,0])
B=np.array([0,0,0,0])
C=np.array([0,0,0,0])
t=0
for c in s:
	if c=="A":
		A[0]+=1
	if c=="B":
		B+=A
	if c=='C':
		C+=B
	if c=='?':
		C[1]+=B[0]
		C[2]+=B[1]
		C[3]+=B[2]
		B[1]+=A[0]
		B[2]+=A[1]
		A[1]+=1
		t+=1
ans=0
for i in range(4):
	ans+=pow(3,t-i)*C[i]
print(int(ans%1000000007))

Submission status: Accepted

Solution code:
import numpy as np
s=input()
wayA=np.array([0,0,0,0])
wayB=np.array([0,0,0,0])
wayC=np.array([0,0,0,0])
hatena=0
for c in s:
	if c=="A":
		wayA[0]+=1
	if c=="B":
		wayB+=wayA
	if c=='C':
		wayC+=wayB
	if c=='?':
		wayC[1]+=wayB[0]
		wayC[2]+=wayB[1]
		wayC[3]+=wayB[2]
		wayB[1]+=wayA[0]
		wayB[2]+=wayA[1]
		wayA[1]+=1
		hatena+=1
ans=0
for i in range(4):
	ans+=pow(3,hatena-i)*wayC[i]
print(int(ans%1000000007))

Submission status: Accepted

Solution code:
import numpy as np
s=input()
n=len(s)
MOD=1000000007
wayA=np.array([0,0,0,0])
wayB=np.array([0,0,0,0])
wayC=np.array([0,0,0,0])
hatena=0
for c in s:
	if c=="A":
		wayA[0]+=1
	if c=="B":
		wayB+=wayA
	if c=='C':
		wayC+=wayB
	if c=='?':
		wayC[1]=wayC[1]+wayB[0]
		wayC[2]=wayC[2]+wayB[1]
		wayC[3]=wayC[3]+wayB[2]
		wayB[1]=wayB[1]+wayA[0]
		wayB[2]=wayB[2]+wayA[1]
		wayA[1]=wayA[1]+1
		hatena+=1
ans=0
for i in range(0,4):
	ans+=pow(3,hatena-i)*wayC[i]
print(int(ans%MOD))

Submission status: Accepted

Solution code:
mod=1000000007
a=0
ab=0
abc=0
Q=1
S=input()
for i in S:
    if i=="A":
        a+=Q
    elif i=="B":
        ab+=a
    elif i=="C":
        abc+=ab
    else:
        abc=abc*3+ab
        ab=ab*3+a
        a=a*3+Q
        Q=Q*3
    a=a%mod
    ab=ab%mod
    abc=abc%mod
    Q=Q%mod
print(abc)

Submission status: Accepted

Solution code:
import numpy as np
s=input()
n=len(s)
MOD=1000000007
wayA=np.array([0,0,0,0])
wayB=np.array([0,0,0,0])
wayC=np.array([0,0,0,0])
hatena=0
for c in s:
	if c=="A":
		wayA[0]+=1
	if c=="B":
		wayB+=wayA
	if c=='C':
		wayC+=wayB
	if c=='?':
		wayC[1]=wayC[1]+wayB[0]
		wayC[2]=wayC[2]+wayB[1]
		wayC[3]=wayC[3]+wayB[2]
		wayB[1]=wayB[1]+wayA[0]
		wayB[2]=wayB[2]+wayA[1]
		wayA[1]=wayA[1]+1
		hatena+=1
ans=0
for i in range(0,4):
	ans=ans+pow(3,hatena-i)*wayC[i]
	ans=ans%MOD
print(int(ans))

Submission status: Accepted

Solution code:
import numpy as np
s=input()
n=len(s)
MOD=1000000007
wayA=np.array([0,0,0,0])
wayB=np.array([0,0,0,0])
wayC=np.array([0,0,0,0])
MOD2=np.array([MOD,MOD,MOD,MOD])
hatena=0
for c in s:
	if c=="A":
		wayA[0]+=1
	if c=="B":
		wayB+=wayA
	if c=='C':
		wayC+=wayB
	if c=='?':
		wayC[1]=wayC[1]+wayB[0]
		wayC[2]=wayC[2]+wayB[1]
		wayC[3]=wayC[3]+wayB[2]
		wayB[1]=wayB[1]+wayA[0]
		wayB[2]=wayB[2]+wayA[1]
		wayA[1]=wayA[1]+1
		hatena+=1
	wayA%=MOD2
	wayB%=MOD2
	wayC%=MOD2
ans=0
for i in range(0,4):
	ans=ans+pow(3,hatena-i)*wayC[i]
	ans=ans%MOD
print(int(ans))

Submission status: Accepted

Solution code:
import numpy as np
s=input()
n=len(s)
MOD=1000000007
wayA=np.array([0,0,0,0],dtype=np.int64)
wayB=np.array([0,0,0,0],dtype=np.int64)
wayC=np.array([0,0,0,0],dtype=np.int64)
MOD2=np.array([MOD,MOD,MOD,MOD],dtype=np.int32)
hatena=0
for c in s:
	if c=="A":
		wayA[0]+=1
	if c=="B":
		wayB+=wayA
	if c=='C':
		wayC+=wayB
	if c=='?':
		wayC[1]=wayC[1]+wayB[0]
		wayC[2]=wayC[2]+wayB[1]
		wayC[3]=wayC[3]+wayB[2]
		wayB[1]=wayB[1]+wayA[0]
		wayB[2]=wayB[2]+wayA[1]
		wayA[1]=wayA[1]+1
		hatena+=1
	wayA%=MOD2
	wayB%=MOD2
	wayC%=MOD2
ans=0
for i in range(0,4):
	ans=ans+pow(3,hatena-i)*wayC[i]
	ans=ans%MOD
print(int(ans))

Submission status: Accepted

Solution code:
import numpy as np
s=input()
n=len(s)
MOD=1000000007
wayA=np.array([0,0,0,0],dtype=np.int64)
wayB=np.array([0,0,0,0],dtype=np.int64)
wayC=np.array([0,0,0,0],dtype=np.int64)
MOD2=np.array([MOD,MOD,MOD,MOD],dtype=np.int32)
hatena=0
for c in s:
	if c=="A":
		wayA[0]+=1
	if c=="B":
		wayB+=wayA
	if c=='C':
		wayC+=wayB
	if c=='?':
		wayC[1]=wayC[1]+wayB[0]
		wayC[2]=wayC[2]+wayB[1]
		wayC[3]=wayC[3]+wayB[2]
		wayB[1]=wayB[1]+wayA[0]
		wayB[2]=wayB[2]+wayA[1]
		wayA[1]=wayA[1]+1
		hatena+=1
	wayA%=MOD2
	wayB%=MOD2
	wayC%=MOD2
ans=0
for i in range(0,4):
	p3=1
	for k in range(0,hatena-i):
		p3=p3*3
		p3=p3%MOD
	ans=ans+p3*wayC[i]
	ans=ans%MOD
print(int(ans))

Submission status: Accepted

Solution code:
import numpy as np
 
s=input()
n=len(s)
MOD=1000000007
wayA=np.array([0,0,0,0],dtype=np.int64)
wayB=np.array([0,0,0,0],dtype=np.int64)
wayC=np.array([0,0,0,0],dtype=np.int64)
MOD2=np.array([MOD,MOD,MOD,MOD],dtype=np.int32)
hatena=0
for c in s:
	if c=="A":
		wayA[0]+=1
	if c=="B":
		wayB+=wayA
	if c=='C':
		wayC+=wayB
	if c=='?':
		wayC[1]=wayC[1]+wayB[0]
		wayC[2]=wayC[2]+wayB[1]
		wayC[3]=wayC[3]+wayB[2]
		wayB[1]=wayB[1]+wayA[0]
		wayB[2]=wayB[2]+wayA[1]
		wayA[1]=wayA[1]+1
		hatena+=1
	wayA%=MOD2
	wayB%=MOD2
	wayC%=MOD2
ans=0
for i in range(0,4):
	p3=1
	if wayC[i]<=0:
		continue
	for k in range(0,hatena-i):
		p3=p3*3
		p3=p3%MOD
	ans=ans+p3*wayC[i]
	ans=ans%MOD
print(int(ans))