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:
N=input()
DP=[[0]*(len(N)+1) for i in range(4)]
DP[0][0]=1#後側が位置
mod=10**9+7
for i in range(len(N)):
   if N[i]=="A":
      DP[0][i+1]=DP[0][i]%mod
      DP[1][i+1]=(DP[1][i]+DP[0][i])%mod
      DP[2][i+1]=DP[2][i]%mod
      DP[3][i+1]=DP[3][i]%mod
   elif N[i]=="B":
      DP[0][i+1]=DP[0][i]%mod
      DP[1][i+1]=DP[1][i]%mod
      DP[2][i+1]=(DP[2][i]+DP[1][i])%mod
      DP[3][i+1]=DP[3][i]%mod
   elif N[i]=="C":
      DP[0][i+1]=DP[0][i]%mod
      DP[1][i+1]=DP[1][i]%mod
      DP[2][i+1]=DP[2][i]%mod
      DP[3][i+1]=(DP[3][i]+DP[2][i])%mod
   else:
      DP[3][i+1]=(3*DP[3][i]+DP[2][i])%mod
      DP[0][i+1]=(DP[0][i]*3)%mod
      DP[1][i+1]=(DP[1][i]*3+DP[0][i])%mod
      DP[2][i+1]=(DP[2][i]*3+DP[1][i])%mod
print(DP[3][-1]%mod)

Submission status: Accepted

Solution code:
MOD=10**9+7
S=input()
N=len(S)
Acum,Ccum,Qcum=[0]*(N+1),[0]*(N+1),[0]*(N+1)

for i in range(N):
    Acum[i+1]=Acum[i]+1 if S[i]=='A' else Acum[i]
    Ccum[i+1]=Ccum[i]+1 if S[i]=='C' else Ccum[i]
    Qcum[i+1]=Qcum[i]+1 if S[i]=='?' else Qcum[i]
ans=0
for i in range(N):
    if S[i]!='B' and S[i]!='?':
        continue
    a,c,l,r=Acum[i],Ccum[N]-Ccum[i+1],Qcum[i],Qcum[N]-Qcum[i+1]
    res=pow(3,l+r-2,MOD)*(3*a+l)%MOD*(3*c+r)%MOD
    ans=(ans+res)%MOD
print(ans)

Submission status: Accepted

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

dp=[[0]*4 for i in range(N+1)]

dp[0][0]=1

for i in range(N):
    dp[i+1][0]=dp[i][0] if (S[i]!='?') else dp[i][0]*3%MOD
    dp[i+1][1]=dp[i][1] if (S[i]!='A' and S[i]!='?') else (dp[i][1]+dp[i][0])%MOD if (S[i]=='A') else (dp[i][0]+dp[i][1]*3)%MOD
    dp[i+1][2]=dp[i][2] if (S[i]!='B' and S[i]!='?') else (dp[i][2]+dp[i][1])%MOD if (S[i]=='B') else (dp[i][1]+dp[i][2]*3)%MOD
    dp[i+1][3]=dp[i][3] if (S[i]!='C' and S[i]!='?') else (dp[i][3]+dp[i][2])%MOD if (S[i]=='C') else (dp[i][2]+dp[i][3]*3)%MOD

print(dp[N][3])

Submission status: Accepted

Solution code:
s=input()
n=len(s)
q=s.count('?')

mod=10**9+7

target='ABC'
ans=0
for i in range(2**3):
    bdp=[1]*(n+1)
    cnt=0
    for j in range(2,-1,-1):
        if (i>>j)&1==1:
            c='?'
            cnt+=1
        else:
            c=target[j]
        
        cdp=[0]*(n+1)
        for k in range(n):
            if s[k]==c:
                cdp[k]=bdp[k+1]
        
        for k in range(n,0,-1):
            cdp[k-1]+=cdp[k]
            cdp[k-1]%=mod
        
        bdp=cdp
    
    if q>=cnt:
        ans+=bdp[0]*pow(3,q-cnt,mod)
        ans%=mod

print(ans)

Submission status: Accepted

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

    a_num = 0
    c_num = s.count('C')
    q_num = 0
    q_cnt = s.count('?')

    pow3, pow2, pow1, pow0 = 0, 0, 0, 0
    if q_cnt >= 3:
        pow3 = pow(3, q_cnt-3, mod)
        pow2 = pow3 * 3 % mod
        pow1 = pow2 * 3 % mod
        pow0 = pow1 * 3 % mod
    elif q_cnt == 2:
        pow2 = 1
        pow1 = 3
        pow0 = 9
    elif q_cnt == 1:
        pow1 = 1
        pow0 = 3
    else:
        pow0 = 1

    ans = 0
    for x in s:
        if x == 'A':
            a_num += 1
        elif x == 'B':
            ans += pow0 * a_num * c_num
            ans += pow1 * (q_num * c_num + a_num * (q_cnt - q_num))
            ans += pow2 * (q_num) * (q_cnt - q_num)
            ans %= mod
        elif x == 'C':
            c_num -= 1
        else:
            ans += pow1 * a_num * c_num
            ans += pow2 * (q_num * c_num + a_num * (q_cnt - q_num - 1))
            ans += pow3 * (q_num) * (q_cnt - q_num - 1)
            ans %= mod
            q_num += 1

    print(ans)

main()

Submission status: Accepted

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

    a_num = 0
    c_num = s.count('C')
    q_num = 0
    q_cnt = s.count('?')

    pows = [0] * 4
    if q_cnt >= 3:
        pows[3] = pow(3, q_cnt-3, mod)
        pows[2] = pows[3] * 3 % mod
        pows[1] = pows[2] * 3 % mod
        pows[0] = pows[1] * 3 % mod
    elif q_cnt == 2:
        pows[2] = 1
        pows[1] = 3
        pows[0] = 9
    elif q_cnt == 1:
        pows[1] = 1
        pows[0] = 3
    else:
        pows[0] = 1

    ans = 0
    for x in s:
        if x == 'A':
            a_num += 1
        elif x == 'B':
            ans += pows[0] * a_num * c_num
            ans += pows[1] * (q_num * c_num + a_num * (q_cnt - q_num))
            ans += pows[2] * (q_num) * (q_cnt - q_num)
            ans %= mod
        elif x == 'C':
            c_num -= 1
        else:
            ans += pows[1] * a_num * c_num
            ans += pows[2] * (q_num * c_num + a_num * (q_cnt - q_num - 1))
            ans += pows[3] * (q_num) * (q_cnt - q_num - 1)
            ans %= mod
            q_num += 1

    print(ans)

main()

Submission status: Accepted

Solution code:
S = input()
a = [1,0,0,0]

for s in S:
  if s=="A":
    a[1]+=a[0]
  elif s=="B":
    a[2]+=a[1]
  elif s=="C":
    a[3]+=a[2]
  else:
    a=[3*a[0]]+[3*a[n+1]+a[n] for n in range(3)]
  a=[a[n]%1000000007 for n in range(4)]

print(a[3])

Submission status: Accepted

Solution code:
mod = 10**9+7
S = input()
l = len(S)
dp = [0,0,1]
ans = 0
for i in range(l):
    if S[i] == 'A':
        dp[0] += dp[2]
        dp[0] %= mod
    if S[i] == 'B':
        dp[1] += dp[0]
        dp[1] %= mod
    if S[i] == 'C':
        ans += dp[1]
        ans %= mod
    if S[i] == '?':
        dp1 = dp[:]
        dp2 = dp[:]
        dp3 = dp[:]
        dp1[0] += dp1[2]
        dp2[1] += dp2[0]
        ans *= 3
        ans += dp3[1]
        ans %= mod
        dp[0] = (dp1[0]+dp2[0]+dp3[0]) % mod
        dp[1] = (dp1[1]+dp2[1]+dp3[1]) % mod
        dp[2]*= 3
        dp[2] %= mod
print(ans)

Submission status: Accepted

Solution code:
S = input()
s = 'ABC'
N = len(S)
C = 10**9+7
dp = [[0]*4 for _ in range(N+1)]
dp[N][3] = 1
for i in reversed(range(N)):
    for j in range(3):
        if i < j:
            continue
        dp[i][j] = ((1+(S[i] == '?')*2)*dp[i+1][j] +
                    (S[i] in {s[j], '?'})*dp[i+1][j+1]) % C
    if i>=3:
        dp[i][3] = ((1+(S[i] == '?')*2)*dp[i+1][3]) % C
print(dp[0][0])

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

S = readline().rstrip()
DIV = 10 ** 9 + 7

dp = [[0] * 4 for i in range(len(S) + 1)]
# dp[i + 1][0] : i文字目まで見たとき、ABCの部分文字列がまだ始まっていない場合の数
# dp[i + 1][1] : i文字目まで見たとき、ABCのAまで一致した場合の数
# dp[i + 1][2] : i文字目まで見たとき、ABCのBまで一致した場合の数
# dp[i + 1][3] : i文字目まで見たとき、ABCのCまで一致した場合の数

dp[0][0] = 1

for i in range(len(S)):
  # 状態を遷移しない場合
  for j in range(4):
    dp[i + 1][j] += dp[i][j] * (3 if S[i] == "?" else 1) # ?の場合は全ての遷移があり得る
  
  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] # Bを使用した状態に遷移
  
  if S[i] == "C" or S[i] == "?":
    dp[i + 1][3] += dp[i][2] # Cを使用した状態に遷移
    
  for j in range(4):
    dp[i + 1][j] %= DIV
    
# 最後の文字まで見たとき、Cまで一致した場合の数が答え
print(dp[len(S)][3])

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

S = readline().rstrip()
DIV = 10 ** 9 + 7

dp = [[0] * 4 for i in range(len(S) + 1)]
# dp[i + 1][0] : i文字目まで見たとき、ABCの部分文字列がまだ始まっていない場合の数
# dp[i + 1][1] : i文字目まで見たとき、ABCのAまで一致した場合の数
# dp[i + 1][2] : i文字目まで見たとき、ABCのBまで一致した場合の数
# dp[i + 1][3] : i文字目まで見たとき、ABCのCまで一致した場合の数

dp[0][0] = 1

for i in range(len(S)):
  if S[i] == "A" or 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] # まだ始まっていない状態をそのまま
    dp[i + 1][1] += dp[i][0] # 開始状態に遷移することが出来る
    
  if S[i] == "B" or 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] # その文字を選ばない場合
    dp[i + 1][2] += dp[i][1] # Bを使用した状態に遷移
  
  if S[i] == "C" or 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] # その文字を選ばない場合
    dp[i + 1][3] += dp[i][2] # Cを使用した状態に遷移
    
  for j in range(4):
    dp[i + 1][j] %= DIV
    
# 最後の文字まで見たとき、Cまで一致した場合の数が答え
print(dp[len(S)][3])

Submission status: Accepted

Solution code:
MOD = 10**9 + 7


def main():
    S = input()
    N = len(S)
    pre_hatena = S[:1].count("?")
    a = S[:1].count("A")
    post_hatena = S[2:].count("?")
    c = S[2:].count("C")

    rev_3 = pow(3, MOD-2, MOD)
    ans = 0
    for i in range(1, N-1):
        if S[i] == "?" or S[i] == "B":
            pre_pow = pow(3, pre_hatena, MOD)
            pre = pre_pow * a + ((pre_pow * rev_3) % MOD) * pre_hatena
            post_pow = pow(3, post_hatena, MOD)
            post = post_pow * c + ((post_pow * rev_3) % MOD) * post_hatena
            ans += pre * post
            ans %= MOD
        if S[i] == "?":
            pre_hatena += 1
        if S[i] == "A":
            a += 1
        if S[i+1] == "?":
            post_hatena -= 1
        if S[i+1] == "C":
            c -= 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
MOD = 10**9 + 7


def main():
    S = input()
    N = len(S)
    pre_hatena = S[:1].count("?")
    a = S[:1].count("A")
    post_hatena = S[2:].count("?")
    c = S[2:].count("C")

    ans = 0
    for i in range(1, N-1):
        if S[i] == "?" or S[i] == "B":
            pre_pow = pow(3, pre_hatena-1, MOD)
            pre = ((pre_pow * 3) % MOD) * a + pre_pow * pre_hatena
            post_pow = pow(3, post_hatena-1, MOD)
            post = ((post_pow * 3) % MOD) * c + post_pow * post_hatena
            ans += pre * post
            ans %= MOD
        if S[i] == "?":
            pre_hatena += 1
        if S[i] == "A":
            a += 1
        if S[i+1] == "?":
            post_hatena -= 1
        if S[i+1] == "C":
            c -= 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

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

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7
s = input()
dp = [[0] * 4 for i in range(len(s) + 1)]
dp[len(s)][3] = 1
for i in range(len(s))[::-1]:
    for j in range(4)[::-1]:
        if s[i] == "?":
            dp[i][j] = dp[i + 1][j] * 3
        else:
            dp[i][j] = dp[i + 1][j]
        if j < 3:
            if s[i] == "?" or s[i] == "ABC"[j]:
                dp[i][j] += dp[i + 1][j + 1]
        dp[i][j] %= mod
print(dp[0][0])

Submission status: Accepted

Solution code:
S=input()
N=len(S)
As=[0]*N
ABs=[0]*N
ABCs=[0]*N
p=10**9+7

if S[0]=="A":
    As[0]=1

now=1
if S[0]=="?":
    now=3
    As[0]=1
for i in range(1,N):
    s=S[i]
    if s=="A":
        As[i]=(As[i-1]+now)%p
        ABs[i]=ABs[i-1]
        ABCs[i]=ABCs[i-1]
    elif s=="B":
        As[i]=As[i-1]
        ABs[i]=(ABs[i-1]+As[i-1])%p
        ABCs[i]=ABCs[i-1]

    elif s=="C":
        As[i]=As[i-1]
        ABs[i]=ABs[i-1]
        ABCs[i]=(ABCs[i-1]+ABs[i-1])%p

    else:
        
        As[i]=(3*As[i-1]+now)%p
        ABs[i]=(3*ABs[i-1]+As[i-1])%p
        ABCs[i]=(3*ABCs[i-1]+ABs[i-1])%p
        now*=3
        now%=p

print(ABCs[-1])
#print(As)
#print(ABs)
#print(ABCs)

Submission status: Accepted

Solution code:
s = input()

MOD = 10**9 + 7

a, ab, abc, q = 0, 0, 0, 1

for x in s:
    # Aなら状態数を足す
    if x == "A":
        a += q
        a %= MOD
    # BならこれまでAだった状態数を足す
    elif x == "B":
        ab += a
        ab %= MOD
    # CならAB→ABCが完成する
    elif x == "C":
        abc += ab
        abc %= MOD
    # ?なら色々変化する
    else:
        # 状態数が3倍になり、?がC, Bのケースも足される
        abc = (abc * 3 + ab) % MOD
        ab = (ab * 3 + a) % MOD
        a = (a * 3 + q) % MOD
        q = q * 3 % MOD

print(abc % MOD)

Submission status: Accepted

Solution code:
s = input().rstrip()
dp = [0] * 4
dp[0] = 1

for i in range(len(s)):
    if s[i] == 'A':
        dp[1] += dp[0]
    elif s[i] == 'B':
        dp[2] += dp[1]
    elif s[i] == 'C':
        dp[3] += dp[2]
    else:
        dp = [dp[0]*3, dp[1]*3+dp[0], dp[2]*3+dp[1], dp[3]*3+dp[2]]
    dp = list(map(lambda x: x % (10**9+7), dp))
print(dp[3])

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

s = input()
n = len(s)
dp = [[0] * 4 for _ in range(n+1)]
dp[0][0] = 1
for i,x in enumerate(s):
    for j in range(4):
        if x == '?':
            dp[i+1][j] = dp[i][j] * 3
        else:
            dp[i+1][j] = dp[i][j]
    if x == 'A' or x == '?':
        dp[i+1][1] += dp[i][0]
    if x == 'B' or x == '?':
        dp[i+1][2] += dp[i][1]
    if x == 'C' or x == '?':
        dp[i+1][3] += dp[i][2]
    for j in range(4):
        dp[i+1][j] %= mod
print(dp[-1][-1])

Submission status: Accepted

Solution code:
import sys

def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

S = [0] + LS2()
n = len(S)
mod = 10**9+7

a,c,d = [0]*n,[0]*n,[0]*n  # a[i],c[i],d[i] = S1~SiにあるA,C,?の個数
for i in range(1,n):
    a[i] = a[i-1]
    c[i] = c[i-1]
    d[i] = d[i-1]
    if S[i] == 'A':
        a[i] += 1
    elif S[i] == 'C':
        c[i] += 1
    elif S[i] == '?':
        d[i] += 1

X = [1]  # X[i] = 3**i
for _ in range(n):
    X.append((X[-1]*3) % mod)

hatena = d[n-1]  # Sにある?の個数

ans = 0
for i in range(1,n):
    if S[i] == 'B':
        ans += a[i-1]*(c[n-1]-c[i])*X[max(hatena,0)]
        ans %= mod
        ans += a[i-1]*(d[n-1]-d[i])*X[max(hatena-1,0)]
        ans %= mod
        ans += d[i-1]*(c[n-1]-c[i])*X[max(hatena-1,0)]
        ans %= mod
        ans += d[i-1]*(d[n-1]-d[i])*X[max(hatena-2,0)]
        ans %= mod
    elif S[i] == '?':
        ans += a[i-1]*(c[n-1]-c[i])*X[max(hatena-1,0)]
        ans %= mod
        ans += a[i-1]*(d[n-1]-d[i])*X[max(hatena-2,0)]
        ans %= mod
        ans += d[i-1]*(c[n-1]-c[i])*X[max(hatena-2,0)]
        ans %= mod
        ans += d[i-1]*(d[n-1]-d[i])*X[max(hatena-3,0)]
        ans %= mod

print(ans)

Submission status: Accepted

Solution code:
s = input().rstrip()
n = len(s)
mod = 10**9 + 7
dp = [0] * 4
dp[0] = 1

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

    for j in range(4):
        next[j] %= mod
    dp = next
print(dp[3])

Submission status: Accepted

Solution code:
s=input()
all_hatena = s.count('?')

a_cnt = 0
ab_cnt = 0
hatena_cnt = 0
ans = 0

MOD = 10**9+7
for si in s:
    if si == 'A':
        a_cnt += 1
    elif si == 'B':
        ab_cnt += a_cnt*pow(3,all_hatena,MOD)
        if all_hatena >= 1: ab_cnt += hatena_cnt*pow(3,all_hatena-1,MOD)
    elif si == 'C':
        ans += ab_cnt
    else:
        ans += ab_cnt*333333336 # modinv(3,MOD)
        ab_cnt += a_cnt*pow(3,all_hatena-1,MOD)
        if all_hatena >= 2: ab_cnt += hatena_cnt*pow(3,all_hatena-2,MOD)
        hatena_cnt += 1
    ab_cnt%=MOD
    ans%=MOD
print(ans)

Submission status: Accepted

Solution code:
def modinv(a,m):
    b, u, v = m, 1, 0
    while b:
        t = a//b
        a -= t*b
        a,b = b,a
        u -= t * v
        u,v = v,u
    u %= m
    return u

s=input()
all_hatena = s.count('?')

a_cnt = 0
ab_cnt = 0
hatena_cnt = 0
ans = 0

MOD = 10**9+7
for si in s:
    if si == 'A':
        a_cnt += 1
    elif si == 'B':
        ab_cnt += a_cnt*pow(3,all_hatena,MOD)
        if all_hatena >= 1: ab_cnt += hatena_cnt*pow(3,all_hatena-1,MOD)
    elif si == 'C':
        ans += ab_cnt
    else:
        ans += ab_cnt*modinv(3,MOD)
        ab_cnt += a_cnt*pow(3,all_hatena-1,MOD)
        if all_hatena >= 2: ab_cnt += hatena_cnt*pow(3,all_hatena-2,MOD)
        hatena_cnt += 1
    ab_cnt%=MOD
    ans%=MOD
print(ans)

Submission status: Accepted

Solution code:
def modinv(a,m):
    b, u, v = m, 1, 0
    while b:
        t = a//b
        a -= t*b
        a,b = b,a
        u -= t * v
        u,v = v,u
    u %= m
    return u

s=input()
all_hatena = s.count('?')

a_cnt = 0
ab_cnt = 0
hatena_cnt = 0
ans = 0

MOD = 10**9+7
for si in s:
    if si == 'A':
        a_cnt += 1
    elif si == 'B':
        ab_cnt += a_cnt*pow(3,all_hatena,MOD)
        if all_hatena >= 1:
            ab_cnt += hatena_cnt*pow(3,all_hatena-1,MOD)
    elif si == 'C':
        ans += ab_cnt
    else:
        ans += ab_cnt*modinv(3,MOD)
        ab_cnt += a_cnt*pow(3,all_hatena-1,MOD)
        if all_hatena >= 2:
            ab_cnt += hatena_cnt*pow(3,all_hatena-2,MOD)
        hatena_cnt += 1
    ab_cnt%=MOD
    ans%=MOD
    # print(a_cnt,ab_cnt,ans)
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**7)
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

S = [0] + LS2()
n = len(S)
mod = 10**9+7

a,c,d = [0]*(n+1),[0]*(n+1),[0]*(n+1)
for i in range(1,n):
    a[i] = a[i-1]
    c[i] = c[i-1]
    d[i] = d[i-1]
    if S[i] == 'A':
        a[i] += 1
    elif S[i] == 'C':
        c[i] += 1
    elif S[i] == '?':
        d[i] += 1

X = [1]
for _ in range(n):
    X.append((X[-1]*3) % mod)

ans = 0
for i in range(1,n):
    if S[i] == 'B':
        ans += a[i-1]*(c[n-1]-c[i])*X[max(d[n-1],0)]
        ans %= mod
        ans += a[i-1]*(d[n-1]-d[i])*X[max(d[n-1]-1,0)]
        ans %= mod
        ans += d[i-1]*(c[n-1]-c[i])*X[max(d[n-1]-1,0)]
        ans %= mod
        ans += d[i-1]*(d[n-1]-d[i])*X[max(d[n-1]-2,0)]
        ans %= mod
    elif S[i] == '?':
        ans += a[i-1]*(c[n-1]-c[i])*X[max(d[n-1]-1,0)]
        ans %= mod
        ans += a[i-1]*(d[n-1]-d[i])*X[max(d[n-1]-2,0)]
        ans %= mod
        ans += d[i-1]*(c[n-1]-c[i])*X[max(d[n-1]-2,0)]
        ans %= mod
        ans += d[i-1]*(d[n-1]-d[i])*X[max(d[n-1]-3,0)]
        ans %= mod

print(ans)

Submission status: Accepted

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


def main():
    S = input()
    N = len(S)
    m = 10**9 + 7
    # dp[i][j]:= 先頭からi-1文字目までみてABCのうちj文字目まで選んでいた時の残りの処理の個数
    dp = [[0]*4 for _ in range(N+1)]
    for i in range(N,-1,-1):
        for j in range(3,-1,-1):
            # print(i,j)
            if i == N:
                if j == 3:
                    # print(i,j)
                    dp[i][j] = 1
                else:
                    dp[i][j] = 0
            else:
                if S[i] == '?':
                    dp[i][j] = dp[i+1][j] * 3 % m
                else:
                    dp[i][j] = dp[i+1][j]
                
                if j < 3:# S[i]文字を選択する場合
                    if S[i] == '?' or S[i] == 'ABC'[j]:
                        dp[i][j] += dp[i+1][j+1]
                        dp[i][j] %= m

    print(dp[0][0])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
s = str(input());MOD = pow(10,9)+7
n = len(s)
dp = [[0,0,0,0]  for _ in range(n+1)]
#i番目まで見て、(x,a,ab,abc)で終わる個数。
dp[0][0] = 1
for i in range(n):
  if s[i] == "A":
    dp[i+1][0] = dp[i][0]
    dp[i+1][1] = dp[i][0]+dp[i][1]
    dp[i+1][2] = dp[i][2]
    dp[i+1][3] = dp[i][3]
  if s[i] == "B":
    dp[i+1][0] = dp[i][0]
    dp[i+1][1] = dp[i][1]
    dp[i+1][2] = dp[i][2]+dp[i][1]
    dp[i+1][3] = dp[i][3]
  if s[i] == "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]
  if s[i] == "?":
    dp[i+1][0] = dp[i][0]*3
    dp[i+1][1] = dp[i][1]*3+dp[i][0]
    dp[i+1][2] = dp[i][2]*3+dp[i][1]
    dp[i+1][3] = dp[i][3]*3+dp[i][2]
  for j in range(4):
    dp[i+1][j] %= MOD
    
ans = dp[n][3]
#print(dp)
print(ans)

Submission status: Accepted

Solution code:
mod=10**9+7
s=input()
n=len(s)
dp=[[0]*4 for _ in range(n+1)]
dp[0][0]=1
for i in range(1,n+1):
    dp[i][0]=dp[i-1][0]*((s[i-1]=="?")*2+1)
    dp[i][1]=dp[i-1][1]*((s[i-1]=="?")*2+1)
    dp[i][2]=dp[i-1][2]*((s[i-1]=="?")*2+1)
    dp[i][3]=dp[i-1][3]*((s[i-1]=="?")*2+1)
    if s[i-1]=="A" or s[i-1]=="?":
        dp[i][1]+=dp[i-1][0]
    if s[i-1]=="B" or s[i-1]=="?":
        dp[i][2]+=dp[i-1][1]
    if s[i-1]=="C" or s[i-1]=="?":
        dp[i][3]+=dp[i-1][2]
    dp[i][0]%=mod
    dp[i][1]%=mod
    dp[i][2]%=mod
    dp[i][3]%=mod
print(dp[n][3])

Submission status: Accepted

Solution code:
S = input()

MOD = 10 ** 9 + 7
dp, dp_a, dp_ab, dp_abc = 1, 0, 0, 0

for s in S:
    if s == 'A':
        dp_a += dp
    elif s == 'B':
        dp_ab += dp_a
    elif s == 'C':
        dp_abc += dp_ab
    else:
        dp, dp_a, dp_ab, dp_abc = dp * 3, dp_a * 3 + dp, dp_ab * 3 + dp_a, dp_abc * 3 + dp_ab
    dp %= MOD
    dp_a %= MOD
    dp_ab %= MOD
    dp_abc %= MOD
print(dp_abc)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()


def main():
	s=RD()
	n=len(s)

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


	for i,ss in enumerate(s):
		if s[i]=="A":
			dp[i+1][0]=dp[i][0]
			dp[i+1][1]=dp[i][0]+dp[i][1]
			dp[i+1][2]=dp[i][2]
			dp[i+1][3]=dp[i][3]
		elif s[i]=="B":
			dp[i+1][0]=dp[i][0]
			dp[i+1][1]=dp[i][1]
			dp[i+1][2]=dp[i][1]+dp[i][2]
			dp[i+1][3]=dp[i][3]
		elif s[i]=="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][2]+dp[i][3]
		else:
			dp[i+1][0]=dp[i][0]*3
			dp[i+1][1]=dp[i][0]+dp[i][1]*3
			dp[i+1][2]=dp[i][1]+dp[i][2]*3
			dp[i+1][3]=dp[i][2]+dp[i][3]*3

		for j in range(4):
			dp[i+1][j]%=10**9+7


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











if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
# def C(n, r ,mod=10**9+7):
#     if n-r<r: r=n-r
#     if r == 0: return 1
#     if r == 1: return n
# 
#     numerator = [n - r + k + 1 for k in range(r)]
#     denominator = [k + 1 for k in range(r)]
# 
#     for p in range(2,r+1):
#         pivot = denominator[p - 1]
#         if pivot > 1:
#             offset = (n - r) % p
#             for k in range(p-1,r,p):
#                 numerator[k - offset] /= pivot
#                 denominator[k] /= pivot
# 
#     result = 1
#     for k in range(r):
#         if numerator[k] > 1:
#             result *= int(numerator[k]) %mod
# 
#     return result % mod

A=list(input())
n=len(A)
mod=10**9+7
ans=0
numa= A[0]=="A" 
numa_= A[0]=="?"
numc=A[2:].count("C")
numc_= A[2:].count("?")

for i in range(1,n-1):
    #print(numa,numa_,numc,numc_)
    apro=cpro=0
    if A[i]=="B" or A[i]=="?":
        # for k in range(numa_+1):
        #     apro+= (((C(numa_,k)*pow(2,numa_-k,mod))%mod)*(numa+k))%mod
        # for k in range(numc_+1):
        #     cpro+= (((C(numc_,k)*pow(2,numc_-k,mod))%mod)*(numc+k))%mod
        #print(apro,cpro)
        apro= ((3*numa+numa_)*pow(3,(numa_-1),mod))%mod
        cpro= ((3*numc+numc_)*pow(3,(numc_-1),mod))%mod
        ans+= (apro*cpro)%mod
        ans%=mod
    if A[i] == "A":
        numa+=1
    if A[i]=="?":
        numa_+=1
    if A[i+1] =="C":
        numc-=1
    if A[i+1]=="?":
        numc_-=1
print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9 +7
S = input().rstrip()
A = 0
B = 0
C = 0
X = 1
for s in S:
    if s=="?":
        C=B + C*3
        B=A + B*3
        A=X + A*3
        X *= 3
    else:
        if s=="A":
            A+=X
        if s=="B":
            B+=A
        if s =="C":
            C+=B
    X %= MOD
    A %= MOD
    B %= MOD
    C %= MOD
print(C)

Submission status: Accepted

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

dp0 = 1 # ''
dp1 = 0 # 'a'
dp2 = 0 # 'ab'
dp3 = 0 # 'abc'

for c in S:
    if c == 'A':
        dp1 = (dp0+dp1)%MOD
    elif c == 'B':
        dp2 = (dp1+dp2)%MOD
    elif c == 'C':
        dp3 = (dp2+dp3)%MOD
    else:
        dp3 = (dp3*3+dp2)%MOD
        dp2 = (dp2*3+dp1)%MOD
        dp1 = (dp1*3+dp0)%MOD
        dp0 = (dp0*3)%MOD
print(dp3)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
S = input()
res = 0
dp0 = 1 # ''
dp1 = 0 # 'a'
dp2 = 0 # 'ab'
dp3 = 0 # 'abc'

for c in S:
    if c == 'A':
        dp1 = (dp0+dp1)%MOD
    elif c == 'B':
        dp2 = (dp1+dp2)%MOD
    elif c == 'C':
        dp3 = (dp2+dp3)%MOD
    else:
        dp3 = (dp3*3+dp2)%MOD
        dp2 = (dp2*3+dp1)%MOD
        dp1 = (dp1*3+dp0)%MOD
        dp0 = (dp0*3)%MOD
print(dp3)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
S = input()
res = 0
dp0 = 1 # ''
dp1 = 0 # 'a'
dp2 = 0 # 'ab'
dp3 = 0 # 'abc'

for c in S:
    if c == 'A':
        dp1 += dp0
    elif c == 'B':
        dp2 += dp1
    elif c == 'C':
        dp3 += dp2
    else:
        dp0,dp1,dp2,dp3 = dp0*3,dp1*3+dp0,dp2*3+dp1,dp3*3+dp2
    dp0 %= MOD
    dp1 %= MOD
    dp2 %= MOD
    dp3 %= MOD
print(dp3)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
S = input()
res = 0
dpn = 1
dp0 = 0 # a
dp1 = 0 # ab

for c in S:
    if c == 'A':
        dp0 += dpn
    elif c == 'B':
        dp1 += dp0
    elif c == 'C':
        res += dp1
    else:
        dp0,dp1,res = dp0*3+dpn,dp1*3+dp0,res*3+dp1
        dpn *= 3
    dpn %= MOD
    dp0 %= MOD
    dp1 %= MOD
    res %= MOD
print(res)

Submission status: Accepted

Solution code:
S=input()
N=len(S)
A=[0]
B=[0]
C=[0]
X=[0]
for i in range(N):
  A.append(A[i])
  B.append(B[i])
  C.append(C[i])
  X.append(X[i])
  if S[i]=='A':
    A[-1]+=1
  elif S[i]=='B':
    B[-1]+=1
  elif S[i]=='C':
    C[-1]+=1
  else:
    X[-1]+=1
P=0
mod=10**9+7
for i in range(N):
  if S[i]=='B':
    P=(P+pow(3,X[N],mod)*A[i]*(C[N]-C[i+1]))%mod
    if X[i]:
      P=(P+pow(3,X[N]-1,mod)*X[i]*(C[N]-C[i+1]))%mod
    if X[N]-X[i+1]:
      P=(P+pow(3,X[N]-1,mod)*A[i]*(X[N]-X[i+1]))%mod
    if X[i] and X[N]-X[i+1]:
      P=(P+pow(3,X[N]-2,mod)*X[i]*(X[N]-X[i+1]))%mod
  if S[i]=='?':
    P=(P+pow(3,X[N]-1,mod)*A[i]*(C[N]-C[i+1]))%mod
    if X[i]:
      P=(P+pow(3,X[N]-2,mod)*X[i]*(C[N]-C[i+1]))%mod
    if X[N]-X[i+1]:
      P=(P+pow(3,X[N]-2,mod)*A[i]*(X[N]-X[i+1]))%mod
    if X[i] and X[N]-X[i+1]:
      P=(P+pow(3,X[N]-3,mod)*X[i]*(X[N]-X[i+1]))%mod
print(P)

Submission status: Accepted

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

s = str(input())

mod = 10**9+7
dp = [[0]*4 for i in range(len(s)+1)]
dp[0][0] = 1
for i in range(1, len(s)+1):
    for j in range(4):
        if s[i-1] == "?":
            dp[i][j] = (dp[i-1][j]*3) % mod
        else:
            dp[i][j] = (dp[i-1][j]) % mod

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

# print(dp)
print(dp[-1][-1] % mod)

Submission status: Accepted

Solution code:
mod=10**9+7
s=list(input())
s=['-']+s
#print(s)
l=len(s)
dp=[[0 for j in range(4)] for i in range(l)]
dp[0][0]=1
for i in range(1,l):
    for j in range(4):
        dp[i][j]=dp[i-1][j]
        if s[i]=='?':
            dp[i][j]*=3;
        if (j  > 0) and (s[i]=='?' or 'ABC'[j-1]==s[i]):
            dp[i][j] += dp[i-1][j-1]
        dp[i][j] %= mod
        
print(dp[-1][3])
#print(dp)

Submission status: Accepted

Solution code:
mod=10**9+7
s=list(input())
s=['-']+s
l=len(s)
dp=[[0 for j in range(4)] for i in range(l)]
dp[0][0]=1
for i in range(1,l):
    for j in range(4):
        dp[i][j]=dp[i-1][j]
        if s[i]=='?':
            dp[i][j]*=3;
        if j and (s[i]=='?' or 'ABC'[j-1]==s[i]):
            dp[i][j]+=dp[i-1][j-1]
        dp[i][j]%=mod
print(dp[-1][3])

Submission status: Accepted

Solution code:
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
from fractions  import gcd
#input=sys.stdin.readline
#import bisect
s=input()
n=len(s)
mod=10**9+7
dp=[[0]*(n+1) for _ in range(4)]
dp[0][0]=1
for i in range(n):
    for j in range(4):
        if s[i]=="?":
            dp[j][i+1]+=dp[j][i]*3
        else:
            dp[j][i+1]+=dp[j][i]
    if s[i]=="A" or s[i]=="?":
        dp[1][i+1]+=dp[0][i]
    if s[i]=="B" or s[i]=="?":
        dp[2][i+1]+=dp[1][i]
    if s[i]=="C" or s[i]=="?":
        dp[3][i+1]+=dp[2][i]
    for j in range(4):
        dp[j][i+1]%=mod
print(dp[3][-1])

Submission status: Accepted

Solution code:
S=input()
MOD=pow(10,9)+7
dp=[0]*4
dp[0]=1
for s in S:
  if s=='A':
    dp[1]+=dp[0]
  elif s=='B':
    dp[2]+=dp[1]
  elif s=='C':
    dp[3]+=dp[2]
  else:
    tmp3=dp[2]
    tmp2=dp[1]
    tmp1=dp[0]
    dp[3]*=3
    dp[3]+=tmp3
    dp[2]*=3
    dp[2]+=tmp2
    dp[1]*=3
    dp[1]+=tmp1
    dp[0]*=3
  dp[3]%=MOD
  dp[2]%=MOD
  dp[1]%=MOD
  dp[0]%=MOD
print(dp[3])