TnT/Multi_CodeNet4Repair huggingface dataset:
Problem: 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.

Submission attempts (in order):
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)

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


Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):

import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

mod = 1000000007

s = ns()

nums = [0]*4
nums[0] = 1
for c in s:
    if c == 'A':
        nums[1] += nums[0]
        nums[1] %= mod
    elif c == "B":
        nums[2] += nums[1]
        nums[2] %= mod
    elif c == "C":
        nums[3] += nums[2]
        nums[3] %= mod
    else:
        nums[3] = nums[3]*3+nums[2]
        nums[2] = nums[2]*3+nums[1]
        nums[1] = nums[1]*3+nums[0]
        nums[0] = nums[0]*3
        for k in range(4):
            nums[k] %= mod
print(nums[3])



import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

mod = 1000000007

s = ns().rstrip()

nums = [0]*4
nums[0] = 1
for c in s:
    if c == 'A':
        nums[1] += nums[0]
        nums[1] %= mod
    elif c == "B":
        nums[2] += nums[1]
        nums[2] %= mod
    elif c == "C":
        nums[3] += nums[2]
        nums[3] %= mod
    else:
        nums[3] = nums[3]*3+nums[2]
        nums[2] = nums[2]*3+nums[1]
        nums[1] = nums[1]*3+nums[0]
        nums[0] = nums[0]*3
        for k in range(4):
            nums[k] %= mod
print(nums[3])



Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
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)


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)



Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
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)

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

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

Verdicts: Runtime Error

Wrong Answer

Accepted
Problem: 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.

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

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

Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
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 = raw_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)


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)


Verdicts: Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
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 % MODE
        if s == c or s == '?':
            dp[j + 1] += dp[j]
    if s == '?':
        dp[0] = dp[0] % MOD

ans = dp[-1] % MOD

print(ans)

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[1:]:
    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
    a, b, c = a % MOD, b % MOD, C % MOD

ans = c % MOD
print(ans)

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)

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)

Verdicts: Runtime Error

Runtime Error

Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
S = ''

def we_love_abc()->int:
    global S
    ABC = 'ABC'

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

    for c in reversed(S):
        if c == '?':
            m, m1 = 3, 3
        else:
            m, m1 = 1, 1

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

    return dp[0] % 1000000007


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


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)


Verdicts: Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
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)
        

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

Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
import bisect
import cmath
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


S = sys.stdin.buffer.readline().decode().rstrip()

a = 0
ab = 0
abc = 0
q = 0
for i, s in enumerate(S):
    if s == 'C':
        abc += ab
    if s == 'B':
        ab += a
    if s == 'A':
        a += 3 ** q
    if s == '?':
        abc = abc * 3 + ab
        ab = ab * 3 + a
        a = a * 3 + 3 ** q
        q += 1
    a %= MOD
    ab %= MOD
    abc %= MOD
    
print(abc)


import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


S = sys.stdin.buffer.readline().decode().rstrip()

a = 0
ab = 0
abc = 0
q = 0
for i, s in enumerate(S):
    if s == 'C':
        abc += ab
    if s == 'B':
        ab += a
    if s == 'A':
        a += pow(3, q, MOD)
    if s == '?':
        abc = abc * 3 + ab
        ab = ab * 3 + a
        a = a * 3 + pow(3, q, MOD)
        q += 1
    a %= MOD
    ab %= MOD
    abc %= MOD
    
print(abc)


Verdicts: Time Limit Exceeded

Accepted
Problem: 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.

Submission attempts (in order):
S=input()
N = len(S)
A = [0]*N
C = [0]*N
L = [0]*N
R = [0]*N
for i in range(1,N):
    A[i] = A[i-1] + (S[i-1] == "A")
    L[i] = L[i-1] + (S[i-1] == "?")
    C[N-1-i] = C[N-i] + (S[N-i] == "C")
    R[N-1-i] = R[N-i] + (S[N-i] == "?")
mod = 10**9+7
d={0:1}
def pow_mod(x,n):
    if d.get(n,False) :return d[n]
    if n<0: return pow_mod(x,mod-2+n)
    if n%2  :
        d[n] = (x*pow_mod(x,n-1))%mod
    else:
        d[n] = (pow_mod(x,n//2)**2)%mod
    return d[n]
ans = 0
for i in range(1,N-1):
    if S[i] in "B?":
        ans += (3*A[i]+L[i])*(3*C[i]+R[i])*pow_mod(3,L[i]+R[i]-2)
        ans %= mod
print(ans)

S=input()
N = len(S)
A = [0]*N
C = [0]*N
L = [0]*N
R = [0]*N
for i in range(1,N):
    A[i] = A[i-1] + (S[i-1] == "A")
    L[i] = L[i-1] + (S[i-1] == "?")
    C[N-1-i] = C[N-i] + (S[N-i] == "C")
    R[N-1-i] = R[N-i] + (S[N-i] == "?")
mod = 10**9+7
d={0:1}
def pow_mod(x,n):
    if d.get(n,False) :return d[n]
    if n<0: return pow_mod(x,mod-1+n)
    if n%2  :
        d[n] = (x*pow_mod(x,n-1))%mod
    else:
        d[n] = (pow_mod(x,n//2)**2)%mod
    return d[n]
ans = 0
for i in range(1,N-1):
    if S[i] in "B?":
        ans += (3*A[i]+L[i])*(3*C[i]+R[i])*pow_mod(3,L[i]+R[i]-2)
        ans %= mod
print(ans)

Verdicts: Wrong Answer

Accepted
Problem: 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.

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

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

S = input()
DP = [0, 0, 0, 1]
p = 10 ** 9 + 7
for s in S[::-1]:
  dp = [0, 0, 0, 0]
  dp[3] = DP[3] * (3 if s == '?' else 1) % p
  for i in range(2, -1, -1):
    dp[i] += DP[i] * (3 if s == '?' else 1)
    dp[i] += DP[i + 1] if s == chr(65 + i) or s == '?' else 0
    dp[i] %= p
  DP = dp
print(DP[0] % p)

Verdicts: Wrong Answer

Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
init_input()

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

A = [0] * n
C = [0] * n
Q = [0] * n
Bi = []
Qi = []

for i, s in enumerate(S):
    if s == 'A':
        A[i] = 1
    elif s == 'B':
        Bi.append(i)
    elif s == 'C':
        C[i] = 1
    else:
        Q[i] = 1
        Qi.append(i)

for i in range(1, n):
    A[i] += A[i - 1]
    C[i] += C[i - 1]
    Q[i] += Q[i - 1]

def mod_pow(x, n, mod):
    if n == 0: return 1
    d, m = n >> 1, n & 1
    p = mod_pow(x, d, mod)
    return (p * p * (x if m else 1))

from itertools import chain
ans = 0
for b in chain(Bi, Qi):
    if b == 0 or n - 1 <= b: continue
    ai = A[b - 1]
    qa = Q[b - 1]
    a = (ai * mod_pow(3, qa, mod))
    if qa > 0:
        a += (mod_pow(3, qa - 1, mod) * qa)

    lc = C[n - 1] - C[b]
    lqc = Q[n - 1] - Q[b]
    c = (lc * mod_pow(3, lqc, mod))
    if lqc > 0:
        c += (mod_pow(3, lqc - 1, mod) * lqc)
    
    ans += (a * c) % mod

print(ans % mod)

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

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

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

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

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

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

Verdicts: Runtime Error

Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
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) 


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) 


Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
????C?????B??????A???????

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


Verdicts: Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
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()))


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


Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
S=input()
N=len(S)

S=input()
N=len(S)
dp=[0,0,0]

mod=10**9+7

p=[1]*(N+1)
for i in range(N):
    p[i+1]=p[i]*3



S=input()
N=len(S)
dp=[0,0,0]

mod=10**9+7

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


count=0
for i in range(N):
    if S[i]=="A":
        dp[0]=(dp[0]+p[count]) %mod
    elif S[i]=="B":
        dp[1]=(dp[1]+dp[0])%mod
    elif S[i]=="C":
        dp[2]=(dp[2]+dp[1])%mod
    else:
        dp[2]=(dp[2]*3+dp[1])%mod
        dp[1]=(dp[1]*3+dp[0])%mod
        dp[0]=(dp[0]*3+p[count])%mod
        count+=1
        
print(dp[2]%mod)   







Verdicts: Wrong Answer

Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
MOD = 10 ** 9 + 7

S = list(input())

a = [0] * len(S)
ab = [0] * len(S)
abc = [0] * len(S)

if S[0] == "A" or S[0] == "?":
    a[0] = 1

for i in range(1,len(S)):
    if S[i] == "A":
        a[i] = a[i-1] + 1
        ab[i] = ab[i-1]
        abc[i] = abc[i-1]
    elif S[i] == "B":
        a[i] = a[i-1]
        ab[i] = (ab[i-1] + a[i-1]) % MOD
        abc[i] = abc[i-1]
    elif S[i] == "C":
        a[i] = a[i-1]
        ab[i] = ab[i-1]
        abc[i] = (abc[i-1] + ab[i-1]) % MOD
    else:
        a[i] = (a[i-1] * 3 + 1) % MOD
        ab[i] = (ab[i-1] * 3 + a[i-1]) % MOD
        abc[i] = (abc[i-1] * 3 + ab[i-1]) % MOD

print(a)
print(ab)
print(abc)
print(abc[-1])


MOD = 10 ** 9 + 7

S = [0] + list(input())
n = len(S) - 1

yet = [0] * (n+1)
a = [0] * (n+1)
ab = [0] * (n+1)
abc = [0] * (n+1)


abc[n] = 1

for i in range(1,n+1):
    if S[n-i+1] == "A":
        yet[n-i] = (yet[n-i+1] + a[n-i+1]) % MOD
        a[n-i] = a[n-i+1]
        ab[n-i] = ab[n-i+1]
        abc[n-i] = abc[n-i+1]
    elif S[n-i+1] == "B":
        yet[n-i] = yet[n-i+1]
        a[n-i] = (ab[n-i+1] + a[n-i+1]) % MOD
        ab[n-i] = ab[n-i+1]
        abc[n-i] = abc[n-i+1]
    elif S[n-i+1] == "C":
        yet[n-i] = yet[n-i+1]
        a[n-i] = a[n-i+1]
        ab[n-i] = (ab[n-i+1] + abc[n-i+1]) % MOD
        abc[n-i] = abc[n-i+1]
    else:
        yet[n-i] = (yet[n-i+1] * 3 + a[n-i+1]) % MOD
        a[n-i] = (a[n-i+1] * 3 + ab[n-i+1]) % MOD
        ab[n-i] = (ab[n-i+1] * 3 + abc[n-i+1]) % MOD
        abc[n-i] = (abc[n-i+1] * 3) % MOD

print(yet[0])

Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
s = input()

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

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 ss[i] == 'A':
        m4 = 1

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

n = 10 ** 9 + 7
ans = dp0 % n
print(ans)

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)

Verdicts: Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
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)

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 += k % mod
print(ans%mod)

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)

Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
s = input()
count = 0
len = len(s)
def isa(char):
    if char == 'A' or char == '?':
        return 1
    else:
        return 0
def isc(char):
    if char == 'C' or char == '?':
        return 1
    else:
        return 0
q = 0
for i in range(len):
    if s[i] == '?':
        q += 1
    else:
        continue
for i in range(len):
    a, c = 0, 0
    if s[i] == 'A' or s[i] == 'C':
        continue
    else:
        for j in range(i):
            a += isa(s[j])
        for j in range(i+1, len):
            c += isc(s[j])
    if s[i] == 'B':
        count += a * c * pow(3, q)
    else:
        count += a * c * pow(3, q-1)
print(count % 1000000007)

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

Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
s=input()
mod=10**9+7
retnum={"?":0,"A":1,"B":2,"C":3}
count=[[0 for i in range(len(s))] for j in range(4)]
for i in range(len(s)):
    for j in range(4):
        if retnum[s[i]] == j:
            count[j][i]=count[j][i-1]+1
        else:
            count[j][i]=count[j][i-1]
ans=0
for i in range(1,len(s)-1):
    if s[i]=="B" or s[i]=="?":
        ans+=((3**(count[0][i-1]-1))*count[0][i-1]+(3**count[0][i-1])*count[1][i-1])*(3**(count[0][-1]-count[0][i]-1)*(count[0][-1]-count[0][i])+(3**(count[0][-1]-count[0][i]))*(count[3][-1]-count[3][i]))
        ans%=mod
print(ans)

s=input()
mod=10**9+7
retnum={"?":0,"A":1,"B":2,"C":3}
count=[[0 for i in range(len(s))] for j in range(4)]
for i in range(len(s)):
    for j in range(4):
        if retnum[s[i]] == j:
            count[j][i]=count[j][i-1]+1
        else:
            count[j][i]=count[j][i-1]
ans=0
g=[1]*100002
for i in range(1,100002):
    g[i]=g[i-1]*3
    g[i]%=mod
for i in range(1,len(s)-1):
    if s[i]=="B" or s[i]=="?":
        ans+=(g[max(0,count[0][i-1]-1)]*count[0][i-1]+g[count[0][i-1]]*count[1][i-1])*(g[max(0,count[0][-1]-count[0][i]-1)]*(count[0][-1]-count[0][i])+g[count[0][-1]-count[0][i]]*(count[3][-1]-count[3][i]))
        ans%=mod
print(ans)

Verdicts: Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
a

a

s=input()

n=len(s)
dc=dict()
dc['A']=0
dc['B']=1
dc['C']=2
dc['?']=3
dp=[[0 for i in range(4)] for j in range(n+1)]
dp[0][0]=1
mo=10**9+7
for i in range(n):
    for t in range(4):
        ch=s[i]
        m = 1 if dc[ch]==t-1 or dc[ch]==3 else 0
        if t!=0:
            dp[i+1][t]+=(dp[i][t-1]*m)%mo
        dp[i+1][t]+=(dp[i][t]*(3 if dc[ch]==3 else 1))%mo

ans=dp[n][3]
print(ans%mo)


Verdicts: Runtime Error

Runtime Error

Accepted