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: Wrong Answer

Solution code:
from collections import Counter
s=input()
D=Counter(list(s))
A,C,Q=D["A"],D["C"],D["?"]
a,c,q=0,0,0
ans=0
MOD=10**9+7

for i in range(len(s)):
    if s[i]=="A":
        a+=1
    elif s[i]=="C":
        c+=1
    elif s[i]=="B":
        ans+=((a*(3**q)+q*(3**(q-1)))%MOD)*(((C-c)*(3**(Q-q))+(Q-q)*(3**(Q-q-1)))%MOD)
        ans%=MOD
    else:
        ans+=((a*(3**q)+q*(3**(q-1)))%MOD)*(((C-c)*(3**(Q-q-1))+(Q-q-1)*(3**(Q-q-2)))%MOD)
        ans%=MOD
        q+=1

print(int(ans%MOD))

Submission status: Wrong Answer

Solution code:
import numpy as np

def main():
    MOD = 10**9+7
    S = input()
    
    dp = np.zeros((4), dtype=np.uint64)
    #dp_next = np.zeros((4), dtype=np.int)
    dp_next = [0, 0, 0, 0]
    dp[0] = 1
    
    for s in S:
        if s == '?':
            m = 3
        else:
            m = 1
        dp_next[:] = m * dp[:]
        
        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
        
        dp[:] = dp_next[:]
        
    print(int(dp[3]))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np

def main():
    MOD = 10**9+7
    S = input()
    
    dp = np.zeros((4), dtype=np.int)
    dp_next = np.zeros((4), dtype=np.int)
    dp[0] = 1
    
    for s in S:
        if s == '?':
            m = 3
        else:
            m = 1
        dp_next[:] = m * dp[:]
        
        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
        
        dp[:] = dp_next[:]
        
    print(dp[3]%MOD)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np

def main():
    MOD = 10**9+7
    S = input()
    
    dp = np.zeros((4), dtype=np.int)
    dp_next = np.zeros((4), dtype=np.int)
    dp[0] = 1
    
    for s in S:
        if s == '?':
            m = 3
        else:
            m = 1
        dp_next[:] = m * dp[:]
        
        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
        
        dp[:] = dp_next[:]
        
    print(dp[3])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
s = input()
mod = 10**9 + 7
n = len(s)
a,b,c=0,0,0
for i in s:
  if i == 'A':
    a += 1
  elif i == 'B':
    b += a
  elif i == 'C':
    c += b
  else:
    c += b
    b += a
    a += 1
  a %= mod
  b %= mod
  c %= mod

print(c)

Submission status: Wrong Answer

Solution code:
def main():
    S = input()
    mod = pow(10, 9) + 7
    n = len(S)
    print(S)
    countA, countAB, countABC = 0, 0, 0
    strA, strNonA = 0, 1
    for i in range(n):
        if S[i] == "A":
            countA += strNonA + strA
            strA += strNonA
            strNonA = 0
        elif S[i] == "B":
            countAB += countA
        elif S[i] == "C":
            countABC += countAB
        else:
            countABC = 3*countABC + countAB
            countAB = 3*countAB + countA
            countA = 3*countA + strNonA + strA
            strA = 3*strA + strNonA
            strNonA *= 2

        countA %= mod
        countAB %= mod
        countABC %= mod
        strA %= mod
        strNonA %= mod
        # print(countA, countAB, countABC, strA, strNonA)

    return countABC % mod

if __name__ == '__main__':
    print(main())

Submission status: Wrong Answer

Solution code:
class BIT():
  def __init__(self, s):
    self.str = s
    self.size = len(s)
    self.Q = s.count('?')
    self.tree = [0] * 4
    self.ab = 0
    self.aq = 0
    self.qb = 0
    self.qq = 0
    self.abc = 0
    self.ans = 0
    
  def add(self, p, x):
    if p == '?':
      self.tree[0] += x
    elif p == 'A':
      self.tree[1] += x
    elif p == 'B':
      self.tree[2] += x
    else:
      self.tree[3] += x
  
  def count(self, p):
    if p == 'C':
      self.abc += self.ab * (3 ** self.Q)
      self.abc += self.aq * (3 ** (self.Q - 1))
      self.abc += self.qb * (3 ** (self.Q - 1))
      self.abc += self.qq * (3 ** (self.Q - 2))
      
    elif p == 'B':
      self.ab += self.tree[1]
      self.qb += self.tree[0]
      
    elif p == '?':
      self.abc += self.ab * (3 ** (self.Q - 1))
      self.abc += self.qb * (3 ** (self.Q - 2))
      self.abc += self.aq * (3 ** (self.Q - 2))
      self.abc += self.qq * (3 ** (self.Q - 3))
      self.qq += self.tree[0]
      self.aq += self.tree[1]
    else:
      pass
    
s = BIT(input())

for p in s.str:
  s.count(p)
  s.add(p, 1)
  if s.abc > 10**9 + 7:
    s.abc = s.abc % (10**9 + 7)
  
print(s.abc % (10**9 + 7))

Submission status: Wrong Answer

Solution code:
class BIT():
  def __init__(self, s):
    self.str = s
    self.size = len(s)
    self.Q = s.count('?')
    self.tree = [0] * 4
    self.ab = 0
    self.aq = 0
    self.qb = 0
    self.qq = 0
    self.abc = 0
    self.ans = 0
    
  def add(self, p, x):
    if p == '?':
      self.tree[0] += x
    elif p == 'A':
      self.tree[1] += x
    elif p == 'B':
      self.tree[2] += x
    else:
      self.tree[3] += x
  
  def count(self, p):
    if p == 'C':
      self.abc += self.ab * (3 ** self.Q)
      self.abc += self.aq * (3 ** (self.Q - 1))
      self.abc += self.qb * (3 ** (self.Q - 1))
      self.abc += self.qq * (3 ** (self.Q - 2))
      
    elif p == 'B':
      self.ab += self.tree[1]
      self.qb += self.tree[0]
      
    elif p == '?':
      self.abc += self.ab * (3 ** (self.Q - 1))
      self.abc += self.qb * (3 ** (self.Q - 2))
      self.abc += self.aq * (3 ** (self.Q - 2))
      self.abc += self.qq * (3 ** (self.Q - 3))
      self.qq += self.tree[0]
      self.aq += self.tree[1]
    else:
      pass
    
s = BIT(input())

for p in s.str:
  s.count(p)
  s.add(p, 1)
  
print(s.abc % (10**9 + 7))

Submission status: Wrong Answer

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

n = len(s)
a = [0] * (n+1)
b = [0] * (n+1)
c = [0] * (n+1)

for i in range(n):
    if s[i] == '?':
        a[i+1] = a[i] * 3 + 1
        b[i+1] = b[i] * 3 + a[i]
        c[i+1] = c[i] * 3 + b[i]
    else:
        a[i+1] = a[i]
        b[i+1] = b[i]
        c[i+1] = c[i]
        if s[i] == 'A':
            a[i+1] += 1
        if s[i] == 'B':
            b[i+1] += a[i]
        if s[i] == 'C':
            c[i+1] += b[i]
    a[i+1] = a[i+1] % MOD
    b[i+1] = b[i+1] % MOD
    c[i+1] = c[i+1] % MOD
print(c[n])

Submission status: Wrong Answer

Solution code:
def makelist(n, m):
    return [[0 for _ in range(m)] for _ in range(n)]

S = input()
l = len(S)


MOD = int(1e9) + 7
dp = makelist(l, 3)

def toInt(c):
    return [ord(c) - 65]

if S[0] in ['?', 'A']:
    dp[0][0] = 1

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

print(dp[l-1][2])

Submission status: Wrong Answer

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

import re
# import numpy as np
# from scipy.misc import perm
# from scipy.misc import comb

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
INF = int(1e18)
MOD = int(1e9)+7 # 10^9 + 7

def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# dp[i][j]
def init_dp_table(i, j, init=INF):
  return [[ init for _ in range(j)] for _ in range(i)]

########

S = input()

dp = init_dp_table(len(S)+1, 4, 0)
dp[0][0] = 1

for i in range(len(S)):
    Si = S[i]
    if Si == "A" or Si == "?":
        dp[i+1][0] += dp[i][0] % MOD
        dp[i+1][1] += dp[i][1] % MOD
        dp[i+1][2] += dp[i][2] % MOD
        dp[i+1][3] += dp[i][3] % MOD
        dp[i+1][1] += dp[i][0] % MOD
    if Si == "B" or Si == "?":
        dp[i+1][0] += dp[i][0] % MOD
        dp[i+1][1] += dp[i][1] % MOD
        dp[i+1][2] += dp[i][2] % MOD
        dp[i+1][3] += dp[i][3] % MOD
        dp[i+1][2] += dp[i][1] % MOD
    if Si == "C" or Si == "?":
        dp[i+1][0] += dp[i][0] % MOD
        dp[i+1][1] += dp[i][1] % MOD
        dp[i+1][2] += dp[i][2] % MOD
        dp[i+1][3] += dp[i][3] % MOD
        dp[i+1][3] += dp[i][2] % MOD

print(dp[len(S)][3])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
#ABC104 D

import sys
import math
import bisect
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter


mod = 10**9 + 7

s = list(input())
n = len(s)
#見るA,B,Cを仮定して
#dp[i][j] := i文字までみたとき、
#            j = 0 := A,B,C全部入っていない
#            j = 1 := Aだけ入っている
#            j = 2 := A,Bだけ入っている
#            j = 3 := A,B,C全て入っている
#           状態のABC数

dp = [[0]*4 for _ in range(n+1)]
dp[0][0] = 1
for i in range(n):
    if s[i] == '?':
        for j in range(4):
            #A,B,Cそれぞれに変換して進めることができるため3倍
            #jの状態変化なし
            dp[i+1][j] = 3*dp[i][j] % mod
    else:
        for j in range(4):
            dp[i+1][j] = dp[i][j]
    if s[i] == 'A':
        #状態0→1に変えることができる
        dp[i+1][1] += dp[i][0] % mod
    elif s[i] == 'B':
        #状態1→2に変えることができる
        dp[i+1][2] += dp[i][1] % mod
    elif s[i] == 'C':
        #状態2→3に変えることができる
        dp[i+1][3] += dp[i][2] % mod
    elif s[i] == '?':
        #状態0→1,1→2,2→3に変えることができる
        for j in range(3):
            dp[i+1][j+1] += dp[i][j] % mod
print(dp[n][3])

Submission status: Wrong Answer

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

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

dp[0][0] = 1

for i in range(ls):
    if s[i] == 'A':
        for j in range(4):
            dp[i+1][j] += dp[i][j]
        dp[i+1][1] += dp[i][0]
    elif s[i] == 'B':
        for j in range(4):
            dp[i+1][j] += dp[i][j]
        dp[i+1][2] += dp[i][1]
    elif s[i] == 'C':
        for j in range(4):
            dp[i+1][j] += dp[i][j]
        dp[i+1][3] += dp[i][2]
    else:
        for j in range(4):
            dp[i+1][j] += dp[i][j]*3

print(dp[ls][3])

Submission status: Wrong Answer

Solution code:
s = input()

def get_sum(J, J3, I, L, L3, K):
    total1 = int(I * J3 + J * J3 / 3)
    total2 = int(K * L3 + L * L3 / 3)
    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
P3_right = 1
P3_left = (3 ** n_q) % (10 ** 9 + 7)
for i in range(len(s)):
    if s[i] == '?':
        P3_left /= 3
        _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], P3_right, n_a_right[i], _n_q_left, P3_left, _n_c_left) %  (10 ** 9 + 7)
        P3_right *= 3
        P3_right = P3_right  % (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], P3_right, n_a_right[i], _n_q_left, P3_left, _n_c_left) %  (10 ** 9 + 7)



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

Submission status: Wrong Answer

Solution code:
s = input()

def get_sum(J, J3, I, L, L3, K):
    total1 = int(I * J3 + J * J3 / 3)
    total2 = int(K * L3 + L * L3 / 3)
    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
P3_right = 1
P3_left = 3 ** n_q % (10 ** 9 + 7)
for i in range(len(s)):
    if s[i] == '?':
        P3_left /= 3
        _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], P3_right, n_a_right[i], _n_q_left, P3_left, _n_c_left) %  (10 ** 9 + 7)
        P3_right *= 3
        P3_right = P3_right  % (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], P3_right, n_a_right[i], _n_q_left, P3_left, _n_c_left) %  (10 ** 9 + 7)



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

Submission status: Wrong Answer

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])

print(total)

Submission status: Wrong Answer

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][0]=a+3**Q
    elif s=="B":
        DP[i][1]=a+b
    elif s=="C":
        DP[i][2]=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: Wrong Answer

Solution code:
mo=10**9+7
s=input()
n=len(s)
dp=[[0]*(1+n) for i in range(3)]
for i in range(n):
    c=s[i]
    if c=='A':
        da=1
        db=0
        dc=0
        dd=1
    elif c=='B':
        da=0
        db=1
        dc=0
        dd=1
    elif c=='C':
        da=0
        db=0
        dc=1
        dd=1
    elif c=='?':
        da=1
        db=1
        dc=1
        dd=3
        
    dp[0][i+1]=dp[0][i]*dd+da
    dp[1][i+1]=dp[1][i]*dd+dp[0][i]*db
    dp[2][i+1]=dp[2][i]*dd+dp[1][i]*dc
    dp[0][i+1]%=mo
    dp[1][i+1]%=mo
    dp[2][i+1]%=mo

print(dp[2][n]%mo)

Submission status: Wrong Answer

Solution code:
S=input()
N = len(S)
A = [0]*N
C = [0]*N
L = [0]*N
R = [0]*N
for i in range(1,N):
    A[i] = A[i-1] + (S[i-1] == "A")
    L[i] = L[i-1] + (S[i-1] == "?")
    C[N-1-i] = C[N-i] + (S[N-i] == "C")
    R[N-1-i] = R[N-i] + (S[N-i] == "?")
mod = 10**9+7
d={0:1}
def pow_mod(x,n):
    if d.get(n,False) :return d[n]
    if n<0: return pow_mod(x,mod-2+n)
    if n%2  :
        d[n] = (x*pow_mod(x,n-1))%mod
    else:
        d[n] = (pow_mod(x,n//2)**2)%mod
    return d[n]
ans = 0
for i in range(1,N-1):
    if S[i] in "B?":
        ans += (3*A[i]+L[i])*(3*C[i]+R[i])*pow_mod(3,L[i]+R[i]-2)
        ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
S=input()
N = len(S)
A = [0]*N
C = [0]*N
L = [0]*N
R = [0]*N
for i in range(1,N):
    A[i] = A[i-1] + (S[i-1] == "A")
    L[i] = L[i-1] + (S[i-1] == "?")
    C[N-1-i] = C[N-i] + (S[N-i] == "C")
    R[N-1-i] = R[N-i] + (S[N-i] == "?")
mod = 10**9+7
d={0:1}
def pow_mod(x,n):
    if d.get(n,False) :return d[n]
    if n%2  :
        d[n] = (x*pow_mod(x,n-1))%mod
    else:
        d[n] = (pow_mod(x,n//2)**2)%mod
    return d[n]
ans = 0
for i in range(1,N-1):
    if S[i] in "B?":
        ans += (3*A[i]+L[i])*(3*C[i]+R[i])*pow_mod(3,L[i]+R[i])//9
        ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
S=input()
N = len(S)
A = [0]*N
C = [0]*N
L = [0]*N
R = [0]*N
for i in range(1,N):
    A[i] = A[i-1] + (S[i-1] == "A")
    L[i] = L[i-1] + (S[i-1] == "?")
    C[N-1-i] = C[N-i] + (S[N-i] == "C")
    R[N-1-i] = R[N-i] + (S[N-i] == "?")
mod = 10**9+7
d={0:1}
def pow_mod(x,n):
    if d.get(n,False) :return d[n]
    if n%2  :
        d[n] = (x*pow_mod(x,n-1))%mod
    else:
        d[n] = (pow_mod(x,n//2)**2)%mod
    return d[n]
ans = 0
for i in range(1,N-1):
    if S[i] in "B?":
        ans += (3*A[i]+L[i])*pow_mod(3,L[i])*(3*C[i]+R[i])*pow_mod(3,R[i])//9
        ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
S=input()
N = len(S)
A = [0]*N
C = [0]*N
L = [0]*N
R = [0]*N
for i in range(1,N):
    A[i] = A[i-1] + (S[i-1] == "A")
    L[i] = L[i-1] + (S[i-1] == "?")
    C[N-1-i] = C[N-i] + (S[N-i] == "C")
    R[N-1-i] = R[N-i] + (S[N-i] == "?")
mod = 10**9+7
def pow_mod(x,n):
    if n< 0 :return 0
    if n==0 :return 1
    if n%2  :return (x*pow_mod(x,n-1))%mod
    return (pow_mod(x,n//2)**2)%mod
ans = 0
for i in range(1,N-1):
    if S[i] in "B?":
        ans += (3*A[i]+L[i])*pow_mod(3,L[i])*(3*C[i]+R[i])*pow_mod(3,R[i])//9
        ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
def get_input(inp):
  li = inp.split("\n")

  def inner():
    return li.pop(0)
  return inner

INPUT="""????C?????B??????A???????"""
input = get_input(INPUT)

s = input().strip()
MOD = pow(10, 9) + 7
# dp: dp[0][...] = ABCカウントを更新しない時の数
# dp: dp[1][...] = Aまで合わせた時の数
# dp: dp[2][...] = Bまで合わせた時の数
# dp: dp[3][...] = Cまで合わせた時の数
dp = [[0 for _ in range(len(s) + 1)] for _ in range(4)]
dp[0][0] = 1

for i, _s in enumerate(s):
  if _s == '?':
    dp[0][i+1] += dp[0][i] * 3 % MOD
    dp[1][i+1] += dp[1][i] * 3 % MOD
    dp[2][i+1] += dp[2][i] * 3 % MOD
    dp[3][i+1] += dp[3][i] * 3 % MOD
    dp[0][i+1] %= MOD
    dp[1][i+1] %= MOD
    dp[2][i+1] %= MOD
    dp[3][i+1] %= MOD
  else:
    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]
    dp[0][i+1] %= MOD
    dp[1][i+1] %= MOD
    dp[2][i+1] %= MOD
    dp[3][i+1] %= MOD
  if _s == 'A' or _s == '?':
    dp[1][i+1] += dp[0][i]
    dp[1][i+1] %= MOD
  if _s == 'B' or _s == '?':
    dp[2][i+1] += dp[1][i]
    dp[2][i+1] %= MOD
  if _s == 'C' or _s == '?':
    dp[3][i+1] += dp[2][i]
    dp[3][i+1] %= MOD

print(dp[3][-1])

Submission status: Wrong Answer

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][0]
        dp[ind+1][2] += dp[ind][2] + dp[ind][1]
        dp[ind+1][3] += dp[ind][3] + dp[ind][2]
    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]

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

Submission status: Wrong Answer

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

C = BC = ABC = 0
for Si in reversed(S):
    print("#", C, BC, ABC)
    if Si == 'C':
        C = (C + 1) % p
    elif Si == 'B':
        BC = (BC + C) % p
    elif Si == 'A':
        ABC = (ABC + BC) % p
    else:
        C_prev, BC_prev, ABC_prev = C, BC, ABC
        C = BC = ABC = 0
        for Ti in ('A', 'B', 'C'):
            C_tmp, BC_tmp, ABC_tmp = C_prev, BC_prev, ABC_prev
            if Ti == 'C':
                C_tmp = (C_tmp + 1) % p
            elif Ti == 'B':
                BC_tmp = (BC_tmp + C_tmp) % p
            else:
                ABC_tmp = (ABC_tmp + BC_tmp) % p
            # print("##", C_tmp, BC_tmp, ABC_tmp)
            C = (C + C_tmp) % p
            BC = (BC + BC_tmp) % p
            ABC = (ABC + ABC_tmp) % p

print(ABC)

Submission status: Wrong Answer

Solution code:
import sys, os

f = lambda:list(map(int,input().split()))
if 'local' in os.environ :
    sys.stdin = open('./input.txt', 'r')

def solve():
    s = input()
    slen = len(s)
    cnt = [0] * 3
    mod = 1000*1000*1000+7
    cnt_q = 0
    for i in range(slen):
        if s[i] == 'A':
            cnt[0] += 1
        elif s[i] == 'B':
            cnt[1] += cnt[0]
        elif s[i] == 'C':
            cnt[2] += cnt[1]
        else:
            cnt[0], cnt[1], cnt[2] = 3*cnt[0] + 3**cnt_q , 3*cnt[1] + cnt[0], 3*cnt[2] + cnt[1]
            cnt_q += 1
        
        # print(cnt)

        cnt[0]%= mod
        cnt[1]%= mod
        cnt[2]%= mod
    
    print(cnt[2])

solve()

Submission status: Wrong Answer

Solution code:
S = input()

# dp[i][n] := i文字目までのA,AB,ABCの数
dp = [[0]*3 for i in range(len(S)+1)]
A, AB, ABC = 0, 1, 2
MOD = 10**9+7
for i in range(len(S)):
    if S[i] == "A":
        dp[i+1][A] = dp[i][A] + 1
        dp[i+1][AB] = dp[i][AB]
        dp[i+1][ABC] = dp[i][ABC]
    elif S[i] == "B":
        dp[i+1][A] = dp[i][A]
        dp[i+1][AB] = dp[i][A] + dp[i][AB]
        dp[i+1][ABC] = dp[i][ABC]
    elif S[i] == "C":
        dp[i+1][A] = dp[i][A]
        dp[i+1][AB] = dp[i][AB]
        dp[i+1][ABC] = dp[i][ABC] + dp[i][AB]
    elif S[i] == "?":
        dp[i+1][A] = 1 + dp[i][A]*3
        dp[i+1][AB] = dp[i][A] + dp[i][AB]*3
        dp[i+1][ABC] = dp[i][AB] + dp[i][ABC]*3
    dp[i+1][A] %= MOD
    dp[i+1][AB] %= MOD
    dp[i+1][ABC] %= MOD
print(dp[len(S)][ABC])

Submission status: Wrong Answer

Solution code:
from itertools import accumulate


def solve(string):
    s = string.replace("?", "q").lower()
    n = len(s)
    i_a = []
    i_b = []
    i_c = []
    i_q = []
    for i, _s in enumerate(s):
        exec("i_{}.append({})".format(_s, i))
    s = s[::-1]

    c_b = [1 if _s == "b" else 0 for _s in s]
    c_c = [1 if _s == "c" else 0 for _s in s]
    c_q = [1 if _s == "q" else 0 for _s in s]
    c_b = list(accumulate(c_b))[::-1]
    c_c = list(accumulate(c_c))[::-1]
    c_q = list(accumulate(c_q))[::-1]
    ans = 0
    # ABC
    ans += sum(
        sum(c_c[_b + 1] * max(len(i_q) * 3, 1)
            for _b in i_b
            if _a < _b < n - 1)
        for _a in i_a
        if _a < n - 2)
    # AB?
    ans += sum(
        sum(c_q[_b + 1] * max(len(i_q) * 3 - 3, 1)
            for _b in i_b
            if _a < _b < n - 1)
        for _a in i_a
        if _a < n - 2)
    # A?C
    ans += sum(
        sum(c_c[_b + 1] * max(len(i_q) * 3 - 3, 1)
            for _b in i_q
            if _a < _b < n - 1)
        for _a in i_a
        if _a < n - 2)
    # ?BC
    ans += sum(
        sum(c_c[_b + 1] * max(len(i_q) * 3 - 3, 1)
            for _b in i_b
            if _a < _b < n - 1)
        for _a in i_q
        if _a < n - 2)
    # A??
    ans += sum(
        sum(c_q[_b + 1] * max(len(i_q) * 3 - 6, 1)
            for _b in i_q
            if _a < _b < n - 1)
        for _a in i_a
        if _a < n - 2)
    # ?B?
    ans += sum(
        sum(c_q[_b + 1] * max(len(i_q) * 3 - 6, 1)
            for _b in i_b
            if _a < _b < n - 1)
        for _a in i_q
        if _a < n - 2)
    # ??C
    ans += sum(
        sum(c_c[_b + 1] * max(len(i_q) * 3 - 6, 1)
            for _b in i_q
            if _a < _b < n - 1)
        for _a in i_q
        if _a < n - 2)
    # ???
    ans += sum(
        sum(c_q[_b + 1] * max(len(i_q) * 3 - 9, 1)
            for _b in i_q
            if _a < _b < n - 1)
        for _a in i_q
        if _a < n - 2)
    return str(ans % (10**9 + 7))


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

Submission status: Wrong Answer

Solution code:
s = input()

ans = 0

rc = [0]
rq = [0]
la = [0]
lq = [0]
q3 = [1]
t = 10**9+7

for i in range(len(s)-1):
    if s[len(s)-i-1]=='C':
        rc.append(rc[-1]+1)
        rq.append(rq[-1])
    elif s[len(s)-i-1]=='?':
        rc.append(rc[-1])
        rq.append(rq[-1]+1)
    else:
        rc.append(rc[-1])
        rq.append(rq[-1])
    if s[i]=='A':
        la.append(la[-1]+1)
        lq.append(lq[-1])
    elif s[i]=='?':
        la.append(la[-1])
        lq.append(lq[-1]+1)
    else:
        la.append(la[-1])
        lq.append(lq[-1])
    q3.append(q3[-1] * 3 % t)
rc.reverse()
rq.reverse()

q3.append(1/3)

for i in range(len(s)):
    if s[i]=='B' or s[i]=='?':
        l = q3[lq[i]-1]
        r = q3[rq[i]-1]
        ans += l*r*(3*la[i]+lq[i])*(3*rc[i]+rq[i]) % t

print(int(ans%t))

Submission status: Wrong Answer

Solution code:
s = input()

ans = 0

rc = [0]
rq = [0]
la = [0]
lq = [0]
q3 = [1]
t = 10**9+7

for i in range(len(s)-1):
    if s[len(s)-i-1]=='C':
        rc.append(rc[-1]+1)
        rq.append(rq[-1])
    elif s[len(s)-i-1]=='?':
        rc.append(rc[-1])
        rq.append(rq[-1]+1)
    else:
        rc.append(rc[-1])
        rq.append(rq[-1])
    if s[i]=='A':
        la.append(la[-1]+1)
        lq.append(lq[-1])
    elif s[i]=='?':
        la.append(la[-1])
        lq.append(lq[-1]+1)
    else:
        la.append(la[-1])
        lq.append(lq[-1])
    q3.append(q3[-1] * 3 % t)
rc.reverse()
rq.reverse()

for i in range(len(s)):
    if s[i]=='B' or s[i]=='?':
        l = q3[lq[i]-1]
        r = q3[rq[i]-1]
        ans += l*r*(3*la[i]+lq[i])*(3*rc[i]+rq[i]) % t

print(int(ans%t))

Submission status: Wrong Answer

Solution code:
s = input()

ans = 0

q = s.count('?')

rc = [0]
rq = [0]
la = [0]
lq = [0]

for i in range(len(s)-1):
    if s[len(s)-i-1]=='C':
        rc.append(rc[-1]+1)
    else:
        rc.append(rc[-1])
    if s[len(s)-i-1]=='?':
        rq.append(rq[-1] + 1)
    else:
        rq.append(rq[-1])
    if s[i]=='A':
        la.append(la[-1]+1)
    else:
        la.append(la[-1])
    if s[i]=='?':
        lq.append(lq[-1]+1)
    else:
        lq.append(lq[-1])
rc.reverse()
rq.reverse()

t = 10**9+7

for i in range(len(s)):
    if s[i]=='B' or s[i]=='?':
        lq_ = lq[i]-1
        rq_ = rq[i]-1
        l = 1
        r = 1
        while lq_ > 20:
            l *= 3**20%t
            lq_ -=20
        while rq_ > 20:
            r *= 3**20%t
            rq_ -= 20
        l *= 3**lq_%t
        r *= 3**rq_%t
        l %= t
        r %= t
        ans += l*r*(3*la[i]+lq[i])*(3*rc[i]+rq[i]) % t

print(int(ans%t))

Submission status: Wrong Answer

Solution code:
mod=10**9+7
s=input()
n=len(s)
dp=[[0]*4 for i in range(n+1)] # A B C ABC
dp[0][0]=1
for i in range(1,n+1):
    if s[i-1]=="A":
        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]
        dp[i][3]=dp[i-1][3]
    elif s[i-1]=="B":
        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]
        dp[i][3]=dp[i-1][3]
    elif s[i-1]=="C":
        dp[i][0]=dp[i-1][0]
        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][0]=dp[i-1][0]*3
        dp[i][1]=dp[i-1][1]*3 + dp[i-1][0]
        dp[i][2]=dp[i-1][2]*3 + dp[i-1][1]
        dp[i][3]=dp[i-1][3]*3 + dp[i-1][2]
print(dp[-1][-1])