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:
# -*- 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

memo = [-999 for i in range(len(S)+1)]
def ab(x):
    if memo[len(x)] >= 0:
        return memo[len(x)]
    if len(x) == 1:
        return 0
    if x[len(x)-1] == '?':
        memo[len(x)]= 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)
        return memo[len(x)]
    elif x[len(x)-1] == 'B':
        memo[len(x)]=  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)
        return memo[len(x)]
    else:
        memo[len(x)]= ab(x[:-1])
        return memo[len(x)]
#ab_ = [ab(S[:i+1]) for i in range(len(S))]
#print(ab(S))

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

Submission status: Runtime Error

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

@author: Yamazaki Kenichi
"""
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) == 2:
        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: Runtime Error

Solution code:
from math import pow

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

Submission status: Runtime Error

Solution code:
from math import pow

  
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)+c) % mod
  if i == "?":
    abc = (abc*3 + bc) % mod
    bc = (bc*3 + c) % mod 
    c = (pow(3,q) + c*3) % mod
    q += 1
print(int(abc))

Submission status: Runtime Error

Solution code:
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y/2)**2 % mod
    else            : return power(x, y/2)**2 * x % mod

  
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 = (power(3,q)+c) % mod
  if i == "?":
    abc = (abc*3 + bc) % mod
    bc = (bc*3 + c) % mod 
    c = (power(3,q) + c*3) % mod
    q += 1
print(abc)

Submission status: Runtime Error

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

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

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

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

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

print(ans)

Submission status: Runtime Error

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

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

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

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

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

print(int(ans))

Submission status: Runtime Error

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

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

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

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

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

print(int(ans))

Submission status: Runtime Error

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

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

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

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

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

print(int(ans))

Submission status: Runtime Error

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

"""
参考：http://tutuz.hateblo.jp/entry/2018/08/06/074104
・別解
・Bの位置を決めて左右パターンを全部数え上げる。
"""

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

ans = 0
for i in range(len(S)):
    if S[i] == '?' or S[i] == 'B':
        # kよりも左にあるAの個数
        a = S[:i].count('A')
        # kよりも左にある?の個数
        lq = S[:i].count('?')
        # kよりも右にあるCの個数
        c = S[i+1:].count('C')
        # kよりも右にある?の個数
        rq = S[i+1:].count('?')

        # (A,B,C) と選ぶ場合(後ろの3**lq * 3**rqは使わなかった?の分)
        case1 = a* c * 3**lq * 3**rq
        # (A,B,?) と選ぶ場合
        case2 = a * rq * 3**lq * 3**(rq-1)
        # (?,B,C) と選ぶ場合
        case3 = lq * c * 3**(lq-1) * 3**rq
        # (?,B,?) と選ぶ場合
        case4 = lq * rq * 3**(lq-1) * 3**(rq-1)

        ans = (ans + case1 + case2 + case3 + case4) % MOD

print(int(ans))

Submission status: Runtime Error

Solution code:
import sys
import collections
from collections import Counter
# from collections import deque
# from collections import defaultdict
import itertools
# from itertools import accumulate
# from itertools import permutations
# from itertools import combinations
# from itertools import takewhile
from itertools import compress
import functools
# from functools import reduce
import math
# from math import gcd
# from math import inf
# from math import ceil
# from math import floor
# from math import log10
# from math import log2
# from math import log
from math import factorial

MOD = (10 ** 9) + 7
# import re

# input = sys.stdin.readline
sys.setrecursionlimit(10000)

S = input()
N = len(S)


def funcA(idx, q):
    if idx >= N:
        return 0
    ret = 0
    if S[idx] == "A" or S[idx] == "?":
        ret += funcB(idx + 1, q)
    q += 1 if S[idx] == "?" else 0
    ret += funcA(idx + 1, q)
    return ret


def funcB(idx, q):
    if idx >= N:
        return 0
    ret = 0
    if S[idx] == "B" or S[idx] == "?":
        ret += funcC(idx + 1, q)
    q += 1 if S[idx] == "?" else 0
    ret += funcB(idx + 1, q)
    return ret


def funcC(idx, q):
    if idx >= N:
        return 0
    ret = 0
    if S[idx] == "C" or S[idx] == "?":
        addQ = S[idx + 1:].count("?")
        ret += 3 ** (q + addQ)

    q += 1 if S[idx] == "?" else 0
    ret += funcC(idx + 1, q)
    return ret


ans = funcA(0, 0)

print(ans % MOD)

Submission status: Runtime Error

Solution code:
import sys
import collections
from collections import Counter
# from collections import deque
# from collections import defaultdict
import itertools
# from itertools import accumulate
# from itertools import permutations
# from itertools import combinations
# from itertools import takewhile
from itertools import compress
import functools
# from functools import reduce
import math
# from math import gcd
# from math import inf
# from math import ceil
# from math import floor
# from math import log10
# from math import log2
# from math import log
from math import factorial

MOD = (10 ** 9) + 7
# import re

# input = sys.stdin.readline

S = input()
N = len(S)


def funcA(idx, q):
    if idx >= N:
        return 0
    ret = 0
    if S[idx] == "A" or S[idx] == "?":
        ret += funcB(idx + 1, q)
    q += 1 if S[idx] == "?" else 0
    ret += funcA(idx + 1, q)
    return ret


def funcB(idx, q):
    if idx >= N:
        return 0
    ret = 0
    if S[idx] == "B" or S[idx] == "?":
        ret += funcC(idx + 1, q)
    q += 1 if S[idx] == "?" else 0
    ret += funcB(idx + 1, q)
    return ret


def funcC(idx, q):
    if idx >= N:
        return 0
    ret = 0
    if S[idx] == "C" or S[idx] == "?":
        addQ = S[idx + 1:].count("?")
        ret += 3 ** (q + addQ)

    q += 1 if S[idx] == "?" else 0
    ret += funcC(idx + 1, q)
    return ret


ans = funcA(0, 0)

print(ans % MOD)

Submission status: Runtime Error

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


MOD = 10**9 + 7
S = 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)

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <string>
#define ll long long
using namespace std;

const int MOD = 1000000007;

int main() {
  string S;
  cin >> S;

  int len = S.size();
  ll a = 0, ab = 0, abc = 0, all_s = 1;

  for (int i = 0; i < len; i++) {
    if (S[i] == 'A')
      a = (a + all_s) % MOD;
    else if (S[i] == 'B')
      ab = (ab + a) % MOD;
    else if (S[i] == 'C')
      abc = (abc + ab) % MOD;
    else if (S[i] == '?') {
      abc   = (abc * 3 + ab) % MOD;
      ab    = (ab * 3 + a) % MOD;
      a     = (a * 3 + all_s) % MOD;
      all_s = (all_s * 3) % MOD;
    }
  }
  cout << abc << endl;
}

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**7)

modulus = 10 ** 9 + 7
s = input()


def dp(i, j):
    """
    dynamic programming for abc 104
    :param i: index of the given string
    :param j: count of letters of composed string (like 'ABC')
    :return: the number of cases
    """
    if i == n:
        if j == 3:
            return 1
        else:
            return 0

    if i < n and j == 3:
        m = 3 if s[i] == '?' else 1
        return m * dp(i + 1, 3) % modulus

    if i < n and j < 3:
        m1 = 3 if s[i] == '?' else 1
        m2 = 1 if s[i] == '?' or s[i] == 'ABC'[j] else 0

        _pass = m1 * dp(i + 1, j) % modulus
        _take = m2 * dp(i + 1, j + 1) % modulus

        return _pass + _take


print(dp(0, 0))

Submission status: Runtime Error

Solution code:
class ABC104:
    modulus = 10 ** 9 + 7

    def __init__(self, s):
        self.s = s
        self.n = len(s)

    def dp(self, i, j):
        """
        dynamic programming for abc 104
        :param i: index of the given string
        :param j: count of letters of composed string (like 'ABC')
        :return: the number of cases
        """
        if i == self.n:
            if j == 3:
                return 1
            else:
                return 0

        if i < self.n and j == 3:
            m = 3 if self.s[i] == '?' else 1
            return m * self.dp(i + 1, 3) % self.modulus

        if i < self.n and j < 3:
            m1 = 3 if self.s[i] == '?' else 1
            m2 = 1 if self.s[i] == '?' or self.s[i] == 'ABC'[j] else 0

            _pass = m1 * self.dp(i + 1, j) % self.modulus
            _take = m2 * self.dp(i + 1, j + 1) % self.modulus

            return _pass + _take


if __name__ == '__main__':
    import sys
    sys.setrecursionlimit(10**15)

    abc = ABC104(input())
    print(abc.dp(0, 0))

Submission status: Runtime Error

Solution code:
class ABC104:
    modulus = 10 ** 9 + 7

    def __init__(self, s):
        self.s = s
        self.n = len(s)

    def dp(self, i, j):
        """
        dynamic programming for abc 104
        :param i: index of the given string
        :param j: count of letters of composed string (like 'ABC')
        :return: the number of cases
        """
        if i == self.n:
            if j == 3:
                return 1
            else:
                return 0

        if i < self.n and j == 3:
            m = 3 if self.s[i] == '?' else 1
            return m * self.dp(i + 1, 3) % self.modulus

        if i < self.n and j < 3:
            m1 = 3 if self.s[i] == '?' else 1
            m2 = 1 if self.s[i] == '?' or self.s[i] == 'ABC'[j] else 0

            _pass = m1 * self.dp(i + 1, j) % self.modulus
            _take = m2 * self.dp(i + 1, j + 1) % self.modulus

            return _pass + _take


if __name__ == '__main__':
    import sys
    sys.setrecursionlimit(10000)

    abc = ABC104(input())
    print(abc.dp(0, 0))

Submission status: Runtime Error

Solution code:
class ABC104:
    modulus = 10 ** 9 + 7

    def __init__(self, s):
        self.s = s
        self.n = len(s)

    def dp(self, i, j):
        """
        dynamic programming for abc 104
        :param i: index of the given string
        :param j: count of letters of composed string (like 'ABC')
        :return: the number of cases
        """
        if i == self.n:
            if j == 3:
                return 1
            else:
                return 0

        if i < self.n and j == 3:
            m = 3 if self.s[i] == '?' else 1
            return m * self.dp(i + 1, 3) % self.modulus

        if i < self.n and j < 3:
            m1 = 3 if self.s[i] == '?' else 1
            m2 = 1 if self.s[i] == '?' or self.s[i] == 'ABC'[j] else 0

            _pass = m1 * self.dp(i + 1, j) % self.modulus
            _take = m2 * self.dp(i + 1, j + 1) % self.modulus

            return  _pass + _take


if __name__ == '__main__':
    abc = ABC104(input())
    print(abc.dp(0, 0))

Submission status: Runtime Error

Solution code:
def ABC104D():
    S = list(input())
    A_cnt = 0
    B_cnt = 0
    C_cnt = 0
    Q_cnt = 0
    ans = 0
    for i in S:
        if i == "A":
            A_cnt += 1
        elif i == "B":
            B_cnt += 1
        elif i == "C":
            C_cnt += 1
        else:
            Q_cnt += 1
    for i in range(Q_cnt + 1):
        for j in range(Q_cnt - i + 1):
            k = Q_cnt - i - j
            if A_cnt + i > 0 and B_cnt + j > 0 and C_cnt + k > 0:
                f_i = math.factorial(i)
                f_j = math.factorial(j)
                f_k = math.factorial(k)
                if f_i == 0:
                    f_i = 1
                if f_j == 0:
                    f_j = 1
                if f_k == 0:
                    f_k = 1
                ans += (A_cnt + i) * (B_cnt + j) * (C_cnt + k) * math.factorial(Q_cnt) // f_i // f_j // f_k
                print(ans, i, j, k, A_cnt + i, B_cnt + j, C_cnt + k)
                print(math.factorial(Q_cnt), f_i, f_j, f_k)
    print(ans)

ABC104D()

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
s = input()
dp = [[1, 0, 0, 0]]
for s in S:
    tmp = [0, 0, 0, 0]
    if s == 'A' or s == '?':
        tmp[0] += dp[-1][0]
        tmp[1] += dp[-1][1]
        tmp[2] += dp[-1][2]
        tmp[3] += dp[-1][3]
        tmp[1] += dp[-1][0]
    if s == 'B' or s == '?':
        tmp[0] += dp[-1][0]
        tmp[1] += dp[-1][1]
        tmp[2] += dp[-1][2]
        tmp[3] += dp[-1][3]
        tmp[2] += dp[-1][1]
    if s == 'C' or s == '?':
        tmp[0] += dp[-1][0]
        tmp[1] += dp[-1][1]
        tmp[2] += dp[-1][2]
        tmp[3] += dp[-1][3]
        tmp[3] += dp[-1][2]
    dp.append(tmp)
print(dp[-1][-1]%(10**9+7))

Submission status: Runtime Error

Solution code:
S = input()
l = len(S)
A,B,C,q = [0]*l,[0]*l,[0]*l,[0]*l
inf = 1000000007
for i in range(l):
    if S[i] == 'A':
        A[i] = 1
    elif S[i] == 'B':
        B[i] = 1
    elif S[i] == 'C':
        C[i] = 1
    else:
        q[i] = 1
    A[]

for i in range(l-1):
    A[i+1] += A[i]
    B[i+1] += B[i]
    C[i+1] += C[i]
    q[i+1] += q[i]

ans = 0
for i in range(1,l-1):
    if S[i] == 'B':
        ans += (A[i-1]) * (C[-1]-C[i]) * (3**q[-1])%inf
        ans %= inf
        if q[-1] >= 1:
            ans += (q[i-1]) * (C[-1] - C[i]) * (3**(q[-1]-1)%inf)
            ans %= inf
            ans += (A[i-1]) * (q[-1] - q[i]) * (3**(q[-1]-1)%inf)
            ans %= inf
        if q[-1] >= 2:
            ans += (q[i-1]) * (q[-1] - q[i]) * (3**(q[-1]-2)%inf)
            ans %= inf

    elif S[i] == '?':
        ans += (A[i-1]) * (C[-1]-C[i]) * (3**(q[-1]-1)%inf)
        ans %= inf
        if q[-1] >= 2:
            ans += (q[i-1]) * (C[-1] - C[i]) * (3**(q[-1]-2)%inf)
            ans %= inf
            ans += (A[i-1]) * (q[-1] - q[i]) * (3**(q[-1]-2)%inf)
            ans %= inf
        if q[-1] >= 3:
            ans += (q[i-1]) * (q[-1] - q[i]) * (3**(q[-1]-3)%inf)
            ans %= inf

print(ans%inf)

Submission status: Runtime Error

Solution code:
import numpy as np
S = input()
n = len(S)
A, C, L, R = np.zeros(n), np.zeros(n), np.zeros(n), np.zeros(n)
a, c, l, r = 0, 0, 0, 0
for i in range(n):
	A[i] = a
	L[i] = l
	C[n-1-i] = c
	R[n-1-i] = r
	if(S[i] == 'A'):
		a += 1
	elif(S[i] == '?'):
		l += 1
	if(S[n-1-i] == 'C'):
		c += 1
	elif(S[n-1-i] == '?'):
		r += 1
ans = 0
for i in range(n):
	if(S[i] == 'B' or S[i] == '?'):
		left  = A[i] if L[i] == 0 else A[i]*(3**L[i])+3**(L[i]-1)
		right = C[i] if R[i] == 0 else C[i]*(3**R[i])+3**(R[i]-1)
		ans += left*right
		ans %= 10**9+7

print(int(ans))
#print(A, C, L, R)
#print(n)

Submission status: Runtime Error

Solution code:
s = input()
dp = [0 for _ in range(0,4)]
dp[3] = 1
dp[0] = 0
dp[1] = 0
dp[2] = 0
abc = "ABC".index
mod = 10**9 + 7
for i in range(len(s)-1,-1,-1):
    if s[i] == "?":
        dp = [
        (dp[0]*3+ dp[1])%mod
        ,(dp[1]*3+ dp[2])%mod
        ,(dp[2]*3 + dp[3])%mod
        ,(dp[3]*3)%mod
        ]
    else:
        num = abc(s[i])
        dp[i][num] += dp[i+1][num+1] % mod
# for i in range(len(s),-1,-1):
#     print(dp[i])
print(dp[0][0] %mod)

Submission status: Runtime Error

Solution code:
S=raw_input()

M=10**9+7

all=1
abc=0
ab=0
a=0

for x in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		abc+=ab

	if x=="?":
		abc=abc*3+ab
		ab=ab*3+a
		a= a*3+all
		all*=3

	abc%=M
	ab%=M
	a%=M
	ans%=M


print abc%M

Submission status: Runtime Error

Solution code:
import sys

S = input()

DEVIDER = 10**9 + 7


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

def mul(a, b):
    return (a % DEVIDER) * (b % DEVIDER) % DEVIDER

cache = [[None for _ in range(4)] for _ in range(len(S) + 1)]


def check(s, j):
    if j == 0 and s == 'A':
        return True
    if j == 1 and s == 'B':
        return True
    if j == 2 and s == 'C':
        return True
    return False

def dp(i, j):
    if not cache[i][j] == None:
        return cache[i][j]

    if i == len(S) and j == 3:
        # end of task
        return 1
    elif i == len(S) and j < 3:
        # fail
        return 0
    elif i < len(S) and j == 3:
        # next
        if S[i] == "?":
            cache[i][j] = (3 * (dp(i + 1, 3) % DEVIDER)) % DEVIDER
            return cache[i][j]
        else:
            cache[i][j] = dp(i + 1, 3)
            return cache[i][j]
    else:
        # i < len(S) and j < 3
        if S[i] == "?":
            pre = (3 * (dp(i + 1, j) % DEVIDER)) % DEVIDER
            lat = dp(i + 1, j + 1)
            cache[i][j] = (pre + lat) % DEVIDER
            return cache[i][j]
        if check(S[i], j):
            cache[i][j] = (dp(i + 1, j) + dp( i + 1, j + 1)) % DEVIDER
            return cache[i][j]
        cache[i][j] = dp(i + 1, j)
        return cache[i][j]


ret = dp(0, 0)
print(ret)

Submission status: Runtime Error

Solution code:
import sys
from functools import lru_cache

S = input()

DEVIDER = 10**9 + 7


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

def mul(a, b):
    return (a % DEVIDER) * (b % DEVIDER) % DEVIDER


@lru_cache(maxsize=32)
def check(s, j):
    if j == 0 and s == 'A':
        return True
    if j == 1 and s == 'B':
        return True
    if j == 2 and s == 'C':
        return True
    return False

@lru_cache(maxsize=None)
def dp(i, j):
    if i == len(S) and j == 3:
        # end of task
        return 1
    elif i == len(S) and j < 3:
        # fail
        return 0
    elif i < len(S) and j == 3:
        # next
        if S[i] == "?":
            return (3 * (dp(i + 1, 3) % DEVIDER)) % DEVIDER
        else:
            return dp(i + 1, 3)
    else:
        # i < len(S) and j < 3
        if S[i] == "?":
            pre = (3 * (dp(i + 1, j) % DEVIDER)) % DEVIDER
            lat = dp(i + 1, j + 1)
            return (pre + lat) % DEVIDER
        if check(S[i], j):
            return (dp(i + 1, j) + dp( i + 1, j + 1)) % DEVIDER
        return dp(i + 1, j)


ret = dp(0, 0)
print(ret)

Submission status: Runtime Error

Solution code:
import sys
from functools import lru_cache

S = input()

DEVIDER = 10**9 + 7


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

def mul(a, b):
    return (a % DEVIDER) * (b % DEVIDER) % DEVIDER

cache_size = len(S) * 4

@lru_cache(maxsize=32)
def check(s, j):
    if j == 0 and s == 'A':
        return True
    if j == 1 and s == 'B':
        return True
    if j == 2 and s == 'C':
        return True
    return False

@lru_cache(maxsize=cache_size)
def dp(i, j):
    if i == len(S) and j == 3:
        # end of task
        return 1
    elif i == len(S) and j < 3:
        # fail
        return 0
    elif i < len(S) and j == 3:
        # next
        if S[i] == "?":
            return (3 * (dp(i + 1, 3) % DEVIDER)) % DEVIDER
        else:
            return dp(i + 1, 3)
    else:
        # i < len(S) and j < 3
        if S[i] == "?":
            pre = (3 * (dp(i + 1, j) % DEVIDER)) % DEVIDER
            lat = dp(i + 1, j + 1)
            return (pre + lat) % DEVIDER
        if check(S[i], j):
            return (dp(i + 1, j) + dp( i + 1, j + 1)) % DEVIDER
        return dp(i + 1, j)


ret = dp(0, 0)
print(ret)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)
from functools import lru_cache

S = input()

DEVIDER = 10**9 + 7


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

def mul(a, b):
    return (a % DEVIDER) * (b % DEVIDER) % DEVIDER

cache_size = len(S) * 4

@lru_cache(maxsize=32)
def check(s, j):
    if j == 0 and s == 'A':
        return True
    if j == 1 and s == 'B':
        return True
    if j == 2 and s == 'C':
        return True
    return False

@lru_cache(maxsize=cache_size)
def dp(i, j):
    if i == len(S) and j == 3:
        # end of task
        return 1
    elif i == len(S) and j < 3:
        # fail
        return 0
    elif i < len(S) and j == 3:
        # next
        if S[i] == "?":
            return mul(3,  dp(i + 1, 3))
        else:
            return dp(i + 1, 3)
    else:
        # i < len(S) and j < 3
        if S[i] == "?":
            return add(mul(3, dp(i + 1, j)),  dp(i + 1, j + 1))
        if check(S[i], j):
            return add(dp(i + 1, j), dp( i + 1, j + 1))
        return dp(i + 1, j)


ret = dp(0, 0)
print(ret)

Submission status: Runtime Error

Solution code:
from functools import lru_cache

S = input()

DEVIDER = 10**9 + 7


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

def mul(a, b):
    return (a % DEVIDER) * (b % DEVIDER) % DEVIDER

cache_size = len(S) * 4

@lru_cache(maxsize=32)
def check(s, j):
    if j == 0 and s == 'A':
        return True
    if j == 1 and s == 'B':
        return True
    if j == 2 and s == 'C':
        return True
    return False

@lru_cache(maxsize=cache_size)
def dp(i, j):
    if i == len(S) and j == 3:
        # end of task
        return 1
    elif i == len(S) and j < 3 :
        # fail
        return 0
    elif i < len(S) and j == 3:
        # next
        if S[i] == "?":
            return mul(3,  dp(i + 1, 3))
        else:
            return dp(i + 1, 3)
    else:
        # i < len(S) and j < 3
        if S[i] == "?":
            return add(mul(3, dp(i + 1, j)),  dp(i + 1, j + 1))
        if check(S[i], j):
            return add(dp(i + 1, j), dp( i + 1, j + 1))
        return dp(i + 1, j)


ret = dp(0, 0)
print(ret)