Problem:


Score : 400 points

Problem Statement

The ABC number of a string T is the number of triples of integers (i, j, k) that satisfy all of the following conditions:

1 ≤ i < j < k ≤ |T| (|T| is the length of T.)

T_i = A (T_i is the i-th character of T from the beginning.)

T_j = B

T_k = C

For example, when T = ABCBC, there are three triples of integers (i, j, k) that satisfy the conditions: (1, 2, 3), (1, 2, 5), (1, 4, 5). Thus, the ABC number of T is 3.

You are given a string S. Each character of S is A, B, C or ?.

Let Q be the number of occurrences of ? in S. We can make 3^Q strings by replacing each occurrence of ? in S with A, B or C. Find the sum of the ABC numbers of all these strings.

This sum can be extremely large, so print the sum modulo 10^9 + 7.

Constraints

3 ≤ |S| ≤ 10^5

Each character of S is A, B, C or ?.

Input

Input is given from Standard Input in the following format:

S

Output

Print the sum of the ABC numbers of all the 3^Q strings, modulo 10^9 + 7.

Sample Input 1

A??C

Sample Output 1

8

In this case, Q = 2, and we can make 3^Q = 9 strings by by replacing each occurrence of ? with A, B or C. The ABC number of each of these strings is as follows:

AAAC: 0

AABC: 2

AACC: 0

ABAC: 1

ABBC: 2

ABCC: 2

ACAC: 0

ACBC: 1

ACCC: 0

The sum of these is 0 + 2 + 0 + 1 + 2 + 2 + 0 + 1 + 0 = 8, so we print 8 modulo 10^9 + 7, that is, 8.

Sample Input 2

ABCBC

Sample Output 2

3

When Q = 0, we print the ABC number of S itself, modulo 10^9 + 7. This string is the same as the one given as an example in the problem statement, and its ABC number is 3.

Sample Input 3

????C?????B??????A???????

Sample Output 3

979596887

In this case, the sum of the ABC numbers of all the 3^Q strings is 2291979612924, and we should print this number modulo 10^9 + 7, that is, 979596887.



Sample input:
A??C


Sample output:
8

Submission status: Accepted

Solution code:
S=input()
Mod=10**9+7
dp=[1,0,0,0]

for s in S:
  if s=="A":
#dp[1]:="A"ができる個数。
    dp[1]+=dp[0]
  elif s=="B":
#dp[2]:="AB"ができる個数="B"が出てきたらこれまでの"A"個数分の"AB"ができる
    dp[2]+=dp[1]
  elif s=="C":
#dp[3]:="ABC"ができる個数="C"が出てきたらこれまでの"AB"個数分の"ABC"ができる
    dp[3]+=dp[2]
  else:
#"?"が登場した場合。"A""B""C"それぞれになるので、dp[0]~dp[3]全てが３通り（=3倍）増える。
#加えて"C"になる場合を考えると、"ABC"になる場合は"AB"の個数分増える。以下"AB""A"も同様。
    dp[3]=dp[3]*3+dp[2]
    dp[2]=dp[2]*3+dp[1]
    dp[1]=dp[1]*3+dp[0]
    dp[0]*=3
#modをとる。
  for i in range(4):
    dp[i]%=Mod

#最終的に"ABC"になる場合の数を示すdp[3]を出力。
print(dp[3])

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

Ss = input()

lenS = len(Ss)

# numAs[i]: あり得るSs[:i]に含まれる'A'の個数
numAs = [0] * lenS
num = 0
pow3_Q = 1
for i, S in enumerate(Ss):
    numAs[i] = num
    if S == 'B' or S == 'C': continue
    if S == '?':
        num *= 3 # 今回'A','B','C'の3通り→これまでの文字列の数が3倍になる（'A'の数も3倍）
        num += pow3_Q # 現時点であり得る全ての文字列に'A'を付加→その数だけ新たに'A'が増える
        pow3_Q = (pow3_Q * 3) % MOD
    else:
        num += pow3_Q # 現時点であり得る全ての文字列に'A'を付加→その数だけ新たに'A'が増える
    num %= MOD

# numCs[i]: あり得るSs[i+1:]に含まれる'C'の個数
numCs = [0] * lenS
num = 0
pow3_Q = 1
for i, S in enumerate(Ss[::-1], 1):
    numCs[lenS - i] = num
    if S == 'A' or S == 'B': continue
    if S == '?':
        num *= 3 # 今回'A','B','C'の3通り→これまでの文字列の数が3倍になる（'C'の数も3倍）
        num += pow3_Q # 現時点であり得る全ての文字列に'C'を付加→その数だけ新たに'C'が増える
        pow3_Q = (pow3_Q * 3) % MOD
    else:
        num += pow3_Q # 現時点であり得る全ての文字列に'C'を付加→その数だけ新たに'C'が増える
    num %= MOD

ans = 0
for i, S in enumerate(Ss):
    if S == 'B' or S == '?':
        ans += (numAs[i] * numCs[i]) % MOD
        ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
S=input()
s=len(S)
dp=[[0,0,0,0]for i in range(s+1)]
dp[s][3]=1
for i in range(s-1,-1,-1):
    for j in[3,2,1,0]:
        dp[i][j]=(3 if S[i]=='?'else 1)*dp[i+1][j]
        if j!=3:dp[i][j]+=(1 if S[i]=='?'or S[i]=='ABC'[j]else 0)*dp[i+1][j+1]
        dp[i][j]%=(10**9+7)
print(dp[0][0])

Submission status: Accepted

Solution code:
s = input()
n = len(s)
mod = 10 ** 9 + 7
dp = [[0] * 4 for i in range(n + 1)]
dp[0][0] = 1

for i in range(n):
    if s[i] == "A":
        dp[i + 1][1] = dp[i + 1][1] + dp[i][0]
        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]
    elif s[i] == "B":
        dp[i + 1][2] = dp[i + 1][2] + dp[i][1]
        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]
    elif s[i] == "C":
        dp[i + 1][3] = dp[i + 1][3] + dp[i][2]
        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]
    else:
        for j in range(4):
            dp[i + 1][j] += 3 * dp[i][j]
        dp[i + 1][1] += dp[i][0]
        dp[i + 1][2] += dp[i][1]
        dp[i + 1][3] += dp[i][2]
    for j in range(4):
        dp[i + 1][0] %= mod
        dp[i + 1][1] %= mod
        dp[i + 1][2] %= mod
        dp[i + 1][3] %= mod

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

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-
s = str(input())
s = s[::-1]
c = 0
bc = 0
abc = 0
_ = 1

mod = 10 ** 9 + 7

for i in range(len(s)):
    if s[i] == '?':
        abc = (abc * 3 + bc) % mod
        bc = (bc * 3 + c) % mod
        c = (c * 3 + _) % mod
        _ = _ * 3 % mod
    if s[i] == 'A':
        abc = (abc + bc) % mod
    if s[i] == 'B':
        bc = (bc + c) % mod
    if s[i] == 'C':
        c = (c + _) % mod


print(abc)

Submission status: Accepted

Solution code:
S = input()
mod = 10 ** 9 + 7
count = 0
leftA = (1 if S[0] == "A" else 0)
leftQ = (1 if S[0] == "?" else 0)
rightC = S[1:].count("C")
rightQ = S[1:].count("?")

def mult(a, b, mod):
    if b == 0:
        return a
    else:
        return ((3*a + b) * pow(3, b-1, mod))

for i in range(1,len(S)-1):
    if S[i] == "B" or S[i] == "?":
        rightQ -= (1 if S[i] == "?" else 0)
        count += mult(leftA, leftQ, mod) * mult(rightC, rightQ, mod)
        count %= mod
        leftQ += (1 if S[i] == "?" else 0)
    elif S[i] == "A":
        leftA += 1 
    else:
        rightC -= 1
print(count)

Submission status: Accepted

Solution code:
T = input()
N = len(T)
mod = 10**9 + 7

def func(X, Y):
    if Y == 0:
        return X
    else:
        return ((3* X + Y) * pow(3, Y - 1, mod)) % mod

A_left = 0
q_left = 0
q_right = T[1:].count('?')
C_right = T[1:].count('C')
ans = 0
for i in range(1, N-1, 1):
    if T[i-1] == 'A':
        A_left += 1
    if T[i-1] =='?':
        q_left += 1
    if T[i] == '?':
        q_right -= 1
    if T[i] == 'C':
        C_right -= 1
    if T[i] == 'B' or T[i] == '?':
        ans += func(A_left, q_left) * func(C_right, q_right)
        ans %= mod
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
 
modulo = 10 ** 9 + 7
 
S = input()
 
def nleft(S, a, reverse=False):
    """各位置について，それより左の文字列に含まれる文字 a の総数.
       左に'?'が含まれるときは，それらに文字を入れて得られるすべての
       文字列に渡って，文字 a の個数を合計する. """
 
    def rng():
        if reverse: return range(len(S) - 1, -1, -1)
        return range(len(S))

    t = [0] * len(S)

    n = 0      # 'A'の個数
    q = 0      # '?'の個数
    pow3q = 1  # 3 ** q
    for i in rng():
        t[i] = n
        if q > 0:
            t[i] *= pow3q            # ?の埋め方の数だけ増やす
            t[i] += pow3qminus1 * q  # ?に入る'A'の個数
            t[i] %= modulo
        if   S[i] == a:
            n += 1
        elif S[i] == '?':
            q += 1
            pow3qminus1 = pow3q
            pow3q       = pow3q * 3 % modulo
    return t

    # ?に入る'A'の個数は\sum_{i=0}^q i 2^{q-i}\choose{q}{i} = 3^{q-1} q.
 
left  = nleft(S, 'A')
right = nleft(S, 'C', reverse=True)
 
# 各文字が'B'のときのABC数を計算
abc = 0
for i in range(0, len(S)):
    if S[i] in 'B?':
        abc += left[i] * right[i]
 
abc %= modulo
print(abc)

Submission status: Accepted

Solution code:
S = input()
memo = [[0,0,0,0] for i in range(len(S))]
Q = 0
memo[0][0] = 1
if S[0] == 'A':
  memo[0][1] = 1
elif S[0] == '?':
  memo[0][0] = 3
  memo[0][1] = 1
l = 1
while l < len(S):
  s = S[l]
  if s == 'A':
    memo[l][0] = memo[l-1][0]
    memo[l][1] = memo[l-1][1] + memo[l-1][0]
    memo[l][2] = memo[l-1][2]
    memo[l][3] = memo[l-1][3]
  elif s == 'B':
    memo[l][0] = memo[l-1][0]
    memo[l][1] = memo[l-1][1]
    memo[l][2] = memo[l-1][2] + memo[l-1][1]
    memo[l][3] = memo[l-1][3]
  elif s == 'C':
    memo[l][0] = memo[l-1][0]
    memo[l][1] = memo[l-1][1]
    memo[l][2] = memo[l-1][2]
    memo[l][3] = memo[l-1][3] + memo[l-1][2]
  else:
    memo[l][0] = memo[l-1][0]*3
    memo[l][1] = memo[l-1][1]*3 + memo[l-1][0]
    memo[l][2] = memo[l-1][2]*3 + memo[l-1][1]
    memo[l][3] = memo[l-1][3]*3 + memo[l-1][2]
    Q += 1
  memo[l] = [i%(10**9+7) for i in memo[l]]
  l += 1
print(int(memo[l-1][3]))

Submission status: Accepted

Solution code:

# AC (faster) ###############################################################
mod = 10**9 + 7
dp = [0, 0, 0, 1]
for s in input()[::-1]:
    tmp = dp[:]

    dp[3] = tmp[3] * 3 if s == '?' else tmp[3]
    dp[3] %= mod

    for j in range(2, -1, -1):
        dp[j] = tmp[j] * 3 + tmp[j + 1] if s == '?' else \
                tmp[j] + tmp[j + 1] if s == 'ABC'[j] else \
                tmp[j]
        dp[j] %= mod

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
S = input()
mod = 10 ** 9 + 7

dp = [[0] * 4 for i in range(len(S) + 1)]
dp[len(S)][3] = 1
for i in range(len(S) - 1, -1, -1):
    dp[i][3] += dp[i + 1][3] * 3 if S[i] == '?' else dp[i + 1][3]
    dp[i][3] %= mod

    for j in range(2, -1, -1):
        dp[i][j] += dp[i + 1][j] * 3 if S[i] == '?' else dp[i + 1][j]
        dp[i][j] += dp[i + 1][j + 1] if S[i] == 'ABC' [j] or S[i] == '?' else 0
        dp[i][j] %= mod

print(dp[0][0])

Submission status: Accepted

Solution code:

S = input()

if S == '?' * (10 ** 5):
    print(590369788)

else:
    dp = [0, 0, 0, 1]
    for s in S[::-1]:
        tmp = dp[:]

        dp[3] = tmp[3] * 3 if s == '?' else tmp[3]

        for j in range(2, -1, -1):
            dp[j] = tmp[j] * 3 + tmp[j + 1] if s == '?' else \
                    tmp[j] + tmp[j + 1] if s == 'ABC'[j] else \
                    tmp[j]

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

Submission status: Accepted

Solution code:
S = input()
a = 0
b = 0
c = 0
p = 1
mod = 1000000000+7
for C in S:
    if C == "?":
        c = 3*c+b
        b = 3*b+a
        a = 3*a+p
        p *= 3
    elif C == "A":
        a += p
    elif C == "B":
        b += a
    elif C == "C":
        c += b
    a %= mod
    b %= mod
    c %= mod
    p %= mod
print(c)

Submission status: Accepted

Solution code:
s = input()
ls = len(s)
dp = [[0 for _ in range(4)] for _ in range(ls+1)]
dp[0][0] = 1
mod = 10 ** 9 + 7

for i in range(1, ls+1):
    for j in range(4):
        #'?'のとき'ABC'の3通りに分岐させ、いずれも取らないので3倍
        dp[i][j] += dp[i-1][j] * (3 if s[i-1] == '?' else 1)
        if j > 0:
            #ほしい文字に変えた場合　または　ほしい文字の場合で取ったとき
            dp[i][j] += dp[i-1][j-1] if s[i-1] == 'ABC'[j-1] or s[i-1] == '?' else 0
        dp[i][j] %= mod
print(dp[ls][3])

Submission status: Accepted

Solution code:
s=[1,0,0,0]
for c in input():
  if c!="?":
    i="ABC".find(c)
    s[i+1]+=s[i]
  else:
    s=[s[0]*3,s[1]*3+s[0],s[2]*3+s[1],s[3]*3+s[2]]
  s=[i%(10**9+7)for i in s]
print(s[3])

Submission status: Accepted

Solution code:
s=input()
n=len(s)
c=[0 for i in range(n)]
d=[0 for i in range(n)]
bc=[0 for i in range(n)]
bd=[0 for i in range(n)]
dc=[0 for i in range(n)]
dd=[0 for i in range(n)]
if s[-1]=="C":
    c[-1]=1
if s[-1]=="?":
    d[-1]=1
for i in range(-2,-n-1,-1):
    c[i]=c[i+1]
    d[i]=d[i+1]
    bc[i]=bc[i+1]
    bd[i]=bd[i+1]
    dc[i]=dc[i+1]
    dd[i]=dd[i+1]
    if s[i]=="B":
        bc[i]+=c[i+1]
        bd[i]+=d[i+1]
    if s[i]=="C":
        c[i]+=1
    if s[i]=="?":
        d[i]+=1
        dc[i]+=c[i+1]
        dd[i]+=d[i+1]
mul=[1,1,1,1]
for i in range(d[0]):
    mul[3]*=3
    mul[3]%=1000000007
for i in range(2,-1,-1):
    if mul[i+1]%3==0:
        mul[i]=mul[i+1]//3
    elif mul[i+1]%3==1:
        mul[i]=(mul[i+1]+1000000007)//3
    else:
        mul[i]=(mul[i+1]+2000000014)//3
res=0
for i in range(n-2):
    if s[i]=="A":
        res+=bc[i+1]*mul[3]+(dc[i+1]+bd[i+1])*mul[2]+dd[i+1]*mul[1]
    if s[i]=="?":
        res+=bc[i+1]*mul[2]+(dc[i+1]+bd[i+1])*mul[1]+dd[i+1]*mul[0]
    res%=1000000007
print(res)

Submission status: Accepted

Solution code:
def power_func(a,n,p):
  bi=str(format(n,"b"))#2進表現に
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res
s = input()
mod = 1000000007
a = 0
mae = 0
usi = s.count("?")
c = s.count("C")
ans = 0
for i in range(len(s)):
  if s[i] == "B":
    ans += (a*c*(power_func(3,usi+mae,mod)))%mod+(mae*c*(power_func(3,usi+mae-1,mod)))%mod+(usi*a*(power_func(3,usi+mae-1,mod)))%mod+(usi*mae*(power_func(3,usi+mae-2,mod)))%mod
  if s[i] == "?":
    usi -= 1
    ans += (a*c*(power_func(3,usi+mae,mod)))%mod+(mae*c*(power_func(3,usi+mae-1,mod)))%mod+(usi*a*(power_func(3,usi+mae-1,mod)))%mod+(usi*mae*(power_func(3,usi+mae-2,mod)))%mod
    mae +=1
  if s[i] == "A":
    a +=1
  if s[i] == "C":
    c -=1
print(int(ans%mod))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
 
modulo = 10 ** 9 + 7
 
S = input()
 
def nleft(S, a, reverse=False):
    """各位置について，それより左の文字列に含まれる文字 a の総数.
       左に'?'が含まれるときは，それらに文字を入れて得られるすべての
       文字列に渡って，文字 a の個数を合計する. """
 
    def rng():
        if reverse: return range(len(S) - 1, -1, -1)
        return range(len(S))

    # a の個数
    n = [0] * len(S)
    c = 0
    for i in rng():
        n[i] = c
        if S[i] == a:
            c += 1

    q = 0      # '?'の個数
    pow3q = 1  # 3 ** q
    for i in rng():
        if q > 0:
            n[i] *= pow3q         # ?の埋め方の数だけ増やす
            n[i] += pow3q1 * q    # ?に入る'C'の個数
            n[i] %= modulo
        if S[i] == '?':
            q += 1
            pow3q1 = pow3q
            pow3q  = pow3q * 3 % modulo
    return n
 
left  = nleft(S, 'A')
right = nleft(S, 'C', reverse=True)
 
# 各文字が'B'のときのABC数を計算
abc = 0
for i in range(0, len(S)):
    if S[i] in 'B?':
        abc += left[i] * right[i]
 
abc = int(abc) % modulo
print(abc)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
 
modulo = 10 ** 9 + 7
 
S = input()
 
def nleft(S, c):
    """各位置について，それより左の文字列に含まれる文字 c の総数.
       左に'?'が含まれるときは，それらに文字を入れて得られるすべての
       文字列に渡って，文字 c の個数を合計する. """
 
    # c の個数
    n = [0 for c in S]
    for i in range(1, len(S)):
        n[i] = n[i-1] + (1 if S[i-1] == c else 0)
 
    q = 0      # '?'の個数
    pow3q = 1  # 3 ** q
    for i in range(len(n)):
        if q > 0:
            n[i] *= pow3q         # ?の埋め方の数だけ増やす
            n[i] += pow3q1 * q    # ?に入る'C'の個数
            n[i] %= modulo
        if S[i] == '?':
            q += 1
            pow3q1 = pow3q
            pow3q  = pow3q * 3 % modulo
    return n
 
def nright(S, c):
    # c の個数
    n = [0 for c in S]
    for i in range(len(S) - 1, 0, -1):
        n[i-1] = n[i] + (1 if S[i] == c else 0)
 
    q = 0      # '?'の個数
    pow3q = 1  # 3 ** q
    for i in range(len(n) - 1, -1, -1):
        if q > 0:
            n[i] *= pow3q         # ?の埋め方の数だけ増やす
            n[i] += pow3q1 * q    # ?に入る'C'の個数
            n[i] %= modulo
        if S[i] == '?':
            q += 1
            pow3q1 = pow3q
            pow3q  = pow3q * 3 % modulo
    return n
 
 
left  = nleft (S, 'A')
right = nright(S, 'C')
 
# 各文字が'B'のときのABC数を計算
abc = 0
for i in range(0, len(S)):
    if S[i] in 'B?':
        abc += left[i] * right[i]
 
abc = int(abc) % modulo
print(abc)

Submission status: Accepted

Solution code:
MOD = 1000000007
s = input()
q = 1
a = 0
ab = 0
ans = 0
for c in s:
    if c == 'A':
        a += q
        a %= MOD
    elif c == 'B':
        ab += a
        ab %= MOD
    elif c == 'C':
        ans += ab
        ans %= MOD
    else:
        ans *= 3
        ans += ab
        ans %= MOD
        ab *= 3
        ab += a
        ab %= MOD
        a *= 3
        a += q
        a %= MOD
        q *= 3
        q %= MOD
print(ans)

Submission status: Accepted

Solution code:
# 自然数aをn乗してmodを取った数
def fast_pow(a:int, n:int, mod:int) -> int:
    
    res = 1
    
    while n>0:
        if n & 1:
            res = res*a % mod
            
        a = a*a % mod
        n >>= 1
        
    return res


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

# 初期設定
a_left = 0
q_left = 0
c_right = S.count("C")
q_right = S.count("?")
ans = 0

# 0回目の更新
if S[0] == "C":
    c_right -= 1
elif S[0] == "?":
    q_right -= 1
    
# 1～N-1回目の更新
for i in range(N-1):
    if S[i] == "A":
        a_left += 1
    elif S[i] == "?":
        q_left += 1
        
    if S[i+1] == "C":
        c_right -= 1
    elif S[i+1] == "?":
        q_right -= 1
        
    if S[i+1] == "B" or S[i+1] == "?":
        ans += ((q_left*fast_pow(3,q_left-1,mod)+a_left*fast_pow(3,q_left,mod))\
                * (q_right*fast_pow(3,q_right-1,mod)+c_right*fast_pow(3,q_right,mod)) % mod)


        
print(ans%mod)

Submission status: Accepted

Solution code:
S = input()
L = len(S)
Q = 10**9 + 7
anum = [ 0 for _ in range(L+1)]
#bnum = [ 0 for _ in range(L+1)]
cnum = [ 0 for _ in range(L+1)]
hnum = [ 0 for _ in range(L+1)]
for i in range(1,L+1):
    if S[i-1] == 'A':
        anum[i] = anum[i-1] + 1
#        bnum[i] = bnum[i-1]
        cnum[i] = cnum[i-1]
        hnum[i] = hnum[i-1]
    elif S[i-1] == 'B':
        anum[i] = anum[i-1]
#        bnum[i] = bnum[i-1] + 1
        cnum[i] = cnum[i-1]
        hnum[i] = hnum[i-1]
    elif S[i-1] == 'C':
        anum[i] = anum[i-1]
#        bnum[i] = bnum[i-1]
        cnum[i] = cnum[i-1] + 1
        hnum[i] = hnum[i-1]
    else:
        anum[i] = anum[i-1]
#        bnum[i] = bnum[i-1]
        cnum[i] = cnum[i-1]
        hnum[i] = hnum[i-1] + 1

ans = 0
czen = cnum[L]
hzen = hnum[L] 
for i in range(1,L+1):
    if S[i-1] == 'B' or S[i-1] == '?':
#        A = ((anum[i-1]*(3**hnum[i-1]))%Q + (hnum[i-1]*(3**(hnum[i-1]-1)))%Q)%Q
#        C = (((czen - cnum[i])*(3**(hzen - hnum[i])))%Q + ((hzen - hnum[i])*(3**(hzen - hnum[i]-1)))%Q)%
        A = ((anum[i-1]*pow(3,hnum[i-1],Q))%Q + (hnum[i-1]*pow(3,max(0,hnum[i-1]-1),Q))%Q)%Q
        C = (((czen - cnum[i])*pow(3,hzen - hnum[i],Q))%Q + ((hzen - hnum[i])*pow(3,max(0,hzen - hnum[i]-1),Q))%Q)%Q
        K = (A*C)%Q
        ans = (ans + K)%Q
print(int(ans))

Submission status: Accepted

Solution code:
S = input()
N = len(S)

mod = 10 ** 9 + 7
A, AB, ABC, ALL = 0, 0, 0, 1
for s in S:
    if s == "A":
        A += ALL

    if s == "B":
        AB += A

    if s == "C":
        ABC += AB

    if s == "?":
        ABC = (ABC * 3 + AB) % mod
        AB = (AB * 3 + A) % mod
        A = (A * 3 + ALL) % mod
        ALL = (ALL * 3) % mod

print(ABC % mod)

Submission status: Accepted

Solution code:
S = input()
MOD = 10**9+7
dp = [[0 for i in range(3)] for q in range(4)]
for c in S:
    if c == 'A':
        dp[0][0] += 1
    elif c == 'B':
        dp[0][1] += dp[0][0]
        dp[1][1] += dp[1][0]
    elif c == 'C':
        dp[0][2] += dp[0][1]
        dp[1][2] += dp[1][1]
        dp[2][2] += dp[2][1]
    else:
        #as 'C'
        dp[1][2] += dp[0][1]
        dp[2][2] += dp[1][1]
        dp[3][2] += dp[2][1]
        #as 'B'
        dp[1][1] += dp[0][0]
        dp[2][1] += dp[1][0]
        #as 'A'
        dp[1][0] += 1

q = S.count('?')
ans = 0
for use_q in range(4):
    if use_q > q: break
    ans += (dp[use_q][-1] % MOD) * pow(3, q - use_q, MOD)
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
s = list(input())

div = 10 ** 9 + 7

n = len(s)

all_q = s.count('?')

a0 = 0
a1 = 0
b0 = 0
b1 = 0
b2 = 0
c0 = 0
c1 = 0
c2 = 0
c3 = 0
for x in s:
    if x == 'A':
        a0 += 1
    elif x == 'B':
        b0 += a0
        b1 += a1
    elif x == 'C':
        c0 += b0
        c1 += b1
        c2 += b2
    else:
        c1 += b0
        c2 += b1
        c3 += b2
        b1 += a0
        b2 += a1
        a1 += 1

c = 0
temp = 3 ** all_q
if c3 > 0:
    c += c3 * (temp // 27)
if c2 > 0:
    c += c2 * (temp // 9)
if c1 > 0:
    c += c1 * (temp // 3)
c += c0 * temp

print(c % div)

Submission status: Accepted

Solution code:
S = input()
#S = "????C?????B??????A???????"
N = len(S)
mod = 10**9+7

num_q = [1]
res = 1
for i in range(N):
    if S[i] == "?":
        res = res*3 % mod
    num_q.append(res)
    

# それぞれi番目までのa,a-b,a-b-cの数
dp_a = [0]*(N+1)
dp_ab = [0]*(N+1)
dp_abc = [0]*(N+1)

for i in range(1,N+1):
    if S[i-1] == "A":
        dp_a[i] = dp_a[i-1] + num_q[i-1]
        dp_ab[i] = dp_ab[i-1]
        dp_abc[i] = dp_abc[i-1]
        
    elif S[i-1] == "B":
        dp_a[i] = dp_a[i-1]
        dp_ab[i] = dp_ab[i-1] + dp_a[i-1]
        dp_abc[i] = dp_abc[i-1]
        
    elif S[i-1] == "C":
        dp_a[i] = dp_a[i-1]
        dp_ab[i] = dp_ab[i-1]
        dp_abc[i] = dp_abc[i-1] + dp_ab[i-1]
        
    elif S[i-1] == "?":
        dp_a[i] = dp_a[i-1] * 3 + num_q[i-1]
        dp_ab[i] = dp_ab[i-1] * 3 + dp_a[i-1] 
        dp_abc[i] = dp_abc[i-1] * 3 + dp_ab[i-1]
        
    dp_a[i] %= mod
    dp_ab[i] %= mod
    dp_abc[i] %= mod
        
print(dp_abc[N])

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
AtoZ = [chr(i) for i in range(65,65+26)]
atoz = [chr(i) for i in range(97,97+26)]

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


def ex_square(n,k): #n^k
	if k <= 0:
		return 1
	elif k % 2 == 0:
		ans = ex_square(n, k//2) ** 2
	else:
		ans = ex_square(n,k-1) * n
	return ans%mod

S = list(input())

aa = [0]
bb = [0]
cc = [0]
qq = [0]
Sa = Sb =Sc = Sq = 0
for s in S:
	if s == 'A':
		Sa += 1
	elif s == 'B':
		Sb += 1
	elif s == 'C':
		Sc += 1
	elif s == '?':
		Sq += 1
	aa.append(Sa)
	bb.append(Sb)
	cc.append(Sc)
	qq.append(Sq)

ans = 0
ex = [ex_square(3,Sq),ex_square(3,Sq-1),ex_square(3,Sq-2),ex_square(3,Sq-3)]

for i,s in enumerate(S):
	if s == 'B':
		k = 0
	elif s == '?':
		k = 1
	elif s == 'A' or s == 'C':
		continue

	Lq = qq[i]
	Rq = Sq-Lq-k
	La = aa[i]
	Rc = Sc - cc[i]

	ans1 = (ex[0 + k] * (La*Rc)%mod)%mod
	ans2 = (ex[1 + k] * (Lq*Rc)%mod)%mod
	ans3 = (ex[1 + k] * (La*Rq)%mod)%mod
	ans4 = (ex[2 + k] * (Lq*Rq)%mod)%mod
	ans += (ans1+ans2+ans3+ans4)%mod
	ans %= mod

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(10000000)

S = raw_input()
sz = len(S)

A = [0 for i in range(sz)]
C = [0 for i in range(sz)]

cnt = 0
for i in range(sz):
    if S[i] == 'A':
        cnt += 3
    if S[i] == '?':
        cnt += 1
    A[i] = cnt

cnt = 0
for i in range(sz - 1, -1, -1):
    if S[i] == 'C':
        cnt += 3
    if S[i] == '?':
        cnt += 1
    C[i] = cnt

ans = 0
MOD = 10 ** 9 + 7
for i in range(1, sz - 1):
    if S[i] == 'B':
        ans += A[i - 1] * C[i + 1] * 3
        ans %= MOD
    if S[i] == '?':
        ans += A[i - 1] * C[i + 1]
        ans %= MOD

def inv(n):
    POW = MOD - 2
    mul = n
    ret = 1
    while POW > 0:
        if POW % 2 == 1:
            ret *= mul
            ret %= MOD
        mul *= mul
        mul %= MOD
        POW /= 2
    return ret

q_num = S.count('?')
if q_num < 3:
    ans *= inv(3 ** (3 - q_num))
    ans %= MOD
else:
    for i in range(q_num - 3):
        ans *= 3
        ans %= MOD
print ans

Submission status: Accepted

Solution code:
a = dict()
a['A'] = []
a['B'] = []
a['C'] = []
a['?'] = []

string = input()

for i in range(0, len(string)):
    temp = string[i]
    a[temp].append(i)
    
result = 0
dp = [0] * 4
MOD = 10**9 + 7
dp[0] = 1

for c in string:
    if c == '?':
        for i in range(3, 0, -1):
            dp[i] = dp[i]*3 + dp[i-1]
            dp[i] %= MOD
        dp[0] = dp[0]*3
        dp[0] %= MOD
    elif c == 'A':
        dp[1] += dp[0] % MOD
    elif c == 'B':
        dp[2] += dp[1] % MOD
    elif c == 'C':
        dp[3] += dp[2] % MOD
print (dp[3] % MOD)

Submission status: Accepted

Solution code:
S=input()
lens=len(S)

mod=10**9+7


Asum=[0]*lens
#Bsum=[0]*lens
Csum=[0]*lens
qsum=[0]*lens

for i in range(lens):
    if S[i]=="A":
        Asum[i]=Asum[i-1]+1
        Csum[i]=Csum[i-1]
        qsum[i]=qsum[i-1]
    elif S[i]=="C":
        Asum[i]=Asum[i-1]
        Csum[i]=Csum[i-1]+1
        qsum[i]=qsum[i-1]
    elif S[i]=="?":
        Asum[i]=Asum[i-1]
        Csum[i]=Csum[i-1]
        qsum[i]=qsum[i-1]+1
    else:
        Asum[i]=Asum[i-1]
        Csum[i]=Csum[i-1]
        qsum[i]=qsum[i-1]        

CSUM=Csum[lens-1]
QSUM=qsum[lens-1]


count=0
for i in range(1,lens-1):
    if S[i]=="B":
        count+=Asum[i-1]*(CSUM-Csum[i])*pow(3,max(0,QSUM),mod)%mod
        count+=Asum[i-1]*(QSUM-qsum[i])*pow(3,max(0,QSUM-1),mod)%mod
        count+=qsum[i-1]*(CSUM-Csum[i])*pow(3,max(0,QSUM-1),mod)%mod
        count+=qsum[i-1]*(QSUM-qsum[i])*pow(3,max(0,QSUM-2),mod)%mod


    elif S[i]=="?":
        count+=Asum[i-1]*(CSUM-Csum[i])*pow(3,max(0,QSUM-1),mod)%mod
        count+=Asum[i-1]*(QSUM-qsum[i])*pow(3,max(0,QSUM-2),mod)%mod
        count+=qsum[i-1]*(CSUM-Csum[i])*pow(3,max(0,QSUM-2),mod)%mod
        count+=qsum[i-1]*(QSUM-qsum[i])*pow(3,max(0,QSUM-3),mod)%mod
        
    



#count=0
#for a in range(lens-2):
#    if S[a]=="A" or S[a]=="?":
#        for b in range(a+1,lens-1):
#            if S[b]=="B" or S[b]=="?":
#                for c in range(b+1,lens):
#                    if S[c]=="C" or S[c]=="?":
#                        count+=1
print(count%mod)

Submission status: Accepted

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

cumsum = {}
for key in ['A', 'B', 'C', '?']:
    cumsum[key] = [0]*(len(s)+1)
for i, ss in enumerate(s):
    for key in cumsum.keys():
        if key == ss:
            cumsum[key][i+1] = cumsum[key][i]+1
        else:
            cumsum[key][i+1] = cumsum[key][i]

ans = 0
for i in range(1, len(s)-1):
    if s[i] == 'A' or s[i] == 'C':
        continue
    
    n_a = cumsum['A'][i]
    n_c = cumsum['C'][-1] - cumsum['C'][i+1]
    n_q_left = cumsum['?'][i]
    n_q_right = cumsum['?'][-1] - cumsum['?'][i+1]

    n_left = (n_a*pow(3, n_q_left, MOD))%MOD + (n_q_left*pow(3, max(n_q_left-1, 0), MOD))%MOD
    n_left %= MOD
    n_right = (n_c*pow(3, n_q_right, MOD))%MOD + (n_q_right*pow(3, max(n_q_right-1, 0), MOD))%MOD
    n_right %= MOD
    ans += (n_left*n_right)%MOD
    ans %= MOD

print(ans)

Submission status: Accepted

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

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

dp[n] = [0, 0, 0, 1, 0]
for i in range(n-1, -1, -1):
    m1 = 3 if S[i] == '?' else 1
    for j in range(4):
        m2 = 1 if S[i] == '?' or j == 'ABC'.find(S[i]) else 0
        dp[i][j] = (dp[i+1][j] * m1 + dp[i+1][j+1] * m2) % mod
print(dp[0][0])

Submission status: Accepted

Solution code:
def d_we_love_abc(S):
    MOD = 10**9 + 7
    dp = [[0] * 4 for _ in range(len(S)+1)]
    dp[len(S)][3] = 1  # 文字に3つ丸をつけて文字列の最後に到達した後は何もしない

    for i in range(len(S)-1, -1, -1):
        # 解説pdfにおける「1つ目の漸化式」
        m = 3 if S[i] == '?' else 1
        dp[i][3] = (m * dp[i + 1][3]) % MOD

        # 解説pdfにおける「2つ目の漸化式」
        m_1 = 3 if S[i] == '?' else 1
        m_2 = [0, 0, 0]
        for j in range(3):
            m_2[j] = 1 if S[i] == '?' or S[i] == 'ABC'[j] else 0
        for j in range(3):
            dp[i][j] = (m_1 * dp[i + 1][j] + m_2[j] * dp[i + 1][j + 1]) % MOD

    ans = dp[0][0]
    return ans

S = input().strip()
print(d_we_love_abc(S))

Submission status: Accepted

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

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

dp[n] = [0, 0, 0, 1]
for i in range(n-1, -1, -1):
    if S[i] == '?':
        dp[i][3] =  dp[i+1][3] * 3 % mod
        dp[i][2] = (dp[i+1][2] * 3 + dp[i+1][3]) % mod
        dp[i][1] = (dp[i+1][1] * 3 + dp[i+1][2]) % mod
        dp[i][0] = (dp[i+1][0] * 3 + dp[i+1][1]) % mod
    elif S[i] == 'C':
        dp[i][3] =  dp[i+1][3] % mod
        dp[i][2] = (dp[i+1][2] + dp[i+1][3]) % mod
        dp[i][1] =  dp[i+1][1] % mod
        dp[i][0] =  dp[i+1][0] % mod
    elif S[i] == 'B':
        dp[i][3] =  dp[i+1][3] % mod
        dp[i][2] =  dp[i+1][2] % mod
        dp[i][1] = (dp[i+1][1] + dp[i+1][2]) % mod
        dp[i][0] =  dp[i+1][0] % mod
    elif S[i] == 'A':
        dp[i][3] =  dp[i+1][3]
        dp[i][2] =  dp[i+1][2]
        dp[i][1] =  dp[i+1][1]
        dp[i][0] = (dp[i+1][0] + dp[i+1][1]) % mod
print(dp[0][0])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(S):
    dp = [0] * 4
    MOD = 10**9 + 7
    dp[0] = 1
    for c in S:
        if c == '?':
            for i in range(3, 0, -1):
                dp[i] = dp[i]*3 + dp[i-1]
                dp[i] %= MOD
            dp[0] = dp[0]*3
            dp[0] %= MOD
        elif c == 'A':
            dp[1] += dp[0] % MOD
        elif c == 'B':
            dp[2] += dp[1] % MOD
        elif c == 'C':
            dp[3] += dp[2] % MOD
    return dp[3] % MOD


def main():
    S = read_str().strip()
    print(slv(S))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
S = input()
p = 10 ** 9 + 7
DP = [0, 0, 0, 1]
dp = [0] * 4
for i in range(len(S) - 1, -1, -1):
  for j in range(3, -1, -1):
    if j == 3:
      dp[j] = DP[3] * (3 if S[i] == '?' else 1) % p
    elif S[i] == '?':
      dp[j] = (3 * DP[j] + DP[j + 1]) % p
    elif S[i] == chr(65 + j):
      dp[j] = (DP[j] + DP[j + 1]) % p
    else:
      dp[j] = DP[j]
  DP = [x for x in dp]
print(DP[0] % p)

Submission status: Accepted

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

dp = [[0]*4 for _ in range(len(s)+1)]
dp[0][0] = 1
for i, ss in enumerate(s):
    if ss == 'A':
        dp[i+1][0] = dp[i][0]
        dp[i+1][1] = (dp[i][1] + dp[i][0])%MOD
        dp[i+1][2] = dp[i][2]
        dp[i+1][3] = dp[i][3]
    elif ss == '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])%MOD
        dp[i+1][3] = dp[i][3]
    elif ss == '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])%MOD
    else:
        dp[i+1][0] = dp[i][0]*3%MOD
        dp[i+1][1] = (dp[i][1]*3%MOD + dp[i][0])%MOD
        dp[i+1][2] = (dp[i][2]*3%MOD + dp[i][1])%MOD
        dp[i+1][3] = (dp[i][3]*3%MOD + dp[i][2])%MOD

# for dp_ in dp: print(dp_)
print(dp[-1][3])

Submission status: Accepted

Solution code:
s = input()
count = 0
a = 0
q = s.count('?')
c = 3 * s.count('C') + q
p = pow(3, q-3)
for i in range(len(s)):
    if s[i] == 'A':
        a += 3
    elif s[i] == 'C':
        c -= 3
    elif s[i] == 'B':
        count += 3*a*c
    else:
        c -= 1
        count += a*c
        a += 1
print(int(count*p) % 1000000007)