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: Time Limit Exceeded

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

"""
参考：http://tutuz.hateblo.jp/entry/2018/08/06/074104
・別解
・予め必要なA,C,?の個数は集めておく。
・Bの位置を決めて、4つの選び方パターンを全部数え上げる。
"""

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

# あるBの位置よりも左にあるAと?の個数
A, LQ = [0] * len(S), [0] * len(S)
for i in range(len(S)-1):
    a = lq = 0
    if S[i] == 'A':
        a += 1
    if S[i] == '?':
        lq += 1
    A[i+1] = A[i] + a
    LQ[i+1] = LQ[i] + lq
# あるBの位置よりも右にあるCと?の個数
C, RQ = [0] * len(S), [0] * len(S)
for i in range(len(S)-1, 0, -1):
    c = rq = 0
    if S[i] == 'C':
        c += 1
    if S[i] == '?':
        rq += 1
    C[i-1] = C[i] + c
    RQ[i-1] = RQ[i] + rq

ans = 0
for i in range(len(S)):
    if S[i] == '?' or S[i] == 'B':
        # (A,B,C) と選ぶ場合(後ろの3べきは使わなかった?の分)
        case1 = (A[i] * C[i] * pow(3, LQ[i]) * pow(3, RQ[i])) % MOD
        # (A,B,?) と選ぶ場合
        case2 = (A[i] * RQ[i] * pow(3, LQ[i]) * pow(3, max(RQ[i]-1, 0))) % MOD
        # (?,B,C) と選ぶ場合
        case3 = (LQ[i] * C[i] * pow(3, max(LQ[i]-1, 0)) * pow(3, RQ[i])) % MOD
        # (?,B,?) と選ぶ場合
        case4 = (LQ[i] * RQ[i] * pow(3, max(LQ[i]-1, 0)) * pow(3, max(RQ[i]-1, 0))) % MOD
        # 全部足し合わせてMOD
        ans = (ans + case1 + case2 + case3 + case4) % MOD

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
s = list(input())
# from random import randrange
# s = [["A","B","C","?"][randrange(4)] for _ in range(10**5)]
n = len(s)
MOD = 10**9 + 7

def modpow(a,n,m):
    res = 1
    while n>0:
        if n%2==1:
            res = (res * a) % m
        a = (a*a) % m
        n = n//2
    return res

al = [0]*(n+1)
bl = [0]*(n+1)
cl = [0]*(n+1)
ql = [0]*(n+1)
for i in range(n):
    if s[i]=="A":
        al[i+1] += 1
    elif s[i]=="B":
        bl[i+1] += 1
    elif s[i]=="C":
        cl[i+1] += 1
    else:
        ql[i+1] += 1

    al[i+1] += al[i]
    bl[i+1] += bl[i]
    cl[i+1] += cl[i]
    ql[i+1] += ql[i]

res = 0
for i in range(n):
    if s[i]=="A" or s[i]=="C":
        continue

    res += (al[i]-al[0])*(cl[n]-cl[i+1])*modpow(3,(ql[i]-ql[0] + ql[n]-ql[i+1]),MOD)
    res %= MOD
    res += (al[i]-al[0])*(ql[n]-ql[i+1])*modpow(3,(ql[i]-ql[0] + ql[n]-ql[i+1]-1),MOD)
    res %= MOD
    res += (ql[i]-ql[0])*(cl[n]-cl[i+1])*modpow(3,(ql[i]-ql[0]-1 + ql[n]-ql[i+1]),MOD)
    res %= MOD
    res += (ql[i]-ql[0])*(ql[n]-ql[i+1])*modpow(3,(ql[i]-ql[0]-1 + ql[n]-ql[i+1]-1),MOD)
    res %= MOD
print(int(res))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
s = list(input())
n = len(s)
MOD = 10**9 + 7

al = [0]*(n+1)
bl = [0]*(n+1)
cl = [0]*(n+1)
ql = [0]*(n+1)
for i in range(n):
    if s[i]=="A":
        al[i+1] += 1
    elif s[i]=="B":
        bl[i+1] += 1
    elif s[i]=="C":
        cl[i+1] += 1
    else:
        ql[i+1] += 1

    al[i+1] += al[i]
    bl[i+1] += bl[i]
    cl[i+1] += cl[i]
    ql[i+1] += ql[i]

res = 0
for i in range(n):
    if s[i]=="A" or s[i]=="C":
        continue

    res += (al[i]-al[0])*(cl[n]-cl[i+1])*3**(ql[i]-ql[0] + ql[n]-ql[i+1])
    res += (al[i]-al[0])*(ql[n]-ql[i+1])*3**(ql[i]-ql[0] + ql[n]-ql[i+1]-1)
    res += (ql[i]-ql[0])*(cl[n]-cl[i+1])*3**(ql[i]-ql[0]-1 + ql[n]-ql[i+1])
    res += (ql[i]-ql[0])*(ql[n]-ql[i+1])*3**(ql[i]-ql[0]-1 + ql[n]-ql[i+1]-1)
    res %= MOD
print(int(res))

Submission status: Time Limit Exceeded

Solution code:
s=input()
table=[1]+[0 for _ in range(3)] 
abc='ABC'
mod=10**9+7
for i in range(len(s)):
    if s[i]=='?':
        for j in range(3,0,-1):
            table[j]=(3*table[j]+table[j-1])
        table[0]=3*table[0]
    else:
        for j in range(3):
            if s[i]==abc[j]:
                table[j+1]+=table[j]
#print(table)
print(table[3]%mod)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
s = list(input())
mod = 1000000007
c = [1] + [0] * 3
for i in s:
    if i == 'A':
        c[1] = (c[1] + c[0]) % mod
    elif i == 'B':
        c[2] = (c[2] + c[1]) % mod
    elif i == 'C':
        c[3] = (c[3] + c[2]) % mod
    else:
        c[3] = (c[3] * 3 + c[2]) % mod
        c[2] = (c[2] * 3 + c[1]) % mod
        c[1] = (c[1] * 3 + c[0]) % mod
        c[0] *= 3
print(c[3])

Submission status: Time Limit Exceeded

Solution code:
S = input()
strs = list(S)

m = {}
l_s = len(strs)

for i in range(l_s+1):
    m[i] = {}
    for j in range(4):
        m[i][j] = 0

m[l_s][3] = 1

for i in range(l_s)[::-1]:
    s = strs[i]
    for j in range(4):
        m[i][j] = m[i+1][j]
    if s == 'A':
        m[i][0] += m[i+1][1]
    elif s == 'B':
        m[i][1] += m[i+1][2]
    elif s == 'C':
        m[i][2] += m[i+1][3]
    else:
        m[i][0] = m[i+1][0] * 3 + m[i+1][1]
        m[i][1] = m[i+1][1] * 3 + m[i+1][2]
        m[i][2] = m[i+1][2] * 3 + m[i+1][3]
        m[i][3] *= 3
mod = 10**9+7
print(m[0][0] % mod)

Submission status: Time Limit Exceeded

Solution code:
st = input()
wa = 10**9 + 7

s = 0

a1 = 0
q1 = 0

b2 = st[1:].count('C')
q2 = st[1:].count('?')

for i in range(1, len(st)):
    bp = st[i-1]
    p = st[i]
    if p == 'A':
        pass
    if p == 'B':
        pass
    if p == 'C':
        b2 -= 1
    if p == '?':
        q2 -= 1
    if bp == 'A':
        a1 += 1
    if bp == 'B':
        pass
    if bp == 'C':
        pass
    if bp == '?':
        q1 += 1
    if not (p == 'B' or p == '?'):
        continue

    # ABC
    s += a1 * b2 * 3**(q1+q2)

    # AB?
    s += a1 * q2 * 3**(q1+(q2-1))

    # # ?BC
    s += q1 * b2 * 3**((q1-1)+q2)

    # # ?B?
    s = (s + q1 * q2 * 3**((q1-1)+(q2-1))) % wa

print(int(s))

Submission status: Time Limit Exceeded

Solution code:
st = input()
wa = 10**9 + 7

s = 0
for i in range(len(st)):
    p = st[i]
    if not (p == 'B' or p == '?'):
        continue

    # ABC
    a1 = st[:i].count('A')
    q1 = st[:i].count('?')

    b2 = st[i+1:].count('C')
    q2 = st[i+1:].count('?')

    # ABC
    s += a1 * b2 * 3**(q1+q2)

    # AB?
    s += a1 * q2 * 3**(q1+(q2-1))

    # # ?BC
    s += q1 * b2 * 3**((q1-1)+q2)

    # # ?B?
    s = (s + q1 * q2 * 3**((q1-1)+(q2-1))) % wa

print(int(s))

Submission status: Time Limit Exceeded

Solution code:
MOD = 1000000007

S = input()

a, ab, abc, all_s = 0, 0, 0, 1

for s in S:
    if s == "A":
        a += all_s
    elif s == "B":
        ab += a
    elif s == "C":
        abc += ab
    elif s == "?":
        abc = abc * 3 + ab
        ab = ab * 3 + a
        a = a * 3 + all_s
        all_s = all_s * 3

print(abc % MOD)

Submission status: Time Limit Exceeded

Solution code:
MOD = 1000000007

S = input()

a = 0
ab = 0
abc = 0
all_s = 1

for s in S:
    if s == "A":
        a += all_s
    elif s == "B":
        ab += a
    elif s == "C":
        abc += ab
    elif s == "?":
        abc = abc * 3 + ab % MOD
        ab = ab * 3 + a % MOD
        a = a * 3 + all_s % MOD
        all_s = all_s * 3 % MOD

print(abc % MOD)

Submission status: Time Limit Exceeded

Solution code:
MOD = 1000000007

S = input()

a = 0
ab = 0
abc = 0
all_s = 1

for i, s in enumerate(S):
    if s == "A":
        a += all_s
    elif s == "B":
        ab += a
    elif s == "C":
        abc += ab
    elif s == "?":
        abc = abc * 3 + ab
        ab = ab * 3 + a
        a = a * 3 + all_s
        all_s *= 3

print(abc % MOD)

Submission status: Time Limit Exceeded

Solution code:
st = input()
wa = 10**9 + 7

s = 0
for i in range(len(st)):
    p = st[i]
    if not (p == 'B' or p == '?'):
        continue

    # ABC
    a1 = 0
    q1 = 0
    for l in range(0, i):
        if st[l] == 'A':
            a1 += 1
        if st[l] == '?':
            q1 += 1

    b2 = 0
    q2 = 0
    for r in range(i+1, len(st)):
        if st[r] == 'C':
            b2 += 1
        if st[r] == '?':
            q2 += 1

    # ABC
    s += a1 * b2 * 3**(q1+q2)

    # AB?
    s += a1 * q2 * 3**(q1+(q2-1))

    # # ?BC
    s += q1 * b2 * 3**((q1-1)+q2)

    # # ?B?
    s = (s + q1 * q2 * 3**((q1-1)+(q2-1))) % wa

print(int(s))

Submission status: Time Limit Exceeded

Solution code:
mod = int(1e9) + 7


def power(x, y):
    if y == 0       : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else            : return power(x, y//2)**2 * x % mod


def div(a, b):
    return a * power(b, mod-2) % mod


fact = [1] * int(1e5)
for i in range(1, int(1e5)):
    fact[i] = (i * fact[i-1]) % mod


def combination(n, r):
    return div(div(fact[n], fact[r]), fact[n-r])


def main():
    S = input()
    cumsum_A = [0] * len(S)
    cumsum_B = [0] * len(S)
    cumsum_C = [0] * len(S)
    cumsum_Q = [0] * len(S)
    for i in range(len(S)):
        cumsum_A[i] = cumsum_A[i-1] if i > 0 else 0
        cumsum_B[i] = cumsum_B[i-1] if i > 0 else 0
        cumsum_C[i] = cumsum_C[i-1] if i > 0 else 0
        cumsum_Q[i] = cumsum_Q[i-1] if i > 0 else 0
        s = S[i]
        if s == "A":
            cumsum_A[i] += 1
        if s == "B":
            cumsum_B[i] += 1
        if s == "C":
            cumsum_C[i] += 1
        if s == "?":
            cumsum_Q[i] += 1
    retval = 0
    for i in range(len(S)):
        s = S[i]
        if s == "B" or s == "?":
            a = cumsum_A[i]
            aq = cumsum_Q[i]
            c = cumsum_C[-1] - cumsum_C[i]
            cq = cumsum_Q[-1] - cumsum_Q[i]
            if s == "?":
                aq -= 1
            asum = 0
            for j in range(aq+1):
                asum += (a + j) * power(2, aq-j) * combination(aq, j)
                asum %= mod
            csum = 0
            for j in range(cq+1):
                csum += (c + j) * power(2, cq-j) * combination(cq, j)
                csum %= mod
            retval = (retval + asum * csum) % mod
    print(retval)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from pprint import pprint

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

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

dp[len(S)][0] = 0
dp[len(S)][1] = 0
dp[len(S)][2] = 0
dp[len(S)][3] = 1

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

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

Submission status: Time Limit Exceeded

Solution code:
S=input()
N=len(S)
O=1
A=[0]*(N+1)
AB=[0]*(N+1)
ABC=[0]*(N+1)
for i in range(1,N+1):
  A[i]=A[i-1]
  AB[i]=AB[i-1]
  ABC[i]=ABC[i-1]
  if S[i-1] is "A":
    A[i]+=O
  elif S[i-1] is "B":
    AB[i]+=A[i-1]
  elif S[i-1] is "C":
    ABC[i]+=AB[i-1]
  elif S[i-1] is "?":
    A[i]*=3
    A[i]+=O
    AB[i]*=3
    AB[i]+=A[i-1]
    ABC[i]*=3
    ABC[i]+=AB[i-1]
    O*=3
  A[i]=A[i]%(10**9+7)
  AB[i]=AB[i]%(10**9+7)
  ABC[i]=ABC[i]%(10**9+7)
print(int(ABC[N]%(10**9+7)))

Submission status: Time Limit Exceeded

Solution code:
S=list(input())
M=S.count("?")
N=len(S)
A=[0]*(N+1)
Q=[0]*(N+1)
AB=[0]*(N+1)
AQandQB=[0]*(N+1)
QQ=[0]*(N+1)
ABC=[0]*(N+1)
for i in range(1,N+1):
  A[i]=A[i-1]
  Q[i]=Q[i-1]
  if S[i-1] is "A":
    A[i]+=1
  elif S[i-1] is "?":
    Q[i]+=1
  AB[i]=AB[i-1]
  AQandQB[i]=AQandQB[i-1]
  QQ[i]=QQ[i-1]
  if S[i-1] is "B":
    AB[i]+=A[i-1]
    AQandQB[i]+=Q[i-1]
  elif S[i-1] is "?":
    AQandQB[i]+=A[i-1]
    QQ[i]+=Q[i-1]
  ABC[i-1]=ABC[i-1]%(10**9+7)
  ABC[i]=ABC[i-1]
  if S[i-1] is "C":
    ABC[i]+=AB[i-1]*(3**M)+(AQandQB[i-1])*(3**(M-1))+QQ[i-1]*(3**(M-2))
  elif S[i-1] is "?":
    ABC[i]+=AB[i-1]*(3**(M-1))+(AQandQB[i-1])*(3**(M-2))+QQ[i-1]*(3**(M-3))
print(int(ABC[N]%(10**9+7)))

Submission status: Time Limit Exceeded

Solution code:
S=input()
N=len(S)
A=[0]*(N+1)
Q=[0]*(N+1)
AB=[0]*(N+1)
AQandQB=[0]*(N+1)
QQ=[0]*(N+1)
ABC=[0]*(N+1)
for i in range(1,N+1):
  A[i]=A[i-1]
  Q[i]=Q[i-1]
  if S[i-1] is "A":
    A[i]+=1
  elif S[i-1] is "?":
    Q[i]+=1
M=Q[N]
for i in range(1,N+1):
  AB[i]=AB[i-1]
  AQandQB[i]=AQandQB[i-1]
  QQ[i]=QQ[i-1]
  if S[i-1] is "B":
    AB[i]+=A[i-1]
    AQandQB[i]+=Q[i-1]
  elif S[i-1] is "?":
    AQandQB[i]+=A[i-1]
    QQ[i]+=Q[i-1]
for i in range(1,N+1):
  ABC[i-1]=ABC[i-1]%(10**9+7)
  ABC[i]=ABC[i-1]
  if S[i-1] is "C":
    ABC[i]+=AB[i-1]*(3**M)+(AQandQB[i-1])*(3**(M-1))+QQ[i-1]*(3**(M-2))
  elif S[i-1] is "?":
    ABC[i]+=AB[i-1]*(3**(M-1))+(AQandQB[i-1])*(3**(M-2))+QQ[i-1]*(3**(M-3))
print(int(ABC[N]%(10**9+7)))

Submission status: Time Limit Exceeded

Solution code:
S=input()
N=len(S)
A=[0]*(N+1)
Q=[0]*(N+1)
AB=[0]*(N+1)
AQandQB=[0]*(N+1)
QQ=[0]*(N+1)
ABC=[0]*(N+1)
for i in range(1,N+1):
  if S[i-1] is "A":
    A[i]=A[i-1]+1
    Q[i]=Q[i-1]
  elif S[i-1] is "?":
    A[i]=A[i-1]
    Q[i]=Q[i-1]+1
  else:
    A[i]=A[i-1]
    Q[i]=Q[i-1]
M=Q[N]
for i in range(1,N+1):
  AB[i]=AB[i-1]
  AQandQB[i]=AQandQB[i-1]
  QQ[i]=QQ[i-1]
  if S[i-1] is "B":
    AB[i]+=A[i-1]
    AQandQB[i]+=Q[i-1]
  elif S[i-1] is "?":
    AQandQB[i]+=A[i-1]
    QQ[i]+=Q[i-1]
for i in range(1,N+1):
  if S[i-1] is "C":
    ABC[i]=int((ABC[i-1]+AB[i-1]*(3**M)+(AQandQB[i-1])*(3**(M-1))+QQ[i-1]*(3**(M-2)))%(10**9+7))
  elif S[i-1] is "?":
    ABC[i]=int((ABC[i-1]+AB[i-1]*(3**(M-1))+(AQandQB[i-1])*(3**(M-2))+QQ[i-1]*(3**(M-3)))%(10**9+7))
  else:
    ABC[i]=ABC[i-1]
print(ABC[N]%(10**9+8))

Submission status: Time Limit Exceeded

Solution code:
S=input()
N=len(S)
A=[0]*(N+1)
Q=[0]*(N+1)
AB=[0]*(N+1)
AQandQB=[0]*(N+1)
QQ=[0]*(N+1)
ABC=[0]*(N+1)
for i in range(1,N+1):
  if S[i-1] is "A":
    A[i]=A[i-1]+1
    Q[i]=Q[i-1]
  elif S[i-1] is "?":
    A[i]=A[i-1]
    Q[i]=Q[i-1]+1
  else:
    A[i]=A[i-1]
    Q[i]=Q[i-1]
M=Q[N]
for i in range(1,N+1):
  AB[i]=AB[i-1]
  AQandQB[i]=AQandQB[i-1]
  QQ[i]=QQ[i-1]
  if S[i-1] is "B":
    AB[i]+=A[i-1]
    AQandQB[i]+=Q[i-1]
  elif S[i-1] is "?":
    AQandQB[i]+=A[i-1]
    QQ[i]+=Q[i-1]
for i in range(1,N+1):
  if S[i-1] is "C":
    ABC[i]=int((ABC[i-1]+AB[i-1]*(3**M)+(AQandQB[i-1])*(3**(M-1))+QQ[i-1]*(3**(M-2)))%(10**9+7))
  elif S[i-1] is "?":
    ABC[i]=int((ABC[i-1]+AB[i-1]*(3**(M-1))+(AQandQB[i-1])*(3**(M-2))+QQ[i-1]*(3**(M-3)))%(10**9+7))
  else:
    ABC[i]=ABC[i-1]
print(ABC[N]%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
S=list(input())
N=len(S)
A=[0]*(N+1)
Q=[0]*(N+1)
AB=[0]*(N+1)
AQandQB=[0]*(N+1)
QQ=[0]*(N+1)
ABC=[0]*(N+1)
for i in range(1,N+1):
  if S[i-1] is "A":
    A[i]=A[i-1]+1
    Q[i]=Q[i-1]
  elif S[i-1] is "?":
    A[i]=A[i-1]
    Q[i]=Q[i-1]+1
  else:
    A[i]=A[i-1]
    Q[i]=Q[i-1]
M=Q[N]
for i in range(1,N+1):
  AB[i]=AB[i-1]
  AQandQB[i]=AQandQB[i-1]
  QQ[i]=QQ[i-1]
  if S[i-1] is "B":
    AB[i]+=A[i-1]
    AQandQB[i]+=Q[i-1]
  elif S[i-1] is "?":
    AQandQB[i]+=A[i-1]
    QQ[i]+=Q[i-1]
for i in range(1,N+1):
  if S[i-1] is "C":
    ABC[i]=int((ABC[i-1]+AB[i-1]*(3**M)+(AQandQB[i-1])*(3**(M-1))+QQ[i-1]*(3**(M-2)))%(10**9+7))
  elif S[i-1] is "?":
    ABC[i]=int((ABC[i-1]+AB[i-1]*(3**(M-1))+(AQandQB[i-1])*(3**(M-2))+QQ[i-1]*(3**(M-3)))%(10**9+7))
  else:
    ABC[i]=ABC[i-1]
print(ABC[N]%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
Mod = 10**9+7
S = input()
N = len(S)
O = 1
A = [0]*N
AB = [0]*N
ABC = [0]*N

for i in range(N):
    A[i] = A[i-1]
    AB[i] = AB[i-1]
    ABC[i] = ABC[i-1]
    if S[i] == 'A':
        A[i] += O
    if S[i] == 'B':
        AB[i] += A[i-1]
    if S[i] == 'C':
        ABC[i] += AB[i-1]
    if S[i] == '?':
        A[i] *= 3
        A[i] += O
        AB[i] *= 3
        AB[i] += A[i-1]
        ABC[i] *= 3
        ABC[i] += AB[i-1]
        O *= 3
    A[i] %= Mod
    AB[i] %= Mod
    ABC[i] %= Mod

print(ABC[-1])

Submission status: Time Limit Exceeded

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

modulus = 10 ** 9 + 7
s = input()
n = len(s)


def dp(i, j):
    """
    dynamic programming for abc 104
    :param i: index of the given string
    :param j: count of letters of composed string (like 'ABC')
    :return: the number of cases
    """
    if i == n:
        if j == 3:
            return 1
        else:
            return 0

    else:
        wildcard = s[i] == '?'
        if j == 3:
            m = 3 if wildcard else 1
            return m * dp(i + 1, 3) % modulus

        else:
            m1 = 3 if wildcard else 1
            m2 = 1 if wildcard or s[i] == 'ABC'[j] else 0
    
            return (m1 * dp(i + 1, j) + m2 * dp(i + 1, j + 1)) % modulus


print(dp(0, 0))

Submission status: Time Limit Exceeded

Solution code:
class ABC104:
    modulus = 10 ** 9 + 7

    def __init__(self, s):
        self.s = s
        self.n = len(s)

    def dp(self, i, j):
        """
        dynamic programming for abc 104
        :param i: index of the given string
        :param j: count of letters of composed string (like 'ABC')
        :return: the number of cases
        """
        if i == self.n:
            if j == 3:
                return 1
            else:
                return 0

        if i < self.n and j == 3:
            m = 3 if self.s[i] == '?' else 1
            return m * self.dp(i + 1, 3) % self.modulus

        if i < self.n and j < 3:
            m1 = 3 if self.s[i] == '?' else 1
            m2 = 1 if self.s[i] == '?' or self.s[i] == 'ABC'[j] else 0

            _pass = m1 * self.dp(i + 1, j) % self.modulus
            _take = m2 * self.dp(i + 1, j + 1) % self.modulus

            return _pass + _take


if __name__ == '__main__':
    import sys
    sys.setrecursionlimit(10**6)

    abc = ABC104(input())
    print(abc.dp(0, 0))

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7
MAX = 10 ** 5 + 10

def main():
    s = str(input())
    l = len(s)
    dp = [[0 for _ in range(4)] for _ in range(MAX)]
    if l < 3:
        return 0
    abc = "ABC"
    dp[l][3] = 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
                if j < 3:
                    dp[i][j] = 0
                continue

            if i < l and j < 3:
                if s[i] == "?": m1 = 3
                else: m1 = 1
                if s[i] == "?" or s[i] == abc[j]:m2 = 1
                else: m2 = 0
                dp[i][j] = m1 * dp[i+1][j] + m2 * dp[i+1][j+1]
                continue

            if i < l:
                if s[i] == "?": m = 3
                else: m = 1
                dp[i][j] = dp[i+1][j] * m
                continue

    return dp[0][0] % MOD


print(main())

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7


def main():
    s = str(input())
    l = len(s)
    dp = [[0 for _ in range(4)] for _ in range(l+1)]
    if l < 3:
        return 0
    abc = "ABC"
    dp[l][3] = 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
                if j < 3:
                    dp[i][j] = 0
                continue

            if i < l and j < 3:
                if s[i] == "?": m1 = 3
                else: m1 = 1
                if s[i] == "?" or s[i] == abc[j]:m2 = 1
                else: m2 = 0
                dp[i][j] = m1 * dp[i+1][j] + m2 * dp[i+1][j+1]
                continue

            if i < l:
                if s[i] == "?": m = 3
                else: m = 1
                dp[i][j] = dp[i+1][j] * m
                continue

    return dp[0][0] % MOD


print(main())

Submission status: Time Limit Exceeded

Solution code:
# coding:utf-8

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


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


# aのp乗を求めるアルゴリズム
# MOD版
def pow_mod(a, p):
    if p == 0: return 1
    if p < 0: return 0

    if p % 2 == 0:
        half_p = p // 2
        half = pow_mod(a, half_p)
        return half * half % MOD
    else:
        return a * pow_mod(a, p - 1) % MOD


S = input()

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

A = [-INF for _ in range(len(S))]
C = A[:]
Q = A[:]

A[0] = 1 if S[0] == 'A' else 0
C[0] = 1 if S[0] == 'C' else 0
Q[0] = 1 if S[0] == '?' else 0

for i in range(1, len(S)):
    A[i] = A[i - 1] + 1 if S[i] == 'A' else A[i - 1]
    C[i] = C[i - 1] + 1 if S[i] == 'C' else C[i - 1]
    Q[i] = Q[i - 1] + 1 if S[i] == '?' else Q[i - 1]

# print(A)
# print(C)
# print(Q)
ans = 0
for i in range(1, len(S) - 1):
    if S[i] == 'A' or S[i] == 'C':
        continue

    # A, B, Cの個数
    ans += A[i - 1] * (C[-1] - C[i]) * pow_mod(3, Q[i - 1] + Q[-1] - Q[i])
    # ?, B, Cの個数
    ans += Q[i - 1] * (C[-1] - C[i]) * pow_mod(3, Q[i - 1] - 1 + Q[-1] - Q[i])
    # A, B, ?の個数
    ans += A[i - 1] * (Q[-1] - Q[i]) * pow_mod(3, Q[i - 1] + Q[-1] - Q[i] - 1)
    # ?, B, ?の個数
    ans += Q[i - 1] * (Q[-1] - Q[i]) * pow_mod(3, Q[i - 1] + Q[-1] - Q[i] - 2)

    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
s = input()

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

for i in reversed(range((len(s)))):
    m = 1
    m1 = 1
    m2 = 0
    m3 = 0
    m4 = 0
    if s[i] == '?':
        m = 3
        m1 = 3
        m2 = 1
        m3 = 1
        m4 = 1

    if s[i] == 'C':
        m2 = 1

    if s[i] == 'B':
        m3 = 1

    if s[i] == 'A':
        m4 = 1

    dp[i][3] = m * dp[i+1][3]
    dp[i][2] = m1 * dp[i+1][2] + m2 * dp[i+1][3]
    dp[i][1] = m1 * dp[i+1][1] + m3 * dp[i+1][2]
    dp[i][0] = m1 * dp[i+1][0] + m4 * dp[i+1][1]

n = 10 ** 9 + 7
ans = dp[0][0] % n
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()

dp3 = 1
dp2 = 0
dp1 = 0
dp0 = 0

for i in reversed(range((len(s)))):
    m = 1
    m1 = 1
    m2 = 0
    m3 = 0
    m4 = 0
    if s[i] == '?':
        m = 3
        m1 = 3
        m2 = 1
        m3 = 1
        m4 = 1

    if s[i] == 'C':
        m2 = 1

    if s[i] == 'B':
        m3 = 1

    if s[i] == 'A':
        m4 = 1

    t_dp3 = m * dp3
    t_dp2 = m1 * dp2 + m2 * dp3
    t_dp1 = m1 * dp1 + m3 * dp2
    t_dp0 = m1 * dp0 + m4 * dp1
    dp3 = t_dp3
    dp2 = t_dp2
    dp1 = t_dp1
    dp0 = t_dp0

n = 10 ** 9 + 7
ans = dp0 % n
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()

dp3 = 1
dp2 = 0
dp1 = 0
dp0 = 0

for i in reversed(range((len(s)))):
    if s[i] == '?':
        m = 3
    else:
        m = 1

    if s[i] == '?':
        m1 = 3
    else:
        m1 = 1

    if s[i] == '?' or s[i] == 'C':
        m2 = 1
    else:
        m2 = 0

    if s[i] == '?' or s[i] == 'B':
        m3 = 1
    else:
        m3 = 0

    if s[i] == '?' or s[i] == 'A':
        m4 = 1
    else:
        m4 = 0

    t_dp3 = m * dp3
    t_dp2 = m1 * dp2 + m2 * dp3
    t_dp1 = m1 * dp1 + m3 * dp2
    t_dp0 = m1 * dp0 + m4 * dp1
    dp3 = t_dp3
    dp2 = t_dp2
    dp1 = t_dp1
    dp0 = t_dp0

n = 10 ** 9 + 7
ans = dp0 % n
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S=raw_input()
L=len(S)
 
M=10**9+7
 
dp=[ [ 0 for i in range(4) ] for k in range(L+1)]
all=1
 
for i in range(L):
	if S[i]=="A":
		dp[i+1][1]=( dp[i][1]+all ) %M
		dp[i+1][2]=dp[i][2]%M
		dp[i+1][3]=dp[i][3]%M
	if S[i]=="B":
		dp[i+1][2]=( dp[i][2]+dp[i][1] )%M
		dp[i+1][3]=dp[i][3]%M
		dp[i+1][1]=dp[i][1]%M
	if S[i]=="C":
		dp[i+1][3]=( dp[i][3]+dp[i][2] )%M
		dp[i+1][2]=dp[i][2]%M
		dp[i+1][1]=dp[i][1]%M
 
	if S[i]=="?":
		dp[i+1][1]=( dp[i][1]*3+all )%M
		dp[i+1][2]=( dp[i][2]*3+dp[i][1] )%M
		dp[i+1][3]=( dp[i][3]*3+dp[i][2] )%M
		all*=3	
 
print ( dp[-1][3] ) %M

Submission status: Time Limit Exceeded

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

num=[ [ 0 for i in range(4) ] for j in range(N) ]		# i=0 A, i=1 B, i=2 C, i=3 ?

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

ans=0

for i in range(1,N):
	if S[i]=="B" or S[i]=="?":
		a=num[i-1][0]
		c=num[N-1][2]-num[i][2]
		ql=num[i-1][3]
		qr=num[N-1][3]-num[i][3]

		#ABC
		ans+=a*(3**ql)*c*(3**qr)%mod

		#AB?
		if qr>0:
			ans+=a*qr*(3**ql)*(3**(qr-1) )%mod

		#?BC
		if ql>0:
			ans+=(3**(ql-1) )*ql*c*(3**qr)%mod

		#?B?
		if ql>0 and qr>0:
			ans+=ql*(3**(ql-1) )*qr*(3**(qr-1) )%mod

print ans%mod

Submission status: Time Limit Exceeded

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

num=[ [ 0 for i in range(4) ] for j in range(N) ]		# i=0 A, i=1 B, i=2 C, i=3 ?

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

ans=0

for i in range(1,N):
	if S[i]=="B" or S[i]=="?":
		a=num[i-1][0]
		c=num[N-1][2]-num[i][2]
		ql=num[i-1][3]
		qr=num[N-1][3]-num[i][3]

		#ABC
		ans+=a*(3**ql)*c*(3**qr)

		#AB?
		if qr>0:
			ans+=a*qr*(3**ql)*(3**(qr-1) )

		#?BC
		if ql>0:
			ans+=(3**(ql-1) )*ql*c*(3**qr)

		#?B?
		if ql>0 and qr>0:
			ans+=ql*(3**(ql-1) )*qr*(3**(qr-1) )

print ans%mod

Submission status: Time Limit Exceeded

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

moji = [[0,0,0,0] for _ in range(n+1)]

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

ans = 0
for i in range(n):
    al,cr,hl,hr = moji[i][0], moji[n][2]-moji[i+1][2], moji[i][3], moji[n][3]-moji[i+1][3]
    if s[i] == 'B' or s[i] == '?':
        k = (al*3 + hl) * (cr*3 + hr) % mod
        k *= 3**(hr+hl-2)
        ans += int(k) % mod
print(ans%mod)

Submission status: Time Limit Exceeded

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

moji = [[0,0,0,0] for _ in range(n+1)]

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

ans = 0
for i in range(n):
    al,cr,hl,hr = moji[i][0], moji[n][2]-moji[i+1][2], moji[i][3], moji[n][3]-moji[i+1][3]
    if s[i] == 'B' or s[i] == '?':
        k = (al*3 + hl) * (cr*3 + hr) * 3**(hr+hl-2)
        ans += int(k) % mod
print(ans%mod)

Submission status: Time Limit Exceeded

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

moji = [[0,0,0,0] for _ in range(n+1)]

for i in range(1,n+1):
    moji[i] = copy.deepcopy(moji[i-1])
    if s[i-1] == 'A':
        moji[i][0] += 1
    if s[i-1] == 'B':
        moji[i][1] += 1
    if s[i-1] == 'C':
        moji[i][2] += 1
    if s[i-1] == '?':
        moji[i][3] += 1

ans = 0
for i in range(n):
    al,cr,hl,hr = moji[i][0], moji[n][2]-moji[i+1][2], moji[i][3], moji[n][3]-moji[i+1][3]
    if s[i] == 'B' or s[i] == '?':
        ans += (al*3 + hl) * (cr*3 + hr) * 3**(hr+hl-2)
    ans %= mod
print(int(ans))

Submission status: Time Limit Exceeded

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

count = 0
for i, s in enumerate(S):
    if s not in ["B", "?"]:
        continue

    left_a = len([j for j in S[:i] if j == "A"])
    left_q = len([j for j in S[:i] if j == "?"])

    right_c = len([j for j in S[i+1:] if j == "C"])
    right_q = len([j for j in S[i+1:] if j == "?"])

    # print(left_a, left_q, right_c, right_q)

    k = 3 ** (left_q + right_q - 2)

    count += left_a * right_c * 3 ** 2 * k
    count += left_q * right_c * 3 * k
    count += left_a * right_q * 3 * k
    count += left_q * right_q * k

print(int(count) % m)

Submission status: Time Limit Exceeded

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

count = 0
for i, s in enumerate(S):
    if s not in ["B", "?"]:
        continue

    left_a = len([j for j in S[:i] if j == "A"])
    left_q = len([j for j in S[:i] if j == "?"])

    right_c = len([j for j in S[i+1:] if j == "C"])
    right_q = len([j for j in S[i+1:] if j == "?"])

    # print(left_a, left_q, right_c, right_q)

    count += left_a * right_c * 3 ** (left_q + right_q)
    count += left_q * right_c * 3 ** (left_q - 1 + right_q)
    count += left_a * right_q * 3 ** (left_q + right_q - 1)
    count += left_q * right_q * 3 ** (left_q + right_q - 2)

print(int(count) % m)