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:
# -*- coding: utf-8 -*-

"""
参考：http://tutuz.hateblo.jp/entry/2018/08/06/074104
・別解
・予め必要なA,C,?の個数は集めておく。
・Bの位置を決めて、4つの選び方パターンを全部数え上げる。
"""

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(int(ans))

Submission status: Accepted

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

"""
参考：http://drken1215.hatenablog.com/entry/2018/08/05/224100_1
・文字列DP
・こういう、ちょっと状況込み入ったDPがまだ自分でうまく書けない。
・もっと数こなして経験積まなきゃなー。
"""

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

# 文字列Sのi文字目まで考えたときにABCのj文字目まで照合させた個数
dp = [[0] * 4 for i in range(len(S)+1)]
dp[0][0] = 1

for i in range(len(S)):
    # i文字目でABCカウントを進めない場合(真下に送る分)
    for j in range(4):
        if S[i] == '?':
            dp[i+1][j] = (dp[i+1][j] + dp[i][j] * 3) % MOD
        else:
            dp[i+1][j] = (dp[i+1][j] + dp[i][j]) % MOD
    # i文字目でABCカウントを進める場合(右下に送る分)
    if S[i] == '?' or S[i] == 'A':
        dp[i+1][1] = (dp[i+1][1] + dp[i][0]) % MOD
    if S[i] == '?' or S[i] == 'B':
        dp[i+1][2] = (dp[i+1][2] + dp[i][1]) % MOD
    if S[i] == '?' or S[i] == 'C':
        dp[i+1][3] = (dp[i+1][3] + dp[i][2]) % MOD

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

Submission status: Accepted

Solution code:
s=input()
table=[1]+[0 for _ in range(3)] 
abc='ABC'
mod=10**9+7
for i in range(len(s)):
    if s[i]=='?':
        for j in range(3,0,-1):
            table[j]=(3*table[j]+table[j-1])%mod
        table[0]=3*table[0]%mod
    else:
        for j in range(3):
            if s[i]==abc[j]:
                table[j+1]+=table[j]
#print(table)
print(table[3]%mod)

Submission status: Accepted

Solution code:
s=input()
table=[[0 for _ in range(4)] for _ in range(len(s)+1)]
table[0][0]=1
abc='ABC'
for i in range(len(s)):
    for j in range(4):
        if s[i]=='?' and j!=0:
            table[i+1][j]=(3*table[i][j]+table[i][j-1])%(10**9+7)
        elif s[i]=='?':
            table[i+1][0]=3*table[i][0]%(10**9+7)
        elif s[i]==abc[j-1] and j!=0:
            table[i+1][j]=(table[i][j]+table[i][j-1])%(10**9+7)
        else:
            table[i+1][j]=table[i][j]%(10**9+7)
#print(table)
print(table[i+1][j]%(10**9+7))

Submission status: Accepted

Solution code:
s = list(input())
mod = 1000000007
c = [1] + [0] * 3
for i in s:
    if i == 'A':
        c[1] = (c[1] + c[0]) % mod
    elif i == 'B':
        c[2] = (c[2] + c[1]) % mod
    elif i == 'C':
        c[3] = (c[3] + c[2]) % mod
    else:
        c[3] = (c[3] * 3 + c[2]) % mod
        c[2] = (c[2] * 3 + c[1]) % mod
        c[1] = (c[1] * 3 + c[0]) % mod
        c[0] = c[0] * 3 % mod
print(c[3])

Submission status: Accepted

Solution code:
import numpy as np
s = list(input())
count = np.array([1] + [0] * 3).astype("int64")
for i in s:
    if i == 'A':
        count[1] += count[0]
    elif i == 'B':
        count[2] += count[1]
    elif i == 'C':
        count[3] += count[2]
    else:
        count[3] = count[3] * 3 + count[2]
        count[2] = count[2] * 3 + count[1]
        count[1] = count[1] * 3 + count[0]
        count[0] *= 3
    count %= 1000000007
print(count[3])

Submission status: Accepted

Solution code:
# coding:utf-8

import sys


input = sys.stdin.readline
INF = float('inf')
MOD = 10 ** 9 + 7


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


S = input().rstrip()

na, a, ab, abc = 1, 0, 0, 0
for s in S:
    if s == 'A':
        a = (a + na) % MOD
    if s == 'B':
        ab = (ab + a) % MOD
    if s == 'C':
        abc = (abc + ab) % MOD
    if s == '?':
        # abc, ab, a, naの順で計算しないと値が上書きされる
        abc = (abc * 3 + ab) % MOD
        ab = (ab * 3 + a) % MOD
        a = (a * 3 + na) % MOD
        na = (na * 3) % MOD

print(abc)

Submission status: Accepted

Solution code:
# coding:utf-8

import sys


input = sys.stdin.readline
INF = float('inf')
MOD = 10 ** 9 + 7


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


S = input().rstrip()

dp = [[0] * 4 for _ in range(len(S) + 1)]
dp[0][0] = 1
for i in range(len(S)):
    if S[i] == '?':
        dp[i + 1][0] = (dp[i][0] * 3) % MOD
        dp[i + 1][1] = (dp[i][1] * 3 + dp[i][0]) % MOD
        dp[i + 1][2] = (dp[i][2] * 3 + dp[i][1]) % MOD
        dp[i + 1][3] = (dp[i][3] * 3 + dp[i][2]) % MOD
    else:
        for j in range(4):
            dp[i + 1][j] = dp[i][j]

        if S[i] == 'A':
            dp[i + 1][1] = (dp[i + 1][1] + dp[i][0]) % MOD
        if S[i] == 'B':
            dp[i + 1][2] = (dp[i + 1][2] + dp[i][1]) % MOD
        if S[i] == 'C':
            dp[i + 1][3] = (dp[i + 1][3] + dp[i][2]) % MOD

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

Submission status: Accepted

Solution code:
# coding:utf-8

import sys


input = sys.stdin.readline
INF = float('inf')
MOD = 10 ** 9 + 7


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


S = input().rstrip()

dp = [[0] * 4 for _ in range(len(S) + 1)]
dp[0][0] = 1
# print(' ', dp[0][:])
for i in range(len(S)):
    # ABCカウントを更新しない
    for j in range(4):
        if S[i] != '?':
            dp[i + 1][j] += dp[i][j]
        else:
            dp[i + 1][j] += dp[i][j] * 3

        dp[i + 1][j] %= MOD

    # ABCカウントを更新する
    if S[i] in ('A', '?'): dp[i + 1][1] += dp[i][0]
    if S[i] in ('B', '?'): dp[i + 1][2] += dp[i][1]
    if S[i] in ('C', '?'): dp[i + 1][3] += dp[i][2]

    for j in range(1, 4):
        dp[i + 1][j] %= MOD

    # print(S[i], dp[i + 1][:])

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

Submission status: Accepted

Solution code:
S = input()

dp = [(-1,-1,-1,-1)] * (len(S) + 1)
dp[0] = (1,0,0,0)
for i in range(len(S)):
    w, x, y, z = dp[i]
    if S[i] == "A":
        x += w
    elif S[i] == "B":
        y += x
    elif S[i] == "C":
        z += y
    else:
        z = 3 * z + y
        y = 3 * y + x
        x = 3 * x + w
        w = 3 * w
    w = w % 1000000007
    x = x % 1000000007
    y = y % 1000000007
    z = z % 1000000007
    dp[i + 1] = (w, x, y, z)

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

Submission status: Accepted

Solution code:
def calc_ABC(a, c, bq, aq):
    ans = 0
    if aq != 0:
        if bq != 0:
            ans = ans + (a*pow(3, bq, MOD) + bq*pow(3, bq-1, MOD)) \
                 * (c*pow(3, aq, MOD) + aq*pow(3, (aq-1), MOD))
        else:
            ans = ans + (a*pow(3, bq, MOD)) \
                 * (c*pow(3, aq, MOD) + aq*pow(3, (aq-1), MOD))
    else:
        if bq != 0:
            ans = ans + (a*pow(3, bq, MOD) + bq*pow(3, bq-1, MOD)) \
                 * (c*pow(3, aq, MOD))
        else:
            ans = ans + (a*pow(3, bq, MOD)) \
                 * (c*pow(3, aq, MOD))
    return ans % MOD


MOD = 10**9 + 7
S = input()
ans = 0
count_a = 0
count_c = S.count('C')
count_afterq = S.count('?')
count_beforeq = 0

for i in range(len(S)):
    if S[i] == 'A':
        count_a += 1
    elif S[i] == 'B':
        ans += calc_ABC(count_a, count_c, count_beforeq, count_afterq)
        ans = ans % MOD
    elif S[i] == 'C':
        count_c -= 1
    elif S[i] == '?':
        count_afterq -= 1
        ans += calc_ABC(count_a, count_c, count_beforeq, count_afterq)
        ans = ans % MOD
        count_beforeq += 1
print(ans)

Submission status: Accepted

Solution code:
S = input()
strs = list(S)

m = {}
l_s = len(strs)

for i in range(l_s+1):
    m[i] = {}
    for j in range(4):
        m[i][j] = 0

m[l_s][3] = 1

mod = 10**9+7
for i in range(l_s)[::-1]:
    s = strs[i]
    for j in range(4):
        m[i][j] = m[i+1][j]
    if s == 'A':
        m[i][0] += m[i+1][1]
    elif s == 'B':
        m[i][1] += m[i+1][2]
    elif s == 'C':
        m[i][2] += m[i+1][3]
    else:
        m[i][0] = m[i+1][0] * 3 + m[i+1][1]
        m[i][1] = m[i+1][1] * 3 + m[i+1][2]
        m[i][2] = m[i+1][2] * 3 + m[i+1][3]
        m[i][3] *= 3
    for j in range(4):
        m[i][j] = m[i][j] % mod
print(m[0][0] % mod)

Submission status: Accepted

Solution code:
MOD = 1000000007

S = input()

a, ab, abc, all_s = 0, 0, 0, 1

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

print(abc)

Submission status: Accepted

Solution code:
mod = int(1e9) + 7


def main():
    S = input()
    a_sum = 0
    ab_sum = 0
    abc_sum = 0
    pattern = 1
    for i in range(len(S)):
        s = S[i]
        if s == "A":
            a_sum = (a_sum + pattern) % mod
        if s == "B":
            ab_sum = (ab_sum + a_sum) % mod
        if s == "C":
            abc_sum = (abc_sum + ab_sum) % mod
        if s == "?":
            abc_sum = (abc_sum * 3 + ab_sum) % mod
            ab_sum = (ab_sum * 3 + a_sum) % mod
            a_sum = (a_sum * 3 + pattern) % mod
            pattern = pattern * 3 % mod
    print(abc_sum)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from pprint import pprint

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

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

dp[len(S)][0] = 0
dp[len(S)][1] = 0
dp[len(S)][2] = 0
dp[len(S)][3] = 1

for i in reversed( range(len(S))):
    dp[i][0] = dp[i+1][0]
    if S[i] == 'C':
        dp[i][3] = dp[i+1][3]
        dp[i][2] = dp[i+1][2] + dp[i+1][3]
        dp[i][1] = dp[i+1][1] 
        dp[i][0] = dp[i+1][0]
    elif S[i] == 'B':
        dp[i][3] = dp[i+1][3]
        dp[i][2] = dp[i+1][2]
        dp[i][1] = dp[i+1][1] + dp[i+1][2]
        dp[i][0] = dp[i+1][0]
    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]
    elif S[i] == '?':
        dp[i][3] = 3*dp[i+1][3]
        dp[i][2] = 3*dp[i+1][2] + dp[i+1][3]
        dp[i][1] = 3*dp[i+1][1] + dp[i+1][2]
        dp[i][0] = 3*dp[i+1][0] + dp[i+1][1]

    dp[i][3] %= MOD
    dp[i][2] %= MOD
    dp[i][1] %= MOD
    dp[i][0] %= MOD


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

Submission status: Accepted

Solution code:
S=input()
N=len(S)
O=1
A=[0]*(N+1)
AB=[0]*(N+1)
ABC=[0]*(N+1)
for i in range(1,N+1):
  A[i]=A[i-1]
  AB[i]=AB[i-1]
  ABC[i]=ABC[i-1]
  if S[i-1] is "A":
    A[i]+=O
  elif S[i-1] is "B":
    AB[i]+=A[i-1]
  elif S[i-1] is "C":
    ABC[i]+=AB[i-1]
  elif S[i-1] is "?":
    A[i]*=3
    A[i]+=O
    AB[i]*=3
    AB[i]+=A[i-1]
    ABC[i]*=3
    ABC[i]+=AB[i-1]
    O*=3
  A[i]=A[i]%(10**9+7)
  AB[i]=AB[i]%(10**9+7)
  ABC[i]=ABC[i]%(10**9+7)
  O=O%(10**9+7)
print(int(ABC[N]%(10**9+7)))

Submission status: Accepted

Solution code:
s = input()
MOD = 10 ** 9 + 7
n = len(s)
ABC = 'ABC'

dp = [[0] * 4 for i in range(n + 1)]
for i in range(n, -1, -1):
    for j in range(3, -1, -1):
        if i == n:
            if j == 3:
                dp[i][j] = 1
            else:
                dp[i][j] = 0
        else:
            if s[i] == '?':
                dp[i][j] = 3 * dp[i+1][j]
            else:
                dp[i][j] = dp[i+1][j]
            if j < 3 and (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:
Mod = 10**9+7
S = input()
N = len(S)
O = 1
A = [0]*N
AB = [0]*N
ABC = [0]*N

for i in range(N):
    A[i] = A[i-1]
    AB[i] = AB[i-1]
    ABC[i] = ABC[i-1]
    if S[i] == 'A':
        A[i] += O
    if S[i] == 'B':
        AB[i] += A[i-1]
    if S[i] == 'C':
        ABC[i] += AB[i-1]
    if S[i] == '?':
        A[i] *= 3
        A[i] += O
        AB[i] *= 3
        AB[i] += A[i-1]
        ABC[i] *= 3
        ABC[i] += AB[i-1]
        O *= 3
    A[i] %= Mod
    AB[i] %= Mod
    ABC[i] %= Mod
    O %= Mod
print(ABC[-1])

Submission status: Accepted

Solution code:
if __name__ == "__main__":
    modulus = 10 ** 9 + 7
    s = input()
    n = len(s)
    dp = [[0] * 4 for _ in range(n + 1)]

    for i in range(n + 1)[::-1]:
        for j in range(4)[::-1]:
            if i == n:
                if j == 3:
                    dp[i][j] = 1
                else:
                    dp[i][j] = 0
            else:
                is_wildcard = s[i] == '?'
                if j == 3:
                    m = 3 if is_wildcard else 1
                    dp[i][j] = m * dp[i + 1][3] % modulus

                else:
                    m1 = 3 if is_wildcard else 1
                    m2 = 1 if is_wildcard or s[i] == 'ABC'[j] else 0

                    dp[i][j] = (m1 * dp[i + 1][j] + m2 * dp[i + 1][j + 1]) % modulus
            # print(i, j, dp[i][j])
    print(dp[0][0])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
s=input()
len_s=len(s)
dp=[[0]*((len_s)+1) for _ in range(4)]
dp[0][0]=1

for j in range(1,len_s+1):
    if(s[j-1]=="?"):
        dp[0][j]=3*dp[0][j-1]
    else:
        dp[0][j]=dp[0][j-1]
    
    if(s[j-1]=="?"):
        dp[1][j]=dp[0][j-1] + 3*dp[1][j-1]
    elif(s[j-1]=="A"):
        dp[1][j]=dp[0][j-1] + dp[1][j-1]
    else:
        dp[1][j]=dp[1][j-1]

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

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

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

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

Submission status: Accepted

Solution code:
S = input()

ZABC = [[0 for i in range(4)] for j in range(len(S))]
if S[0] == '?':  
    ZABC[0][0] = 3
else:
    ZABC[0][0] = 1
if S[0] == '?' or S[0] == 'A':  
    ZABC[0][1] = 1
else:
    ZABC[0][1] = 0
for i in range(2):
    ZABC[0][i+2] = 0

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

Submission status: Accepted

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

for s in S:
    if s == "A":
        A = (A + ALL) % mod

    if s == "B":
        AB = (AB + A) % mod

    if s == "C":
        ABC = (ABC + AB) % mod

    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:
# -*- coding: utf-8 -*-
from sys import stdin

s_in = lambda: stdin.readline()[:-1] # s = s_in()
d_in = lambda: int(stdin.readline()) # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split())) # List = ds_in()

S = s_in()
Mod = 10**9 + 7

dp = [0] * 4 # [*, A, B, C]
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:
        temp = dp.copy()
        for i in range(4):
            dp[i] *= 3
        dp[1] += temp[0]
        dp[2] += temp[1]
        dp[3] += temp[2]
    for i in range(4):
        dp[i] %= Mod

print(dp[3])

Submission status: Accepted

Solution code:
s = input()

MOD = 10 ** 9 + 7

# dp[0 .. len(s)][0..3] = その状態の数
dp = [[0 for _ in range(3 + 1)] for _ in range(len(s) + 1)]
dp[0][0] = 1

for i in range(1, len(s) + 1):
    # s[i]を取らない
    dp[i][0] += dp[i - 1][0] * (3 if s[i - 1] == '?' else 1)
    dp[i][1] += dp[i - 1][1] * (3 if s[i - 1] == '?' else 1)
    dp[i][2] += dp[i - 1][2] * (3 if s[i - 1] == '?' else 1)
    dp[i][3] += dp[i - 1][3] * (3 if s[i - 1] == '?' else 1)

    # s[i]を取る
    if s[i - 1] == 'A':
        dp[i][1] += dp[i - 1][0]
    elif s[i - 1] == 'B':
        dp[i][2] += dp[i - 1][1]
    elif s[i - 1] == 'C':
        dp[i][3] += dp[i - 1][2]
    elif s[i - 1] == '?':
        dp[i][1] += dp[i - 1][0]
        dp[i][2] += dp[i - 1][1]
        dp[i][3] += dp[i - 1][2]

    for j in range(3 + 1):
        dp[i][j] %= MOD

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

Submission status: Accepted

Solution code:
# coding:utf-8

INF = float('inf')
MOD = 10 ** 9 + 7


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


S = input()

A = [-INF for _ in range(len(S))]
C = A[:]
Q = A[:]

A[0] = 1 if S[0] == 'A' else 0
C[0] = 1 if S[0] == 'C' else 0
Q[0] = 1 if S[0] == '?' else 0

for i in range(1, len(S)):
    A[i] = A[i - 1] + 1 if S[i] == 'A' else A[i - 1]
    C[i] = C[i - 1] + 1 if S[i] == 'C' else C[i - 1]
    Q[i] = Q[i - 1] + 1 if S[i] == '?' else Q[i - 1]

# TLEになるので3^X%MODを予め計算
pow_three = [1]
for i in range(Q[-1]):
    tmp = pow_three[-1] * 3
    tmp %= MOD
    pow_three.append(tmp)

ans = 0
for i in range(1, len(S) - 1):
    if S[i] == 'A' or S[i] == 'C':
        continue

    # A, B, Cの個数
    tmp = Q[i - 1] + Q[-1] - Q[i]
    if tmp < 0: tmp = 0
    ans += A[i - 1] * (C[-1] - C[i]) * pow_three[tmp]
    # ?, B, Cの個数
    tmp = Q[i - 1] - 1 + Q[-1] - Q[i]
    if tmp < 0: tmp = 0
    ans += Q[i - 1] * (C[-1] - C[i]) * pow_three[tmp]
    # A, B, ?の個数
    tmp = Q[i - 1] + Q[-1] - Q[i] - 1
    if tmp < 0: tmp = 0
    ans += A[i - 1] * (Q[-1] - Q[i]) * pow_three[tmp]
    # ?, B, ?の個数
    tmp = Q[i - 1] + Q[-1] - Q[i] - 2
    if tmp < 0: tmp = 0
    ans += Q[i - 1] * (Q[-1] - Q[i]) * pow_three[tmp]

    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
# coding:utf-8

INF = float('inf')
MOD = 10 ** 9 + 7


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


# aのp乗を求めるアルゴリズム
# MOD版
def pow_mod(a, p):
    if p == 0: return 1
    if p < 0: return 0

    if p % 2 == 0:
        half_p = p // 2
        half = pow_mod(a, half_p)
        return half * half % MOD
    else:
        return a * pow_mod(a, p - 1) % MOD


S = input()

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

A = [-INF for _ in range(len(S))]
C = A[:]
Q = A[:]

A[0] = 1 if S[0] == 'A' else 0
C[0] = 1 if S[0] == 'C' else 0
Q[0] = 1 if S[0] == '?' else 0

for i in range(1, len(S)):
    A[i] = A[i - 1] + 1 if S[i] == 'A' else A[i - 1]
    C[i] = C[i - 1] + 1 if S[i] == 'C' else C[i - 1]
    Q[i] = Q[i - 1] + 1 if S[i] == '?' else Q[i - 1]

pow_three = [1]
for i in range(Q[-1]):
    tmp = pow_three[-1] * 3
    tmp %= MOD
    pow_three.append(tmp)

ans = 0
for i in range(1, len(S) - 1):
    if S[i] == 'A' or S[i] == 'C':
        continue

    # A, B, Cの個数
    tmp = Q[i - 1] + Q[-1] - Q[i]
    if tmp < 0: tmp = 0
    ans += A[i - 1] * (C[-1] - C[i]) * pow_three[tmp]
    # ?, B, Cの個数
    tmp = Q[i - 1] - 1 + Q[-1] - Q[i]
    if tmp < 0: tmp = 0
    ans += Q[i - 1] * (C[-1] - C[i]) * pow_three[tmp]
    # A, B, ?の個数
    tmp = Q[i - 1] + Q[-1] - Q[i] - 1
    if tmp < 0: tmp = 0
    ans += A[i - 1] * (Q[-1] - Q[i]) * pow_three[tmp]
    # ?, B, ?の個数
    tmp = Q[i - 1] + Q[-1] - Q[i] - 2
    if tmp < 0: tmp = 0
    ans += Q[i - 1] * (Q[-1] - Q[i]) * pow_three[tmp]

    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
MOD=10**9+7
def func(s):
    abc="ABC"
    n = len(s)
    dp=[[0 for _ in range(3+1)] for _ in range(n+1)]
    dp[n][3]=1

    for i in range(n-1,-1,-1):
        for j in range(3,-1,-1):
            if j==3:
                if s[i]=='?':
                    dp[i][j]=(dp[i+1][j]*3)%MOD
                else:
                    dp[i][j]=dp[i+1][j]
            else:
                m1=3 if s[i]=='?' else 1
                m2=1 if s[i]=='?' or s[i]==abc[j] else 0
                dp[i][j]=((m1*dp[i+1][j])%MOD +(m2*dp[i+1][j+1])%MOD)%MOD
    return dp[0][0]
print(func(input()))

Submission status: Accepted

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

MOD = 10**9 + 7

def func(s):
    abc = "ABC"
    n = len(s)
    dp =[[0 for _ in range(3+1)] for _ in range(n+1)]
    dp[n][3] = 1

    for i in range(n-1,-1,-1):
        for j in range(3,-1,-1):
            if j==3:
                if s[i]=="?":
                    dp[i][j] = (dp[i+1][j]*3)%MOD
                else:
                    dp[i][j] = dp[i+1][j]
            else:
                m1 = 3 if s[i]=="?" else 1
                m2 = 1 if s[i]=="?" or s[i]==abc[j] else 0
                dp[i][j] = ((m1*dp[i+1][j])%MOD + (m2*dp[i+1][j+1])%MOD)%MOD
    return dp[0][0]

class Test(unittest.TestCase):
    def test(self):
        self.assertEqual(func("A??C"), 8)
        self.assertEqual(func("ABCBC"), 3)
        self.assertEqual(func("????C?????B??????A???????"), 979596887
)

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

Submission status: Accepted

Solution code:
t=10**9+7
s=[1,0,0,0]
n=input()
for i in n:
    if i=="?":
        for j in range(3,0,-1):
            s[j]*=3
            s[j]+=s[j-1]
            s[j]%=t
        s[0]*=3
        s[0]%=t
    else:
        j="1ABC".index(i)
        s[j]+=s[j-1]
        s[j]%=t
print(s[3])

Submission status: Accepted

Solution code:
s = input()

dp3 = 1
dp2 = 0
dp1 = 0
dp0 = 0

n = 10 ** 9 + 7

for i in reversed(range((len(s)))):
    if s[i] == '?':
        m = 3
    else:
        m = 1

    if s[i] == '?':
        m1 = 3
    else:
        m1 = 1

    if s[i] == '?' or s[i] == 'C':
        m2 = 1
    else:
        m2 = 0

    if s[i] == '?' or s[i] == 'B':
        m3 = 1
    else:
        m3 = 0

    if s[i] == '?' or s[i] == 'A':
        m4 = 1
    else:
        m4 = 0

    t_dp3 = (m * dp3) % n
    t_dp2 = (m1 * dp2 + m2 * dp3) % n
    t_dp1 = (m1 * dp1 + m3 * dp2) % n
    t_dp0 = (m1 * dp0 + m4 * dp1) % n
    dp3 = t_dp3
    dp2 = t_dp2
    dp1 = t_dp1
    dp0 = t_dp0

ans = dp0
print(ans)

Submission status: Accepted

Solution code:
s = input()

dp = [[0 for _ in range(4)] for _ in range(len(s) + 1)]
dp[len(s)][3] = 1
n = 10 ** 9 + 7

for i in reversed(range((len(s)))):
    m = 1
    m1 = 1
    m2 = 0
    m3 = 0
    m4 = 0
    if s[i] == '?':
        m = 3
        m1 = 3
        m2 = 1
        m3 = 1
        m4 = 1

    if s[i] == 'C':
        m2 = 1

    if s[i] == 'B':
        m3 = 1

    if s[i] == 'A':
        m4 = 1

    dp[i][3] = (m * dp[i+1][3]) % n
    dp[i][2] = (m1 * dp[i+1][2] + m2 * dp[i+1][3]) % n
    dp[i][1] = (m1 * dp[i+1][1] + m3 * dp[i+1][2]) % n
    dp[i][0] = (m1 * dp[i+1][0] + m4 * dp[i+1][1]) % n

ans = dp[0][0]
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

A = np.array([[1,0,0,0], [1,1,0,0], [0,0,1,0], [0,0,0,1]])
B = np.array([[1,0,0,0], [0,1,0,0], [0,1,1,0], [0,0,0,1]])
C = np.array([[1,0,0,0], [0,1,0,0], [0,0,1,0], [0,0,1,1]])
Q = A + B + C

x = np.array([1,0,0,0])

for ch in raw_input().rstrip():
    if ch == 'A':
        x = np.dot(A, x) 
    elif ch == 'B':
        x = np.dot(B, x) 
    elif ch == 'C':
        x = np.dot(C, x) 
    elif ch == '?':
        x = np.dot(Q, x) 

    x %= 1000000007

print x[3]

Submission status: Accepted

Solution code:
S=raw_input()
N=len(S)
mod=10**9+7

num=[ [ 0 for i in range(4) ] for j in range(N) ]		# i=0 A, i=1 B, i=2 C, i=3 ?

for i in range(N):
	if i==0:
		if S[i]=="A":  num[i][0]=1
		elif S[i]=="B":  num[i][1]=1		
		elif S[i]=="C":  num[i][2]=1
		elif S[i]=="?":  num[i][3]=1
	else:
		for j in range(4):
			num[i][j]=num[i-1][j]
			
		if S[i]=="A":  num[i][0]+=1
		elif S[i]=="B":  num[i][1]+=1		
		elif S[i]=="C":  num[i][2]+=1
		elif S[i]=="?":  num[i][3]+=1		

ans=0

for i in range(1,N):
	if S[i]=="B" or S[i]=="?":
		a=num[i-1][0]
		c=num[N-1][2]-num[i][2]
		ql=num[i-1][3]
		qr=num[N-1][3]-num[i][3]

		#ABC
		ans+=a*pow(3,ql,mod)*c*pow(3,qr,mod)

		#AB?
		if qr>0:
			ans+=a*pow(3,ql,mod)*pow(3,(qr-1),mod )*qr

		#?BC
		if ql>0:
			ans+=pow(3,(ql-1),mod )*ql*c*pow(3,qr,mod)

		#?B?
		if ql>0 and qr>0:
			ans+=pow(3,(ql-1),mod )*ql*pow(3,(qr-1),mod )*qr

print ans%mod

Submission status: Accepted

Solution code:
def main():
	s = input()
	md = 10 ** 9 + 7

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

	d_q = {"?":3, "A":1, "B":1, "C":1}
	
	d_abc = [
	{"?":1, "A":1, "B":0, "C":0},
	{"?":1, "A":0, "B":1, "C":0},
	{"?":1, "A":0, "B":0, "C":1},
	]

	for i in reversed(range(0, len(s))):
		dp[i][3] = (dp[i + 1][3] * d_q[s[i]]) % md

	for j in reversed(range(3)):
		dp[len(s) - 1][j] = 0
		for i in reversed(range(0, len(s))):
			dp[i][j] = (dp[i + 1][j] * d_q[s[i]] + dp[i + 1][j + 1] * d_abc[j][s[i]]) % md
		
	print(dp[0][0] % md)

if __name__ == '__main__':
	main()

Submission status: Accepted

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

moji = [[0,0,0,0] for _ in range(n+1)]

for i in range(1,n+1):
    for k in range(4):
        moji[i][k] += moji[i-1][k]
    if s[i-1] == 'A':
        moji[i][0] += 1
        continue
    elif s[i-1] == 'B':
        moji[i][1] += 1
        continue
    elif s[i-1] == 'C':
        moji[i][2] += 1
        continue
    else:
        moji[i][3] += 1

h = s.count('?')
mt = [1]
for i in range(h+1):
    mt.append(mt[-1]*3 % mod)
mt += [1/9,1/3]
ans = 0
for i in range(n):
    al,cr,hl,hr = moji[i][0], moji[n][2]-moji[i+1][2], moji[i][3], moji[n][3]-moji[i+1][3]
    if s[i] == 'B' or s[i] == '?':
        k = (al*3 + hl) * (cr*3 + hr) * mt[hr+hl-2]
        ans += int(k) % mod
print(ans%mod)

Submission status: Accepted

Solution code:
s=input()
l=len(s)
a=[[0,0,0] for i in range(l)]
num=1
for i in range(l):
    if s[i]=='A':
        a[i][0]=a[i-1][0]+1*num
        a[i][1]=a[i-1][1]
        a[i][2]=a[i-1][2]
    elif s[i]=='B':
        a[i][0]=a[i-1][0]
        a[i][1]=a[i-1][1]+a[i-1][0]
        a[i][2]=a[i-1][2]
    elif s[i]=='C':
        a[i][0]=a[i-1][0]
        a[i][1]=a[i-1][1]
        a[i][2]=a[i-1][2]+a[i-1][1]
    elif s[i]=='?':
        
        a[i][0]=a[i-1][0]*3+1*num
        a[i][1]=a[i-1][1]*3+a[i-1][0]
        a[i][2]=a[i-1][2]*3+a[i-1][1]
        
        num=(num*3)%1000000007


    a[i][0]=a[i][0]%1000000007
    a[i][1]=a[i][1]%1000000007
    a[i][2]=a[i][2]%1000000007
print(a[-1][2])

Submission status: Accepted

Solution code:
s=input()
l=len(s)
a=[[0,0,0] for i in range(l)]
num=1
for i in range(l):
    if s[i]=='A':
        a[i][0]=a[i-1][0]+1*num
        a[i][1]=a[i-1][1]
        a[i][2]=a[i-1][2]
    if s[i]=='B':
        a[i][0]=a[i-1][0]
        a[i][1]=a[i-1][1]+a[i-1][0]
        a[i][2]=a[i-1][2]
    if s[i]=='C':
        a[i][0]=a[i-1][0]
        a[i][1]=a[i-1][1]
        a[i][2]=a[i-1][2]+a[i-1][1]
    if s[i]=='?':
        
        a[i][0]=a[i-1][0]*3+1*num
        a[i][1]=a[i-1][1]*3+a[i-1][0]
        a[i][2]=a[i-1][2]*3+a[i-1][1]
        
        num=(num*3)%1000000007


    a[i][0]=a[i][0]%1000000007
    a[i][1]=a[i][1]%1000000007
    a[i][2]=a[i][2]%1000000007
print(a[-1][2])

Submission status: Accepted

Solution code:
mod = 1000000007
s = input()
ans = [0,1,0,0,0]
for c in s:
    if c == "?":
        for i in range(4,0,-1):
            ans[i] *= 3
            ans[i] += ans[i-1]
            ans[i] %= mod
    else:
        i = "00ABC".index(c)
        ans[i] += ans[i-1]
        ans[i] %= mod
print(ans[-1])

Submission status: Accepted

Solution code:
s=input()
dp=[[-1 for _ in range(4)] for _ in range(len(s)+1)]
dp[len(s)][3]=1
for i in range(len(s),-1,-1):
    for j in range(3,-1,-1):
        if j<3:
            dp[len(s)][j]=0
        if i<len(s):
            dp[i][3]=3*dp[i+1][3] if s[i]=='?' else dp[i+1][3]
            dp[i][3]%=1e9+7
        if i<len(s) and j<3:
            m1=3 if s[i]=='?' else 1
            m2=1 if s[i]=='?' or s[i]==list('ABC')[j] else 0
            dp[i][j]=m1*dp[i+1][j]+m2*dp[i+1][j+1]
            dp[i][j]%=1e9+7
print(int(dp[0][0]))