Problem:


Score : 400 points

Problem Statement

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

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

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

T_j = B

T_k = C

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

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

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

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

Constraints

3 ≤ |S| ≤ 10^5

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

Input

Input is given from Standard Input in the following format:

S

Output

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

Sample Input 1

A??C

Sample Output 1

8

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

AAAC: 0

AABC: 2

AACC: 0

ABAC: 1

ABBC: 2

ABCC: 2

ACAC: 0

ACBC: 1

ACCC: 0

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

Sample Input 2

ABCBC

Sample Output 2

3

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

Sample Input 3

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

Sample Output 3

979596887

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



Sample input:
A??C


Sample output:
8

Submission status: Wrong Answer

Solution code:
def main():
    """
    1 <= i < j < k <= |T|
    Ti = A
    Tj = B
    Tk = C
    """
    S = input()
    ans3 = cumsum(S)

    print(ans3)

def cumsum(S):
    """
    考えたときに累積和が浮かんだ
    ABCとあるので
    i文字目までのA相当の数、つまり?も含んだ数
    これをBとCにも適用する
    Aを決め打ちで進めるとBも走査することになる
    Cは定数倍で求められるが、|S|^2: TLE で意味がない

    ここで断念していろいろ調べると
    Bを決め打ちすれば
    A: 0-(B-1)
    C: (B+1)-N
    なのでNでおｋ

    と、思ったがWAと同じ間違いをしている
    3^q パターンをきちんと考える
    """
    n = len(S)
    q = [0 for _ in range(n+1)]
    abc = [[0] * 3 for _ in range(n+1)]
    for i in range(n):
        is_q = S[i] == "?"
        q[i+1] += q[i] + int(is_q)

        # for j, c in enumerate("ABC"):
        #    add = int(is_q or S[i] == c)
        for j, c in enumerate("ABC"):
            if c == "B":
                add = int(is_q or S[i] == c)
            else:
                add = int(S[i] == c)
            abc[i+1][j] += abc[i][j] + add

    ans = 0
    MOD = 10 ** 9 + 7
    for i in range(1, n-1):
        a = abc[i][0]
        b = abc[i+1][1] - abc[i][1]
        c = abc[n][2] - abc[i+1][2]
        l = q[i]
        r = q[n] - q[i+1]

        # WA: ? を無視している
        # ans += a * b * c

        # ABC の作り方
        # AB?: ? 1つをCに割り当てる
        # ?BC: ? 1つをAに割り当てる
        # ?B?: ? 2つをACに割り当てる
        ac = a * b * c * (3 ** (l + r))
        aq = a * b * r * (3 ** (l + r - 1))
        qc = l * b * c * (3 ** (l + r - 1))
        qq = l * b * r * (3 ** (l + r - 2))
        ans += ac + aq + qc + qq
        ans %= MOD

    return ans


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    """
    1 <= i < j < k <= |T|
    Ti = A
    Tj = B
    Tk = C
    """
    S = input()
    ans3 = cumsum(S)

    print(ans3)
    

def cumsum(S):
    """
    考えたときに累積和が浮かんだ
    ABCとあるので
    i文字目までのA相当の数、つまり?も含んだ数
    これをBとCにも適用する
    Aを決め打ちで進めるとBも走査することになる
    Cは定数倍で求められるが、|S|^2: TLE で意味がない

    ここで断念していろいろ調べると
    Bを決め打ちすれば
    A: 0-(B-1)
    C: (B+1)-N
    なのでNでおｋ

    と、思ったがWAと同じ間違いをしている
    3^q パターンをきちんと考える
    """
    n = len(S)
    q = [0 for _ in range(n+1)]
    abc = [[0] * 3 for _ in range(n+1)]
    for i in range(n):
        is_q = S[i] == "?"
        q[i+1] += q[i] + int(is_q)

        # for j, c in enumerate("ABC"):
        #    add = int(is_q or S[i] == c)
        for j, c in enumerate("ABC"):
            if c == "B":
                add = int(is_q or S[i] == c)
            else:
                add = int(S[i] == c)
            abc[i+1][j] += abc[i][j] + add

    ans = 0
    MOD = 10 ** 9 + 7
    for i in range(1, n-1):
        a = abc[i][0]
        b = abc[i+1][1] - abc[i][1]
        c = abc[n][2] - abc[i+1][2]
        l = q[i]
        r = q[n] - q[i+1]

        # WA: ? を無視している
        # ans += a * b * c

        # ABC の作り方
        # AB?: ? 1つをCに割り当てる
        # ?BC: ? 1つをCに割り当てる
        # ?B?: ? 2つをACに割り当てる
        ac = a * b * c * (3 ** (l + r))
        aq = a * b * r * (3 ** (l + r - 1))
        qc = l * b * c * (3 ** (l + r - 1))
        qq = l * b * r * (3 ** (l + r - 2))
        ans += ac + aq + qc + qq
        ans %= MOD

    return ans


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
S=input()
N=len(S)
INF=1e9+7
dp=[[0]*4 for _ in range(N+1)]
dp[0][0]=1
for i in range(N):
    if S[i]=="?":
        for j in range(4):
            dp[i+1][j]+=dp[i][j]*3%INF
    else:
        for j in range(4):
            dp[i+1][j]+=dp[i][j]%INF
    if S[i]=="A" or S[i]=="?":
        dp[i+1][1]+=dp[i][0]%INF
    if S[i]=="B" or S[i]=="?":
        dp[i+1][2]+=dp[i][1]%INF
    if S[i]=="C" or S[i]=="?":
        dp[i+1][3]+=dp[i][2]%INF
print(int(dp[N][3]))

Submission status: Wrong Answer

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

MOD = 1000000007  # type: int


def solve(S: str):
    dp = [[0 for j in range(4)] for i in range(len(S) + 1)]
    STR = "XABC"
    dp[0][0] = 1
    for i in range(len(S)):
        c = S[i]
        for j in range(4):
            next = dp[i][j]
            if c == "?":
                next *= 3
                next += dp[i][j-1]
            if STR[j] == c:  # 選んだ文字列が次選ぶべき文字列だったら
                next += dp[i][j-1]
            dp[i+1][j] = next % MOD
    #  print(dp)
    print(dp[len(S)][3])
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
import itertools
import collections
import functools
import math
from queue import Queue
INF = float("inf")

MOD = 1000000007  # type: int

d = {}


def thpow(q):
    if q < 0:
        return 0
    if q == 0:
        return 1
    if q in d:
        return d[q]
    else:
        d[q] = (3*thpow(q-1)) % MOD
        return d[q]


def solve(S: str):
    dp = [0, 0, 0]
    q = 0
    for ch in S:
        a, b, c = dp
        if ch == "A":
            dp = [(a+thpow(q)) % MOD, b, c]
        elif ch == "B":
            dp = [a, b+a, c]
        elif ch == "C":
            dp = [a, b, c+b]
        elif ch == "?":
            dp = [((a*3 % MOD)+thpow(q)) % MOD,
                  ((b*3) % MOD+a) % MOD,
                  ((c*3) % MOD+b) % MOD]
            q += 1
        # print(dp)

    # print(d)
    print(dp[2])
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
import itertools
import collections
import functools
import math
from queue import Queue
INF = float("inf")

MOD = 1000000007  # type: int

d = {}


def thpow(q):
    if q < 0:
        return 0
    if q == 0:
        return 1
    if q in d:
        return d[q]
    else:
        d[q] = (3*thpow(q-1)) % MOD
        return d[q]


def solve(S: str):
    dp = [0, 0, 0]
    q = 0
    for ch in S:
        # print(dp)
        a, b, c = dp
        if ch == "A":
            dp = [a+1, b, c]
        elif ch == "B":
            dp = [a, b+a, c]
        elif ch == "C":
            dp = [a, b, c+b]
        elif ch == "?":
            dp = [((a*3 % MOD)+thpow(q)) % MOD,
                  ((b*3) % MOD+a) % MOD,
                  ((c*3) % MOD+b) % MOD]
            q += 1
    # print(dp)
    print(dp[-1])
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
s=input()
d=[[0]*(len(s)+1)for i in range(4)]
d[3][-1]+=1
e="ABC"
for i in range(len(s)-1,-1,-1):
    for j in range(3,-1,-1):
        if j==3:
            if s[i]=="?":
                d[3][i]=d[3][i+1]*3
            else:
                d[3][i]=d[3][i+1]
        else:
            if s[i]=="?":
                d[j][i]=3*d[j][i+1]+d[j+1][i+1]
            else:
                d[j][i]=d[j][i+1]
                if e[j]==s[i]:
                    d[j][i]+=d[j+1][i]
print(d[0][0])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

S=raw_input()
l=len(S)

mod=10**9+7

dp=defaultdict(lambda: 0)   #dp[ (i,j) ]	i: i-mojime,  j=0:None , 1:A, 2:AB, 3:ABC
dp[(0,0)]=1

nashi=0
a=1
ab=2
abc=3

n=1
for i,s in enumerate(S):
	if s=="A":
		dp[ (i+1,a) ]+=dp[ (i,a) ]
		dp[ (i+1,a) ]+=dp[ (i,nashi) ]
		dp[ (i+1,ab) ]+=dp[ (i,ab) ]
		dp[ (i+1,abc) ]+=dp[ (i,abc) ]
	elif s=="B":
		dp[ (i+1,ab) ]+=dp[ (i,ab) ]
		dp[ (i+1,ab) ]+=dp[ (i,a) ]
		dp[ (i+1,a) ]+=dp[ (i,a) ]
		dp[ (i+1,abc) ]+=dp[ (i,abc) ]
	elif s=="C":
		dp[ (i+1,abc) ]+=dp[ (i,abc) ]
		dp[ (i+1,abc) ]+=dp[ (i,ab) ]
		dp[ (i+1,a) ]+=dp[ (i,a) ]
		dp[ (i+1,ab) ]+=dp[ (i,ab) ]
	elif s=="?":
		dp[ (i+1,a) ]+=dp[ (i,a) ]*3+n
		dp[ (i+1,a) ]+=dp[ (i,nashi) ]
		dp[ (i+1,ab) ]+=dp[ (i,ab) ]*3
		dp[ (i+1,ab) ]+=dp[ (i,a) ]	
		dp[ (i+1,abc) ]+=dp[ (i,abc) ]*3
		dp[ (i+1,abc) ]+=dp[ (i,ab) ]
		n*=3

print dp[(l,3)]%mod

Submission status: Wrong Answer

Solution code:
S = str(input())
mod = 10 ** 9 + 7
L = len(S)
d = "ABC".index
dp = [0 for _ in range(4)]
dp[0] = 1
for i in range(len(S)):
    if S[i] == '?':
        dp = [dp[0]*3, dp[1]*3+dp[0], dp[2]*3+dp[1], dp[3]*3+dp[2]]
        for j in range(4):
            dp[j] %= mod
    else:
        j = d(S[i])
        dp[j+1] += dp[j] % mod

print(dp[-1])

Submission status: Wrong Answer

Solution code:
S = str(input())
mod = 10 ** 9 + 7
L = len(S)
d = "ABC".index
dp = [[0 for _ in range(4)] for _ in range(L+1)]
dp[0][0] = 1
for i in range(len(S)):
    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
    else:
        dp[i+1] = dp[i]
        j = d(S[i])
        dp[i+1][j+1] += dp[i][j] % mod

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

Submission status: Wrong Answer

Solution code:
e,a,b,c=1,0,0,0
p=10**+7
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%p)

Submission status: Wrong Answer

Solution code:
e,a,b,c=1,0,0,0
p=10**+7
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)

Submission status: Wrong Answer

Solution code:
a=[1]+[0]*4
for s in input():
 i=ord(s)-64
 if i>0:a[i]+=a[i-1]
 else:a=[(a[i]*3+a[i-1])%(10**9+7)for i in range(4)]+[0]
print(a[3])

Submission status: Wrong Answer

Solution code:
a=[1,0,0,0]
for s in input():
 i=ord(s)-64
 if i>0:a[i]+=a[i-1]
 else:a=[(a[i]*3+a[i-1])%(10**9+7)for i in range(4)]+[0]
print(a[3])

Submission status: Wrong Answer

Solution code:
s=input()
Bcount=s[1:].count("?")+s[1:].count("B")-1
Ccount=s[2:].count("?")+s[2:].count("C")
ans=0
Acount=0
if s[0]=="A":
    Acount+=1
    ans+=(Bcount+1)*Bcount//2

for i in range(1,len(s)-1):
    if Ccount==0:
        break
    if s[i]=="B":
        ans+=Acount*Ccount
    elif s[i]=="?":
        ans+=Acount*Ccount
        Acount+=1
        Ccount-=1
        ans+=(Bcount+1)*Bcount//2
    elif s[i]=="A":
        Acount-=1
        ans+=(Bcount+1)*Bcount//2
    else:
        Ccount-=1
print(ans)

Submission status: Wrong Answer

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

dp[0][0] = 1
for i in range(len(S)):
    for j in range(4):
        if S[i] == '?':
            dp[i + 1][j] = dp[i][j] * 3 % mod
        else:
            dp[i + 1][j] = dp[i][j]
            
    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]
    if S[i] == 'C' or S[i] == '?':
        dp[i + 1][3] += dp[i][2]
        
print(dp[len(S)][3])

Submission status: Wrong Answer

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*3 + AB
        AB *= 3#AB + C and AB + B and AB + C
        AB += A[1] # AB + B
        A[1] = A[1]*3 + A[0]
        A[0] *= 3
    print(c+" " + str(A)+" " + str(AB) + " " + str(ABC))

print(ABC%D)

Submission status: Wrong Answer

Solution code:
s = input()

C = [1,0]
BC = 0

C_pre = (0,0)
BC_pre = 0

C_next = (0,0)
BC_next = 0

ABC = 0
D = 10**9 + 7
for c in s[::-1]:

    if c == 'C':
        C[1] += C[0]
    elif c == 'B':
        BC += C[1]
    elif c == 'A':
        ABC += BC
    elif c == '?':
        ABC += BC
        BC *= 3 # A + BC and B + BC and C + BC
        BC += C[1] #B + C
        C[1] = 3*C[1] + C[0]
        C[0] *= 3
    #print(c+" "+str(C)+" "+str(BC)+" "+str(ABC))
print(ABC%D)

Submission status: Wrong Answer

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] % MOD

ans = dp[-1] % MOD

print(ans)

Submission status: Wrong Answer

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

q = 3 if S[0] == '?' else 1
a = b = c = 0
if S[0] in 'A?':
    a = 1
for s in S:
    if s == '?':
        c = c * 3 + b
        b = b * 3 + a
        a = a * 3 + q
        q *= 3
    elif s == 'A':
        a += q
    elif s == 'B':
        b += a
    elif s == 'C':
        c += b

ans = c % MOD
print(ans)

Submission status: Wrong Answer

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

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

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

    return dp[0] % 1000000007


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

Submission status: Wrong Answer

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

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

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

    return dp[0] % 1000000007


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

Submission status: Wrong Answer

Solution code:
a = list(input())
su = 0

dp = [[0]*4 for i in range(len(a)+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] + 1
	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] + 1
	for j in range(3):
		dp[i][j] %= 1000000007
print(dp[0][0] % 1000000007)

Submission status: Wrong Answer

Solution code:
a = list(input())
su = 0

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


for i in range(len(a))[::-1]:
	if a[i] == "A":
		dp[i][0] += dp[i+1][0] + dp[i+1][1]
	elif a[i] == "B":
		dp[i][1] += dp[i+1][1] + dp[i+1][2]
	elif a[i] == "C":
		dp[i][2] += dp[i+1][2] + 1
	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] + 1
	for j in range(3):
		dp[i][j] %= 1000000007
print(dp[0][0] % 1000000007)

Submission status: Wrong Answer

Solution code:
a = list(input())
su = 0

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


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

Submission status: Wrong Answer

Solution code:
a = list(input())
su = 0

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


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

Submission status: Wrong Answer

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

s = input()[::-1]
n = len(s)
#DP = [[0]*3 for i in range(n+1)]
DP = np.zeros((n+1, 3), dtype=np.int64)

htn_cnt = 0
for i, c in enumerate(list(s)):
    if c == "?":
        DP[i+1] = 3*DP[i] % mod
    else:
        DP[i+1] = DP[i] % mod
    if c == "C" or c == "?":
        DP[i+1][0] = (DP[i+1][0] + 3**htn_cnt) % 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 == "?":
        htn_cnt += 1
print(int(DP[n][2] % mod))

Submission status: Wrong Answer

Solution code:
s = input()

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

Submission status: Wrong Answer

Solution code:
s = input()

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

Submission status: Wrong Answer

Solution code:
S = input()
N = len(S)
dp = [[0]*(3) for _ in [0]*(N+1)]
c=0
Mod=1000000007
for i in range(N):
    if S[i] =="A":
        dp[i][0] +=dp[i-1][0]+1
        dp[i][1] =dp[i-1][1]
        dp[i][2] =dp[i-1][2]
    elif S[i] =="B" and dp[i-1][0]!=0:
        dp[i][1] +=dp[i-1][1]+1
        dp[i][0] =dp[i-1][0]
        dp[i][2] =dp[i-1][2]
    elif S[i] =="C" and dp[i-1][1]!=0:
        dp[i][2] +=dp[i-1][2]+1
        dp[i][0] =dp[i-1][0]
        dp[i][1] =dp[i-1][1]
        c += dp[i][0]*dp[i][1]
    elif  S[i] =="?":
        dp[i][0] =dp[i-1][0]+1 
        dp[i][1] =dp[i-1][1]+1 if dp[i-1][0]!=0 else dp[i-1][1]
        dp[i][2] =dp[i-1][2]+1 if dp[i-1][1]!=0 else dp[i-1][2]
        c = c + (dp[i][0]-1)*(dp[i][1]-1) if dp[i][2] !=0 else c

print(c%Mod)

Submission status: Wrong Answer

Solution code:
s=input()
a=0
ab=0
abc=0
total=0
if s[0]=='A':
    a=1
    total=1
elif s[0]=='?':
    a=1
    total=3
for i in range(1,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
ans=abc%(10**9+7)
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Wed Jan 16 23:07:29 2019

@author: Yamazaki Kenichi
"""
import sys
sys.setrecursionlimit(1000000)

S = input()

a = [0 for i in range(len(S))]
q = [0 for i in range(len(S))]
counta,countq = 0,0
for i in range(len(S)):
    if S[i] == 'A':
        counta += 1
    elif S[i] == '?':
        countq += 1
    a[i] =counta
    q[i] =countq
    
def ab(x):
    if len(x) == 1:
        return 0
    if x[len(x)-1] == '?':
        return ab(x[:-1])*3 \
                +a[len(x)-1-1]*pow(3,q[len(x)-1-1])\
                +q[len(x)-1-1]*pow(3,q[len(x)-1-1]-1)
    elif x[len(x)-1] == 'B':
        return  ab(x[:-1]) \
                +a[len(x)-1-1]*pow(3,q[len(x)-1-1])\
                +q[len(x)-1-1]*pow(3,q[len(x)-1-1]-1)
    else:
        return ab(x[:-1])
ab_ = [ab(S[:i+1]) for i in range(len(S))]

def abc(x):
    if len(x) == 1:
        return 0
    if x[len(x)-1] == '?':
        return abc(x[:-1])*3 +ab_[len(x)-1-1]
    elif x[len(x)-1] == 'C':
        return abc(x[:-1]) +ab_[len(x)-1-1]
    else:
        return abc(x[:-1])
print(int(abc(S)%1000000007))

Submission status: Wrong Answer

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+?」か「?+?」
            ab += alpha[0] * nowQues  # (3 ** ques)
            # ？の中からaを選ぶ場合
            if ques > 0:
                ab += ques * (nowQues//3)  # (3 ** (ques - 1))
            ques += 1
            nowQues *= 3
        elif _s == "A":
            alpha[0] += 1
        elif _s == "B":
            # あるBを末尾とするABの選び方は「A + B」か「? + B」
            ab += alpha[0] * nowQues  # (3 ** ques)
            if ques > 0:
                ab += ques * (nowQues//3)  # (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: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from collections import Counter
mod = 10**9+7
s = input()
n = len(s)
dn = [0]*(n+1)
da = [0]*(n+1)
dx = [0]*(n+1)
dh = [0]*(n+1)
for i in range(n):
    dn[i+1] = dn[i]%mod
    da[i+1] = da[i]%mod
    dx[i+1] = dx[i]%mod
    dh[i+1] = dh[i]%mod
    if s[i] == "A":
        da[i+1] += 1
    elif s[i] == "B":
        if dh[i]:
            dx[i+1] += (da[i] + 3**dh[i])%mod
        else:
            dx[i+1] += da[i]%mod
    elif s[i] == "C":
        dn[i+1] += (dn[i] + dx[i])%mod
        dx[i+1] = 0
'''
    elif s[i] == "?":
        da[i+1] += 1
        dh[i+1] += 1
        dx[i+1] = da[i]*3**dh[i]
        dn[i+1] += dx[i]
'''
print(dn[n]%mod)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
S=" "+raw_input()
l=len(S)

mod=10**9+7

dp=[  [ 0  for j in range(4) ]   for i in range(l) ] 

for i in range(l):
	dp[i][0]=1


for i in range(1,l):
	if S[i]=="A":
		dp[i][1]+=dp[i-1][1]+dp[i-1][0]
		dp[i][2]+=dp[i-1][2]
		dp[i][3]+=dp[i-1][3]
	elif S[i]=="B":
		dp[i][1]+=dp[i-1][1]
		dp[i][2]+=dp[i-1][2]+dp[i-1][1]
		dp[i][3]+=dp[i-1][3]
	elif S[i]=="C":
		dp[i][1]+=dp[i-1][1]
		dp[i][2]+=dp[i-1][2]
		dp[i][3]+=dp[i-1][3]+dp[i-1][2]
	elif S[i]=="?":
		dp[i][1]+=3*dp[i-1][1]+dp[i-1][0]
		dp[i][2]+=dp[i-1][2]+dp[i-1][1]+dp[i-2][2]+2*dp[i-2][1]
		dp[i][3]+=2*dp[i-1][3]+dp[i-1][2]+dp[i-2][3]+2*dp[i-2][2]

#print dp

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

Submission status: Wrong Answer

Solution code:
S=" "+raw_input()
l=len(S)

mod=10**9+7

dp=[  [ 0  for j in range(4) ]   for i in range(l) ] 

for i in range(l):
	dp[i][0]=1


for i in range(1,l):
	if S[i]=="A":
		dp[i][1]+=dp[i-1][1]+dp[i-1][0]
		dp[i][2]+=dp[i-1][2]
		dp[i][3]+=dp[i-1][3]
	elif S[i]=="B":
		dp[i][1]+=dp[i-1][1]
		dp[i][2]+=dp[i-1][2]+dp[i-1][1]
		dp[i][3]+=dp[i-1][3]
	elif S[i]=="C":
		dp[i][1]+=dp[i-1][1]
		dp[i][2]+=dp[i-1][2]
		dp[i][3]+=dp[i-1][3]+dp[i-1][2]
	elif S[i]=="?":
		dp[i][1]+=dp[i-1][1]+dp[i-1][0]
		dp[i][2]+=dp[i-1][2]
		dp[i][3]+=dp[i-1][3]
		dp[i][1]+=dp[i-1][1]
		dp[i][2]+=dp[i-1][2]+dp[i-1][1]
		dp[i][3]+=dp[i-1][3]
		dp[i][1]+=dp[i-1][1]
		dp[i][2]+=dp[i-1][2]
		dp[i][3]+=dp[i-1][3]+dp[i-1][2]


print dp[-1][-1]%mod

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10**5)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

mod = 10**9+7

s = lc()
n = len(s)

a__ = [0]*(n+1)
ab_ = [0]*(n+1)
abc = [0]*(n+1)

for i,si in enumerate(s):

    if si == 'A':
        a__[i+1] = (a__[i] + 1) % mod
        
        ab_[i+1] = ab_[i]
        abc[i+1] = abc[i]

    elif si == 'B':
        ab_[i+1] = (ab_[i] + a__[i]) % mod
        
        a__[i+1] = a__[i]
        abc[i+1] = abc[i]
        
    elif si == 'C':
        abc[i+1] = (abc[i] + ab_[i]) % mod
        
        a__[i+1] = a__[i]
        ab_[i+1] = ab_[i]
        
        
    else:
        a__[i+1] = (3*a__[i] + 1) % mod
        ab_[i+1] = (ab_[i] + a__[i]) % mod
        abc[i+1] = (abc[i] + ab_[i]) % mod
        
print(abc[n])

Submission status: Wrong Answer

Solution code:
Mod = 10**9+7
S = input()
N = len(S)
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] += 1
    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] += 1
        AB[i] *= 3
        AB[i] += A[i-1]
        ABC[i] *= 3
        ABC[i] += AB[i-1]
    A[i] %= Mod
    AB[i] %= Mod
    ABC[i] %= Mod

print(ABC[-1])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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
    print(dp)
    return dp[0][0]
print(func(input()))