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:
from collections import deque
mod = 1000000007

S = input()
L = len(S)
i = L-1
A = [0 for _ in range(L+1)]
B = [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]
    B[i] = B[i+1]

    if S[i] == '?':
        Q[i] += 1
    elif S[i] == 'A':
        A[i] += 1
    elif S[i] == 'B':
        B[i] += 1
    elif S[i] == 'C':
        C[i] += 1
    else:
        print("error")
    i -= 1
#i以降にある文字の数

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]
        #print(i)
        #print((a,qleft,c,qright))
        if qleft > 0:
            LEFT = a*3**qleft + qleft*3**(qleft-1)
        else: 
            LEFT = a*3**qleft
        if qright > 0:
            RIGHT = c*3**qright + qright*3**(qright-1)
        else:
            RIGHT = c*3**qright
        LEFT = LEFT%mod
        RIGHT = RIGHT%mod
        number = (LEFT * RIGHT)%mod
        #print(number)
        ans = (ans + number)%mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
l = tuple(input())
n = len(l)
ABC_n = 0
BC_n = 0
C_n = 0
ha_n = 0





for i in range(n-1, -1, -1):
    car = l[i]
    if car == 'A':
        ABC_n += BC_n
        ABC_n = ABC_n % (10**9 + 7)
    elif car == 'B':
        BC_n += C_n
        BC_n = BC_n % (10**9 + 7)
    elif car == 'C':
        C_n += 3**ha_n
        C_n = C_n % (10**9 + 7)
    else:
        ABC_n = 3*ABC_n +  BC_n
        ABC_n = ABC_n % (10**9 + 7)
        BC_n = 3*BC_n + C_n
        BC_n = BC_n % (10**9 + 7)
        C_n = 3*C_n  + 3**ha_n
        C_n = C_n % (10**9 + 7)
        ha_n += 1


print(ABC_n)

Submission status: Time Limit Exceeded

Solution code:
S = input()
a = 0
c = S.count("C")
ql = 0
qr = S.count("?")
ans = 0
mod = 10**9 + 7
for s in S:
    if s == "C":
        c -= 1
    elif s == "?":
        qr -= 1

    if s == "B" or s == "?":
        ans += ((ql * 3**max(0, ql-1) + a * 3**ql) % mod) * ((qr * 3**max(0, qr-1) + c * 3**qr) % mod)
        ans %= mod

    if s == "A":
        a += 1
    elif s == "?":
        ql += 1

print(ans)

Submission status: Time Limit Exceeded

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
  elif s[i]=="C":
    abc=(abc+ab)%m
  else:
    abc=(abc*3+ab)%m
    ab=ab*3+a
    a=(a*3+q)%m
    q=(q*3)%m
print(abc)

Submission status: Time Limit Exceeded

Solution code:
S = input()
a = 0
c = S.count("C")
ql = 0
qr = S.count("?")
ans = 0
for s in S:
    if s == "C":
        c -= 1
    elif s == "?":
        qr -= 1

    if s == "B" or s == "?":
        ans += (ql * 3**max(0, ql-1) + a * 3**ql) * (qr * 3**max(0, qr-1) + c * 3**qr)
        ans %= 10**9 + 7

    if s == "A":
        a += 1
    elif s == "?":
        ql += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from scipy.misc import comb

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


ca = [0] * N
cq1 = [0] * N
if S[0] == 'A':
    ca[0] = 1
if S[0] == '?':
    cq1[0] = 1
for i in range(1, N):
    if S[i] == 'A':
        ca[i] = ca[i - 1] + 1
    else:
        ca[i] = ca[i - 1]
    if S[i] == '?':
        cq1[i] = cq1[i - 1] + 1
    else:
        cq1[i] = cq1[i - 1]

cc = [0] * N
cq2 = [0] * N
if S[-1] == 'C':
    cc[0] = 1
if S[-1] == '?':
    cq2[0] = 1
for i in range(1, N):
    if S[N - 1 - i] == 'C':
        cc[i] = cc[i - 1] + 1
    else:
        cc[i] = cc[i - 1]
    if S[N - 1 - i] == '?':
        cq2[i] = cq2[i - 1] + 1
    else:
        cq2[i] = cq2[i - 1]
cc = cc[::-1]
cq2 = cq2[::-1]

memo = {}
def f(q):
    if q in memo:
        return memo[q]
    x = [0] * (q + 1)
    for i in range(q + 1):
        x[i] = 2 ** (q - i) * comb(q, i, exact=True)
    memo[q] = x
    return x


def g(x, q):
    t = f(q)
    c = 0
    for i in range(q + 1):
        c += t[i] * (i + x)
    return c


ans = 0
for i in range(1, N - 1):
    if S[i] in ['B', '?']:
        ans += g(ca[i - 1], cq1[i - 1]) * g(cc[i + 1], cq2[i + 1])
print(ans % mod)

Submission status: Time Limit Exceeded

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
  elif s[i]=="C":
    abc=(abc+ab)%m
  else:
    abc=(abc*3+ab)%m
    ab=ab*3+a
    a=(a*3+q)%m
    q=q*3
print(abc)

Submission status: Time Limit Exceeded

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 = (3**A2[i])*A1[i] + 3**(A2[i]-1)*A2[i]
            if ta>mod:
                ta %= mod
        if C2[i]==0:
            tc = C1[i]
        else:
            tc = (3**C2[i])*C1[i] + 3**(C2[i]-1)*C2[i]
            if tc > mod:
                tc %= mod
        Ans += ta*tc
        if Ans > mod:
            Ans %= mod

print(Ans)

Submission status: Time Limit Exceeded

Solution code:
s=input()

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

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

Submission status: Time Limit Exceeded

Solution code:
S = input()
mod = 10 ** 9 + 7
count = 0
for i in range(1,len(S)-1):
    if S[i] == "B" or S[i] == "?":
        leftA, leftQ = S[:i].count("A"), S[:i].count("?")
        rightC, rightQ = S[i+1:].count("C"), S[i+1:].count("?")
        if leftQ >= 1:
            leftpatt = leftA * (3 ** leftQ) + leftQ * (3 ** (leftQ - 1))
        else:
            leftpatt = leftA
        if rightQ >= 1:
            rightpatt = rightC * (3 ** rightQ) + rightQ * (3 ** (rightQ - 1))
        else:
            rightpatt = rightC
        count += leftpatt * rightpatt
        count %= mod
print(int(count))

Submission status: Time Limit Exceeded

Solution code:
s = input()

ans = 0

for i in range(1,len(s)-1):
    if s[i]=='B' or s[i]=='?':
        x = s[:i].count('?')
        a = s[:i].count('A')
        if x ==0:
            a_ = a % (10 ** 9 + 7)
        else:
            a_ = ((3*a+x)*(3 ** (x-1))) % (10 ** 9 + 7)
        y = s[i+1:].count('?')
        c = s[i+1:].count('C')
        if y ==0:
            c_ = c%(10**9+7)
        else:
            c_ = ((3*c+y)*(3**(y-1)))%(10**9+7)
        ans += (a_*c_)%(10**9+7)

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

Submission status: Time Limit Exceeded

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 = (3**A2[i])*A1[i] + 3**(A2[i]-1)*A2[i]
            ta %= mod
        if C2[i]==0:
            tc = C1[i]
        else:
            tc = (3**C2[i])*C1[i] + 3**(C2[i]-1)*C2[i]
            tc %= mod
        Ans += ta*tc
        Ans %= mod

print(Ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
S = input()
MOD = 10 ** 9 + 7
ans = 0
front = Counter({})
back = Counter(S)
for i in range(len(S)):
  c = S[i]
  back[c] -= 1
  # Bの位置を固定
  if c == 'B' or c == '?':
    # ?を使わない
    ans += front['A'] * back['C'] * (3 ** (front['?'] + back['?']))
    # Aだけ?をつかう
    ans += front['?'] * back['C'] * (3 ** (front['?'] + back['?'] - 1))
    # Cだけ?をつかう
    ans += front['A'] * back['?'] * (3 ** (front['?'] + back['?'] - 1))
    # 両方?をつかう
    ans += front['?'] * back['?'] * (3 ** (front['?'] + back['?'] - 2))
    ans %= MOD
  front[c] += 1

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
s=input()

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

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

Submission status: Time Limit Exceeded

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 = (3**A2[i])*A1[i] + 3**(A2[i]-1)*A2[i]
        if C2[i]==0:
            tc = C1[i]
        else:
            tc = (3**C2[i])*C1[i] + 3**(C2[i]-1)*C2[i]
        Ans += ta*tc
        Ans %= mod

print(Ans)

Submission status: Time Limit Exceeded

Solution code:
s=input()

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

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

Submission status: Time Limit Exceeded

Solution code:
l = list(input())
n = len(l)
ABC_n = 0
BC_n = 0
C_n = 0
ha_n = 0


def count_inc(car):
    global ABC_n, BC_n, C_n, ha_n
    if car == 'A':
        ABC_n += BC_n
        ABC_n = ABC_n % (10**9 + 7)
    elif car == 'B':
        BC_n += C_n
        BC_n = BC_n % (10**9 + 7)
    elif car == 'C':
        C_n += 3**ha_n
        C_n = C_n % (10**9 + 7)
    else:
        ABC_n = 3*ABC_n +  BC_n
        ABC_n = ABC_n % (10**9 + 7)
        BC_n = 3*BC_n + C_n
        BC_n = BC_n % (10**9 + 7)
        C_n = 3*C_n  + 3**ha_n
        C_n = C_n % (10**9 + 7)
        ha_n += 1

for i in range(n-1, -1, -1):
    count_inc(l[i])
    

print(ABC_n)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
S = input()
MOD = 10 ** 9 + 7
ans = 0
for i in range(len(S)):
  # Bの位置を固定
  if S[i] == 'B' or S[i] == '?':
    front = Counter(S[:i])
    back = Counter(S[i+1:])
    # ?を使わない
    ans += front['A'] * back['C'] * (3 ** (front['?'] + back['?']))
    # Aだけ?をつかう
    ans += front['?'] * back['C'] * (3 ** (front['?'] + back['?'] - 1))
    # Cだけ?をつかう
    ans += front['A'] * back['?'] * (3 ** (front['?'] + back['?'] - 1))
    # 両方?をつかう
    ans += front['?'] * back['?'] * (3 ** (front['?'] + back['?'] - 2))
    ans %= MOD

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
s=input()

a=0
ab=0
abc=0
q=0

#if s[0]=="A" :
#  a=1
#elif s[0]=="?":
#  a=1
#  q=1
#print(str(a)+" "+str(ab)+" "+str(abc)+" "+str(q))

for i in range(len(s)):
  if s[i]=="A":
    a=(a+3**q)%(10**9+7)
  elif s[i]=="B":
    ab=(ab+a)%(10**9+7)
  elif s[i]=="C":
    abc=(abc+ab)%(10**9+7)
  elif s[i]=="?":
    abc=(abc*3+ab)%(10**9+7)
    
    ab=(ab*3+a)%(10**9+7)
    a=(a*3+3**q)%(10**9+7)
    q+=1
  #print(str(a)+" "+str(ab)+" "+str(abc)+" "+str(q))
    
print(abc)

Submission status: Time Limit Exceeded

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
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)
    mem[idx][num] = res
    return res

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

Submission status: Time Limit Exceeded

Solution code:
s=input()

a=0
ab=0
abc=0
q=0

#if s[0]=="A" :
#  a=1
#elif s[0]=="?":
#  a=1
#  q=1
#print(str(a)+" "+str(ab)+" "+str(abc)+" "+str(q))

for i in range(len(s)):
  if s[i]=="A":
    a=a+3**q
  elif s[i]=="B":
    ab=ab+a
  elif s[i]=="C":
    abc=(abc+ab)%(10**9+7)
  elif s[i]=="?":
    abc=(abc*3+ab)%(10**9+7)
    
    ab=ab*3+a
    a=a*3
    
    a=a+3**q
    q+=1
  #print(str(a)+" "+str(ab)+" "+str(abc)+" "+str(q))
    
print(abc)

Submission status: Time Limit Exceeded

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

S = input()
N = len(S)

rS = S[::-1]
p = [1] * (N+1)
for i in range(1, N+1):
    p[i] = p[i-1]
    if rS[i-1] == '?':
        p[i] = p[i] * 3
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)
print (ans)

Submission status: Time Limit Exceeded

Solution code:
s=input()

a=0
ab=0
abc=0
q=0

#if s[0]=="A" :
#  a=1
#elif s[0]=="?":
#  a=1
#  q=1
#print(str(a)+" "+str(ab)+" "+str(abc)+" "+str(q))

for i in range(len(s)):
  if s[i]=="A":
    a=a+3**q
  elif s[i]=="B":
    ab=ab+a
  elif s[i]=="C":
    abc=abc+ab
  elif s[i]=="?":
    abc=abc*3+ab
    
    ab=ab*3+a
    a=a*3
    
    a=a+3**q
    q+=1
  #print(str(a)+" "+str(ab)+" "+str(abc)+" "+str(q))
    
print(abc%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
S = input()
mod = 10 ** 9 + 7
count = 0
for i in range(1,len(S)-1):
    if S[i] == "B" or S[i] == "?":
        left, right = list(S[:i]), list(S[i+1:])
        leftA, leftQ = left.count("A"), left.count("?")
        rightC, rightQ = right.count("C"), right.count("?")
        if leftQ >= 1:
            leftpatt = leftA * (3 ** leftQ) + leftQ * (3 ** (leftQ - 1))
        else:
            leftpatt = leftA
        if rightQ >= 1:
            rightpatt = rightC * (3 ** rightQ) + rightQ * (3 ** (rightQ - 1))
        else:
            rightpatt = rightC
        count += leftpatt * rightpatt
        count %= mod
print(int(count))

Submission status: Time Limit Exceeded

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+=np.roll(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: Time Limit Exceeded

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+=np.roll(wayB,1)
		wayB+=np.roll(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))

Submission status: Time Limit Exceeded

Solution code:
s = input()
n = 0
a = 0
b = 0
c = 0

v = 0

for i in range(len(s)):
    if s[i]=='?':
        v += 1

for i in range(len(s)):
    if s[i]=='A' or s[i]=='?':
        if s[i]=='?':
            a = 1
        else:
            a = 0
        for j in range(i+1, len(s)):
            if s[j]=='B' or s[j]=='?':
                if s[j] == '?':
                    b = 1
                else:
                    b = 0
                for k in range(j+1, len(s)):
                    if s[k] == 'C' or s[k]=='?':
                        if s[k] == '?':
                            c = 1
                        else:
                            c = 0
                        n += 3**(v-a-b-c)
                        n %= 1000000007
                            
print(n)

Submission status: Time Limit Exceeded

Solution code:
#a,b=map(int,input().split())
import numpy as np
 
s=input()
n=len(s)
wayA=np.array([0,0,0,0],dtype=np.int32)
wayB=np.array([0,0,0,0],dtype=np.int32)
wayC=np.array([0,0,0,0],dtype=np.int32)
hatena=0
MOD=1000000007
for c in s:
	if c=="A":
		wayA[0]=wayA[0]+1
	if c=="B":
		wayB+=wayA;
	if c=='C':
		wayC=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=hatena+1
	for z in range(0,4):
		wayA[z]=wayA[z]%MOD
		wayB[z]=wayB[z]%MOD
		wayC[z]=wayC[z]%MOD
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(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
 
s=input()
n=len(s)
MOD=1000000007
wayA=np.array([0,0,0,0],dtype=np.int32)
wayB=np.array([0,0,0,0],dtype=np.int32)
wayC=np.array([0,0,0,0],dtype=np.int32)
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+=np.roll(wayB,1)
		wayB+=np.roll(wayA,1)
		wayA[1]+=1
		hatena+=1
	wayA%=MOD2
	wayB%=MOD2
	wayC%=MOD2
ans=0
for i in range(0,4):
	p3=1
	for j in range(hatena-i):
		p3*=3
		p3%=MOD
	ans+=p3*wayC[i]
	ans=ans%MOD
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
#a,b=map(int,input().split())
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.int64)
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+=np.roll(wayB,1)
		wayB+=np.roll(wayA,1)
		wayA[1]+=1
		hatena+=1
	wayA%=MOD2
	wayB%=MOD2
	wayC%=MOD2
ans=0
for i in range(0,4):
	p3=1
	for j in range(hatena-i):
		p3*=3
		p3%=MOD
	ans+=p3*wayC[i]
	ans=ans%MOD
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
#a,b=map(int,input().split())
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.int64)
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+=np.roll(wayB,1)
		wayB+=np.roll(wayA,1)
		wayA[1]+=1
		hatena+=1
	wayA%=MOD2
	wayB%=MOD2
	wayC%=MOD2
ans=0
for i in range(0,4):
	ans+=pow(3,hatena-i)*wayC[i]
	ans=ans%MOD
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
#a,b=map(int,input().split())
s=input()
n=len(s)
wayA=[0,0,0,0]
wayB=[0,0,0,0]
wayC=[0,0,0,0]
hatena=0
MOD=1000000007
for c in s:
	if c=="A":
		wayA[0]=wayA[0]+1
	if c=="B":
		wayB[0]=wayB[0]+wayA[0]
		wayB[1]=wayB[1]+wayA[1]
	if c=='C':
		wayC=wayC+wayB
		wayC[0]=wayC[0]+wayB[0]
		wayC[1]=wayC[1]+wayB[1]
		wayC[2]=wayC[2]+wayB[2]
	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=hatena+1
	#for z in range(0,4):
	#	wayA[z]=wayA[z]%MOD
	#	wayB[z]=wayB[z]%MOD
	#	wayC[z]=wayC[z]%MOD
ans=0
for i in range(0,4):
	p3=1
	wayC[i]=wayC[i]%MOD
	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%1000000007
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
#a,b=map(int,input().split())
s=input()
n=len(s)
wayA=[0,0,0,0]
wayB=[0,0,0,0]
wayC=[0,0,0,0]
hatena=0
MOD=1000000007
for c in s:
	if c=="A":
		wayA[0]=wayA[0]+1
	if c=="B":
		wayB[0]=wayB[0]+wayA[0]
		wayB[1]=wayB[1]+wayA[1]
	if c=='C':
		wayC=wayC+wayB
		wayC[0]=wayC[0]+wayB[0]
		wayC[1]=wayC[1]+wayB[1]
		wayC[2]=wayC[2]+wayB[2]
	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=hatena+1
	for z in range(0,4):
		wayA[z]=wayA[z]%MOD
		wayB[z]=wayB[z]%MOD
		wayC[z]=wayC[z]%MOD
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%1000000007
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
#a,b=map(int,input().split())
s=input()
n=len(s)
wayA=[0,0,0,0]
wayB=[0,0,0,0]
wayC=[0,0,0,0]
hatena=0
MOD=1000000007
for c in s:
	if c=="A":
		wayA[0]=wayA[0]+1
	if c=="B":
		wayB[0]=wayB[0]+wayA[0]
		wayB[1]=wayB[1]+wayA[1]
	if c=='C':
		wayC=wayC+wayB
		wayC[0]=wayC[0]+wayB[0]
		wayC[1]=wayC[1]+wayB[1]
		wayC[2]=wayC[2]+wayB[2]
	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=hatena+1
	for z in range(0,4):
		wayA[z]=wayA[z]%MOD
		wayB[z]=wayB[z]%MOD
		wayC[z]=wayC[z]%MOD
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%1000000007
print(int(ans))

Submission status: Memory Limit Exceeded

Solution code:
s = input()
dp = [[0 for _ in range(0,4)] for _ in range(0,len(s)+1)]
dp[len(s)][3] = 1
dp[len(s)][0] = 0
dp[len(s)][1] = 0
dp[len(s)][2] = 0
abc = "ABC".index
mod = 10**9 + 7
for i in range(len(s)-1,-1,-1):
    m = 1
    if s[i] ==  "?":
        m=3
    dp[i][3] += m * dp[i+1][3]
for i in range(len(s)-1,-1,-1):
    if s[i] == "?":
        dp[i] = [
        (dp[i+1][0]*3+ dp[i+1][1])%mod
        ,(dp[i+1][1]*3+ dp[i+1][2])%mod
        ,(dp[i+1][2]*3 + dp[i+1][3])%mod
        ,(dp[i+1][3]*3)%mod
        ]
    else:
        dp[i] = [
        dp[i+1][0]
        ,dp[i+1][1]
        ,dp[i+1][2]
        ,dp[i+1][3]
        ]
        num = abc(s[i])
        dp[i][num] += dp[i+1][num+1] % mod
# for i in range(len(s),-1,-1):
#     print(dp[i])
print(dp[0][0] %mod)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
MOD = 10 ** 9 + 7

def main():
    string = input().strip()
    n = len(string)
    dp = [[0, 0, 0, 0] for _ in range(n + 1)]
    dp[0][0] = 1
    for i, s in enumerate(string):
        if s == "A":
            dp[i + 1][0] = dp[i][0]
            dp[i + 1][1] = dp[i][1] + dp[i][0]
            dp[i + 1][2] = dp[i][2]
            dp[i + 1][3] = dp[i][3]
        elif s == "B":
            dp[i + 1][0] = dp[i][0]
            dp[i + 1][1] = dp[i][1]
            dp[i + 1][2] = dp[i][2] + dp[i][1]
            dp[i + 1][3] = dp[i][3]
        elif s == "C":
            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][2]
        else:
            dp[i + 1][0] = 3 * dp[i][0]
            dp[i + 1][1] = 3 * dp[i][1] + dp[i][0]
            dp[i + 1][2] = 3 * dp[i][2] + dp[i][1]
            dp[i + 1][3] = 3 * dp[i][3] + dp[i][2]
        for j in range(4):
            dp[i + 1][j] %= MOD
    print(dp[-1][-1] % MOD)
    
main()

Submission status: Accepted

Solution code:
# dp[i][j] := sのi文字目まで見たときに、ABCのj文字目までを部分列として取り出す方法の数。

s = input()

dp = [[0 for _ in range(4)]for _ in range(len(s))]
mod = 10 ** 9 + 7

power_3 = 1
for idx, letter in enumerate(s):
    dp[idx] = dp[idx-1].copy()

    if letter == 'A':
        dp[idx][1] += power_3
    elif letter == 'B':
        dp[idx][2] += dp[idx-1][1]
    elif letter == 'C':
        dp[idx][3] += dp[idx-1][2]
    elif letter == '?':
        dp[idx][1] *= 3
        dp[idx][2] *= 3
        dp[idx][3] *= 3
        dp[idx][1] += power_3 # 3**(この?を含まない、今までの?の個数)だけ、Aの手前の場合が考えられる。
        power_3 *= 3
        power_3 %= mod
        dp[idx][2] += dp[idx-1][1]
        dp[idx][3] += dp[idx-1][2]
        dp[idx][1] %= mod
        dp[idx][2] %= mod
        dp[idx][3] %= mod


print(dp[len(s)-1][3] % mod) 
# print(dp)

Submission status: Accepted

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

dpa = [0]*(10**5+10)
dpc = [0]*(10**5+10)

hatena_count = 0
pow3 = [1]*(10**5+10)

for i in range(1, 10**5+10):
    pow3[i] = pow3[i-1]*3 % mod

for i in range(n):
    if S[i] == "A":
        dpa[i+1] = (dpa[i] + pow3[hatena_count]) % mod
    elif S[i] == "?":
        dpa[i+1] = (3*dpa[i] + pow3[hatena_count]) % mod
        hatena_count += 1
    else:
        dpa[i+1] = dpa[i]

S.reverse()

hatena_count = 0
for i in range(n):
    if S[i] == "C":
        dpc[i+1] = (dpc[i] + pow3[hatena_count]) % mod
    elif S[i] == "?":
        dpc[i+1] = (3*dpc[i] + pow3[hatena_count]) % mod
        hatena_count += 1
    else:
        dpc[i+1] = dpc[i]

ans = 0
for i in range(1, n - 1):
    if S[i] == "B" or S[i] == "?":
        ans += dpa[n-1-i]*dpc[i]
        ans %= mod
print(ans)

Submission status: Accepted

Solution code:
s = input().lower()
n = len(s)

dp_a = 0
dp_ab = 0
dp_abc = 0
hatena = 1

mod = 10**9 + 7

for i in range(n):
    if s[i]=="a":
        dp_a = (dp_a + hatena) % mod
    elif s[i]=="b":
        dp_ab = (dp_a + dp_ab) % mod
    elif s[i]=="c":
        dp_abc = (dp_ab + dp_abc) % mod
    else:
        dp_abc = (dp_ab + 3 * dp_abc) % mod
        dp_ab = (3 * dp_ab + dp_a) % mod
        dp_a = (3 * dp_a + hatena) % mod
        hatena = (hatena * 3) % mod

print(dp_abc)

Submission status: Accepted

Solution code:
def pow3(a):
    return 0 if a == -1 else p[a]

s = list(input())
n = len(s)
mod = pow(10, 9) + 7
x = [[0] * 2 for _ in range(n - 1)]
y = [[0] * 2 for _ in range(n - 1)]
p = [1] * n
ans = 0
for i in range(1, n):
    p[i] = 3 * p[i - 1] % mod
for i in range(n - 2):
    if s[i] == "A":
        x[i + 1][0] = 1
    elif s[i] == "?":
        x[i + 1][1] = 1
    for j in range(2):
        x[i + 1][j] += x[i][j]
    k = n - i - 1
    if s[k] == "C":
        y[i + 1][0] = 1
    elif s[k] == "?":
        y[i + 1][1] = 1
    for j in range(2):
        y[i + 1][j] += y[i][j]
for i in range(n - 2):
    j, k = i + 1, n - i - 2
    if s[j] == "B" or s[j] == "?":
        c1 = (x[j][0] * pow3(x[j][1]) + x[j][1] * pow3(x[j][1] - 1)) % mod
        c2 = (y[k][0] * pow3(y[k][1]) + y[k][1] * pow3(y[k][1] - 1)) % mod
        ans += c1 * c2
        ans %= mod
print(ans)

Submission status: Accepted

Solution code:
def getval():
    s = input()
    return s
    
def main(s):
    #dp for "a","ab","abc"
    mod = 10**9 + 7
    dp = [0,0,0,0]
    p3 = [1]
    for i in range(len(s)):
        p3.append((3*p3[i])%mod)
    for i in s:
        if i=="A":
            dp[0] += p3[dp[3]]
            dp[0] %= mod
        elif i=="B":
            dp[1] += dp[0]
            dp[1] %= mod
        elif i=="C":
            dp[2] += dp[1]
            dp[2] %= mod
        else:
            temp1 = dp[0]*2
            temp2 = dp[1]*2
            temp3 = dp[2]*2
            dp[2] += dp[1]
            dp[1] += dp[0]
            dp[0] += p3[dp[3]]
            dp[2] += temp3
            dp[1] += temp2
            dp[0] += temp1
            dp[3] += 1
            for j in range(3):
                dp[j] %= mod
            #print(dp)
    print(dp[2])

if __name__=="__main__":
    s = getval()
    main(s)

Submission status: Accepted

Solution code:
S = input()
lct_A = 0
lct_q = 0
rct_C = S.count("C")
rct_q = S.count("?")

MOD = 10**9 + 7

ans = 0
for s in S:
  if s == "C":
    rct_C -= 1
  elif s == "?":
    rct_q -= 1
  #print(s, lct_A, lct_q, rct_C, rct_q)
    
  if s == "B" or s == "?":
    ans += (lct_A * rct_C * pow(3, lct_q+rct_q, MOD)) % MOD
    if lct_q > 0:
      ans += (lct_q * rct_C * pow(3, lct_q+rct_q-1, MOD) ) % MOD
    if rct_q > 0:
      ans += (rct_q * lct_A * pow(3, lct_q+rct_q-1, MOD) ) % MOD
    if lct_q > 0 and rct_q > 0:
      ans += (lct_q * rct_q * pow(3, lct_q+rct_q-2, MOD) ) % MOD   
    ans %= MOD
    #print(" ", ans)
    
  if s == "A":
    lct_A += 1
  elif s == "?":
    lct_q += 1
    
print(ans % MOD)

Submission status: Accepted

Solution code:
s=input()
mod=10**9+7
n,a,b,c=1,0,0,0
for i in s:
  if i=="A":
    a+=n
  if i=="B":
    b+=a
  if i=="C":
    c+=b
  if i=="?":
    n,a,b,c=3*n,3*a+n,3*b+a,3*c+b
  n%=mod
  a%=mod
  b%=mod
  c%=mod
print(c)

Submission status: Accepted

Solution code:
MOD=10**9+7
dp=[[0]*5 for _ in range(210000)]

def add(a,b):
  ret_val=a+b
  if ret_val>=MOD:
    ret_val-=MOD
  return ret_val

S=input()

dp[0][0]=1
for i in range(len(S)):
  for j in range(5):
    if S[i]!="?":
      temp=add(dp[i+1][j],dp[i][j])
      dp[i+1][j]=temp
    else:
      temp=add(dp[i+1][j],dp[i][j]*3%MOD)
      dp[i+1][j]=temp

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