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:
import sys
sys.setrecursionlimit(1000000)
#def input():
#    return sys.stdin.readline()[:-1]

'''
n=int(input())
for i in range(n):
    a[i]=int(input())
    a[i],b[i]=map(int,input().split())
a=[int(x) for x in input().split()]
n,m=map(int,input.split())
from operator import itemgetter
a = [(1, "c", 1), (1, "b", 3), (2, "a", 0), (1, "a", 2)]
print(sorted(a))  # 0 番目の要素でソート、先頭の要素が同じなら 1 番目以降の要素も見る
print(sorted(a, key=itemgetter(0)))  # 0 番目の要素だけでソート
print(sorted(a, key=itemgetter(0, 2)))  # 0 番目と 2 番目の要素でソート
print(sorted(a, key=lambda x: x[0] * x[2]))  # 0 番目の要素 * 2 番目の要素でソート
print(sorted(a, reverse=True))  # 降順にソート
a.sort()  # 破壊的にソート、sorted() よりも高速
try: # エラーキャッチ list index out of range
    for i in range():
        k=b[i]
except IndexError as e:
    print(i)
'''

test_data1 = '''\
A??C
'''

test_data2 = '''\
ACACAC
'''

test_data3 = '''\
????C?????B??????A???????
'''

test_data4 = '''\
?AC?AC
'''
td_num=3

def GetTestData(index):
    if index==1:
        return test_data1
    if index==2:
        return test_data2
    if index==3:
        return test_data3
    if index==4:
        return test_data4
    
if False:
    with open("../test.txt", mode='w') as f:
        f.write(GetTestData(td_num))
    with open("../test.txt") as f:
        # Start Input code ---------------------------------------
        s=f.readline()
        # End Input code ---------------------------------------
else:
    # Start Input code ---------------------------------------
    s=input()
    # End Input code ---------------------------------------
n=len(s)
lc_a=[0]*n
lc_c=[0]*n
lc_w=[0]*n
rc_a=[0]*n
rc_c=[0]*n
rc_w=[0]*n
rc_a0=s.count('A')
rc_c0=s.count('C')
rc_w0=s.count('?')
c_a=0
c_c=0
c_w=0
for i in range(n-1):
    ch=s[i]
    if ch=='A':
        c_a+=1
    if ch=='C':
        c_c+=1        
    if ch=='?':
        c_w+=1
    lc_a[i+1]=c_a
    #lc_c[i+1]=c_c
    lc_w[i+1]=c_w
    #rc_a[i+1]=rc_a[0]-c_a
    rc_c[i]=rc_c0-c_c
    rc_w[i]=rc_w0-c_w
      
ans=0
mo=10**9+7
#mo=2291979612924+1
#print(ans,'n,s=',n,s,'lc(a,w)=',lc_a,lc_w,'rc(c,w)=',rc_c,rc_w)
for i in range(1,n-1):
    ch=s[i]
    if ch=='B' or ch=='?':
        ans+=(lc_a[i]*pow(3,lc_w[i],mo)+pow(3,max(0,lc_w[i]-1),mo)*lc_w[i])*(rc_c[i]*pow(3,rc_w[i],mo)+pow(3,max(0,rc_w[i]-1),mo)*rc_w[i])%mo
    #print('i,ans',i,ans)
#print(ans,'n,s=',n,s,'lc(a,w)=',lc_a,lc_w,'rc(c,w)=',rc_c,rc_w)
print(ans%mo)
#ans=count(0)+2^(count(n)-1)

Submission status: Accepted

Solution code:
S = input()

dp = [[None] * 4 for _ in range(len(S))]
dp.append([0, 0, 0, 1])
next_str = ["A", "B", "C"]
MOD = 10**9 + 7

for i, s in enumerate(reversed(S)):
    i = len(S) - i - 1
    for j in range(4):
        if j == 3:
            if s == "?":
                dp[i][j] = (3 * dp[i + 1][j]) % MOD
            else:
                dp[i][j] = dp[i + 1][j] % MOD
        else:
            if s == "?":
                m_1 = 3
                m_2 = 1
            else:
                m_1 = 1
                if s == next_str[j]:
                    m_2 = 1
                else:
                    m_2 = 0
            dp[i][j] = (m_1 * dp[i + 1][j] + m_2 * dp[i + 1][j + 1]) % MOD


print(dp[0][0])

Submission status: Accepted

Solution code:
S = input()
MOD = 10**9 + 7
SLen = len(S)
targets = "ABC"
dp = [[0 for i in range(SLen + 1)] for _ in range(4)]
dp[0][0] = 1
for i in range(SLen):
    for j in range(4):
        if S[i] == '?':
            if j < 3:
                dp[j + 1][i + 1] = (dp[j + 1][i + 1] + dp[j][i]) % MOD
            dp[j][i + 1] = (dp[j][i + 1] + dp[j][i] * 3) % MOD
        else:
            if j < 3 and S[i] == targets[j]:
                dp[j + 1][i + 1] = (dp[j + 1][i + 1] + dp[j][i]) % MOD
            dp[j][i + 1] = (dp[j][i + 1] + dp[j][i]) % MOD

print(dp[3][SLen])

Submission status: Accepted

Solution code:
s = input()

a = [0] * len(s)
b = [0] * len(s)
c = [0] * len(s)
q = 0
m = 10**9 + 7

if s[0] == "A":
    a[0] = 1
elif s[0] == "?":
    a[0] = 1
    q = 1

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

Submission status: Accepted

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

MOD = 10**9+7

S = input()[:-1]
N = len(S)

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

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

Submission status: Accepted

Solution code:
s = input()

A = [1,0]
AB = 0
ABC = 0
D = 10**9 + 7
for c in s:
    if c == 'A':
        A[1] += A[0]
    elif c == 'B':
        AB += A[1]
    elif c == 'C':
        ABC += AB
    elif c == '?':
        ABC = (((ABC%D) *3)%D + (AB)%D)%D
        AB = (((AB%D) *3)%D + (A[1])%D)%D
        A[1] = (((A[1]%D)*3)%D + A[0]%D)%D
        A[0] = ((A[0]%D) * 3)%D

print(ABC%D)

Submission status: Accepted

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

dp = [0, 0, 0, 0]
dp[0] = 1

for s in S:
    factor = 3 if s == '?' else 1
    for j, c in zip([2, 1, 0], 'CBA'):
        dp[j + 1] = dp[j + 1] * factor % MOD
        if s == c or s == '?':
            dp[j + 1] += dp[j]
    if s == '?':
        dp[0] = (dp[0] * 3) % MOD

ans = dp[-1] % MOD

print(ans)

Submission status: Accepted

Solution code:
def we_love_abc(S: str)->int:
    ABC = 'ABC'
    MOD = 1000000007

    dp = [0, 0, 0, 0]
    dp[3] = 1

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

    return dp[0] % MOD


if __name__ == "__main__":
    S = input()
    ans = we_love_abc(S)
    print(ans)

Submission status: Accepted

Solution code:
a = list(input())

dp = [[0]*3 for i in range(len(a)+1)]

ppp = 1
for i in range(len(a))[::-1]:
	if a[i] == "A":
		dp[i][0] += dp[i+1][0] + dp[i+1][1]
		dp[i][1] += dp[i+1][1]
		dp[i][2] += dp[i+1][2]
	elif a[i] == "B":
		dp[i][0] += dp[i+1][0]
		dp[i][1] += dp[i+1][1] + dp[i+1][2]
		dp[i][2] += dp[i+1][2]
	elif a[i] == "C":
		dp[i][0] += dp[i+1][0]
		dp[i][1] += dp[i+1][1]
		dp[i][2] += dp[i+1][2] + ppp
	else:
		dp[i][0] += 3 * dp[i+1][0] + dp[i+1][1]
		dp[i][1] += 3 * dp[i+1][1] + dp[i+1][2]
		dp[i][2] += 3 * dp[i+1][2] + ppp
		ppp *= 3
		ppp %= 10**9+7
	for j in range(3):
		dp[i][j] %= (10**9 + 7)
print(dp[0][0] % (10**9 + 7))

Submission status: Accepted

Solution code:
S = input()
mod = 10 ** 9 + 7
A, AB, ABC, ALL = 0, 0, 0, 1

for s in S:
    if s == 'A':
        A += ALL
        A %= mod

    if s == 'B':
        AB += A
        AB %= mod

    if s == 'C':
        ABC += AB
        ABC %= mod

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

print(ABC)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))

s = input()
n = len(s)
xc, yc, zc, wc = 1,0,0,0

for c in s:
    if c == "?":
        x = xc*3
        y = xc + yc * 3
        z = yc + zc * 3
        w = zc + wc * 3

    elif c == "A":
        x = xc
        y= yc + xc
        z = zc
        w = wc

    elif c == "B":
        x = xc
        y = yc
        z = zc + yc
        w = wc

    else:
        x = xc
        y = yc
        z = zc
        w = wc + zc

    xc,yc,zc,wc = [cur%1000000007 for cur in [x,y,z,w]]

print(wc)

Submission status: Accepted

Solution code:
s = list(input())
law = 10 ** 9 + 7
l = len(s)
dp = [[0 for _ in range(4)] for _ in range(l+1)]
dp[0][0] = 1
for i in range(l):
    dp[i+1][0] = (1 + 2 * int(s[i] == '?')) * dp[i][0]
    dp[i+1][1] = int(s[i] in ('A', '?')) * dp[i][0] + dp[i][1] * (1 + 2 * int(s[i] == '?'))
    dp[i+1][2] = int(s[i] in ('B', '?')) * dp[i][1] + dp[i][2] * (1 + 2 * int(s[i] == '?'))
    dp[i+1][3] = int(s[i] in ('C', '?')) * dp[i][2] + dp[i][3] * (1 + 2 * int(s[i] == '?'))
    dp[i+1][0] %= law
    dp[i+1][1] %= law
    dp[i+1][2] %= law
    dp[i+1][3] %= law
print(dp[l][3])

Submission status: Accepted

Solution code:
s = input();n = len(s)
dp = [[0 for i in range(4)] for j in range(len(s)+1)]
dp[0][0] = 1;string = ["A","B","C"];num = 10**9+7
for i in range(n):
    for j in range(4):
        m = 0;b = 1
        if '?' == s[i]:b = 3
        if j == 0:
            if '?' == s[i]:dp[i+1][j] = (dp[i][j] * 3)%num
            else:dp[i+1][j] = (dp[i][j])%num
            continue
        if s[i] == string[j-1]or s[i] == '?':m = 1
        dp[i+1][j] = (m*dp[i][j-1] + b*dp[i][j])%num
print(dp[-1][3])

Submission status: Accepted

Solution code:
import numpy as np
mod = 10**9 + 7

s = input()[::-1]
#s = "?"*(10**5)
n = len(s)
DP = [[0]*3 for i in range(n+1)]

power_three = 1

for i, c in enumerate(list(s)):
    for j in range(3):
        if c == "?":
            DP[i+1][j] = 3*DP[i][j] % mod
        else:
            DP[i+1][j] = DP[i][j] % mod
    if c == "C" or c == "?":
        DP[i+1][0] = (DP[i+1][0] + power_three) % mod
    if c == "B" or c == "?":
        DP[i+1][1] = (DP[i+1][1] + DP[i][0]) % mod
    if c == "A" or c == "?":
        DP[i+1][2] = (DP[i+1][2] + DP[i][1]) % mod
    if c == "?":
        power_three = 3*power_three % mod
print(DP[n][2] % mod)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
e,a,b,c=1,0,0,0
p=1000000007
for i in input():
  if i == "A":
    a+=e
  elif i == "B":
    b+=a
  elif i == "C":
    c+=b
  else:
    e,a,b,c = (3*e)%p,(e+3*a)%p,(a+3*b)%p,(b+3*c)%p
print(c%1000000007)

Submission status: Accepted

Solution code:
from functools import reduce
M = 10**9 + 7
S = input()
ans = reduce(
    lambda t, s:
        (t[0], t[1] + t[0], t[2], t[3]) if s == 'A' else
        (t[0], t[1], t[1] + t[2], t[3]) if s == 'B' else
        (t[0], t[1], t[2], t[2] + t[3]) if s == 'C' else
        ((3 * t[0]) % M, (3 * t[1] + t[0]) % M, (3 * t[2] + t[1]) % M, (3 * t[3] + t[2]) % M),
    S,
    (1, 0, 0, 0)
)[3] % M
print(ans)

Submission status: Accepted

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
# N,M = map(int, input().split())

MOD = int(1e9+7)
S = input()

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

dp[0][0] = 1
for e,s in enumerate(S,1):

    dp[e][0] = dp[e-1][0] * (3 if s == "?" else 1)

    if s == "A" or s == "?":
        dp[e][1] += dp[e-1][0] 
    dp[e][1] += dp[e-1][1] * (3 if s == "?" else 1) 

    if s == "B" or s == "?":
        dp[e][2] += dp[e-1][1]
    dp[e][2] += dp[e-1][2] * (3 if s == "?" else 1)

    if s == "C" or s == "?":
        dp[e][3] += dp[e-1][2]
    dp[e][3] += dp[e-1][3] * (3 if s == "?" else 1)


    for i in range(4):
        dp[e][i] %= MOD



    # dp[i,0] = 1
    # dp[i][1] = dp[i-1][0]* if s == "A" or "?"


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

Submission status: Accepted

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
# N,M = map(int, input().split())
S = input()
from collections import defaultdict
from bisect import bisect_left, bisect_right
a = []
b = []
c = []
# a = defaultdict(list)
# b = defaultdict(list)
# c = defaultdict(list)
q = []

for e,s in enumerate(S):
    if s == "A" :
        a.append(e)
    if s == "B" :
        b.append(e)
    if s == "C" :
        c.append(e)
    if s == "?":
        q.append(e)

ans = 0
MOD = int(1e9+7)

for eb in b:
    range_a = bisect_right(a, eb-1)
    # print("eb: {eb}, bisect_right({a}, {eb1}): {bis}".format
            # (eb = eb, a=a, eb1=eb-1, bis=bisect_right(a,eb-1)))
    range_c = len(c) - bisect_left(c, eb+1)
    
    range_cq = len(q) - bisect_left(q, eb+1)
    range_aq = bisect_right(q, eb-1)

    ans += range_a*range_c * pow(3, len(q), MOD) % MOD
    ans %= MOD
    if len(q)>=1:
        ans += range_a*range_cq * pow(3, len(q)-1, MOD)
        ans += range_aq*range_c * pow(3, len(q)-1, MOD)
        ans %= MOD
    if len(q)>=2:
        ans += range_aq*range_cq * pow(3, len(q)-2, MOD)
        ans %= MOD
for eq in q:
    # print("eb: {eb}, bisect_right({a}, {eb1}): {bis}".format
            # (eb = eq, a=a, eb1=eq-1, bis=bisect_right(a,eq-1)))
    range_a = bisect_right(a, eq-1)
    range_c = len(c) - bisect_left(c, eq+1)
    range_cq = len(q) - bisect_left(q, eq+1)
    range_aq = bisect_right(q, eq-1)

    ans += range_a*range_c * pow(3, len(q)-1, MOD)
    ans %= MOD
    if len(q) >= 2:
        ans += range_a*range_cq * pow(3, len(q)-2, MOD)
        ans += range_aq*range_c * pow(3, len(q)-2, MOD)
        ans %= MOD
    if len(q) >= 3:
        ans += range_aq*range_cq * pow(3, len(q)-3, MOD)
        ans %= MOD
    
print(ans % MOD)

Submission status: Accepted

Solution code:
S = input()

a=0
ab=0
ans=0
n=1
m=10**9+7
for s in S:
    if s=='A':
        a+=n
    elif s=='B':
        ab+=a
    elif s=='C':
        ans+=ab
    else:
        ans+=2*ans+ab
        ab+=2*ab+a
        a+=2*a+n
        n*=3
        n%=m
    ans%=m
    ab%=m
    a%=m
print(ans)

Submission status: Accepted

Solution code:
s=input()
a=0
ab=0
abc=0
total=1
mod=10**9+7
for i in range(len(s)):
    if s[i]=='A':
        a+=total
    elif s[i]=='B':
        ab+=a
    elif s[i]=='C':
        abc+=ab
    else:
        abc=3*abc+ab
        ab=3*ab+a
        a=3*a+total
        total*=3
    a%=mod
    ab%=mod
    abc%=mod
    total%=mod
print(abc)

Submission status: Accepted

Solution code:
S = input()
mod = 10**9 + 7
# dp[i+1][j]: S[i]まで見て状態jであるような場合の数
# (状態0): 何も丸をつけてない, (状態1): Aのみに丸をつけている
# (状態2): AとBに丸をつけている, (状態3): A,B,C 全てに丸をつけている
dp = [[0]*4 for i in range(len(S)+1)]
# 文字列を何も見ていない,何も丸をつけていない状態 dp[0][0] = 1 が初期条件
dp[0][0] = 1
for i in range(len(S)):
    if S[i] == "A" or S[i] == "?":
        # S[i]に丸を付けない場合
        for j in range(4):
            dp[i+1][j] += dp[i][j]
        # S[i] の A or ? に丸をつける場合
        dp[i+1][1] += dp[i][0]
    if S[i] == "B" or S[i] == "?":
        # 同様
        for j in range(4):
            dp[i+1][j] += dp[i][j]
        # S[i] の B or ? に丸をつける場合
        dp[i+1][2] += dp[i][1]
    if S[i] == "C" or S[i] == "?":
        # 同様
        for j in range(4):
            dp[i+1][j] += dp[i][j]
        # S[i] の C or ? に丸をつける場合
        dp[i+1][3] += dp[i][2]
    for j in range(4):
        dp[i+1][j] %= mod

# S[len(S)-1]まで見て状態3(全てに丸をつけている)の場合の数 
print(dp[len(S)][3])

Submission status: Accepted

Solution code:
S = input()

a = 0
ab = 0
abc = 0
all = 1
mod = 10**9 + 7

for i in range(len(S)):
    if S[i] == 'A':
        a += all
    elif S[i] == 'B':
        ab += a
    elif S[i] == 'C':
        abc += ab
    elif S[i] == '?':
        abc = 3*abc + ab
        ab = 3*ab + a
        a = 3*a + all
        all *= 3

    a %= mod
    ab %= mod
    abc %= mod
    all %= mod

print(abc)

Submission status: Accepted

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

MOD = 10 ** 9 + 7

S = input()

a, ab, abc = [0] * 3
c = 1

for s in S:
    if s == "A":
        a = (a + c) % MOD
    elif s == "B":
        ab = (ab + a) % MOD
    elif s == "C":
        abc = (abc + ab) % MOD
    elif s == "?":
        abc = (3 * abc + ab) % MOD
        ab = (3 * ab + a) % MOD
        a = (3 * a + c) % MOD
        c = (3 * c) % MOD
print(abc % MOD)

Submission status: Accepted

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

def main():
    S = input()

    N = len(S)

    AC = [0] * N
    CC = [0] * N
    QCA = [0] * N
    QCD = [0] * N

    a = 0
    q = 0
    for i in range(N):
        if S[i] == 'A':
            a += 1
        elif S[i] == '?':
            q += 1
        AC[i] = a
        QCA[i] = q

    c = 0
    q = 0
    for i in range(N - 1, -1, -1):
        if S[i] == 'C':
            c += 1
        elif S[i] == '?':
            q += 1
        CC[i] = c
        QCD[i] = q

    qc = q

    t = 0
    tt = 0
    m = 10 ** 9 + 7

    for i in range(1, N - 1):
        if S[i] == 'B':
            t += AC[i - 1] * CC[i + 1]
            t %= m

    if 1 <= qc:
        t *= 3
        t %= m
        for i in range(1, N - 1):
            if S[i] == 'B':
                t += QCA[i - 1] * CC[i + 1]
                t %= m
                t += AC[i - 1] * QCD[i + 1]
                t %= m
            elif S[i] == '?':
                t += AC[i - 1] * CC[i + 1]
                t %= m

    if 2 <= qc:
        t *= 3
        t %= m
        for i in range(1, N - 1):
            if S[i] == 'B':
                t += QCA[i - 1] * QCD[i + 1]
                t %= m
            elif S[i] == '?':
                t += QCA[i - 1] * CC[i + 1]
                t %= m
                t += AC[i - 1] * QCD[i + 1]
                t %= m

    if 3 <= qc:
        t *= 3
        t %= m
        for i in range(1, N - 1):
            if S[i] == '?':
                t += QCA[i - 1] * QCD[i + 1]
                t %= m

    for i in range(3, qc):
        t *= 3
        t %= m


    print(t)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
S = input().strip()
mod = 10**9+7
a = 0
ab = 0
ans = 0
q = 1
for c in S:
    if c == 'A':
        a += q
    elif c == 'B':
        ab += a
    elif c == 'C':
        ans += ab
    elif c == '?':
        a, ab, ans, q = a*3+q, ab*3+a, ans*3+ab, q*3
    a %= mod
    ab %= mod
    ans %= mod
    q %= mod
print(ans % mod)

Submission status: Accepted

Solution code:
def func(s):
    alpha = [0, 0, 0]
    ques = 0
    nowQues = 1
    ab = 0  # ABの選び方
    count = 0
    for _s in s:
        if _s == "?":
            count *= 3  # 既にabcとなっている場合の数
            count += ab  # 「? == c」とする場合
            ab *= 3
            # ある?(== B)を末尾とするABの選び方は「A+?」か「?+?」
            if ques > 0:
                ab += alpha[0] * nowQues*3  # (3 ** ques)
            else:
                ab += alpha[0]
            # ？の中からaを選ぶ場合
            if ques > 0:
                ab += ques * nowQues  # (3 ** (ques - 1))
            ques += 1
            if ques > 1:
                nowQues *= 3
        elif _s == "A":
            alpha[0] += 1
        elif _s == "B":
            # あるBを末尾とするABの選び方は「A + B」か「? + B」
            if ques > 0:
                ab += alpha[0] * nowQues*3  # (3 ** ques)
            else:
                ab += alpha[0]
            if ques > 0:
                ab += ques * nowQues  # (3 ** (ques - 1))
            alpha[1] += 1
        elif _s == "C":
            # あるCを末尾とするABCの選び方は「bSelect通り」
            count += ab
            alpha[2] += 1
        count %= 10 ** 9 + 7
        ab %= 10 ** 9 + 7
        nowQues %= 10 ** 9 + 7
        # print("{} -> alpha:{} ab:{} count:{}".format(_s, alpha, ab, count))
    return count % (10 ** 9 + 7)


"""
print(func("A??C") == 8)
print(func("ABCBC") == 3)
print(func("????C?????B??????A???????") == 979596887)
def listToString(_list, split=""):
    maped_list = map(str, _list)  # mapで要素すべてを文字列に
    mojiretu = split.join(maped_list)
    return mojiretu
print(func(listToString(["?" for _ in range(10 ** 5)])))
print("finish")
"""
print(func(input()))

Submission status: Accepted

Solution code:
def index(c):return ord(c)-ord('A')+1
s=' '+input()
m=10**9+7
dp=[[0]*4 for _ in range(len(s))]
dp[0][0]=1
for i in range(1,len(s)):
    for j in range(4):
        dp[i][j]=dp[i-1][j]
    if s[i]=='?':
        dp[i][0]=dp[i-1][0]*3%m
        for j in range(1,4):
            dp[i][j]=(dp[i-1][j-1]+dp[i-1][j]*3)%m
    else:
        k=index(s[i])
        dp[i][k]=(dp[i-1][k-1]+dp[i-1][k])%m
print(dp[-1][3])

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7
S = input()
abc = 0
bc = 0
c = 0
q = 0

for i in S[::-1]:
    if i == 'C':
        c = (pow(3, q, mod) + c) % mod
    if i == 'B':
        bc = (bc + c) % mod
    if i == 'A':
        abc = (abc + bc) % mod
    if i == '?':
        abc = (abc * 3 + bc) % mod
        bc = (bc * 3 + c) % mod
        c = (c * 3 + pow(3, q, mod)) % mod
        q += 1
        
print(abc)

Submission status: Accepted

Solution code:
S = input()
mod = 10 ** 9 + 7
abc = 0
bc = 0
c = 0
q = 0

for i in S[::-1]:
    if i == 'A':
        abc = (bc + abc) % mod
        
    if i == 'B':
        bc = (c + bc) % mod
        
    if i == 'C':
        c = (pow(3, q, mod) + c) % mod
        
    if i == '?':
        abc = (bc + abc * 3) % mod
        bc = (c + bc * 3) % mod
        c = (pow(3, q, mod) + c * 3) % mod
        q += 1
        
print(abc)

Submission status: Accepted

Solution code:
S = input()
mod = 10 ** 9 + 7
abc = 0
bc = 0
c = 0
q = 0

for i in S[::-1]:
    if i == 'A':
        abc = (bc + abc) % mod
    if i == 'B':
        bc = (c + bc) % mod
    if i == 'C':
        c = (pow(3, q, mod) + c ) % mod
    if i == '?':
        abc = (abc * 3 + bc) % mod
        bc = (bc * 3 + c) % mod
        c = (pow(3, q, mod) + c * 3) % mod
        q += 1
        
print(int(abc))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
S = input()
mod = 10**9 + 7
N = len(S)
cA = 0
cAB = 0
cABC = 0
total = 1
for i in range(N):
    if S[i] == 'A':
        cA += total
    elif S[i] == 'B':
        cAB += cA
    elif S[i] == 'C':
        cABC += cAB
    else:
        cABC *= 3
        cABC += cAB
        cAB *= 3
        cAB += cA
        cA *= 3
        cA += total
        total *= 3
    cABC %= mod
    cAB %= mod
    cA %= mod
    total %= mod
print(cABC)

Submission status: Accepted

Solution code:
S = input()
mod = 10**9 + 7
N = len(S)
cA = 0
cAB = 0
cABC = 0
all = 1
for i in range(N):
    if S[i] == 'A':
        cA += all
    elif S[i] == 'B':
        cAB += cA
    elif S[i] == 'C':
        cABC += cAB
    else:
        cABC *= 3
        cABC += cAB
        cAB *= 3
        cAB += cA
        cA *= 3
        cA += all
        all *= 3
    cABC %= mod
    cAB %= mod
    cA %= mod
    all %= mod
print(cABC)

Submission status: Accepted

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

for i in range(n, -1, -1):
    for j in range(3, -1, -1):
        if i == n:
            if j == 3:
                dp[j][i] = 1
            else:
                dp[j][i] = 0

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

            if j < 3 and (s[i] == '?' or s[i] == 'ABC'[j]):
                dp[j][i] += dp[j + 1][i + 1]

            dp[j][i] %= mod

print(dp[0][0])

Submission status: Accepted

Solution code:
from collections import Counter
mod = 10**9+7
s = input()
k = 1
a = 0
ab = 0
abc = 0
for c in s:
    if c == "A":
        a += k
    elif c == "B":
        ab += a
    elif c == "C":
        abc += ab
    else:
        abc = 3*abc + ab
        ab = 3*ab + a
        a = 3*a + k
        k *= 3
    a %= mod
    ab %= mod
    abc %= mod
    k %= mod
print(abc%mod)

Submission status: Accepted

Solution code:
S = input()
dp = list()
for i in range(4):
	dp.append([0] * 4)
dp[0][0] = 1
target = "ABC"
modulo = 1000000007
N = len(S)
for i in range(N):
	for j in range(2, -1, -1):
		if target[j] == S[i] or S[i] == '?':
			for k in range(2, -1, -1):
				tark = k + (1 if S[i] == '?' else 0)
				dp[j + 1][tark] += dp[j][k]
				if dp[j + 1][tark] >= modulo:
					dp[j + 1][tark] -= modulo
numquestion = 0
for i in range(N):
	if S[i] == '?':
		numquestion += 1
ans = 0
for i in range(4):
	if dp[3][i] >= 1:
		delta = dp[3][i] * pow(3, numquestion - i, modulo) % modulo
		ans += delta
		ans %= modulo
print(ans)

Submission status: Accepted

Solution code:
s = input()
mod = 10**9 + 7
abc = 0
bc = 0
c = 0
q = 0
for i in s[::-1]:
  if i == "A":
    abc = (abc + bc) % mod
  if i == "B":
    bc = (bc + c) % mod
  if i == "C":
    c = (pow(3,q,mod) + c) % mod
  if i == "?":
    abc = (abc*3 + bc) % mod
    bc = (bc*3 + c) % mod 
    c = (pow(3,q,mod) + c*3) % mod
    q += 1
print(int(abc))

Submission status: Accepted

Solution code:
S = input()

mod = 10 ** 9 + 7
ALL, A, AB, ABC = 1, 0, 0, 0

for s in S:
    if s == 'A':
        A = (A + ALL) % mod
    elif s == 'B':
        AB = (AB + A) % mod
    elif s == 'C':
        ABC = (ABC + AB) % mod
    elif s == '?':
        ABC = (3 * ABC + AB) % mod
        AB = (3 * AB + A) % mod
        A = (3 * A + ALL) % mod
        ALL = 3 * ALL % mod

print(ABC % mod)

Submission status: Accepted

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

l_a = [0] * (n + 1)
l_q = [0] * (n + 1)
r_c = [0] * (n + 1)
r_q = [0] * (n + 1)
total = 0

for i in range(1, n):
    l_a[i] = l_a[i - 1] + (1 if t[i - 1] == 'A' else 0)
    l_q[i] = l_q[i - 1] + (1 if t[i - 1] == '?' else 0)
for i in range(n - 1, 0, -1):
    r_c[i - 1] = r_c[i] + (1 if t[i] == 'C' else 0)
    r_q[i - 1] = r_q[i] + (1 if t[i] == '?' else 0)


pow3mod = [1] * (n+1)
for i in range(n):
    pow3mod[i+1] = pow3mod[i] * 3 % mod

for i in range(n):
    if t[i] in 'B?':
        total += l_a[i] * r_c[i] * pow3mod[l_q[i] + r_q[i]] + \
            l_a[i] * r_q[i] * pow3mod[l_q[i] + r_q[i] - 1] +\
            l_q[i] * r_c[i] * pow3mod[l_q[i] + r_q[i] - 1] +\
            l_q[i] * r_q[i] * pow3mod[l_q[i] + r_q[i] - 2]
        total %= mod
print(int(total))

Submission status: Accepted

Solution code:
S=raw_input()
 
M=10**9+7
 
all=1
abc=0
ab=0
a=0
 
for x in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		abc+=ab
 
	if x=="?":
		abc=abc*3+ab
		ab=ab*3+a
		a= a*3+all
		all*=3
 
	abc%=M
	ab%=M
	a%=M
	all%=M
 
 
print abc%M

Submission status: Accepted

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

S = input()
N = len(S)

nums = [1, 0, 0, 0]

for i in range(0, N):
    s = S[i]
    m = 3 if s == "?" else 1
    a = 1 if s == "A" or s == "?" else 0
    b = 1 if s == "B" or s == "?" else 0
    c = 1 if s == "C" or s == "?" else 0

    n0 = (nums[0] * m) % MOD
    n1 = (nums[1] * m + nums[0] * a) % MOD
    n2 = (nums[2] * m + nums[1] * b) % MOD
    n3 = (nums[3] * m + nums[2] * c) % MOD
    nums = [n0, n1, n2, n3]

print(nums[3] % MOD)

Submission status: Accepted

Solution code:
import gc

MOD = (10 ** 9) + 7

S = input()
N = len(S)

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

dp[0][0] = 1
dp[1][0] = 0
dp[2][0] = 0
dp[3][0] = 0

for i in range(1, N + 1):
    for j in range(4):
        s = S[i - 1]
        m = 3 if s == "?" else 1
        dp[j][i] += m * dp[j][i - 1]
        if j == 1:
            if s == "A" or s == "?":
                dp[j][i] += dp[j - 1][i - 1]
        elif j == 2:
            if s == "B" or s == "?":
                dp[j][i] += dp[j - 1][i - 1]
        elif j == 3:
            if s == "C" or s == "?":
                dp[j][i] += dp[j - 1][i - 1]
        dp[j][i] = dp[j][i] % MOD

print(dp[3][N] % MOD)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

"""
参考：http://tutuz.hateblo.jp/entry/2018/08/06/074104
　　　https://www.hamayanhamayan.com/entry/2018/08/05/232127
・別解
・予め必要なA,C,?の個数は集めておく。
・Bの位置を決めて、4つの選び方パターンを全部数え上げる。
・3べきの計算はpowの第三引数modで高速化
"""

MOD = 10 ** 9 + 7
S = input()

# あるBの位置よりも左にあるAと?の個数
A, LQ = [0] * len(S), [0] * len(S)
for i in range(len(S)-1):
    a = lq = 0
    if S[i] == 'A':
        a += 1
    if S[i] == '?':
        lq += 1
    A[i+1] = A[i] + a
    LQ[i+1] = LQ[i] + lq
# あるBの位置よりも右にあるCと?の個数
C, RQ = [0] * len(S), [0] * len(S)
for i in range(len(S)-1, 0, -1):
    c = rq = 0
    if S[i] == 'C':
        c += 1
    if S[i] == '?':
        rq += 1
    C[i-1] = C[i] + c
    RQ[i-1] = RQ[i] + rq

ans = 0
for i in range(len(S)):
    if S[i] == '?' or S[i] == 'B':
        # (A,B,C) と選ぶ場合(後ろの3べきは使わなかった?の分)
        case1 = (A[i] * C[i] * pow(3, LQ[i] + RQ[i], MOD)) % MOD
        # (A,B,?) と選ぶ場合
        case2 = (A[i] * RQ[i] * pow(3, max(LQ[i] + RQ[i] - 1, 0), MOD)) % MOD
        # (?,B,C) と選ぶ場合
        case3 = (LQ[i] * C[i] * pow(3, max(LQ[i] + RQ[i] - 1, 0), MOD)) % MOD
        # (?,B,?) と選ぶ場合
        case4 = (LQ[i] * RQ[i] * pow(3, max(LQ[i] + RQ[i] - 2, 0), MOD)) % MOD
        # 全部足し合わせてMOD
        ans = (ans + case1 + case2 + case3 + case4) % MOD

print(ans)