human
I found an interesting problem on https://atcoder.jp/contests/abc104/tasks/abc104_d:
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-----
A??C

-----Sample Output-----
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.

I tried it in Python, but could not do it. Can you solve it?
assistant
#Here is Python program to find the sum of the ABC numbers of all these strings.

# def C(n, r ,mod=10**9+7):
#     if n-r<r: r=n-r
#     if r == 0: return 1
#     if r == 1: return n
# 
#     numerator = [n - r + k + 1 for k in range(r)]
#     denominator = [k + 1 for k in range(r)]
# 
#     for p in range(2,r+1):
#         pivot = denominator[p - 1]
#         if pivot > 1:
#             offset = (n - r) % p
#             for k in range(p-1,r,p):
#                 numerator[k - offset] /= pivot
#                 denominator[k] /= pivot
# 
#     result = 1
#     for k in range(r):
#         if numerator[k] > 1:
#             result *= int(numerator[k]) %mod
# 
#     return result % mod

A=list(input())
n=len(A)
mod=10**9+7
ans=0
numa= A[0]=="A" 
numa_= A[0]=="?"
numc=A[2:].count("C")
numc_= A[2:].count("?")

for i in range(1,n-1):
    #print(numa,numa_,numc,numc_)
    apro=cpro=0
    if A[i]=="B" or A[i]=="?":
        # for k in range(numa_+1):
        #     apro+= (((C(numa_,k)*pow(2,numa_-k,mod))%mod)*(numa+k))%mod
        # for k in range(numc_+1):
        #     cpro+= (((C(numc_,k)*pow(2,numc_-k,mod))%mod)*(numc+k))%mod
        #print(apro,cpro)
        apro= ((3*numa+numa_)*pow(3,(numa_-1),mod))%mod
        cpro= ((3*numc+numc_)*pow(3,(numc_-1),mod))%mod
        ans+= (apro*cpro)%mod
        ans%=mod
    if A[i] == "A":
        numa+=1
    if A[i]=="?":
        numa_+=1
    if A[i+1] =="C":
        numc-=1
    if A[i+1]=="?":
        numc_-=1
print(ans)