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:
MOD = 10**9+7
S = input()

dp = [0] * 4
dp_next = [0] * 4
dp[0] = 1

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

Submission status: Time Limit Exceeded

Solution code:

S = input()

lis = [1,0,0,0]
nlis = [1,0,0,0]

for s in S:

    if s == "?":

        nlis[0] += lis[0] * 2
        nlis[1] += lis[1] * 2
        nlis[2] += lis[2] * 2
        nlis[3] += lis[3] * 2

    if s == "A" or s == "?":

        nlis[1] += lis[0]

    if s == "B" or s == "?":

        nlis[2] += lis[1]

    if s == "C" or s == "?":

        nlis[3] += lis[2]

    lis = nlis.copy()

print (lis[3]  % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

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

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

for i in range(size):
  cn = dp[i][0]
  a = dp[i][1]
  b = dp[i][2]
  c = dp[i][3]
  if(S[i] == 'A'):
    dp[i+1][0] += cn
    dp[i+1][1] += (a+cn)
    dp[i+1][2] += b
    dp[i+1][3] += c
  elif(S[i] == 'B'):
    dp[i+1][0] += cn
    dp[i+1][1] += a
    dp[i+1][2] += (b+a)
    dp[i+1][3] += c
  elif(S[i] == 'C'):
    dp[i+1][0] += cn
    dp[i+1][1] += a
    dp[i+1][2] += b
    dp[i+1][3] += (c+b)
  else:
    dp[i+1][0] += (3*cn)
    dp[i+1][1] += (3*a+cn)
    dp[i+1][2] += (3*b+a)
    dp[i+1][3] += (3*c+b)
  #for j in range(3):
    #dp[i+1][j] = (dp[i+1][j])

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

Submission status: Time Limit Exceeded

Solution code:
S = input()

MOD = 1000000007

As = []
Bs = []
Cs = []
S_length = len(S)
hatena_count = 0
for i, c in enumerate(S):
    # 'A':0, 'B':1, 'C':2
    if c == 'A':
        As.append([S_length - i, 3])
    elif c == 'B':
        Bs.append([S_length - i, 3])
    elif c == 'C':
        Cs.append([S_length - i, 3])
    elif c == '?':
        hatena_count += 1
        As.append([S_length - i, 1])
        Bs.append([S_length - i, 1])
        Cs.append([S_length - i, 1])

new_Bs = []
for b in Bs:
    new_Bs.append([b, sum([c[1] for c in Cs if b[0] > c[0]])])

count = 0
for a in As:
    count += 3**(hatena_count - 3) * a[1] * sum([b[0][1] * b[1] for b in new_Bs if a[0] > b[0][0]])

print(int(count % MOD))

Submission status: Time Limit Exceeded

Solution code:
"""
http://jellyfish026.hatenablog.com/entry/2018/08/07/155558
分かりやすい
"""
S = input()
dp = [[0 for i in range(4)] for q in range(len(S)+1)]
dp[0][0] = 1


# 一致のカウントなし→Aまで一致→Bまで一致→Cまで完全一致　の順で処理
for i in range(len(S)):
    # i文字目でABCのカウントを進めない場合
    for j in range(4):
        if S[i] == "?":
            dp[i+1][j] += dp[i][j] * 3 # ?にはABCどれを入れてもOK
        else:
            dp[i+1][j] += dp[i][j] # ?以外の場合はそれまでの｛ABCとの一致をスタートしてない数｝と同じ

    # i文字目でABCとの一致のカウントを進める場合
    if S[i] == "A" or S[i] == "?":
        dp[i+1][1] += dp[i][0] # それまでの「一致なし」を「Aまで一致」にカウントできる
    if S[i] == "B" or S[i] == "?":
        dp[i+1][2] += dp[i][1] # それまでの「Aまで一致」を「Bまで一致」にカウントできる
    if S[i] == "C" or S[i] == "?":
        dp[i+1][3] += dp[i][2] # それまでの「Bまで一致」を「Cまで一致」にカウントできる

print(dp[len(S)][3] % (10**9+7))

Submission status: Time Limit Exceeded

Solution code:
S = input()

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

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

Submission status: Time Limit Exceeded

Solution code:
S = input()

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

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

Submission status: Time Limit Exceeded

Solution code:
S = input()

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

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

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

Submission status: Time Limit Exceeded

Solution code:
S = input()

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

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


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

Submission status: Time Limit Exceeded

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

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

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

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

MOD = 10**9+7

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

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
s = input()

def get_sum(J, I, L, K):
    total1 = int(I * P3[J] + J * P3[J-1])
    total2 = int(K * P3[L] + L * P3[L-1])
    return total1 * total2

n_q = 0
n_c = 0
for i in range(len(s)):
    if s[i] == '?':
        n_q += 1
    elif s[i] == 'C':
        n_c += 1

n_q_right = [0]
n_a_right = [0]
n_c_right = [0]
for i in range(len(s) - 1):
    if s[i] == '?':
        n_q_right.append(n_q_right[-1] + 1)
        n_a_right.append(n_a_right[-1])
        n_c_right.append(n_c_right[-1])
    elif s[i] == 'A':
        n_q_right.append(n_q_right[-1])
        n_a_right.append(n_a_right[-1] + 1)
        n_c_right.append(n_c_right[-1])
    elif s[i] == 'C':
        n_q_right.append(n_q_right[-1])
        n_a_right.append(n_a_right[-1])
        n_c_right.append(n_c_right[-1] + 1)
    elif s[i] == 'B':
        n_q_right.append(n_q_right[-1])
        n_a_right.append(n_a_right[-1])
        n_c_right.append(n_c_right[-1])

P3 = [1]
for i in range(1, 10 ** 5):
    P3.append(P3[-1] * 3)

total = 0
for i in range(len(s)):
    if s[i] == '?':
        _n_q_left = n_q - n_q_right[i] - 1
        _n_c_left = n_c - n_c_right[i]
        total += get_sum(n_q_right[i], n_a_right[i], _n_q_left, _n_c_left) %  (10 ** 9 + 7)
    elif s[i] == 'B':
        _n_q_left = n_q - n_q_right[i]
        _n_c_left = n_c - n_c_right[i]
        total += get_sum(n_q_right[i], n_a_right[i], _n_q_left, _n_c_left) %  (10 ** 9 + 7)



print(total % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

Solution code:
s = input()

def get_sum(J, I, L, K):
    total1 = int(I * 3 ** J + J * 3 ** (J - 1))
    total2 = int(K * 3 ** L + L * 3 ** (L - 1))
    return total1 * total2

n_q = 0
n_c = 0
for i in range(len(s)):
    if s[i] == '?':
        n_q += 1
    elif s[i] == 'C':
        n_c += 1

n_q_right = [0]
n_a_right = [0]
n_c_right = [0]
for i in range(len(s) - 1):
    if s[i] == '?':
        n_q_right.append(n_q_right[-1] + 1)
        n_a_right.append(n_a_right[-1])
        n_c_right.append(n_c_right[-1])
    elif s[i] == 'A':
        n_q_right.append(n_q_right[-1])
        n_a_right.append(n_a_right[-1] + 1)
        n_c_right.append(n_c_right[-1])
    elif s[i] == 'C':
        n_q_right.append(n_q_right[-1])
        n_a_right.append(n_a_right[-1])
        n_c_right.append(n_c_right[-1] + 1)
    elif s[i] == 'B':
        n_q_right.append(n_q_right[-1])
        n_a_right.append(n_a_right[-1])
        n_c_right.append(n_c_right[-1])

total = 0
for i in range(len(s)):
    if s[i] == '?':
        _n_q_left = n_q - n_q_right[i] - 1
        _n_c_left = n_c - n_c_right[i]
        total += get_sum(n_q_right[i], n_a_right[i], _n_q_left, _n_c_left) %  (10 ** 9 + 7)
    elif s[i] == 'B':
        _n_q_left = n_q - n_q_right[i]
        _n_c_left = n_c - n_c_right[i]
        total += get_sum(n_q_right[i], n_a_right[i], _n_q_left, _n_c_left) %  (10 ** 9 + 7)



print(total % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

Solution code:
s = input()

def get_sum(J, I, L, K):
    total1 = int(I * 3 ** J + J * 3 ** (J - 1))
    total2 = int(K * 3 ** L + L * 3 ** (L - 1))
    return total1 * total2

n_q_right = [0]
n_a_right = [0]
n_c_right = [0]
n_q = 0
n_c = 0
for i in range(len(s) - 1):
    if s[i] == '?':
        n_q_right.append(n_q_right[-1] + 1)
        n_a_right.append(n_a_right[-1])
        n_c_right.append(n_c_right[-1])
        n_q += 1
    elif s[i] == 'A':
        n_q_right.append(n_q_right[-1])
        n_a_right.append(n_a_right[-1] + 1)
        n_c_right.append(n_c_right[-1])
    elif s[i] == 'C':
        n_q_right.append(n_q_right[-1])
        n_a_right.append(n_a_right[-1])
        n_c_right.append(n_c_right[-1] + 1)
        n_c += 1
    elif s[i] == 'B':
        n_q_right.append(n_q_right[-1])
        n_a_right.append(n_a_right[-1])
        n_c_right.append(n_c_right[-1])

if s[-1] == '?':
    n_q += 1
elif s[-1] == 'C':
    n_c += 1

n_q_left = []
n_c_left = []
total = 0
for i in range(len(s)):
    if s[i] == '?':
        n_q_left.append(n_q - n_q_right[i] - 1)
        n_c_left.append(n_c - n_c_right[i])
        total += get_sum(n_q_right[i], n_a_right[i], n_q_left[i], n_c_left[i]) %  (10 ** 9 + 7)
    elif s[i] == 'A':
        n_q_left.append(n_q - n_q_right[i])
        n_c_left.append(n_c - n_c_right[i])
    elif s[i] == 'C':
        n_q_left.append(n_q - n_q_right[i])
        n_c_left.append(n_c - n_c_right[i] - 1)
    elif s[i] == 'B':
        n_q_left.append(n_q - n_q_right[i])
        n_c_left.append(n_c - n_c_right[i])
        total += get_sum(n_q_right[i], n_a_right[i], n_q_left[i], n_c_left[i]) %  (10 ** 9 + 7)



print(total % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

Solution code:
s = input()

def get_sum(J, I, L, K):
    if J > 0:
        total1 = I * 3 ** J + J * 3 ** (J - 1) # + 2 ** J
    else:
        total1 = I

    if L > 0:
        total2 = K * 3 ** L + L * 3 ** (L - 1) # + 2 ** L
    else:
        total2 = K
    return total1 * total2

n_q_right = [0]
n_a_right = [0]
n_c_right = [0]
for i in range(len(s) - 1):
    if s[i] == '?':
        n_q_right.append(n_q_right[-1] + 1)
    else:
        n_q_right.append(n_q_right[-1])

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

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

n_q = 0
n_c = 0
for i in range(len(s)):
    if s[i] == '?':
        n_q += 1
    elif s[i] == 'C':
        n_c += 1

n_q_left = []
n_c_left = []
for i in range(len(n_q_right)):
    if s[i] == '?':
        n_q_left.append(n_q - n_q_right[i] - 1)
    else:
        n_q_left.append(n_q - n_q_right[i])
    if s[i] == 'C':
        n_c_left.append(n_c - n_c_right[i] - 1)
    else:
        n_c_left.append(n_c - n_c_right[i])

total = 0
for i in range(len(s)):
    if s[i] == 'B' or s[i]== '?':
        total += get_sum(n_q_right[i], n_a_right[i], n_q_left[i], n_c_left[i]) %  (10 ** 9 + 7)

print(total % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

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


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



if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9+7
S = list(input())
Q=0
DP=[[0]*3 for i in range(len(S))]#DP[x][y] x+1文字目までの
#y=0,1,2,3 = A,AB,ABC
if S[0] == "A" or S[0]=="?":
    DP[0] = [1,0,0]
    if S[0]=="?":
        Q=1
else:
    DP[0] = [0,0,0]
for i,s in enumerate(S):
    if i==0:continue
    a,b,c = DP[i-1]
    if s=="A":
        DP[i]=[(a+3**Q)%mod,b,c]
    elif s=="B":
        DP[i]=[a,(a+b)%mod,c]
    elif s=="C":
        DP[i]=[a,b,(b+c)%mod]
    else:
        DP[i]=[(3**Q+3*a)%mod,(a+3*b)%mod,(b+3*c)%mod]
        Q+=1
print(DP[len(S)-1][2]%mod)

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9+7
S = input()
Q=0
DP=[[0]*3 for i in range(len(S))]#DP[x][y] x+1文字目までの
#y=0,1,2,3 = A,AB,ABC
if S[0] == "A" or S[0]=="?":
    DP[0] = [1,0,0]
    if S[0]=="?":
        Q=1
else:
    DP[0] = [0,0,0]
for i,s in enumerate(S):
    if i==0:continue
    a,b,c = DP[i-1]
    if s=="A":
        DP[i]=[(a+3**Q)%mod,b,c]
    elif s=="B":
        DP[i]=[a,(a+b)%mod,c]
    elif s=="C":
        DP[i]=[a,b,(b+c)%mod]
    else:
        DP[i]=[(3**Q+3*a)%mod,(a+3*b)%mod,(b+3*c)%mod]
        Q+=1
print(DP[len(S)-1][2]%mod)

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9+7
S = input()
Q=0
DP=[[0]*3 for i in range(len(S))]#DP[x][y] x+1文字目までの
#y=0,1,2,3 = A,AB,ABC
if S[0] == "A" or S[0]=="?":
    DP[0] = [1,0,0]
    if S[0]=="?":
        Q=1
else:
    DP[0] = [0,0,0]
for i in range(1,len(S)):
    s = S[i]
    a,b,c = DP[i-1]
    if s=="A":
        DP[i]=[a+3**Q,b,c]
    elif s=="B":
        DP[i]=[a,a+b,c]
    elif s=="C":
        DP[i]=[a,b,b+c]
    else:
        DP[i]=[3**Q+3*a,a+3*b,b+3*c]
        Q+=1
    for j in range(3):
        DP[i][j]%=mod
print(DP[len(S)-1][2])

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

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

for i in range(l):
    if s[i]=="A":
        dp[i][0]=dp[i-1][0]+3**c
        dp[i][1]=dp[i-1][1]
        dp[i][2]=dp[i-1][2]
    elif s[i]=="B":
        dp[i][0]=dp[i-1][0]
        dp[i][1]=dp[i-1][1]+dp[i-1][0]
        dp[i][2]=dp[i-1][2]
    elif s[i]=="C":
        dp[i][0]=dp[i-1][0]
        dp[i][1]=dp[i-1][1]
        dp[i][2]=dp[i-1][2]+dp[i-1][1]
    else:
        dp[i][0]=dp[i-1][0]*3+3**c
        dp[i][1]=dp[i-1][1]*3+dp[i-1][0]
        dp[i][2]=dp[i-1][2]*3+dp[i-1][1]
        c+=1
    dp[i][0]=dp[i][0]%mod
    dp[i][1]=dp[i][1]%mod
    dp[i][2]=dp[i][2]%mod

print(dp[-1][2])

Submission status: Time Limit Exceeded

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

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

for i in range(l):
    if s[i]=="A":
        dp[i][0]=dp[i-1][0]+3**c
        dp[i][1]=dp[i-1][1]
        dp[i][2]=dp[i-1][2]
    elif s[i]=="B":
        dp[i][0]=dp[i-1][0]
        dp[i][1]=dp[i-1][1]+dp[i-1][0]
        dp[i][2]=dp[i-1][2]
    elif s[i]=="C":
        dp[i][0]=dp[i-1][0]
        dp[i][1]=dp[i-1][1]
        dp[i][2]=dp[i-1][2]+dp[i-1][1]
    else:
        dp[i][0]=dp[i-1][0]*3+3**c
        dp[i][1]=dp[i-1][1]*3+dp[i-1][0]
        dp[i][2]=dp[i-1][2]*3+dp[i-1][1]
        c+=1
    dp[i][0]=dp[i][0]%mod
    dp[i][1]=dp[i][1]%mod
    dp[i][2]=dp[i][2]%mod

print(dp[-1][2])

Submission status: Time Limit Exceeded

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

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

for i in range(l):
    if s[i]=="A":
        dp[i][1]=dp[i-1][1]+3**c
        dp[i][2]=dp[i-1][2]
        dp[i][3]=dp[i-1][3]
    elif s[i]=="B":
        dp[i][1]=dp[i-1][1]
        dp[i][2]=dp[i-1][2]+dp[i-1][1]
        dp[i][3]=dp[i-1][3]
    elif s[i]=="C":
        dp[i][1]=dp[i-1][1]
        dp[i][2]=dp[i-1][2]
        dp[i][3]=dp[i-1][3]+dp[i-1][2]
    else:
        dp[i][1]=dp[i-1][1]*3+3**c
        dp[i][2]=dp[i-1][2]*3+dp[i-1][1]
        dp[i][3]=dp[i-1][3]*3+dp[i-1][2]
        c+=1
    dp[i][1]=dp[i][1]%mod
    dp[i][2]=dp[i][2]%mod
    dp[i][3]=dp[i][3]%mod

print(dp[-1][3])

Submission status: Time Limit Exceeded

Solution code:
"""
We Love ABC
DP使う問題
T : 文字列
i < j < k < len(T)
Ti = "A"
Tj = "B"
Tk = "C"
i j k の順で取れたら、1カウント
- TはA, B, C, ? で構成される
- ? は　ABC のいずれか
これらを満たす場合の数

i番目の文字において、ABCのどこまで進んだか
null:   0
A   :   1
B   :   2
C   :   3

?の扱いが厄介
?があると単純に選択肢が3倍になる
A? -> AA, AB, AC
B? -> BA, BB, BC
まだ選んでいない時 : 入力の選択肢が3倍に増える
dp[i+1][1]: 
    すでにAを選んでいる時 : iまでのAの選び方が3倍に増えるので、dp[i][1]*3
    何も選んでいない場合  : ?がAになれるので、dp[i][0]を加える
ほかも同じ
"""
mod = 10**9 + 7

S = input()
N = len(S)
dp = [[0]*4 for i in range(100800)]
dp[0][0] = 1
for i in range(N):
    s = S[i]
    dp[i+1][0] = dp[i][0] 
    dp[i+1][1] = dp[i][1] 
    dp[i+1][2] = dp[i][2] 
    dp[i+1][3] = dp[i][3] 
    if s == "A":
        # Aを選ぶ選択肢がそれまでのA,?分増える
        dp[i+1][1] += dp[i][0]
    if s == "B":
        # Bを選ぶ選択肢がそれまでのAの選択肢分増える
        dp[i+1][2] = dp[i][2] + dp[i][1] 
    if s == "C":
        # Cを選ぶ選択肢がBまでを選んだ分だけ増える
        dp[i+1][3] = dp[i][3] + dp[i][2]
    if s == "?":
        # ?を選んだ場合。選択肢は3倍に広がる
        dp[i+1][0] = 3*dp[i][0]
        dp[i+1][1] = dp[i][0] + 3*dp[i][1]
        dp[i+1][2] = dp[i][1] + 3*dp[i][2]  
        dp[i+1][3] = dp[i][2] + 3*dp[i][3]
        
# Cまで行った数を求める
print(dp[N][3]%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
# input = sys.stdin.readline
S = list(input())
p = 10 ** 9 + 7
# p = 10 ** 18

A = AB = ABC = 0
Q = 0
for i, Si in enumerate(S):
    # print("#", A, AB, ABC)
    if Si == 'A':
        A = (A + 1 * (3 ** Q)) % p
    elif Si == 'B':
        AB = (AB + A) % p
    elif Si == 'C':
        ABC = (ABC + AB) % p
    else:
        ABC = (3 * ABC + AB) % p
        AB = (3 * AB + A) % p
        #A = (3 * A + 1 * (3 ** Q)) % p
        A = (3 * A + 1 * (pow(3,Q,p))) % p
        Q += 1

print(ABC)

Submission status: Time Limit Exceeded

Solution code:
import sys
# input = sys.stdin.readline
S = list(input())
p = 10 ** 9 + 7
# p = 10 ** 18

A = AB = ABC = 0
Q = 0
for i, Si in enumerate(S):
    # print("#", A, AB, ABC)
    if Si == 'A':
        A = (A + 1 * (3 ** Q)) % p
    elif Si == 'B':
        AB = (AB + A) % p
    elif Si == 'C':
        ABC = (ABC + AB) % p
    else:
        ABC = (3 * ABC + AB) % p
        AB = (3 * AB + A) % p
        #A = (3 * A + 1 * (3 ** Q)) % p
        A = (3 * A + 1 * (pow(3,Q))) % p
        Q += 1

print(ABC)

Submission status: Time Limit Exceeded

Solution code:
import sys
# input = sys.stdin.readline
S = list(input())
p = 10 ** 9 + 7
# p = 10 ** 18

A = AB = ABC = 0
Q = 0
for i, Si in enumerate(S):
    # print("#", A, AB, ABC)
    if Si == 'A':
        A = (A + 1 * (3 ** Q)) % p
    elif Si == 'B':
        AB = (AB + A) % p
    elif Si == 'C':
        ABC = (ABC + AB) % p
    else:
        ABC = (3 * ABC + AB) % p
        AB = (3 * AB + A) % p
        A = (3 * A + 1 * (3 ** Q)) % p
        Q += 1

print(ABC)

Submission status: Time Limit Exceeded

Solution code:
S = input()

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

for ind,i in enumerate(S):
    if(i!='?'):
        dp[ind+1][0] = dp[ind][0]
        dp[ind+1][1] = dp[ind][1]
        dp[ind+1][2] = dp[ind][2]
        dp[ind+1][3] = dp[ind][3]
        if(i=='A'):
            dp[ind+1][1] += dp[ind][0]
        elif(i=='B'):
            dp[ind+1][2] += dp[ind][1]
        elif(i=='C'):
            dp[ind+1][3] += dp[ind][2]
    else:
        dp[ind+1][0] = dp[ind][0]*3
        dp[ind+1][1] = dp[ind][1]*3 + dp[ind][0]
        dp[ind+1][2] = dp[ind][2]*3 + dp[ind][1]
        dp[ind+1][3] = dp[ind][3]*3 + dp[ind][2]


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

Submission status: Time Limit Exceeded

Solution code:
S = input()

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

for ind,i in enumerate(S):
    if(i!='?'):
        dp[ind+1][0] += dp[ind][0]
        dp[ind+1][1] += dp[ind][1]
        dp[ind+1][2] += dp[ind][2]
        dp[ind+1][3] += dp[ind][3]
        if(i=='A'):
            dp[ind+1][1] += dp[ind][0]
        elif(i=='B'):
            dp[ind+1][2] += dp[ind][1]
        elif(i=='C'):
            dp[ind+1][3] += dp[ind][2]
    else:
        dp[ind+1][0] += dp[ind][0]*3
        dp[ind+1][1] += dp[ind][1]*3 + dp[ind][0]
        dp[ind+1][2] += dp[ind][2]*3 + dp[ind][1]
        dp[ind+1][3] += dp[ind][3]*3 + dp[ind][2]


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

Submission status: Time Limit Exceeded

Solution code:
S = input()

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

for ind,i in enumerate(S):
    if(i!='?'):
        dp[ind+1][0] += dp[ind][0]
        dp[ind+1][1] += dp[ind][1]
        dp[ind+1][2] += dp[ind][2]
        dp[ind+1][3] += dp[ind][3]
    else:
        dp[ind+1][0] += dp[ind][0]*3
        dp[ind+1][1] += dp[ind][1]*3
        dp[ind+1][2] += dp[ind][2]*3
        dp[ind+1][3] += dp[ind][3]*3

    if(i=='A'):
        dp[ind+1][1] += dp[ind][0]
    elif(i=='B'):
        dp[ind+1][2] += dp[ind][1]
    elif(i=='C'):
        dp[ind+1][3] += dp[ind][2]
    else:
        dp[ind+1][3] += dp[ind][2]
        dp[ind+1][2] += dp[ind][1]
        dp[ind+1][1] += dp[ind][0]
print(dp[-1][3]%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:



def main():
    data = list(input())
    # dp = [[0 for i in range(4)] for i in range(len(data) + 1)]
    # dp[len(data)][3] += 1

    dp = [0, 0, 0, 1]

    dic = {0:'A', 1:'B', 2:'C'}
    for i in range(len(data))[::-1]:
        element = data[i]
        for j in range(4):
            if j == 3:
                if element == '?':
                    dp[j] *= 3
            else:
                if dic[j] == element:
                    dp[j] += dp[j + 1]

                elif element == '?':
                    dp[j] = dp[j] * 3 + dp[j + 1]


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





if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:



def main():
    data = list(input())
    dp = [[0 for i in range(4)] for i in range(len(data) + 1)]
    dp[len(data)][3] += 1

    dic = {0:'A', 1:'B', 2:'C'}
    for i in range(len(data))[::-1]:
        element = data[i]
        for j in range(4):
            if j == 3:
                if element == '?':
                    dp[i][j] = dp[i + 1][j] * 3
                else:
                    dp[i][j] = dp[i + 1][j]
            else:
                if dic[j] == element or element == '?':
                    dp[i][j] += dp[i + 1][j + 1]

                if element == '?':
                    dp[i][j] += dp[i + 1][j] * 3
                else:
                    dp[i][j] += dp[i + 1][j]

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





if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
try:
    from math import gcd
except Exception:
    from fractions import gcd

MOD = 1000000007  # type: int

def solve(S: str):
    dp = [[0] * 4 for _ in range(len(S) + 1)]
    dp[0][0] = 1

    for i, s in enumerate(S):
        for j, a in enumerate('_ABC'):
            dp[i+1][j] = dp[i][j]
            if s == '?':
                dp[i+1][j] = 3 * dp[i][j] + (dp[i][j-1] if 1 <= j else 0)
            if s == a:
                dp[i+1][j] += dp[i][j-1]
    return dp[-1][-1] % MOD


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    result = solve(S)
    print(result)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def solve(string):
    s = string.replace("?", "d").lower()
    n = len(s)
    dp = [[0] * (n + 1) for _ in range(4)]
    dp[0][0] = 1
    for i, _s in enumerate(s):
        dp[0][i + 1] = dp[0][i]
        dp[1][i + 1] = dp[1][i]
        dp[2][i + 1] = dp[2][i]
        dp[3][i + 1] = dp[3][i]
        if _s == "a":
            dp[1][i + 1] += dp[0][i]
        if _s == "b":
            dp[2][i + 1] += dp[1][i]
        if _s == "c":
            dp[3][i + 1] += dp[2][i]
        if _s == "d":
            dp[0][i + 1] *= 3
            dp[1][i + 1] *= 3
            dp[1][i + 1] += dp[0][i]
            dp[2][i + 1] *= 3
            dp[2][i + 1] += dp[1][i]
            dp[3][i + 1] *= 3
            dp[3][i + 1] += dp[2][i]
    return str(int(dp[3][-1] % (10**9 + 7)))


if __name__ == '__main__':
    print(solve(input()))

Submission status: Time Limit Exceeded

Solution code:
def f(s):
    n = len(s)
    dp = [[0, 0, 0, 0] for _ in range(n + 1)]
    pre = dp[0]
    for i, c in enumerate(s):
        cur = dp[i + 1]
        if c == "A":
            cur[0] = (pre[0] + 3 ** pre[3]) % md
            cur[1:] = pre[1:]
        elif c == "B":
            cur[0] = pre[0]
            cur[1] = (pre[0] + pre[1]) % md
            cur[2:] = pre[2:]
        elif c == "C":
            cur[:2] = pre[:2]
            cur[2] = (pre[1] + pre[2]) % md
            cur[3] = pre[3]
        else:
            cur[0] = (pre[0] * 3 + 3 ** pre[3]) % md
            cur[1] = (pre[1] * 3 + pre[0]) % md
            cur[2] = (pre[2] * 3 + pre[1]) % md
            cur[3] = (pre[3] + 1) % md
        pre = cur
    print(dp[-1][-2])

md = 10 ** 9 + 7
s = input()
f(s)

Submission status: Time Limit Exceeded

Solution code:
md = 10 ** 9 + 7
s = input()
n = len(s)
dp = [[0, 0, 0, 0] for _ in range(n + 1)]
pre = dp[0]
for i, c in enumerate(s):
    cur = dp[i + 1]
    if c == "A":
        cur[0] = (pre[0] + 3 ** pre[3]) % md
        cur[1:] = pre[1:]
    elif c == "B":
        cur[0] = pre[0]
        cur[1] = (pre[0] + pre[1]) % md
        cur[2:] = pre[2:]
    elif c == "C":
        cur[:2] = pre[:2]
        cur[2] = (pre[1] + pre[2]) % md
        cur[3] = pre[3]
    else:
        cur[0] = (pre[0] * 3 + 3 ** pre[3]) % md
        cur[1] = (pre[1] * 3 + pre[0]) % md
        cur[2] = (pre[2] * 3 + pre[1]) % md
        cur[3] = (pre[3] + 1) % md
    pre = cur
print(dp[-1][-2])