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[i][four] =: i + 1番目まで見たとき,照合したケツがfourとなるものの総数
dp = [[0 for _ in range(4)] for _ in range(len(S)+1 )]
dp[0][0] = 1
mod = 10**9 + 7
for i in range(len(S)):
    if S[i] == '?':
        dp[i+1][1] += dp[i][0] 
        dp[i+1][1] %= mod
        dp[i+1][2] += dp[i][1] 
        dp[i+1][2] %= mod
        dp[i+1][3] += dp[i][2] 
        dp[i+1][3] %= mod
    if S[i] == 'A':
        dp[i+1][1] += dp[i][0] 
        dp[i+1][1] %= mod
    if S[i] == 'B':
        dp[i+1][2] += dp[i][1]
        dp[i+1][2] %= mod
    if S[i] == 'C':
        dp[i+1][3] += dp[i][2]
        dp[i+1][3] %= mod
    for f in range(4):
        if S[i] != '?':
            dp[i+1][f] += dp[i][f]
        else:
            dp[i+1][f] += dp[i][f] * 3
        dp[i+1][f] %= mod
print(dp[len(S)][3]%mod)

Submission status: Accepted

Solution code:
def main():
    MOD = 10**9 + 7
    S = input()
    N = len(S)
    CHARS = ['A', 'B', 'C']
    dp = [[0 for _ in range(4)] for _ in range(N + 1)]
    dp[N][3] = 1
    for i in range(N - 1, -1, -1):
        a = 3 if S[i] == '?' else 1
        dp[i][3] = a * dp[i + 1][3]
        dp[i][3] %= MOD
    for i in range(N - 1, -1, -1):
        a = 3 if S[i] == '?' else 1
        ch = S[i]
        for j in range(3):
            b = 1 if ch in ['?', CHARS[j]] else 0
            dp[i][j] = a * dp[i + 1][j] + b * dp[i + 1][j + 1]
            dp[i][j] %= MOD
    print(dp[0][0])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
S = input()
MOD = 10**9+7
A = 0
AB = 0
ABC = 0
cnt = 1
for c in S:
  if c=='A':
    A += cnt
    A %= MOD
  elif c=='B':
    AB += A
    AB %= MOD
  elif c=='C':
    ABC += AB
    ABC %= MOD
  else:
    nA = 3*A+cnt
    nAB = 3*AB+A
    nABC = 3*ABC+AB
    cnt *= 3
    A,AB,ABC = nA%MOD,nAB%MOD,nABC%MOD
    cnt %= MOD
print(ABC)

Submission status: Accepted

Solution code:
# ABC104D

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))

M = 10**9+7
s = input()
n = len(s)
anum = [None] * n # s[:i+1]のAの数
cnum = [None] * n # s[i+1:]のCの数
hnum1 = [None] * n
hnum2 = [None] * n
acount = 0
ccount = 0
hcount1 = 0
hcount2 = 0
for i,(c,cc) in enumerate(zip(s, s[::-1])):
    if c in "A":
        acount += 1
    if c=="?":
        hcount1 += 1
    anum[i] = acount
    hnum1[i] = hcount1
    if cc in "C":
        ccount += 1
    if cc=="?":
        hcount2 += 1
    cnum[-(i+1)] = ccount
    hnum2[-(i+1)] = hcount2
ans = 0
hn = hnum1[-1]
for i,c in enumerate(s):
    if i in (0, n-1):
        continue
    if c=="B":
        ans += (anum[i-1]*cnum[i+1]*pow(3, hn, M))
        if hn>=1:
            ans += (anum[i-1]*hnum2[i+1]*pow(3, hn-1, M))
            ans += (hnum1[i-1]*cnum[i+1]*pow(3, hn-1, M))
        if hn>=2:
            ans += (hnum1[i-1]*hnum2[i+1]*pow(3, hn-2, M))
    if c=="?":
        ans += (anum[i-1]*cnum[i+1]*pow(3, hn-1, M))
        if hn>=2:
            ans += (anum[i-1]*(hnum2[i+1])*pow(3, hn-2, M))
            ans += (hnum1[i-1]*cnum[i+1]*pow(3, hn-2, M))
        if hn>=3:
            ans += (hnum1[i-1]*hnum2[i+1]*pow(3, hn-3, M))
    ans %= M
#     print(ans)
print(ans)

Submission status: Accepted

Solution code:
mod = 1000000007
s = input()
al = 0
cr = s.count('C')
ql = 0
qr = s.count('?')
ans = 0
for c in s:
  if c == 'C':
    cr -= 1
  elif c == '?':
    qr -= 1
    ans += (3 * al + ql) * (3 * cr + qr) * pow(3, ql + qr + mod - 3, mod)
    ans %= mod
    ql += 1
  elif c == 'B':
    ans += (3 * al + ql) * (3 * cr + qr) * pow(3, ql + qr + mod - 3, mod)
    ans %= mod
  else:
    al += 1
print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9+7

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

Submission status: Accepted

Solution code:
MOD = 10**9+7

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000000)
input = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = 10 ** 15

def main():
    S = input()
    N = len(S)
    C = [0] * (N + 1)
    QL = [0] * (N + 1)
    A = [0] * (N + 1)
    QR = [0] * (N + 1)
    for i in range(N):
        if S[i] == 'A':
            A[i + 1] = A[i] + 1
        else:
            A[i + 1] = A[i]
        if S[i] == '?':
            QL[i + 1] = QL[i] + 1
        else:
            QL[i + 1] = QL[i]
    
    for i in range(N - 1,-1,-1):
        if S[i] == 'C':
            C[i] = C[i + 1] + 1
        else:
            C[i] = C[i + 1]
        if S[i] == '?':
            QR[i] = QR[i + 1] + 1
        else:
            QR[i] = QR[i + 1]
    
    power3 = [1]
    for i in range(N):
        power3.append(power3[-1]*3%MOD)

    ans = 0
    for i in range(N):
        if S[i] in 'AC':
            continue
        choose_A = (A[i]*power3[QL[i]] + (QL[i] > 0)*QL[i]*power3[QL[i] - 1])%MOD
        choose_B = (C[i + 1]*power3[QR[i + 1]] + (QR[i + 1] > 0)*QR[i + 1]*power3[QR[i + 1] - 1])%MOD
        ans += choose_A*choose_B%MOD
        ans %= MOD
    print(ans) 

if __name__ == '__main__':
    main()

Submission status: Accepted

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

    s = input()

    x, a, b, c = 1, 0, 0, 0

    for char in s:
        if char == 'A':
            a = (a + x) % MOD
        elif char == 'B':
            b = (b + a) % MOD
        elif char == 'C':
            c = (c + b) % MOD
        else:
            x, a, b, c = 3 * x % MOD, (3 * a + x) % MOD, (3 * b + a) % MOD, (3 * c + b) % MOD

    print(c)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

    s = input()
    n = len(s)

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

    for i, c in enumerate(s, start=1):
        for j in range(4):
            dp[i][j] = dp[i - 1][j]
        if c == 'A':
            dp[i][1] += dp[i - 1][0]
        elif c == 'B':
            dp[i][2] += dp[i - 1][1]
        elif c == 'C':
            dp[i][3] += dp[i - 1][2]
        else:
            for j in range(1, 4):
                dp[i][j] += dp[i - 1][j - 1]
            for j in range(4):
                dp[i][j] += dp[i - 1][j] * 2
        for j in range(4):
            dp[i][j] %= MOD

    print(dp[n][3])


if __name__ == '__main__':
    main()

Submission status: Accepted

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

    s = input()
    n = len(s)

    acc_a = [0] * (n + 1)
    acc_c = [0] * (n + 1)
    acc_q = [0] * (n + 1)

    a = 0
    c = 0
    q = 0
    for i, char in enumerate(s, 1):
        if char == 'A':
            a += 1
        elif char == 'C':
            c += 1
        elif char == '?':
            q += 1
        acc_a[i] = a
        acc_c[i] = c
        acc_q[i] = q

    sq = [1]
    for _ in range(acc_q[n]):
        sq.append(sq[-1] * 3 % MOD)

    ans = 0
    qn = acc_q[n]
    for i, char in enumerate(s, 1):
        if char == 'B' or char == '?':
            is_q = int(char == '?')
            rq = acc_q[n] - acc_q[i]
            rc = acc_c[n] - acc_c[i]
            t = 0
            if qn - is_q >= 0:
                t += acc_a[i - 1] * rc * sq[acc_q[n] - is_q]
            if qn - 1 - is_q >= 0:
                t += acc_a[i - 1] * rq * sq[acc_q[n] - 1 - is_q]
                t += acc_q[i - 1] * rc * sq[acc_q[n] - 1 - is_q]
            if qn - 2 - is_q >= 0:
                t += acc_q[i - 1] * rq * sq[acc_q[n] - 2 - is_q]
            t %= MOD
            ans = (ans + t) % MOD
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
def main():
    s = input()
    dp = [[0]*3 for _ in range(len(s)+1)]
# dp[idx][A, AB, ABC]
    tmp = 1
    for i in range(len(s)):
        c = s[i]
        if c == "A":
            dp[i][0] += tmp
            dp[i][0] %= MOD
        elif c == "B":
            dp[i][1] += dp[i][0]
            dp[i][1] %= MOD
        elif c == "C":
            dp[i][2] += dp[i][1]
            dp[i][2] %= MOD
        else:
            pre = [v for v in dp[i]]
            dp[i] = [0, 0, 0]
# ? = A
            dp[i][0] += pre[0] + tmp
            dp[i][1] += pre[1]
            dp[i][2] += pre[2]
# ? = B
            dp[i][0] += pre[0]
            dp[i][1] += pre[0] + pre[1]
            dp[i][2] += pre[2]
# ? = C
            dp[i][0] += pre[0]
            dp[i][1] += pre[1]
            dp[i][2] += pre[1] + pre[2]
            tmp *= 3
            tmp %= MOD
            dp[i][0] %= MOD
            dp[i][1] %= MOD
            dp[i][2] %= MOD
        dp[i+1][0] = dp[i][0]
        dp[i+1][1] = dp[i][1]
        dp[i+1][2] = dp[i][2]
#        print(dp[i])
    print(dp[len(s)][2] % MOD)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def modinv(a,m):
    return pow(a,m-2,m)

import copy

S = input()
N = len(S)
dp = [[[0,0], [0,0,0], [0,0,0,0]] for i in range(N+1)]
mod = 10**9 + 7

for i in range(N):
    dp[i+1] = copy.deepcopy(dp[i])
    if S[i] == 'A':
        dp[i+1][0][0] += 1

    elif S[i] == 'B':
        for j in range(2):
            dp[i+1][1][j] = (dp[i+1][1][j] + dp[i][0][j])%mod

    elif S[i] == 'C':
        for j in range(3):
            dp[i+1][2][j] = (dp[i+1][2][j] + dp[i][1][j])%mod

    else:
        dp[i+1][0][1] += 1
        for j in range(2):
            dp[i+1][1][j+1] = (dp[i+1][1][j+1] + dp[i][0][j])%mod
        for j in range(3):
            dp[i+1][2][j+1] = (dp[i+1][2][j+1] + dp[i][1][j])%mod

Q = S.count('?')

inv3 = modinv(3,mod)
inv9 = inv3*inv3%mod
inv27 = inv9*inv3%mod
threeQ = pow(3,Q,mod)

ans = threeQ * (dp[N][2][0] + dp[N][2][1]*inv3 + dp[N][2][2]*inv9 + dp[N][2][3]*inv27) % mod
print(ans)

Submission status: Accepted

Solution code:
S = input()

def solve(S):
    mod = 10**9+7
    N = len(S)
    Aquest = []
    Cquest = []
    cntA,cntquest = 0,0
    for i in range(N):
        if S[i] in 'B?':
            Aquest.append([cntA,cntquest])
        if S[i]=='A':
            cntA += 1
        if S[i]=='?':
            cntquest += 1
    cntC,cntquest = 0,0
    for i in range(N-1,-1,-1):
        if S[i] in 'B?':
            Cquest.append([cntC,cntquest])
        if S[i]=='C':
            cntC += 1
        if S[i]=='?':
            cntquest += 1
    Cquest = Cquest[::-1]
    ans = 0
    for aquest,cquest in zip(Aquest,Cquest):
        a = aquest[0]*pow(3,aquest[1],mod)
        if aquest[1]>0:
            a += aquest[1]*pow(3,aquest[1]-1,mod)
        c = cquest[0]*pow(3,cquest[1],mod)
        if cquest[1]>0:
            c += cquest[1]*pow(3,cquest[1]-1,mod)
        ans += a*c%mod
    ans %= mod
    return ans
print(solve(S))

Submission status: Accepted

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

a, ab, abc, n = 0, 0, 0, 1
for s in S:
    if s == "A":
        a += n
        a %= mod
    elif s == "B":
        ab += a
        ab %= mod
    elif s == "C":
        abc += ab
        abc %= mod
    else:
        a, ab, abc, n = 3 * a + n, 3 * ab + a, 3 * abc + ab, 3 * n
        a %= mod
        ab %= mod
        abc %= mod
        n %= mod

print(abc)

Submission status: Accepted

Solution code:
s = input()
n = len(s)
mod = 10**9+7
qcnt = [[0,0]for i in range(n)]#それより左の？、右の？のこすう
Acnt = [0]*n#それより左のAのこすう
Ccnt = [0]*n#それより右のCの個数
q = 0
for i in range(n-1):
    if s[i] == '?':
        q += 1
        qcnt[i+1][0] += 1
    elif s[i] == 'A':
        Acnt[i+1] += 1
    qcnt[i+1][0] += qcnt[i][0]
    Acnt[i+1] += Acnt[i]
    qcnt[i+1][0]%=mod
    Acnt[i+1]%=mod
if s[-1] == '?':q += 1
for i in range(n-1,0,-1):
    if s[i] == '?':
        
        qcnt[i-1][1] += 1
    elif s[i] == 'C':
        Ccnt[i-1] += 1
    qcnt[i-1][1] += qcnt[i][1]
    Ccnt[i-1] += Ccnt[i]
    qcnt[i-1][1]%=mod
    Ccnt[i-1]%=mod
ans = 0
for i in range(n):
    
    if s[i] == 'B' or s[i] == '?':
        if qcnt[i][0]+qcnt[i][1]-2 <0:
            val = -(qcnt[i][0]+qcnt[i][1]-2)
            p = pow(3,val,mod)
            q = pow(p,mod-2,mod)
            ans +=q%mod*(3*Acnt[i] + qcnt[i][0])*(3*Ccnt[i]+ qcnt[i][1])%mod
        
        else:ans +=pow(3,qcnt[i][0]+qcnt[i][1]-2,mod)%mod*(3*Acnt[i] + qcnt[i][0])*(3*Ccnt[i]+ qcnt[i][1])%mod
        ans %= mod
    
    
print(ans%mod)

Submission status: Accepted

Solution code:
from sys import stdin
def main():
    #入力
    readline=stdin.readline
    s=readline().strip()

    mod=10**9+7
    n=len(s)
    dp=[[0]*4 for _ in range(n+1)]
    dp[0][0]=1
    for i in range(1,n+1):
        #i文字目を選ばない
        for j in range(4):
            if s[i-1]!="?":
                dp[i][j]+=dp[i-1][j]
            else:
                dp[i][j]+=dp[i-1][j]*3

        #i文字目を選ぶ
        if s[i-1]=="A":
            dp[i][1]+=dp[i-1][0]
        elif s[i-1]=="B":
            dp[i][2]+=dp[i-1][1]
        elif s[i-1]=="C":
            dp[i][3]+=dp[i-1][2]
        elif s[i-1]=="?":
            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]%=mod
            
    print(dp[n][3])
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7

S = list(input())
N = len(S)

count = 0
DP = [[0] *  (N + 1) for _ in range(3)]
for i in range(1, N + 1):
    s = S[i - 1]
    if s == 'A':
        DP[0][i] = (DP[0][i - 1] + pow(3, count, MOD)) % MOD
        DP[1][i] = DP[1][i - 1]
        DP[2][i] = DP[2][i - 1]
    elif s == 'B':
        DP[0][i] = DP[0][i -1]
        DP[1][i] = (DP[1][i - 1] + DP[0][i - 1]) % MOD
        DP[2][i] = DP[2][i - 1]
    elif s == 'C':
        DP[0][i] = DP[0][i - 1]
        DP[1][i] = DP[1][i - 1]
        DP[2][i] = (DP[2][i - 1] + DP[1][i - 1]) % MOD
    else:
        DP[0][i] = (3 * DP[0][i - 1] + pow(3, count, MOD)) % MOD
        DP[1][i] = (3 * DP[1][i - 1] + DP[0][i - 1]) % MOD
        DP[2][i] = (3 * DP[2][i - 1] + DP[1][i - 1]) % MOD
        count += 1

print (DP[2][N])

# print (DP)

Submission status: Accepted

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

A = 0
AB = 0
ABC = 0
prd = 1

for s in S:
    if s == 'A':
        A += prd
    elif s == 'B':
        AB += A
    elif s == 'C':
        ABC += AB
    else:
        a = A * 3 + prd
        ab = AB * 3 + A
        abc = ABC * 3 + AB
        A, AB, ABC = a, ab, abc
        prd *= 3
    A %= MOD
    AB %= MOD
    ABC %= MOD
    prd %= MOD

print(ABC)

Submission status: Accepted

Solution code:

mod = 10 ** 9 + 7

def main():
    s = input()

    n = len(s)

    dp = [[0 for _ in range(4)] for _ in range(n+1)]
    dp[0][0] = 1
    for i in range(n):
        if s[i] in ('A', '?'):
            dp[i+1][0] = (dp[i+1][0] + dp[i][0]) % mod
            dp[i+1][1] = (dp[i+1][1] + dp[i][1]) % mod
            dp[i+1][2] = (dp[i+1][2] + dp[i][2]) % mod
            dp[i+1][3] = (dp[i+1][3] + dp[i][3]) % mod
            dp[i+1][1] = (dp[i+1][1] + dp[i][0]) % mod
        if s[i] in ('B', '?'):
            dp[i+1][0] = (dp[i+1][0] + dp[i][0]) % mod
            dp[i+1][1] = (dp[i+1][1] + dp[i][1]) % mod
            dp[i+1][2] = (dp[i+1][2] + dp[i][2]) % mod
            dp[i+1][3] = (dp[i+1][3] + dp[i][3]) % mod
            dp[i+1][2] = (dp[i+1][2] + dp[i][1]) % mod
        if s[i] in ('C', '?'):
            dp[i+1][0] = (dp[i+1][0] + dp[i][0]) % mod
            dp[i+1][1] = (dp[i+1][1] + dp[i][1]) % mod
            dp[i+1][2] = (dp[i+1][2] + dp[i][2]) % mod
            dp[i+1][3] = (dp[i+1][3] + dp[i][3]) % mod
            dp[i+1][3] = (dp[i+1][3] + dp[i][2]) % mod

    print(dp[n][3])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
S = input()
N = len(S)
mod = 10 ** 9 + 7
dp1 = [0 for _ in range(N+1)]
dp2 = [0 for _ in range(N+1)]
dp3 = [0 for _ in range(N+1)]
dp4 = [0 for _ in range(N+1)]
dp1[0] = 1

for i in range(N):
    if S[i] == '?':
        dp1[i+1] += 3 * dp1[i]
        dp2[i+1] += 3 * dp2[i] + dp1[i]
        dp3[i+1] += 3 * dp3[i] + dp2[i]
        dp4[i+1] += 3 * dp4[i] + dp3[i]
    else:
        dp1[i+1] += dp1[i]
        dp2[i+1] += dp2[i]
        dp3[i+1] += dp3[i]
        dp4[i+1] += dp4[i]
    if S[i] == 'A':
        dp2[i+1] += dp1[i]
    if S[i] == 'B':
        dp3[i+1] += dp2[i]
    if S[i] == 'C':
        dp4[i+1] += dp3[i]
    dp1[i+1] %= mod
    dp2[i+1] %= mod
    dp3[i+1] %= mod
    dp4[i+1] %= mod

print(dp4[N])

Submission status: Accepted

Solution code:
from bisect import *
S = input()
mod = 10**9 + 7
A = []
B = []
C = []
X = []
q = 0
for i,s in enumerate(S):
    if s == 'A':
        A.append(i)
    elif s == 'B':
        B.append((i,0))
    elif s == 'C':
        C.append(i)
    else:
        X.append(i)
        B.append((i,1))
        q += 1

pow3 = [pow(3,q,mod),pow(3,max(0,q-1),mod),pow(3,max(0,q-2),mod),pow(3,max(0,q-3),mod)]
ans = 0
for b,flag in B:
    Al = bisect_left(A,b)
    Cr = (len(C) - bisect_right(C,b))
    Xl = bisect_left(X,b)
    Xr = (len(X) - bisect_right(X,b))
    ans += (Al*Cr%mod)*pow3[flag]%mod
    ans %= mod
    ans += (Al*Xr%mod + Xl*Cr%mod)*pow3[flag+1]%mod
    ans %= mod
    ans += (Xl*Xr%mod)*pow3[flag+2]%mod
print(ans)

Submission status: Accepted

Solution code:
S=input()
A=0 #Aの数
B=0 #ABの数
C=0 #ABCの数
n=1 #通り数
mod=10**9+7
for s in S:
    if s=="?":
        C=3*C+B
        B=3*B+A
        A=3*A+n
        n*=3
    elif s=="A":
        A+=n
    elif s=="B":
        B+=A
    else:
        C+=B
    A%=mod
    B%=mod
    C%=mod
    n%=mod
print(C)

Submission status: Accepted

Solution code:
s = input()
n_a = [0]
n_l = [0]
n_c = [0]
n_r = [0]

mod = 10 ** 9 + 7
n = len(s)

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

for i in range(n):
    if s[i] == 'A':
        n_a.append(n_a[-1]+1)
    else:
        n_a.append(n_a[-1])

    if s[i] == '?':
        n_l.append(n_l[-1]+1)
    else:
        n_l.append(n_l[-1])

    if s[-i-1] == 'C':
        n_c.append(n_c[-1]+1)
    else:
        n_c.append(n_c[-1])

    if s[-i-1] == '?':
        n_r.append(n_r[-1]+1)
    else:
        n_r.append(n_r[-1])

ans = 0

for i in range(1, n - 1):
    if s[i] in ['B', '?']:
        # ABC
        ans += n_a[i] * n_c[n -  1 - i] * pow3[n_l[i]] * pow3[n_r[n - 1 - i]] % mod
        ans %= mod
        # ?BC   
        ans += n_l[i] * n_c[n -  1 - i] * pow3[n_l[i] - 1] * pow3[n_r[n - 1 - i]] % mod
        ans %= mod
        # AB?
        ans += n_a[i] * n_r[n -  1 - i] * pow3[n_l[i]] * pow3[n_r[n - 1 - i] - 1] % mod
        ans %= mod
        # ?B?
        ans += n_l[i] * n_r[n -  1 - i] * pow3[n_l[i]-1] * pow3[n_r[n - 1 - i] - 1] % mod
        ans %= mod

print(ans)

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
# from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

s=input()
dp=[[0]*(len(s)+1) for i in range(4)]
dp[0][0]=1
lst="ABC"
for i in range(len(s)):
    for j in range(3):
        m1=1
        m2=0
        if s[i]=="?":
            m1=3
            m2=1
        
        if lst[j]==s[i]:
            m2=1
        
        dp[j][i+1]+=m1*dp[j][i]
        dp[j+1][i+1]+=m2*dp[j][i]
        dp[j][i+1]%=mod
        
    if s[i]=="?":
        dp[3][i+1]+=3*dp[3][i]
    else:
        dp[3][i+1]+=dp[3][i]
    dp[3][i+1]%=mod

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

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
# from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

s=input()
ab=[0,0]
ans=0
cnt=0
for i in range(len(s)):
    if s[i]=="A":
        ab[0]+=pow(3,cnt,mod)
    elif s[i]=="B":
        ab[1]+=ab[0]
    elif s[i]=="C":
        ans+=ab[1]
    else:
        ans=ab[1]+3*ans
        ab[1]=ab[0]+3*ab[1]
        ab[0]=pow(3,cnt,mod)+3*ab[0]
        cnt+=1
    ab[0]%=mod
    ab[1]%=mod
    ans%=mod
print(ans%mod)

Submission status: Accepted

Solution code:
s=input()
dp = [[0 for _ in range(4)] for _ in range(len(s)+1)]
dp[0][0] = 1
for i in range(len(s)):
    for j in range(4):
        dp[i][j] %= 10**9+7
        if s[i]=="?":
            dp[i+1][j] += (3*dp[i][j])
        else:
            dp[i+1][j] += dp[i][j]

    if s[i] == "A" or s[i] == "?":
        dp[i+1][1] += dp[i][0]
    if s[i] == "B" or s[i] == "?":
        dp[i+1][2] += dp[i][1]
    if s[i] == "C" or s[i] == "?":
        dp[i+1][3] += dp[i][2]

print(dp[-1][-1] % (10**9+7))

Submission status: Accepted

Solution code:
s=input()
mod=10**9+7
retnum={"?":0,"A":1,"B":2,"C":3}
count=[[0 for i in range(len(s))] for j in range(4)]
for i in range(len(s)):
    for j in range(4):
        if retnum[s[i]] == j:
            count[j][i]=count[j][i-1]+1
        else:
            count[j][i]=count[j][i-1]
ans=0
g=[1]*100002
for i in range(1,100002):
    g[i]=g[i-1]*3
    g[i]%=mod
for i in range(1,len(s)-1):
    if s[i]=="B" or s[i]=="?":
        ans+=(g[max(0,count[0][i-1]-1)]*count[0][i-1]+g[count[0][i-1]]*count[1][i-1])*(g[max(0,count[0][-1]-count[0][i]-1)]*(count[0][-1]-count[0][i])+g[count[0][-1]-count[0][i]]*(count[3][-1]-count[3][i]))
        ans%=mod
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    S=list(input())
    A,C,Q=[0]*(len(S)+1),[0]*(len(S)+1),[0]*(len(S)+1)
    l_B=[]
    l_Q=[]
    q=0
    for i in range(len(S)):
        A[i+1]=A[i]+(S[i]=='A')
        C[i+1]=C[i]+(S[i]=='C')
        Q[i+1]=Q[i]+(S[i]=='?')
        if S[i]=='?':
            q+=1
            l_Q.append(i)
        if S[i]=='B':
            l_B.append(i)
    ans=0
    pow3q=pow(3,q,MOD)
    if q-1>=0:
        pow3q_1=pow(3,q-1,MOD)
    else:
        pow3q_1=0
    if q-2>=0:
        pow3q_2=pow(3,q-2,MOD)
    else:
        pow3q_2=0
    if q-3>=0:
        pow3q_3=pow(3,q-3,MOD)
    else:
        pow3q_3=0
    
    for x in l_B:
        ans+=A[x]*(C[len(S)]-C[x+1])*pow3q
        ans+=Q[x]*(C[len(S)]-C[x+1])*pow3q_1
        ans+=A[x]*(Q[len(S)]-Q[x+1])*pow3q_1
        ans+=Q[x]*(Q[len(S)]-Q[x+1])*pow3q_2
        ans%=MOD
    for x in l_Q:
        ans+=A[x]*(C[len(S)]-C[x+1])*pow3q_1
        ans+=Q[x]*(C[len(S)]-C[x+1])*pow3q_2
        ans+=A[x]*(Q[len(S)]-Q[x+1])*pow3q_2
        ans+=Q[x]*(Q[len(S)]-Q[x+1])*pow3q_3
        ans%=MOD        
    print(ans)
    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
data = input()
MOD = 10**9 + 7
SLen = len(data)
targets = "ABC"
array = [[0 for i in range(SLen + 1)] for _ in range(4)]
array[0][0] = 1
for i in range(SLen):
    for j in range(4):
        if data[i] == '?':
            if j < 3:
                array[j + 1][i + 1] = (array[j + 1][i + 1] + array[j][i]) % MOD
            array[j][i + 1] = (array[j][i + 1] + array[j][i] * 3) % MOD
        else:
            if j < 3 and data[i] == targets[j]:
                array[j + 1][i + 1] = (array[j + 1][i + 1] + array[j][i]) % MOD
            array[j][i + 1] = (array[j][i + 1] + array[j][i]) % MOD

print(array[3][SLen])

Submission status: Accepted

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

S = input().rstrip()
N = len(S)
mod = 10**9 + 7
cnt = 0
A = B = C = 0
for c in S:
    if c == 'A':
        A += pow(3, cnt, mod)
    if c == 'B':
        B += A
    if c == 'C':
        C += B
    if c == '?':
        C = C * 3 + B
        B = B * 3 + A
        A = A * 3 + pow(3, cnt, mod)
        cnt += 1
    A %= mod
    B %= mod
    C %= mod
print(C)

Submission status: Accepted

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

Submission status: Accepted

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

# i = 0, ..., nについて
# dp[i][0] = i文字目まででありうる文字列の数（ABCなら1、AB?なら3）
# dp[i][1] = i文字目までに含まれるAの数
# dp[i][2] = i文字目までに含まれるABのパターン数
# dp[i][3] = i文字目までに含まれるABCのパターン数
dp = [[0 for j in range(4)] for i in range(n + 1)]
dp[0][0] = 1 # ''空の文字列は1パターン
for j in range(1, 4):
    dp[0][j] = 0  # 空の文字列にはAもABもABCも入っていない

for i in range(1, n + 1):
    m = 3 if s[i - 1] == '?' else 1

    for j in range(4):
        dp[i][j] = dp[i - 1][j] * m % p

    if s[i - 1] == 'A' or s[i - 1] == '?':
        dp[i][1] =  (dp[i][1] + dp[i - 1][0]) % p
    if s[i - 1] == 'B' or s[i - 1] == '?':
        dp[i][2] = (dp[i][2] + dp[i - 1][1]) % p
    if s[i - 1] == 'C' or s[i - 1] == '?':
        dp[i][3] = (dp[i][3] + dp[i - 1][2]) % p

print(dp[n][3])

Submission status: Accepted

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

q = s.count('?')
l_a = [0] * n  # l_a[i] := s[i]より左にあるAの数
l_x = [0] * n  # l_x[i] := s[i]より左にある?の数
r_c = [0] * n  # r_c[i] := s[i]より右にあるCの数
r_x = [0] * n  # r_x[i] := s[i]より右にある?の数

for i in range(1, n):  # 1〜n-1
    l_a[i] = l_a[i - 1] + int(s[i - 1] == 'A')
    l_x[i] = l_x[i - 1] + int(s[i - 1] == '?')
    r_c[n - i - 1] = r_c[n - i] + int(s[n - i] == 'C')
    r_x[n - i - 1] = r_x[n - i] + int(s[n - i] == '?')

ans = 0
pow_q = []
for i in range(0, 4):
    pow_q.append(max(1, 3 ** (q - i) % p))

for i in range(n):
    if s[i] == 'B':
        ans += (l_a[i] * r_c[i] % p) * pow_q[0] % p  # ABC
        ans += (l_x[i] * r_c[i] % p) * pow_q[1] % p # ?BC
        ans += (l_a[i] * r_x[i] % p) * pow_q[1] % p # AB?
        ans += (l_x[i] * r_x[i] % p) * pow_q[2] % p # ?B?
        ans %= p
    elif s[i] == '?':
        ans += (l_a[i] * r_c[i] % p) * pow_q[1] % p # A?C
        ans += (l_x[i] * r_c[i] % p) * pow_q[2] % p # ??C
        ans += (l_a[i] * r_x[i] % p) * pow_q[2] % p # A??
        ans += (l_x[i] * r_x[i] % p) * pow_q[3] % p # ???
        ans %= p

print(ans)

Submission status: Accepted

Solution code:
def main():
    S = input()
    mod = 10 ** 9 + 7
    A = AB = ABC = 0
    n = 1
    for i in S:
        if i == '?':
            ABC = ABC * 3 + AB
            AB = AB * 3 + A
            A = A * 3 + n
            n = n * 3 % mod
        if i == 'C':
            ABC = ABC + AB
        if i == 'B':
            AB = AB + A
        if i == 'A':
            A += n
    print(ABC % mod)

main()

Submission status: Accepted

Solution code:
from functools import lru_cache
class cmbs(object):
    def __init__(self, mod):
        self.mod = mod
        self.g1 = [1, 1]
        self.g2 = [1, 1]
        inverse = [0, 1]
        for i in range(2, 10 ** 6 + 1):
            self.g1.append((self.g1[-1] * i) % mod)
            inverse.append((-inverse[mod % i] * (mod // i)) % mod)
            self.g2.append((self.g2[-1] * inverse[-1]) % mod)
    @lru_cache(maxsize=None)
    def cmb(self, n, r):
        if n > 10 ** 6:
            return self.cmbl(n, r)
        return self.cmbr(n, r)

    def cmbr(self, n, r):
        if r < 0 or r > n:
            return 0
        r = min(r, n - r)
        return self.g1[n] * self.g2[r] * self.g2[n-r] % self.mod

    def cmbl(self, n, r):
        t = 1
        r = min(r, n-r)
        for i in range(n - r + 1, n + 1):
            t = t * i % self.mod
        return t * self.g2[r] % self.mod
def main():
    S = input()
    mod = 10**9 + 7
    n = len(S)
    A = [0] * n
    B = [0] * n
    C = [0] * n
    Q = [0] * n
    d = {'A':0, 'B':0, 'C':0, '?':0}
    for i, v in enumerate(S):
        d[v] += 1
        A[i] = d['A']
        B[i] = d['B']
        C[i] = d['C']
        Q[i] = d['?']
    r = 0
    c = cmbs(mod)
    t = d['?']
    # ???
    if t >= 3:
        r += c.cmb(t, 3) * pow(3, t - 3)
        r %= mod
    if t >= 2:
        r2 = 0
        for i in range(n):
            p = t - Q[i]
            # A??
            if S[i] == 'A' and p >= 2:
                r2 += c.cmb(p, 2)
            # ?B?
            if S[i] == 'B' and Q[i] >= 1 and p >= 1:
                r2 += Q[i] * p
            # ??C
            if S[i] == 'C' and Q[i] >= 2:
                r2 += c.cmb(Q[i], 2)
        r2 *= pow(3, t-2)
        r += r2
        r %= mod
    if t >= 1:
        r1 = 0
        for i in range(n):
            if S[i] == 'B':
                #AB?
                r1 += A[i] * (t - Q[i])
                #?BC
                r1 += Q[i] * (d['C']-C[i])
            if S[i] == '?':
                #A?C
                r1 += A[i] * (d['C']-C[i])
        r1 *=  pow(3, t-1)
        r += r1
        r %= mod
    r0 = 0
    for i in range(n):
        if S[i] == 'B':
            r0 += A[i] * (d['C'] - C[i])
    r0 *= pow(3, t)
    r += r0
    r %= mod
    return r
print(main())

Submission status: Accepted

Solution code:
s=input()
mod=10**9+7
a=0
ab=0
abc=0
q=1
for i in s:
    if i=="?":
        abc*=3
        abc+=ab
        ab*=3
        ab+=a
        a*=3
        a+=q
        q*=3
        q%=mod
    elif i=="A":
        a+=q
    elif i=="B":
        ab+=a
    else:
        abc+=ab
    abc%=mod
    ab%=mod
    a%=mod
print(abc)