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: Runtime Error

Solution code:
#TEST#

from collections import Counter
s=input()
D=Counter(list(s))
A,C,Q=D["A"],D["C"],D["?"]
a,c,q=0,0,0
ans=0
MOD=10**9+7

for i in range(len(s)):
    if s[i]=="A":
        a+=1
    elif s[i]=="C":
        c+=1
    elif s[i]=="B":
        ans+=(a*(3**q)+q*(3**(q-1)))*((C-c)*(3**(Q-q))+(Q-q)*(3**(Q-q-1)))
        ans%=MOD
    else:
        ans+=(a*(3**q)+q*(3**(q-1)))*((C-c)*(3**(Q-q-1))+(Q-q-1)*(3**(Q-q-2)))
        ans%=MOD
        q+=1

print(int(ans%MOD))

Submission status: Runtime Error

Solution code:
from collections import Counter
s=input()
D=Counter(list(s))
A,C,Q=D["A"],D["C"],D["?"]
a,c,q=0,0,0
ans=0
MOD=10**9+7

for i in range(len(s)):
    if s[i]=="A":
        a+=1
    elif s[i]=="C":
        c+=1
    elif s[i]=="B":
        ans+=(a*(3**q)+q*(3**(q-1)))*((C-c)*(3**(Q-q))+(Q-q)*(3**(Q-q-1)))
        ans%=MOD
    else:
        ans+=(a*(3**q)+q*(3**(q-1)))*((C-c)*(3**(Q-q-1))+(Q-q-1)*(3**(Q-q-2)))
        ans%=MOD
        q+=1

print(int(ans%MOD))

Submission status: Runtime Error

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

dp = [[0, 0, 0, 0] for i in range(len(S)+1)]
dp[0][0] = 1

for i in range(len(S)):
    if S[i] == '?':
        m = 3
    else:
        m = 1
    for j in range(4):
        dp[i+1][j] = m * dp[i][j]
    
    if S[i] == '?':
        for j in range(3):
            dp[i+1][j+1] += dp[i][j]
    else:
        idx = 'ABC'.index(S[i])
        dp[i+1][idx+1] += dp[i][idx]
        
    for i in range(4):
        dp[i+1][j] %= MOD
        
print(dp[-1][3]%MOD)

Submission status: Runtime Error

Solution code:
s = input()
mod = 10**9 + 7
n = len(s)
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:
    c += b
    b += a
    a += 1
  a %= mod
  b %= mod
  c %= mod

pribt(c)

Submission status: Runtime Error

Solution code:
S = input()

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

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

Submission status: Runtime Error

Solution code:
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <numeric>
#include <bitset>

using namespace std;
using ll = long long;
using ld = long double;
const ll mod =  1000000007;

#define REP(i, n) for (ll i = 0; i < (n); ++i)
#define REP_FROM(i, j, n) for (ll i = (j); i < (n); ++i)
#define all(x) (x).begin(),(x).end()

ll power(ll base, ll exponent, ll module){ if(exponent % 2){ return power(base, exponent - 1, module) * base % module; }else if(exponent){ ll root_ans = power(base, exponent / 2, module); return root_ans * root_ans % module; }else{ return 1; }}
ll inverse(ll x){ return power(x, mod - 2, mod);}
ll gcd(ll a, ll b) {if(a < b) gcd(b, a);ll r;while(r=a%b) {a=b;b=r;}return b;}
struct combination{ vector<ll> fact, inv; combination(int sz) : fact(sz + 1), inv(sz + 1){ fact[0] = 1; for(int i = 1; i <= sz; i++){ fact[i] = fact[i - 1] * i % mod; } inv[sz] = power(fact[sz], mod - 2, mod); for(int i = sz - 1; i >= 0; i--){ inv[i] = inv[i + 1] * (i + 1) % mod; } } ll C(int p, int q) const{ if(q < 0 || p < q) return 0; return (fact[p] * inv[q] % mod * inv[p - q] % mod); } };

int bsearch(const vector<ll>& a, ll x){
  int lft = 0;
  int rgt = a.size();
  while (rgt - lft > 1) {
    int mid = (lft + rgt) / 2;
    if(a[mid] < x) {
      lft = mid;
    }
    else {
      rgt = mid;
    }
  }
  return lft;
}


signed main() {
  ios::sync_with_stdio(false);
  string t;
  cin >> t;
  ll n = t.size();
  vector<vector<ll>> dp(n+1, vector<ll>(4));
  ll ans = 0;
  dp[0][0] = 1;
  REP(i, n) {
    if(t[i] == '?') {
      REP(j, 4) {
        dp[i+1][j] = 3 * dp[i][j];
      }
      REP(j, 3) {
        dp[i+1][j+1] += dp[i][j];
      }
    }
    else {
      REP(j, 4) {
        dp[i+1][j] = dp[i][j];
      }
      int j = t[i] - 'A';
      dp[i+1][j+1] += dp[i][j];
    }
    REP(j, 4) dp[i+1][j] %= mod;
  }
  cout << dp[n][3] << endl;
  return 0;
}

Submission status: Runtime Error

Solution code:
s = input()

def get_sum(J, J3, I, L, L3, K):
    total1 = int(I * J3 * 3 + J * J3)%  (10 ** 9 + 7)
    total2 = int(K * L3 * 3 + L * L3)%  (10 ** 9 + 7)
    return total1 * total2

n_q = 0
n_c = 0
for i in range(len(s)):
    if s[i] == '?':
        n_q += 1
    elif s[i] == 'C':
        n_c += 1

n_q_right = [0]
n_a_right = [0]
n_c_right = [0]
for i in range(len(s) - 1):
    if s[i] == '?':
        n_q_right.append(n_q_right[-1] + 1)
        n_a_right.append(n_a_right[-1])
        n_c_right.append(n_c_right[-1])
    elif s[i] == 'A':
        n_q_right.append(n_q_right[-1])
        n_a_right.append(n_a_right[-1] + 1)
        n_c_right.append(n_c_right[-1])
    elif s[i] == 'C':
        n_q_right.append(n_q_right[-1])
        n_a_right.append(n_a_right[-1])
        n_c_right.append(n_c_right[-1] + 1)
    elif s[i] == 'B':
        n_q_right.append(n_q_right[-1])
        n_a_right.append(n_a_right[-1])
        n_c_right.append(n_c_right[-1])

total = 0
P3_right = 1/3.0
P3_left = 3 ** (n_q - 1)
for i in range(len(s)):
    if s[i] == '?':
        P3_left /= 3
        _n_q_left = n_q - n_q_right[i] - 1
        _n_c_left = n_c - n_c_right[i]
        total += get_sum(n_q_right[i], P3_right, n_a_right[i], _n_q_left, P3_left, _n_c_left)
        P3_right = P3_right * 3  % (10 ** 9 + 7)
    elif s[i] == 'B':
        _n_q_left = n_q - n_q_right[i]
        _n_c_left = n_c - n_c_right[i]
        total += get_sum(n_q_right[i], P3_right, n_a_right[i], _n_q_left, P3_left, _n_c_left)



print(total % (10 ** 9 + 7))

Submission status: Runtime Error

Solution code:
s = input()

def get_sum(J, J3, I, L, L3, K):
    total1 = int(I * J3 + J * J3 / 3)%  (10 ** 9 + 7)
    total2 = int(K * L3 + L * L3 / 3)%  (10 ** 9 + 7)
    return total1 * total2

n_q = 0
n_c = 0
for i in range(len(s)):
    if s[i] == '?':
        n_q += 1
    elif s[i] == 'C':
        n_c += 1

n_q_right = [0]
n_a_right = [0]
n_c_right = [0]
for i in range(len(s) - 1):
    if s[i] == '?':
        n_q_right.append(n_q_right[-1] + 1)
        n_a_right.append(n_a_right[-1])
        n_c_right.append(n_c_right[-1])
    elif s[i] == 'A':
        n_q_right.append(n_q_right[-1])
        n_a_right.append(n_a_right[-1] + 1)
        n_c_right.append(n_c_right[-1])
    elif s[i] == 'C':
        n_q_right.append(n_q_right[-1])
        n_a_right.append(n_a_right[-1])
        n_c_right.append(n_c_right[-1] + 1)
    elif s[i] == 'B':
        n_q_right.append(n_q_right[-1])
        n_a_right.append(n_a_right[-1])
        n_c_right.append(n_c_right[-1])

total = 0
P3_right = 1
P3_left = 3 ** n_q
for i in range(len(s)):
    if s[i] == '?':
        P3_left /= 3
        _n_q_left = n_q - n_q_right[i] - 1
        _n_c_left = n_c - n_c_right[i]
        total += get_sum(n_q_right[i], P3_right, n_a_right[i], _n_q_left, P3_left, _n_c_left) %  (10 ** 9 + 7)
        P3_right = P3_right * 3  % (10 ** 9 + 7)
    elif s[i] == 'B':
        _n_q_left = n_q - n_q_right[i]
        _n_c_left = n_c - n_c_right[i]
        total += get_sum(n_q_right[i], P3_right, n_a_right[i], _n_q_left, P3_left, _n_c_left) %  (10 ** 9 + 7)



print(total % (10 ** 9 + 7))

Submission status: Runtime Error

Solution code:
s = input()

def get_sum(J, J3, I, L, L3, K):
    total1 = int(I * J3 + J * J3 / 3)
    total2 = int(K * L3 + L * L3 / 3)
    return total1 * total2

n_q = 0
n_c = 0
for i in range(len(s)):
    if s[i] == '?':
        n_q += 1
    elif s[i] == 'C':
        n_c += 1

n_q_right = [0]
n_a_right = [0]
n_c_right = [0]
for i in range(len(s) - 1):
    if s[i] == '?':
        n_q_right.append(n_q_right[-1] + 1)
        n_a_right.append(n_a_right[-1])
        n_c_right.append(n_c_right[-1])
    elif s[i] == 'A':
        n_q_right.append(n_q_right[-1])
        n_a_right.append(n_a_right[-1] + 1)
        n_c_right.append(n_c_right[-1])
    elif s[i] == 'C':
        n_q_right.append(n_q_right[-1])
        n_a_right.append(n_a_right[-1])
        n_c_right.append(n_c_right[-1] + 1)
    elif s[i] == 'B':
        n_q_right.append(n_q_right[-1])
        n_a_right.append(n_a_right[-1])
        n_c_right.append(n_c_right[-1])

total = 0
P3_right = 1
P3_left = 3 ** n_q
for i in range(len(s)):
    if s[i] == '?':
        P3_left /= 3
        _n_q_left = n_q - n_q_right[i] - 1
        _n_c_left = n_c - n_c_right[i]
        total += get_sum(n_q_right[i], P3_right, n_a_right[i], _n_q_left, P3_left, _n_c_left) %  (10 ** 9 + 7)
        P3_right = P3_right * 3  % (10 ** 9 + 7)
    elif s[i] == 'B':
        _n_q_left = n_q - n_q_right[i]
        _n_c_left = n_c - n_c_right[i]
        total += get_sum(n_q_right[i], P3_right, n_a_right[i], _n_q_left, P3_left, _n_c_left) %  (10 ** 9 + 7)



print(total % (10 ** 9 + 7))

Submission status: Runtime Error

Solution code:
s = input()

def get_sum(J, J3, I, L, L3, K):
    total1 = int(I * J3 + J * J3 / 3)
    total2 = int(K * L3 + L * L3 / 3)
    return total1 * total2

n_q = 0
n_c = 0
for i in range(len(s)):
    if s[i] == '?':
        n_q += 1
    elif s[i] == 'C':
        n_c += 1

n_q_right = [0]
n_a_right = [0]
n_c_right = [0]
for i in range(len(s) - 1):
    if s[i] == '?':
        n_q_right.append(n_q_right[-1] + 1)
        n_a_right.append(n_a_right[-1])
        n_c_right.append(n_c_right[-1])
    elif s[i] == 'A':
        n_q_right.append(n_q_right[-1])
        n_a_right.append(n_a_right[-1] + 1)
        n_c_right.append(n_c_right[-1])
    elif s[i] == 'C':
        n_q_right.append(n_q_right[-1])
        n_a_right.append(n_a_right[-1])
        n_c_right.append(n_c_right[-1] + 1)
    elif s[i] == 'B':
        n_q_right.append(n_q_right[-1])
        n_a_right.append(n_a_right[-1])
        n_c_right.append(n_c_right[-1])

total = 0
P3_right = 1
P3_left = 3 ** n_q
for i in range(len(s)):
    if s[i] == '?':
        P3_left /= 3
        _n_q_left = n_q - n_q_right[i] - 1
        _n_c_left = n_c - n_c_right[i]
        total += get_sum(n_q_right[i], P3_right, n_a_right[i], _n_q_left, P3_left, _n_c_left) %  (10 ** 9 + 7)
        P3_right *= 3
    elif s[i] == 'B':
        _n_q_left = n_q - n_q_right[i]
        _n_c_left = n_c - n_c_right[i]
        total += get_sum(n_q_right[i], P3_right, n_a_right[i], _n_q_left, P3_left, _n_c_left) %  (10 ** 9 + 7)



print(total % (10 ** 9 + 7))

Submission status: Runtime Error

Solution code:
s = input()

def get_sum(J, J3, I, L, L3, K):
    total1 = int(I * J3 + J * J3 / 3) % (10 ** 9 + 7)
    total2 = int(K * L3 + L * L3 / 3) % (10 ** 9 + 7)
    return total1 * total2

n_q = 0
n_c = 0
for i in range(len(s)):
    if s[i] == '?':
        n_q += 1
    elif s[i] == 'C':
        n_c += 1

n_q_right = [0]
n_a_right = [0]
n_c_right = [0]
for i in range(len(s) - 1):
    if s[i] == '?':
        n_q_right.append(n_q_right[-1] + 1)
        n_a_right.append(n_a_right[-1])
        n_c_right.append(n_c_right[-1])
    elif s[i] == 'A':
        n_q_right.append(n_q_right[-1])
        n_a_right.append(n_a_right[-1] + 1)
        n_c_right.append(n_c_right[-1])
    elif s[i] == 'C':
        n_q_right.append(n_q_right[-1])
        n_a_right.append(n_a_right[-1])
        n_c_right.append(n_c_right[-1] + 1)
    elif s[i] == 'B':
        n_q_right.append(n_q_right[-1])
        n_a_right.append(n_a_right[-1])
        n_c_right.append(n_c_right[-1])

total = 0
_n_q_right_3 = 1
_n_q_left_3 = 3 ** n_q
for i in range(len(s)):
    if s[i] == '?':
        _n_q_left_3 /= 3
        total += get_sum(n_q_right[i], _n_q_right_3, n_a_right[i], n_q - n_q_right[i] - 1, _n_q_left_3, n_c - n_c_right[i])
        _n_q_right_3 *= 3
    elif s[i] == 'B':
        total += get_sum(n_q_right[i], _n_q_right_3, n_a_right[i], n_q - n_q_right[i], _n_q_left_3, n_c - n_c_right[i])

print(total % (10 ** 9 + 7))

Submission status: Runtime Error

Solution code:
s = input()

n_q = 0
n_c = 0
for i in range(len(s)):
    if s[i] == '?':
        n_q += 1
    elif s[i] == 'C':
        n_c += 1

n_q_right = [0]
n_a_right = [0]
n_c_right = [0]
for i in range(len(s) - 1):
    if s[i] == '?':
        n_q_right.append(n_q_right[-1] + 1)
        n_a_right.append(n_a_right[-1])
        n_c_right.append(n_c_right[-1])
    elif s[i] == 'A':
        n_q_right.append(n_q_right[-1])
        n_a_right.append(n_a_right[-1] + 1)
        n_c_right.append(n_c_right[-1])
    elif s[i] == 'C':
        n_q_right.append(n_q_right[-1])
        n_a_right.append(n_a_right[-1])
        n_c_right.append(n_c_right[-1] + 1)
    elif s[i] == 'B':
        n_q_right.append(n_q_right[-1])
        n_a_right.append(n_a_right[-1])
        n_c_right.append(n_c_right[-1])

total = 0
Jp3 = 1/3.0
Lp3 = 3 ** (n_q - 1)
for i in range(len(s)):
    if s[i] == '?':
        Lp3 /= 3
        total1 = int((n_a_right[i] * 3 + n_q_right[i]) * Jp3)  %  (10 ** 9 + 7)
        total2 = int(((n_c - n_c_right[i]) * 3 + n_q - n_q_right[i] - 1) * Lp3)  %  (10 ** 9 + 7)
        total += total1 * total2
        Jp3 *= 3

    elif s[i] == 'B':
        total1 = int((n_a_right[i] * 3 + n_q_right[i]) * Jp3)  %  (10 ** 9 + 7)
        total2 = int(((n_c - n_c_right[i]) * 3 + n_q - n_q_right[i]) * Lp3)  %  (10 ** 9 + 7)
        total += total1 * total2

print(total % (10 ** 9 + 7))

Submission status: Runtime Error

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

import sys
sys.setrecursionlimit(200000)

from functools import lru_cache

@lru_cache(maxsize=None)
def dp(cur,i):
	if cur==N:
		if i==3:
			return 1
		else:
			return 0
	else:
		if S[cur]=='ABCD'[i]:
			return (dp(cur+1,i+1)+dp(cur+1,i))%mod
		elif S[cur]=='?' and i!=3:
			return (dp(cur+1,i+1)+3*dp(cur+1,i))%mod
		elif S[cur]=='?':
			return 3*dp(cur+1,i)%mod
		else:
			return dp(cur+1,i)%mod

print(dp(0,0)%mod)

Submission status: Runtime Error

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

#import sys
#sys.setrecursionlimit(200000)

from functools import lru_cache

@lru_cache(maxsize=None)
def dp(cur,i):
	if cur==N:
		if i==3:
			return 1
		else:
			return 0
	else:
		if S[cur]=='ABCD'[i]:
			return (dp(cur+1,i+1)+dp(cur+1,i))%mod
		elif S[cur]=='?' and i!=3:
			return (dp(cur+1,i+1)+3*dp(cur+1,i))%mod
		elif S[cur]=='?':
			return 3*dp(cur+1,i)%mod
		else:
			return dp(cur+1,i)%mod

print(dp(0,0)%mod)

Submission status: Runtime Error

Solution code:
S=input()
N=len(S)

import sys
sys.setrecursionlimit(200000)

from functools import lru_cache

@lru_cache(maxsize=None)
def dp(cur,i):
	if cur==N:
		if i==3:
			return 1
		else:
			return 0
	else:
		if S[cur]=='ABCD'[i]:
			return dp(cur+1,i+1)+dp(cur+1,i)
		elif S[cur]=='?':
			return dp(cur+1,i+1)+3*dp(cur+1,i)
		else:
			return dp(cur+1,i)

print(dp(0,0))

Submission status: Runtime Error

Solution code:
S=input()
N=len(S)

from functools import lru_cache

@lru_cache(maxsize=None)
def dp(cur,i):
	if cur==N:
		if i==3:
			return 1
		else:
			return 0
	else:
		if S[cur]=='ABCD'[i]:
			return dp(cur+1,i+1)+dp(cur+1,i)
		elif S[cur]=='?':
			return dp(cur+1,i+1)+3*dp(cur+1,i)
		else:
			return dp(cur+1,i)

print(dp(0,0))

Submission status: Runtime Error

Solution code:
S = input()
l = len(S)
d = {"A":1,"B":2,"C":3}

dp = [0 for _ in range(4)]
dp[0] = 1
for i in range(l):
    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] += dp[j-1] % mod

print(dp[3]%mod)

Submission status: Runtime Error

Solution code:
s=input()
x=len(s)
dp=[[0 for i in range(4)] for j in range(100005)]
for i in range(x,-1,-1):
    for j in range(3,-1,-1):
        if i==x:
            dp[i][j]=[0,1][j==3]
        else:
            dp[i][j]=dp[i+1][j]*([1,3][s[i]=="?"])
            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: Runtime Error

Solution code:
S = input()
dp = [[0 for i in range(4)] for i in range(len(S)+1)]
MOD = 10**9+7
dp[0][3] = 1
for i in range(len(S)):
    if S[i] == '?': k = 3
    else: k = 1
    for _ in range(k):
      for l in range(4)
        dp[i+1][l] += dp[i][l] 
    if S[i] == 'A':
        dp[i+1][0] +=  dp[i][3]
    elif S[i] == 'B':
        dp[i+1][1] +=  dp[i][0]
    elif S[i] == 'C':
        dp[i+1][2] += dp[i][1]
    else:
        dp[i+1][0] += dp[i][3]
        dp[i+1][1] += dp[i][0]
        dp[i+1][2] += dp[i][1]
    for j in range(4):
        if dp[i][j] > MOD: dp[i][j] %= MOD
print(dp[len(S)][2]%MOD)

Submission status: Runtime Error

Solution code:
s = input()

ans = 0

q = s.count('?')

rc = [0]
rq = [0]
la = [0]
lq = [0]

for i in range(len(s)-1):
    if s[len(s)-i-1]=='C':
        rc.append(rc[-1]+1)
    else:
        rc.append(rc[-1])
    if s[len(s)-i-1]=='?':
        rq.append(rq[-1] + 1)
    else:
        rq.append(rq[-1])
    if s[i]=='A':
        la.append(la[-1]+1)
    else:
        la.append(la[-1])
    if s[i]=='?':
        lq.append(lq[-1]+1)
    else:
        lq.append(lq[-1])
rc.reverse()
rq.reverse()

t = 10**9+7

for i in range(len(s)):
    if s[i]=='B' or s[i]=='?':
        lq_ = lq[i]-1
        rq_ = rq[i]-1
        l = 1
        r = 1
        while lq_ > 20:
            l *= 3**20%t
            lq -=20
        while rq_ > 20:
            r *= 3**20%t
            rq_ -= 20
        l *= 3**lq_%t
        r *= 3**rq_%t
        l %= t
        r %= t
        ans += l*r*(3*la[i]+lq[i])*(3*rc[i]+rq[i]) % t

print(int(ans%t))

Submission status: Runtime Error

Solution code:
s = input()

ans = 0

q = s.count('?')

rc = [0]
rq = [0]
la = [0]
lq = [0]

for i in range(len(s)-1):
    if s[len(s)-i-1]=='C':
        rc.append(rc[-1]+1)
    else:
        rc.append(rc[-1])
    if s[len(s)-i-1]=='?':
        rq.append(rq[-1] + 1)
    else:
        rq.append(rq[-1])
    if s[i]=='A':
        la.append(la[-1]+1)
    else:
        la.append(la[-1])
    if s[i]=='?':
        lq.append(lq[-1]+1)
    else:
        lq.append(lq[-1])
rc.reverse()
rq.reverse()

t = 10**9+7

for i in range(len(s)):
    if s[i]=='B' or s[i]=='?':
        lq_ = lq[i]-1
        rq_ = rq[i]-1
        l = 1
        r = 1
        while lq_ > 20:
            l *= 3**20%t
            lq -=20
        while rq_ > 20:
            r *= 3**20%t
            rq_ -= 20
        l *= 3**lq_%t
        r *= 3**rq_%t
        ans += l*r*(3*la[i]+lq[i])*(3*rc[i]+rq[i]) % t

print(int(ans%t))

Submission status: Runtime Error

Solution code:
s = input()

ans = 0

q = s.count('?')

rc = [0]
rq = [0]
la = [0]
lq = [0]

for i in range(len(s)-1):
    if s[len(s)-i-1]=='C':
        rc.append(rc[-1]+1)
    else:
        rc.append(rc[-1])
    if s[len(s)-i-1]=='?':
        rq.append(rq[-1] + 1)
    else:
        rq.append(rq[-1])
    if s[i]=='A':
        la.append(la[-1]+1)
    else:
        la.append(la[-1])
    if s[i]=='?':
        lq.append(lq[-1]+1)
    else:
        lq.append(lq[-1])
rc.reverse()
rq.reverse()


for i in range(len(s)):
    if s[i]=='B' or s[i]=='?':
        ans += la[i]*(3**lq[i])*rc[i]*(3**rq[i]) % (10**9+7)
        ans += lq[i]*(3**(lq[i]-1))*rc[i]*(3**rq[i]) % (10**9+7)
        ans += la[i]*(3**lq[i])*rq[i]*(3**(rq[i]-1)) % (10**9+7)
        ans += lq[i]*(3**(lq[i]-1))*rq[i]*(3**(rq[i]-1)) % (10**9+7)

print(int(ans%(10**9+7)))

Submission status: Runtime Error

Solution code:
s = input()

ans = 0

q = s.count('?')

rc = [0]
rq = [0]
la = [0]
lq = [0]

for i in range(len(s)-1):
    if s[len(s)-i-1]=='C':
        rc.append(rc[-1]+1)
    else:
        rc.append(rc[-1])
    if s[len(s)-i-1]=='?':
        rq.append(rq[-1] + 1)
    else:
        rq.append(rq[-1])
    if s[i]=='A':
        la.append(la[-1]+1)
    else:
        la.append(la[-1])
    if s[i]=='?':
        lq.append(lq[-1]+1)
    else:
        lq.append(lq[-1])
rc.reverse()
rq.reverse()


for i in range(len(s)):
    if s[i]=='B' or s[i]=='?':
        ans += la[i]*(3**lq[i])*rc[i]*(3**rq[i]) + lq[i]*(3**(lq[i]-1))*rc[i]*(3**rq[i]) + la[i]*(3**lq[i])*rq[i]*(3**(rq[i]-1)) + lq[i]*(3**(lq[i]-1))*rq[i]*(3**(rq[i]-1))
        ans %= 10**9+7

print(int(ans))

Submission status: Runtime Error

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)
    aa = [0 for _ in range(n+1)]
    cc = [0 for _ in range(n+1)]
    q = [0 for _ in range(n+1)]
    for i in range(n):
        aa[i+1] += aa[i] + int(S[i] == "A")
        cc[i+1] += cc[i] + int(S[i] == "C")
        q[i+1] += q[i] + int(S[i] == "?")

    ans = 0
    MOD = 10 ** 9 + 7
    for i in range(1, n-1):
        a = aa[i]
        c = cc[n] - cc[i+1]
        l = q[i]
        r = q[n] - q[i+1]
        # ABC の作り方
        # AB?: ? 1つをCに割り当てる
        # ?BC: ? 1つをAに割り当てる
        # ?B?: ? 2つをACに割り当てる
        if S[i] in ("B", "?"):
            ac = a * c * pow(3, l + r, MOD)
            aq, qc, qq = (0, 0, 0)
            if l + r - 1:
                p = pow(3, l + r - 1, MOD)
                aq = a * r * p
                qc = l * c * p
            if l + r - 1:
                qq = l * r * pow(3, l + r - 2, MOD)
            # print(a, c, l, r, ((l+r, l+r-1, l+r-2)), (ac, aq, qc, qq))
            # 3^x: xが負になるときに少数になってしまうので、float -> int にする必要がある
            # 上記が重いのでTLE: pow+mod引数で対応
            ans += ac + aq + qc + qq
            ans %= MOD

    return ans


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

    print(ans)


def TLE(S):
    """文字列全列挙
    ?をすべて置き換えるパターンを作成し
    それについてABC数を算出
    """
    s = list(S)
    qi = [i for i, c in enumerate(S) if c == "?"]
    nq = len(qi)

    def rec(i):
        if i == nq:
            return n_ABC(s)

        ans = 0
        for x in list("ABC"):
            s[qi[i]] = x
            ans += rec(i+1)

        return ans

    ans = rec(0)
    return ans


def n_ABC(S):
    """3^Q を考えていないパターン がABCを求めるパターンになっていた
    """
    ans = 0
    n = len(S)
    for i in range(n):
        for j in range(i+1, n):
            for k in range(j+1, n):
                # print(i, j, k, S[i] + S[j] + S[k])
                if S[i] in ("A", "?") and S[j] in ("B", "?") and S[k] in ("C", "?"):
                    ans += 1

    return ans


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
mod=10**9+7
s=input()
n=len(s)
Sum_A=[0]*(n+1)
Sum_B=[0]*(n+1)
Sum_C=[0]*(n+1)
Sum_q=[0]*(n+1)
for i in range(1, n+1):
    Sum_A[i]=Sum_A[i-1]
    Sum_C[i]=Sum_C[i-1]
    Sum_q[i]=Sum_q[i-1]
    if s[i-1]=='A':
        Sum_A[i]+=1
    elif s[i-1]=='C':
        Sum_C[i]+=1
    elif s[i-1]=='?':
        Sum_q[i]+=1
ans=0
def count(x, q):
    return int(x*pow(3, q, mod)+q*pow(3, (q-1), mod))
for i in range(n):
    if s[i]=='B' or s[i]=='?':
        ans+=count(Sum_A[i], Sum_q[i])*count(Sum_C[n]-Sum_C[i+1], Sum_q[n]-Sum_q[i+1])
        ans%=mod
print(ans)

Submission status: Runtime Error

Solution code:
#速度テスト　
mod = 1000000007

def add(a, b):
    return (a + b) % mod


S = input()
A = [[0 for _ in range(len(S)+1)] for _ in range(5)]

A[0][0] = 1;
for i, s in enumerate(S):
    for j in range(5):
        if (s != '?'):
            A[i+1][j] = add(A[i+1][j], A[i][j])
        else:
            A[i+1][j] = add(A[i+1][j], A[i][j] * 3 % mod);

    if (s == 'A' or s == '?'):
        A[i+1][1] = add(A[i+1][1], A[i][0])
    elif (s == 'B' or s == '?'):
        A[i+1][2] = add(A[i+1][2], A[i][1])
    elif (s == 'C' or s == '?'):
        A[i+1][3] = add(A[i+1][3], A[i][2])


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

Submission status: Runtime Error

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    def dfs(i,k):
        if i == d:
            l.append(k)
        else:
            for j in range(2):
                dfs(i+1,k+[j])
    d,g = LI()
    p = LIR(d)
    ans = float("inf")
    l = []
    dfs(0,[])
    for k in l:
        m = 0
        o = 0
        q = [[p[i][0],p[i][1]] for i in range(d)]
        for i in range(d):
            if k[i]:
                o += q[i][0]
                m += q[i][0]*(i+1)*100+q[i][1]
                q[i][0] = 0
        while m < g:
            for i in range(d)[::-1]:
                for j in range(q[i][0]):
                    m += (i+1)*100
                    o += 1
                    if m >= g:break
                if m >= g:break
        ans = min(ans,o)
    print(ans)
#D
def D():
    s = S()
    n = len(s)
    dp = [[0,0,0,0] for i in range(n+1)]
    dp[0][0] = 1
    for i in range(n):
        if s[i] == "?":
            dp[i+1] = [3*dp[i][0]%mod,3*dp[i][1]%mod,3*dp[i][2]%mod,3*dp[i][3]%mod]
        else:
            dp[i+1] = dp[i].copy()
        if s[i] == "A":
            dp[i+1][1] += dp[i][0]
            dp[i+1][1] %= mod
        elif s[i] == "B":
            dp[i+1][2] += dp[i][1]
            dp[i+1][2] %= mod
        elif s[i] == "C":
            dp[i+1][3] += dp[i][2]
            dp[i+1][3] %= mod
        else:
            dp[i+1][1] += dp[i][0]
            dp[i+1][2] += dp[i][1]
            dp[i+1][3] += dp[i][2]
            dp[i+1][1] %= mod
            dp[i+1][2] %= mod
            dp[i+1][3] %= mod
    print(dp[n][3])
#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    D()

Submission status: Runtime Error

Solution code:
a

Submission status: Runtime Error

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 % MODE
        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: Runtime Error

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

Submission status: Runtime Error

Solution code:
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)

Submission status: Runtime Error

Solution code:
a = list(input())

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

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

Submission status: Runtime Error

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

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

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

Submission status: Runtime Error

Solution code:
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)