AtCoder Beginner Contest 104 - We Love ABC

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.

Difficulty: MEDIUM

Starter code:

Solutions:
def main():
	MOD = 10 ** 9 + 7
	s = input()
	n = len(s)
	acc_a = [0] * (n + 1)
	acc_c = [0] * (n + 1)
	acc_q = [0] * (n + 1)
	a = 0
	c = 0
	q = 0
	for (i, char) in enumerate(s, 1):
		if char == 'A':
			a += 1
		elif char == 'C':
			c += 1
		elif char == '?':
			q += 1
		acc_a[i] = a
		acc_c[i] = c
		acc_q[i] = q
	sq = [1]
	for _ in range(acc_q[n]):
		sq.append(sq[-1] * 3 % MOD)
	ans = 0
	qn = acc_q[n]
	for (i, char) in enumerate(s, 1):
		if char == 'B' or char == '?':
			is_q = int(char == '?')
			rq = acc_q[n] - acc_q[i]
			rc = acc_c[n] - acc_c[i]
			t = 0
			if qn - is_q >= 0:
				t += acc_a[i - 1] * rc * sq[acc_q[n] - is_q]
			if qn - 1 - is_q >= 0:
				t += acc_a[i - 1] * rq * sq[acc_q[n] - 1 - is_q]
				t += acc_q[i - 1] * rc * sq[acc_q[n] - 1 - is_q]
			if qn - 2 - is_q >= 0:
				t += acc_q[i - 1] * rq * sq[acc_q[n] - 2 - is_q]
			t %= MOD
			ans = (ans + t) % MOD
	print(ans)

def __starting_point():
	main()
__starting_point()


s = input()
mod = 10 ** 9 + 7
(a, ab, abc) = (0, 0, 0)
q = 0
for c in s:
	if c == 'A':
		a = (a + pow(3, q, mod)) % mod
	elif c == 'B':
		ab = (a + ab) % mod
	elif c == 'C':
		abc = (ab + abc) % mod
	else:
		(a, ab, abc) = ((3 * a + pow(3, q, mod)) % mod, (3 * ab + a) % mod, (3 * abc + ab) % mod)
		q += 1
print(abc)


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)


inf = 1000000007
a = 0
ab = 0
abc = 0
r = 1
s = input()
for c in s:
	if c == 'A':
		a += r
	elif c == 'B':
		ab += a
	elif c == 'C':
		abc += ab
	else:
		abc = abc * 3 + ab
		ab = ab * 3 + a
		a = a * 3 + r
		r *= 3
	a %= inf
	ab %= inf
	abc %= inf
	r %= inf
print(abc)


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


M = 10 ** 9 + 7
(N, A, AB, ABC) = (1, 0, 0, 0)
idx = {'A': 1, 'B': 2, 'C': 3}
for c in input():
	if c == '?':
		(N, A, AB, ABC) = (N * 3 % M, (A * 3 + N) % M, (AB * 3 + A) % M, (ABC * 3 + AB) % M)
	else:
		dp = [N, A, AB, ABC]
		dp[idx[c]] += dp[idx[c] - 1]
		(N, A, AB, ABC) = dp
print(ABC % M)


S = input()
dp = [[0] * 4 for _ in range(len(S) + 1)]
dp[0][0] = 1
W = 'ABC'
MOD = 10 ** 9 + 7

def update1(i):
	for j in range(4):
		dp[i + 1][j] += dp[i][j] % MOD

def update2(i, c):
	ic = W.index(c)
	dp[i + 1][ic + 1] += dp[i][ic] % MOD
for i in range(len(S)):
	if S[i] == '?':
		for c in W:
			update1(i)
			update2(i, c)
	else:
		update1(i)
		update2(i, S[i])
print(dp[len(S)][-1] % MOD)


def main():
	MOD = 10 ** 9 + 7
	s = input()
	(x, a, b, c) = (1, 0, 0, 0)
	for char in s:
		if char == 'A':
			a = (a + x) % MOD
		elif char == 'B':
			b = (b + a) % MOD
		elif char == 'C':
			c = (c + b) % MOD
		else:
			(x, a, b, c) = (3 * x % MOD, (3 * a + x) % MOD, (3 * b + a) % MOD, (3 * c + b) % MOD)
	print(c)
main()


import sys
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7
S = list(input())
N = len(S)
count = 0
DP = [[0] * (N + 1) for _ in range(3)]
for i in range(1, N + 1):
	s = S[i - 1]
	if s == 'A':
		DP[0][i] = (DP[0][i - 1] + pow(3, count, MOD)) % MOD
		DP[1][i] = DP[1][i - 1]
		DP[2][i] = DP[2][i - 1]
	elif s == 'B':
		DP[0][i] = DP[0][i - 1]
		DP[1][i] = (DP[1][i - 1] + DP[0][i - 1]) % MOD
		DP[2][i] = DP[2][i - 1]
	elif s == 'C':
		DP[0][i] = DP[0][i - 1]
		DP[1][i] = DP[1][i - 1]
		DP[2][i] = (DP[2][i - 1] + DP[1][i - 1]) % MOD
	else:
		DP[0][i] = (3 * DP[0][i - 1] + pow(3, count, MOD)) % MOD
		DP[1][i] = (3 * DP[1][i - 1] + DP[0][i - 1]) % MOD
		DP[2][i] = (3 * DP[2][i - 1] + DP[1][i - 1]) % MOD
		count += 1
print(DP[2][N])


S = input()
lens = len(S)
mod = 10 ** 9 + 7
cnt = [0, 0, 0, 1]
for s in S:
	if s == 'A':
		cnt[0] = (cnt[0] + cnt[3]) % mod
	elif s == 'B':
		cnt[1] = (cnt[0] + cnt[1]) % mod
	elif s == 'C':
		cnt[2] = (cnt[1] + cnt[2]) % mod
	else:
		cnt[2] = (cnt[1] + 3 * cnt[2]) % mod
		cnt[1] = (cnt[0] + 3 * cnt[1]) % mod
		cnt[0] = (3 * cnt[0] + cnt[3]) % mod
		cnt[3] = cnt[3] * 3 % mod
print(cnt[2] % mod)


S = input()
e = 1
a = 0
ab = 0
abc = 0
M = 10 ** 9 + 7
for i in S:
	if i == 'A':
		a = (a + e) % M
	if i == 'B':
		ab = (ab + a) % M
	if i == 'C':
		abc = (abc + ab) % M
	if i == '?':
		abc = (3 * abc + ab) % M
		ab = (3 * ab + a) % M
		a = (3 * a + e) % M
		e = e * 3 % M
print(abc)


mod = 10 ** 9 + 7
S = input()
A = 0
AB = 0
ABC = 0
N = 1
for i in range(len(S)):
	if S[i] == 'A':
		A += N
	elif S[i] == 'B':
		AB += A
	elif S[i] == 'C':
		ABC += AB
	else:
		ABC = 3 * ABC + AB
		AB = 3 * AB + A
		A = 3 * A + N
		N *= 3
	A %= mod
	AB %= mod
	ABC %= mod
	N %= mod
print(ABC)


MOD = 10 ** 9 + 7
S = input()
N = len(S)
nums = [1, 0, 0, 0]
for i in range(0, N):
	s = S[i]
	m = 3 if s == '?' else 1
	a = 1 if s == 'A' or s == '?' else 0
	b = 1 if s == 'B' or s == '?' else 0
	c = 1 if s == 'C' or s == '?' else 0
	n0 = nums[0] * m % MOD
	n1 = (nums[1] * m + nums[0] * a) % MOD
	n2 = (nums[2] * m + nums[1] * b) % MOD
	n3 = (nums[3] * m + nums[2] * c) % MOD
	nums = [n0, n1, n2, n3]
print(nums[3] % MOD)


import sys

def main():
	S = input()
	l = len(S)
	MOD = 10 ** 9 + 7
	dp = [[0 for _ in range(3)] for _ in range(2)]
	cq = 1
	for st in S:
		if st == 'A':
			dp[1][0] = dp[0][0] + cq
			dp[1][1] = dp[0][1]
			dp[1][2] = dp[0][2]
		elif st == 'B':
			dp[1][0] = dp[0][0]
			dp[1][1] = dp[0][0] + dp[0][1]
			dp[1][2] = dp[0][2]
		elif st == 'C':
			dp[1][0] = dp[0][0]
			dp[1][1] = dp[0][1]
			dp[1][2] = dp[0][1] + dp[0][2]
		else:
			dp[1][0] = dp[0][0] * 3 + cq
			dp[1][1] = dp[0][1] * 3 + dp[0][0]
			dp[1][2] = dp[0][2] * 3 + dp[0][1]
			cq *= 3
			cq %= MOD
		for i in range(3):
			dp[0][i] = dp[1][i] % MOD
	print(dp[0][-1])

def __starting_point():
	main()
__starting_point()


data = input()
MOD = 10 ** 9 + 7
SLen = len(data)
targets = 'ABC'
array = [[0 for i in range(SLen + 1)] for _ in range(4)]
array[0][0] = 1
for i in range(SLen):
	for j in range(4):
		if data[i] == '?':
			if j < 3:
				array[j + 1][i + 1] = (array[j + 1][i + 1] + array[j][i]) % MOD
			array[j][i + 1] = (array[j][i + 1] + array[j][i] * 3) % MOD
		else:
			if j < 3 and data[i] == targets[j]:
				array[j + 1][i + 1] = (array[j + 1][i + 1] + array[j][i]) % MOD
			array[j][i + 1] = (array[j][i + 1] + array[j][i]) % MOD
print(array[3][SLen])


S = input()
MOD = 10 ** 9 + 7
A = 0
AB = 0
Q = 1
ans = 0
for s in S:
	if s == '?':
		ans = (3 * ans + AB) % MOD
		AB = (3 * AB + A) % MOD
		A = (3 * A + Q) % MOD
		Q = Q * 3 % MOD
	elif s == 'A':
		A = (A + Q) % MOD
	elif s == 'B':
		AB = (AB + A) % MOD
	elif s == 'C':
		ans = (ans + AB) % MOD
print(ans)


import sys
sys.setrecursionlimit(100000000)
input = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = 10 ** 15

def main():
	S = input()
	N = len(S)
	C = [0] * (N + 1)
	QL = [0] * (N + 1)
	A = [0] * (N + 1)
	QR = [0] * (N + 1)
	for i in range(N):
		if S[i] == 'A':
			A[i + 1] = A[i] + 1
		else:
			A[i + 1] = A[i]
		if S[i] == '?':
			QL[i + 1] = QL[i] + 1
		else:
			QL[i + 1] = QL[i]
	for i in range(N - 1, -1, -1):
		if S[i] == 'C':
			C[i] = C[i + 1] + 1
		else:
			C[i] = C[i + 1]
		if S[i] == '?':
			QR[i] = QR[i + 1] + 1
		else:
			QR[i] = QR[i + 1]
	power3 = [1]
	for i in range(N):
		power3.append(power3[-1] * 3 % MOD)
	ans = 0
	for i in range(N):
		if S[i] in 'AC':
			continue
		choose_A = (A[i] * power3[QL[i]] + (QL[i] > 0) * QL[i] * power3[QL[i] - 1]) % MOD
		choose_B = (C[i + 1] * power3[QR[i + 1]] + (QR[i + 1] > 0) * QR[i + 1] * power3[QR[i + 1] - 1]) % MOD
		ans += choose_A * choose_B % MOD
		ans %= MOD
	print(ans)

def __starting_point():
	main()
__starting_point()


s = input().rstrip()
dp = [0] * 4
dp[0] = 1
for i in range(len(s)):
	if s[i] == 'A':
		dp[1] += dp[0]
	elif s[i] == 'B':
		dp[2] += dp[1]
	elif s[i] == 'C':
		dp[3] += dp[2]
	else:
		dp = [dp[0] * 3, dp[1] * 3 + dp[0], dp[2] * 3 + dp[1], dp[3] * 3 + dp[2]]
	dp = list([x % (10 ** 9 + 7) for x in dp])
print(dp[3])


s = input()
a = [1, 0, 0, 0]
for i in range(len(s)):
	c = s[i]
	if c == 'A':
		a[1] = (a[1] + a[0]) % 1000000007
	elif c == 'B':
		a[2] = (a[2] + a[1]) % 1000000007
	elif c == 'C':
		a[3] = (a[3] + a[2]) % 1000000007
	elif c == '?':
		tmp = [a[i] for i in range(4)]
		a[0] = tmp[0] * 3
		for j in range(3):
			a[j + 1] = tmp[j + 1] * 3 + tmp[j]
		a = list(map(lambda x: x % 1000000007, a))
print(a[3] % 1000000007)


mod = 10 ** 9 + 7
sl = list(input())
a = 0
ab = 0
abc = 0
p = 1
for s in sl:
	if s == 'A':
		a += p
		a %= mod
	elif s == 'B':
		ab += a
		ab %= mod
	elif s == 'C':
		abc += ab
		abc %= mod
	elif s == '?':
		abc = 3 * abc + ab
		abc %= mod
		ab = 3 * ab + a
		ab %= mod
		a = 3 * a + p
		a %= mod
		p *= 3
		p %= mod
print(abc)


MOD = 10 ** 9 + 7
p3 = [1]
S = input()
n = len(S)
a = []
c = []
q = []
for i in range(n):
	p3.append(int(p3[i] * 3 % MOD))
	if S[i] == 'A':
		a.append(1)
	else:
		a.append(0)
	if S[i] == 'C':
		c.append(1)
	else:
		c.append(0)
	if S[i] == '?':
		q.append(1)
	else:
		q.append(0)
for i in range(1, n):
	a[i] += a[i - 1]
	c[i] += c[i - 1]
	q[i] += q[i - 1]
count = 0
for i in range(1, n - 1):
	if S[i] == 'B' or S[i] == '?':
		bq = 0 if S[i] == 'B' else 1
		count += a[i - 1] * (c[n - 1] - c[i]) * p3[q[n - 1] - bq]
		count += q[i - 1] * (c[n - 1] - c[i]) * p3[q[n - 1] - 1 - bq]
		count += a[i - 1] * (q[n - 1] - q[i]) * p3[q[n - 1] - 1 - bq]
		count += q[i - 1] * (q[n - 1] - q[i]) * p3[q[n - 1] - 2 - bq]
print(int(count % MOD))


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)


S = input()
nQ_r = S.count('?')
nC_r = S.count('C')
nQ_l = 0
nA_l = 0
N = len(S)
mod = 10 ** 9 + 7
pow3 = [1] * N
p = 1
for i in range(1, N):
	pow3[i] = p = p * 3 % mod
ans = 0
for (n, c) in enumerate(S):
	if c == 'C':
		nC_r -= 1
	if c == '?':
		nQ_r -= 1
	if n > 0 and n < N - 1 and (c == 'B' or c == '?'):
		p = (nQ_l * pow3[max(0, nQ_l - 1)] + nA_l * pow3[nQ_l]) % mod
		q = (nQ_r * pow3[max(0, nQ_r - 1)] + nC_r * pow3[nQ_r]) % mod
		ans += p * q
		ans %= mod
	if c == 'A':
		nA_l += 1
	if c == '?':
		nQ_l += 1
print(ans)


MOD = 10 ** 9 + 7
S = input()
N = len(S)
target = 'ABC'
n = len(target)
cur = [0] * (n + 1)
cur[0] = 1
for s in S:
	for w in range(n):
		if s == target[w]:
			cur[w + 1] += cur[w]
			cur[w + 1] %= MOD
			break
	else:
		for w in range(n - 1, -1, -1):
			cur[w + 1] = (cur[w + 1] * 3 + cur[w]) % MOD
		cur[0] *= 3
		cur[0] %= MOD
print(cur[-1])


S = list(input())
MOD = 10 ** 9 + 7
n_possible = 1
A = 0
B = 0
C = 0
for s in S:
	if s == 'A':
		A += n_possible
	elif s == 'B':
		B += A
	elif s == 'C':
		C += B
	else:
		C = 3 * C + B
		B = 3 * B + A
		A = 3 * A + n_possible
		n_possible *= 3
	n_possible %= MOD
	A %= MOD
	B %= MOD
	C %= MOD
print(C)


S = list(input())
n = len(S)
mod = 10 ** 9 + 7
dpa = [0] * (10 ** 5 + 10)
dpc = [0] * (10 ** 5 + 10)
hatena_count = 0
pow3 = [1] * (10 ** 5 + 10)
for i in range(1, 10 ** 5 + 10):
	pow3[i] = pow3[i - 1] * 3 % mod
for i in range(n):
	if S[i] == 'A':
		dpa[i + 1] = (dpa[i] + pow3[hatena_count]) % mod
	elif S[i] == '?':
		dpa[i + 1] = (3 * dpa[i] + pow3[hatena_count]) % mod
		hatena_count += 1
	else:
		dpa[i + 1] = dpa[i]
S.reverse()
hatena_count = 0
for i in range(n):
	if S[i] == 'C':
		dpc[i + 1] = (dpc[i] + pow3[hatena_count]) % mod
	elif S[i] == '?':
		dpc[i + 1] = (3 * dpc[i] + pow3[hatena_count]) % mod
		hatena_count += 1
	else:
		dpc[i + 1] = dpc[i]
ans = 0
for i in range(1, n - 1):
	if S[i] == 'B' or S[i] == '?':
		ans += dpa[n - 1 - i] * dpc[i]
		ans %= mod
print(ans)


MOD = 10 ** 9 + 7
S = input()
res = 0
dpn = 1
dp0 = 0
dp1 = 0
for c in S:
	if c == 'A':
		dp0 += dpn
	elif c == 'B':
		dp1 += dp0
	elif c == 'C':
		res += dp1
	else:
		(dp0, dp1, res) = (dp0 * 3 + dpn, dp1 * 3 + dp0, res * 3 + dp1)
		dpn *= 3
	dpn %= MOD
	dp0 %= MOD
	dp1 %= MOD
	res %= MOD
print(res)


S = input()
mod = 10 ** 9 + 7
(A, AB, ABC, ALL) = (0, 0, 0, 1)
for s in S:
	if s == 'A':
		A += ALL
		A %= mod
	if s == 'B':
		AB += A
		AB %= mod
	if s == 'C':
		ABC += AB
		ABC %= mod
	if s == '?':
		ABC = (3 * ABC + AB) % mod
		AB = (3 * AB + A) % mod
		A = (3 * A + ALL) % mod
		ALL *= 3
		ALL %= mod
print(ABC)


s = input()
mod = 10 ** 9 + 7
l = len(s)
dp = [[0] * 4 for _ in range(l + 1)]
dp[0][0] = 1
for (i, e) in enumerate(s, 1):
	for j in range(4):
		if e == '?':
			dp[i][j] += dp[i - 1][j] * 3
		else:
			dp[i][j] += dp[i - 1][j]
	if e == 'A' or e == '?':
		dp[i][1] += dp[i - 1][0]
	if e == 'B' or e == '?':
		dp[i][2] += dp[i - 1][1]
	if e == 'C' or e == '?':
		dp[i][3] += dp[i - 1][2]
	for j in range(4):
		dp[i][j] %= mod
ans = dp[l][3]
print(ans)


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)


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)


S = input()

def solve(S):
	mod = 10 ** 9 + 7
	N = len(S)
	Aquest = []
	Cquest = []
	(cntA, cntquest) = (0, 0)
	for i in range(N):
		if S[i] in 'B?':
			Aquest.append([cntA, cntquest])
		if S[i] == 'A':
			cntA += 1
		if S[i] == '?':
			cntquest += 1
	(cntC, cntquest) = (0, 0)
	for i in range(N - 1, -1, -1):
		if S[i] in 'B?':
			Cquest.append([cntC, cntquest])
		if S[i] == 'C':
			cntC += 1
		if S[i] == '?':
			cntquest += 1
	Cquest = Cquest[::-1]
	ans = 0
	for (aquest, cquest) in zip(Aquest, Cquest):
		a = aquest[0] * pow(3, aquest[1], mod)
		if aquest[1] > 0:
			a += aquest[1] * pow(3, aquest[1] - 1, mod)
		c = cquest[0] * pow(3, cquest[1], mod)
		if cquest[1] > 0:
			c += cquest[1] * pow(3, cquest[1] - 1, mod)
		ans += a * c % mod
	ans %= mod
	return ans
print(solve(S))


S = input()
N = len(S)
mod = 10 ** 9 + 7
dp1 = [0 for _ in range(N + 1)]
dp2 = [0 for _ in range(N + 1)]
dp3 = [0 for _ in range(N + 1)]
dp4 = [0 for _ in range(N + 1)]
dp1[0] = 1
for i in range(N):
	if S[i] == '?':
		dp1[i + 1] += 3 * dp1[i]
		dp2[i + 1] += 3 * dp2[i] + dp1[i]
		dp3[i + 1] += 3 * dp3[i] + dp2[i]
		dp4[i + 1] += 3 * dp4[i] + dp3[i]
	else:
		dp1[i + 1] += dp1[i]
		dp2[i + 1] += dp2[i]
		dp3[i + 1] += dp3[i]
		dp4[i + 1] += dp4[i]
	if S[i] == 'A':
		dp2[i + 1] += dp1[i]
	if S[i] == 'B':
		dp3[i + 1] += dp2[i]
	if S[i] == 'C':
		dp4[i + 1] += dp3[i]
	dp1[i + 1] %= mod
	dp2[i + 1] %= mod
	dp3[i + 1] %= mod
	dp4[i + 1] %= mod
print(dp4[N])


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


S = input()
MOD = 10 ** 9 + 7
A = 0
AB = 0
ABC = 0
prd = 1
for s in S:
	if s == 'A':
		A += prd
	elif s == 'B':
		AB += A
	elif s == 'C':
		ABC += AB
	else:
		a = A * 3 + prd
		ab = AB * 3 + A
		abc = ABC * 3 + AB
		(A, AB, ABC) = (a, ab, abc)
		prd *= 3
	A %= MOD
	AB %= MOD
	ABC %= MOD
	prd %= MOD
print(ABC)


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] += dp[i + 1][j + 1]
		dp[i][j] %= MOD
	dp[i][3] = m * dp[i + 1][3] % MOD
print(dp[0][0] % MOD)


M = 10 ** 9 + 7
S = input()
A = 0
AB = 0
ABC = 0
X = 1
for c in S:
	if c == 'C':
		ABC = (ABC + AB) % M
	elif c == 'B':
		AB = (AB + A) % M
	elif c == 'A':
		A = (A + X) % M
	elif c == '?':
		ABC = (3 * ABC + AB) % M
		AB = (3 * AB + A) % M
		A = (3 * A + X) % M
		X = 3 * X % M
print(ABC)


s = input()
n = len(s)
MOD = 10 ** 9 + 7
dp = [[0] * 4 for _ in range(n + 1)]
dp[0][0] = 1
for (i, x) in enumerate(s):
	if x == 'A' or x == '?':
		dp[i + 1][0] += dp[i][0]
		dp[i + 1][1] += dp[i][1]
		dp[i + 1][2] += dp[i][2]
		dp[i + 1][3] += dp[i][3]
		dp[i + 1][1] += dp[i][0]
	if x == 'B' or x == '?':
		dp[i + 1][0] += dp[i][0]
		dp[i + 1][1] += dp[i][1]
		dp[i + 1][2] += dp[i][2]
		dp[i + 1][3] += dp[i][3]
		dp[i + 1][2] += dp[i][1]
	if x == 'C' or x == '?':
		dp[i + 1][0] += dp[i][0]
		dp[i + 1][1] += dp[i][1]
		dp[i + 1][2] += dp[i][2]
		dp[i + 1][3] += dp[i][3]
		dp[i + 1][3] += dp[i][2]
	for j in range(4):
		dp[i + 1][j] %= MOD
print(dp[n][3])


S = input()
pr = 10 ** 9 + 7
(a1, a2, a3) = (0, 0, 0)
c = 0
for i in S:
	if i == 'A':
		a1 = (a1 + pow(3, c, pr)) % pr
	elif i == 'B':
		a2 = (a2 + a1) % pr
	elif i == 'C':
		a3 = (a3 + a2) % pr
	else:
		(a1, a2, a3) = ((3 * a1 + pow(3, c, pr)) % pr, (3 * a2 + a1) % pr, (3 * a3 + a2) % pr)
		c += 1
print(a3)


S = input()
MOD = 10 ** 9 + 7
A = 0
AB = 0
ABC = 0
cnt = 1
for s in S:
	if s == 'A':
		A = (A + cnt) % MOD
	elif s == 'B':
		AB = (A + AB) % MOD
	elif s == 'C':
		ABC = (AB + ABC) % MOD
	else:
		(A, AB, ABC) = ((A * 3 + cnt) % MOD, (AB * 3 + A) % MOD, (ABC * 3 + AB) % MOD)
		cnt = cnt * 3 % MOD
print(ABC)


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


mod = 10 ** 9 + 7

def main():
	s = input()
	n = len(s)
	dp = [[0 for _ in range(4)] for _ in range(n + 1)]
	dp[0][0] = 1
	for i in range(n):
		if s[i] in ('A', '?'):
			dp[i + 1][0] = (dp[i + 1][0] + dp[i][0]) % mod
			dp[i + 1][1] = (dp[i + 1][1] + dp[i][1]) % mod
			dp[i + 1][2] = (dp[i + 1][2] + dp[i][2]) % mod
			dp[i + 1][3] = (dp[i + 1][3] + dp[i][3]) % mod
			dp[i + 1][1] = (dp[i + 1][1] + dp[i][0]) % mod
		if s[i] in ('B', '?'):
			dp[i + 1][0] = (dp[i + 1][0] + dp[i][0]) % mod
			dp[i + 1][1] = (dp[i + 1][1] + dp[i][1]) % mod
			dp[i + 1][2] = (dp[i + 1][2] + dp[i][2]) % mod
			dp[i + 1][3] = (dp[i + 1][3] + dp[i][3]) % mod
			dp[i + 1][2] = (dp[i + 1][2] + dp[i][1]) % mod
		if s[i] in ('C', '?'):
			dp[i + 1][0] = (dp[i + 1][0] + dp[i][0]) % mod
			dp[i + 1][1] = (dp[i + 1][1] + dp[i][1]) % mod
			dp[i + 1][2] = (dp[i + 1][2] + dp[i][2]) % mod
			dp[i + 1][3] = (dp[i + 1][3] + dp[i][3]) % mod
			dp[i + 1][3] = (dp[i + 1][3] + dp[i][2]) % mod
	print(dp[n][3])

def __starting_point():
	main()
__starting_point()


mo = 10 ** 9 + 7
s = input()
n = len(s)
dp = [[0] * (1 + n) for i in range(3)]
cc = 0
for i in range(n):
	c = s[i]
	if c == 'A':
		(da, db, dc, dd) = (1, 0, 0, 1)
	elif c == 'B':
		(da, db, dc, dd) = (0, 1, 0, 1)
	elif c == 'C':
		(da, db, dc, dd) = (0, 0, 1, 1)
	elif c == '?':
		(da, db, dc, dd) = (1, 1, 1, 3)
	dp[0][i + 1] = dp[0][i] * dd + da * pow(3, cc, mo)
	dp[1][i + 1] = dp[1][i] * dd + dp[0][i] * db
	dp[2][i + 1] = dp[2][i] * dd + dp[1][i] * dc
	dp[0][i + 1] %= mo
	dp[1][i + 1] %= mo
	dp[2][i + 1] %= mo
	if c == '?':
		cc += 1
print(dp[2][n] % mo)


from itertools import accumulate as ac
s = input()
n = len(s)
mod = int(1000000000.0) + 7
(*aca,) = ac([0] + [1 if i == 'A' else 0 for i in s])
(*acc,) = ac([0] + [1 if i == 'C' else 0 for i in s])
(*acq,) = ac([0] + [1 if i == '?' else 0 for i in s])
v = 0
for i in range(1, n - 1):
	if s[i] == 'B' or s[i] == '?':
		a = aca[i]
		l = acq[i]
		c = acc[n] - acc[i + 1]
		r = acq[n] - acq[i + 1]
		v += a * c * pow(3, l + r, mod)
		if l + r - 1 >= 0:
			v += a * r * pow(3, l + r - 1, mod) + l * c * pow(3, l + r - 1, mod)
		if l + r - 2 >= 0:
			v += l * r * pow(3, l + r - 2, mod)
		v %= mod
print(v)


S = input()
INF = 10 ** 9 + 7
dp = [0, 0, 0]
N = 1
for i in range(len(S)):
	if S[i] == 'A':
		dp[0] += N
		dp[0] %= INF
	elif S[i] == 'B':
		dp[1] += dp[0]
		dp[1] %= INF
	elif S[i] == 'C':
		dp[2] += dp[1]
		dp[2] %= INF
	else:
		a = dp[0]
		b = dp[1]
		dp[0] = N + dp[0] * 3
		dp[1] = a + dp[1] * 3
		dp[2] = b + dp[2] * 3
		dp[0] %= INF
		dp[1] %= INF
		dp[2] %= INF
		N = 3 * N % INF
print(dp[2] % INF)


S = input().strip()
mod = 10 ** 9 + 7
dp = [1] + [0] * 3
for s in S:
	dp1 = dp[:]
	if s == 'A':
		dp1[1] += dp[0]
	elif s == 'B':
		dp1[2] += dp[1]
	elif s == 'C':
		dp1[3] += dp[2]
	else:
		dp1[1] += dp[0]
		dp1[2] += dp[1]
		dp1[3] += dp[2]
		dp1[0] += 2 * dp[0]
		dp1[1] += 2 * dp[1]
		dp1[2] += 2 * dp[2]
		dp1[3] += 2 * dp[3]
	dp = [d % mod for d in dp1]
print(dp[-1])


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


def main():
	mod = 10 ** 9 + 7
	s = input()
	n = len(s)
	a_num = 0
	c_num = s.count('C')
	q_num = 0
	q_cnt = s.count('?')
	pows = [0] * 4
	if q_cnt >= 3:
		pows[3] = pow(3, q_cnt - 3, mod)
		pows[2] = pows[3] * 3 % mod
		pows[1] = pows[2] * 3 % mod
		pows[0] = pows[1] * 3 % mod
	elif q_cnt == 2:
		pows[2] = 1
		pows[1] = 3
		pows[0] = 9
	elif q_cnt == 1:
		pows[1] = 1
		pows[0] = 3
	else:
		pows[0] = 1
	ans = 0
	for x in s:
		if x == 'A':
			a_num += 1
		elif x == 'B':
			ans += pows[0] * a_num * c_num
			ans += pows[1] * (q_num * c_num + a_num * (q_cnt - q_num))
			ans += pows[2] * q_num * (q_cnt - q_num)
			ans %= mod
		elif x == 'C':
			c_num -= 1
		else:
			ans += pows[1] * a_num * c_num
			ans += pows[2] * (q_num * c_num + a_num * (q_cnt - q_num - 1))
			ans += pows[3] * q_num * (q_cnt - q_num - 1)
			ans %= mod
			q_num += 1
	print(ans)
main()


MOD = 10 ** 9 + 7
S = input()
dp0 = 1
dp1 = 0
dp2 = 0
dp3 = 0
for c in S:
	if c == 'A':
		dp1 = (dp0 + dp1) % MOD
	elif c == 'B':
		dp2 = (dp1 + dp2) % MOD
	elif c == 'C':
		dp3 = (dp2 + dp3) % MOD
	else:
		dp3 = (dp3 * 3 + dp2) % MOD
		dp2 = (dp2 * 3 + dp1) % MOD
		dp1 = (dp1 * 3 + dp0) % MOD
		dp0 = dp0 * 3 % MOD
print(dp3)


S = list(input())
mod = 10 ** 9 + 7
n = len(S)
dp = [[0] * 4 for _ in range(n)]
dp[-1][0] = 1
for (i, s) in enumerate(S):
	if s == '?':
		dp[i][0] = dp[i - 1][0] * 3 % mod
		dp[i][1] = (dp[i - 1][0] + dp[i - 1][1] * 3) % mod
		dp[i][2] = (dp[i - 1][1] + dp[i - 1][2] * 3) % mod
		dp[i][3] = (dp[i - 1][2] + dp[i - 1][3] * 3) % mod
	elif s == '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 == 'B':
		dp[i][0] = dp[i - 1][0]
		dp[i][1] = dp[i - 1][1]
		dp[i][2] = (dp[i - 1][1] + dp[i - 1][2]) % mod
		dp[i][3] = dp[i - 1][3]
	else:
		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
print(dp[-1][-1])


MOD = 10 ** 9 + 7
S = input()
d = 'ABC'.index
s = [0] * 4
s[0] = 1
for c in S:
	if c == '?':
		s = [s[0] * 3, s[1] * 3 + s[0], s[2] * 3 + s[1], s[3] * 3 + s[2]]
		for i in range(4):
			s[i] %= MOD
	else:
		i = d(c)
		s[i + 1] += s[i] % MOD
print(s[3] % MOD)


MOD = 10 ** 9 + 7
s = input()
n = len(s)
dp = [[0] * 4 for _ in range(n + 1)]
dp[0][0] = 1
for i in range(n):
	if s[i] == '?':
		dp[i + 1][0] += dp[i][0] * 3
		dp[i + 1][0] %= MOD
	else:
		dp[i + 1][0] += dp[i][0]
	for j in range(3):
		if s[i] == 'ABC'[j] or s[i] == '?':
			dp[i + 1][j + 1] += dp[i][j]
		dp[i + 1][j + 1] += dp[i][j + 1] * (3 if s[i] == '?' else 1)
		dp[i + 1][j + 1] %= MOD
print(dp[n][3] % MOD)


MOD = 10 ** 9 + 7
S = input()
dp = []
for i in range(len(S) + 1):
	dp.append([0, 0, 0, 0])
dp[-1][3] = 1
for i in reversed(range(len(S))):
	if S[i] == '?':
		m1 = 3
	else:
		m1 = 1
	dp[i][3] = m1 * dp[i + 1][3]
	dp[i][3] %= MOD
	for j in range(3):
		if S[i] == '?':
			m2 = 1
		elif S[i] == ['A', 'B', 'C'][j]:
			m2 = 1
		else:
			m2 = 0
		dp[i][j] = m1 * dp[i + 1][j] + m2 * dp[i + 1][j + 1]
		dp[i][j] %= MOD
print(dp[0][0])


S = input()
MOD = 10 ** 9 + 7
A = 0
C = S.count('C')
Q = 0
QMAX = S.count('?')
ans = 0
b = 3 ** (QMAX - 2) % MOD
q = 3 ** (QMAX - 3) % MOD
for s in S:
	if s == 'A':
		A += 1
	elif s == 'C':
		C -= 1
	elif s == 'B':
		ans = (ans + (3 * A + Q) * b * (3 * C + QMAX - Q)) % MOD
	else:
		ans = (ans + (3 * A + Q) * q * (3 * C + QMAX - Q - 1)) % MOD
		Q += 1
print(int(ans))


mod = 1000000007
s = input()
al = 0
cr = s.count('C')
ql = 0
qr = s.count('?')
ans = 0
for c in s:
	if c == 'C':
		cr -= 1
	elif c == '?':
		qr -= 1
		ans += (3 * al + ql) * (3 * cr + qr) * pow(3, ql + qr + mod - 3, mod)
		ans %= mod
		ql += 1
	elif c == 'B':
		ans += (3 * al + ql) * (3 * cr + qr) * pow(3, ql + qr + mod - 3, mod)
		ans %= mod
	else:
		al += 1
print(ans)


S = input()
MOD = pow(10, 9) + 7
dp = [0] * 4
dp[0] = 1
for s in S:
	if s == 'A':
		dp[1] += dp[0]
	elif s == 'B':
		dp[2] += dp[1]
	elif s == 'C':
		dp[3] += dp[2]
	else:
		tmp3 = dp[2]
		tmp2 = dp[1]
		tmp1 = dp[0]
		dp[3] *= 3
		dp[3] += tmp3
		dp[2] *= 3
		dp[2] += tmp2
		dp[1] *= 3
		dp[1] += tmp1
		dp[0] *= 3
	dp[3] %= MOD
	dp[2] %= MOD
	dp[1] %= MOD
	dp[0] %= MOD
print(dp[3])


import sys
input = sys.stdin.readline
MOD = 10 ** 9 + 7
S = input()
(a, ab, abc) = [0] * 3
c = 1
for s in S:
	if s == 'A':
		a = (a + c) % MOD
	elif s == 'B':
		ab = (ab + a) % MOD
	elif s == 'C':
		abc = (abc + ab) % MOD
	elif s == '?':
		abc = (3 * abc + ab) % MOD
		ab = (3 * ab + a) % MOD
		a = (3 * a + c) % MOD
		c = 3 * c % MOD
print(abc % MOD)


def main():
	MOD = 10 ** 9 + 7
	S = input()
	(z, a, b, c) = (1, 0, 0, 0)
	for x in S:
		if x == 'C':
			c = (c + b) % MOD
		elif x == 'B':
			b = (b + a) % MOD
		elif x == 'A':
			a = (a + z) % MOD
		elif x == '?':
			(z, a, b, c) = (z * 3 % MOD, (a * 3 + z) % MOD, (b * 3 + a) % MOD, (c * 3 + b) % MOD)
	print(c)

def __starting_point():
	main()
__starting_point()


S = input()
d = [0, 0, 0, 1]
max_ans = 10 ** 9 + 7
for c in reversed(S):
	m = [c == 'A', c == 'B', c == 'C', c == '?']
	if m[3] is True:
		tmp = 3
	else:
		tmp = 1
	for j in range(3):
		d[j] = (tmp * d[j] + int(m[j] or m[3]) * d[j + 1]) % max_ans
	d[3] = tmp * d[3] % max_ans
print(d[0])


mod = 10 ** 9 + 7
S = input()
s = len(S)
dp = [[0 for i in range(4)] for j in range(s + 1)]
mod = 10 ** 9 + 7
dp[0][0] = 1
for j in range(4):
	for i in range(s):
		dp[i + 1][j] = dp[i][j] % mod
		if S[i] == '?':
			dp[i + 1][j] = dp[i][j] * 3 % mod
			if j > 0:
				dp[i + 1][j] += dp[i][j - 1] % mod
		elif 'ABC'.index(S[i]) + 1 == j:
			dp[i + 1][j] += dp[i][j - 1] % mod
print(dp[s][3] % mod)


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


s = input()
a = [1, 0, 0, 0]
for i in range(len(s)):
	c = s[i]
	if c == 'A':
		a[1] += a[0]
	elif c == 'B':
		a[2] += a[1]
	elif c == 'C':
		a[3] += a[2]
	elif c == '?':
		a = [a[0] * 3] + [a[j] * 3 + a[j - 1] for j in range(1, 4)]
	a = [a[i] % 1000000007 for i in range(4)]
print(a[3])


mod = 1000000007
a = 0
ab = 0
abc = 0
Q = 1
S = input()
for i in S:
	if i == 'A':
		a += Q
	elif i == 'B':
		ab += a
	elif i == 'C':
		abc += ab
	else:
		abc = abc * 3 + ab
		ab = ab * 3 + a
		a = a * 3 + Q
		Q = Q * 3
	a = a % mod
	ab = ab % mod
	abc = abc % mod
	Q = Q % mod
print(abc)


s = input()
l = len(s)
dp = [4 * [0] for _ in range(l + 1)]
dp[0][0] = 1
for i in range(1, l + 1):
	si = s[i - 1]
	if si == '?':
		dp[i][0] = dp[i - 1][0] * 3
		dp[i][1] = dp[i - 1][1] * 3
		dp[i][2] = dp[i - 1][2] * 3
		dp[i][3] = dp[i - 1][3] * 3
	else:
		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]
	if si == 'A':
		dp[i][1] = dp[i - 1][0] + dp[i][1]
	elif si == 'B':
		dp[i][2] = dp[i - 1][1] + dp[i][2]
	elif si == 'C':
		dp[i][3] = dp[i - 1][2] + dp[i][3]
	else:
		dp[i][1] = dp[i - 1][0] + dp[i][1]
		dp[i][2] = dp[i - 1][1] + dp[i][2]
		dp[i][3] = dp[i - 1][2] + dp[i][3]
	for j in range(4):
		dp[i][j] = dp[i][j] % 1000000007
print(int(dp[-1][-1]))


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


def index(c):
	return ord(c) - ord('A') + 1
s = ' ' + input()
m = 10 ** 9 + 7
dp = [[0] * 4 for _ in range(len(s))]
dp[0][0] = 1
for i in range(1, len(s)):
	for j in range(4):
		dp[i][j] = dp[i - 1][j]
	if s[i] == '?':
		dp[i][0] = dp[i - 1][0] * 3 % m
		for j in range(1, 4):
			dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j] * 3) % m
	else:
		k = index(s[i])
		dp[i][k] = (dp[i - 1][k - 1] + dp[i - 1][k]) % m
print(dp[-1][3])


MOD = 10 ** 9 + 7
s = input()
Anum = 0
ABnum = 0
ABCnum = 0
q = 0
for c in s:
	if c == 'A':
		Anum = (Anum + pow(3, q, MOD)) % MOD
	elif c == 'B':
		ABnum = (ABnum + Anum) % MOD
	elif c == 'C':
		ABCnum = (ABCnum + ABnum) % MOD
	else:
		(Anum, ABnum, ABCnum) = (3 * Anum + pow(3, q, MOD), 3 * ABnum + Anum, 3 * ABCnum + ABnum)
		(Anum, ABnum, ABCnum) = (Anum % MOD, ABnum % MOD, ABCnum % MOD)
		q += 1
print(ABCnum)


s = input()
l = len(s)
dp = [4 * [0] for _ in range(l + 1)]
dp[0][0] = 1
for i in range(1, l + 1):
	si = s[i - 1]
	for j in range(4):
		dp[i][j] = dp[i - 1][j] * ((si == '?') * 2 + 1)
	if si == 'A':
		dp[i][1] += dp[i - 1][0]
	if si == 'B':
		dp[i][2] += dp[i - 1][1]
	if si == 'C':
		dp[i][3] += dp[i - 1][2]
	if si == '?':
		dp[i][1] += dp[i - 1][0]
		dp[i][2] += dp[i - 1][1]
		dp[i][3] += dp[i - 1][2]
	for j in range(4):
		dp[i][j] %= 10 ** 9 + 7
print(dp[-1][-1])


S = input()
N = len(S)
O = 1
A = [0] * (N + 1)
AB = [0] * (N + 1)
ABC = [0] * (N + 1)
for i in range(1, N + 1):
	A[i] = A[i - 1]
	AB[i] = AB[i - 1]
	ABC[i] = ABC[i - 1]
	if S[i - 1] is 'A':
		A[i] += O
	elif S[i - 1] is 'B':
		AB[i] += A[i - 1]
	elif S[i - 1] is 'C':
		ABC[i] += AB[i - 1]
	elif S[i - 1] is '?':
		A[i] *= 3
		A[i] += O
		AB[i] *= 3
		AB[i] += A[i - 1]
		ABC[i] *= 3
		ABC[i] += AB[i - 1]
		O *= 3
	A[i] = A[i] % (10 ** 9 + 7)
	AB[i] = AB[i] % (10 ** 9 + 7)
	ABC[i] = ABC[i] % (10 ** 9 + 7)
	O = O % (10 ** 9 + 7)
print(int(ABC[N] % (10 ** 9 + 7)))


def ary(r, c, v):
	return [[v for _ in range(c)] for _ in range(r)]
s = input()
ls = len(s)
dp = ary(ls + 1, 4, 0)
dp[0][0] = 1
mod = 10 ** 9 + 7
for i in range(1, ls + 1):
	for j in range(4):
		dp[i][j] += dp[i - 1][j] * (3 if s[i - 1] == '?' else 1)
		if j > 0:
			if s[i - 1] == '?' or s[i - 1] == 'ABC'[j - 1]:
				dp[i][j] += dp[i - 1][j - 1]
		dp[i][j] %= mod
print(dp[ls][3])


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):
	apro = cpro = 0
	if A[i] == 'B' or A[i] == '?':
		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)


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


from collections import *
from itertools import *
import copy
from heapq import *
S = input()
mod = 10 ** 9 + 7
A = 0
AB = 0
ABC = 0
count = 0
for s in S:
	if s == 'A':
		A += pow(3, count, mod)
	elif s == 'B':
		AB += A
	elif s == 'C':
		ABC += AB
	else:
		ABC = (ABC * 3 + AB) % mod
		AB = (AB * 3 + A) % mod
		A = (A * 3 + pow(3, count, mod)) % mod
		count += 1
print(ABC % mod)


import sys
readline = sys.stdin.readline
S = list(str(readline().rstrip()))
MOD = 10 ** 9 + 7
a = 0
ab = 0
abc = 0
pat = 1
for s in S:
	if s == 'A':
		a = (a + pat) % MOD
	elif s == 'B':
		ab = (ab + a) % MOD
	elif s == 'C':
		abc = (abc + ab) % MOD
	else:
		tmpa = a
		tmpab = ab
		a = (3 * a + pat) % MOD
		ab = (3 * ab + tmpa) % MOD
		abc = (3 * abc + tmpab) % MOD
		pat = pat * 3 % MOD
print(abc)


MOD = 10 ** 9 + 7
S = input()
N = len(S)
dp = [[0] * 4 for i in range(N + 1)]
dp[0][0] = 1
for i in range(N):
	s = S[i]
	for j in range(4):
		if s == '?':
			dp[i + 1][j] += dp[i][j] * 3
		else:
			dp[i + 1][j] += dp[i][j]
		dp[i + 1][j] %= MOD
		if j < 3 and (s == '?' or s == 'ABC'[j]):
			dp[i + 1][j + 1] += dp[i][j]
			dp[i + 1][j + 1] %= MOD
print(dp[N][3] % MOD)


def main():
	S = input()
	N = len(S)
	m = 10 ** 9 + 7
	dp = [[0] * 4 for _ in range(N + 1)]
	for i in range(N, -1, -1):
		for j in range(3, -1, -1):
			if i == N:
				if j == 3:
					dp[i][j] = 1
				else:
					dp[i][j] = 0
			else:
				if S[i] == '?':
					dp[i][j] = dp[i + 1][j] * 3 % m
				else:
					dp[i][j] = dp[i + 1][j]
				if j < 3:
					if S[i] == '?' or S[i] == 'ABC'[j]:
						dp[i][j] += dp[i + 1][j + 1]
						dp[i][j] %= m
	print(dp[0][0])

def __starting_point():
	main()
__starting_point()


import sys
input = sys.stdin.readline
S = input().rstrip()
N = len(S)
mod = 10 ** 9 + 7
cnt = 0
A = B = C = 0
for c in S:
	if c == 'A':
		A += pow(3, cnt, mod)
	if c == 'B':
		B += A
	if c == 'C':
		C += B
	if c == '?':
		C = C * 3 + B
		B = B * 3 + A
		A = A * 3 + pow(3, cnt, mod)
		cnt += 1
	A %= mod
	B %= mod
	C %= mod
print(C)


MOD = 1000000007
S = input()
(a, ab, abc, all_s) = (0, 0, 0, 1)
for s in S:
	if s == 'A':
		a = (a + all_s) % MOD
	elif s == 'B':
		ab = (ab + a) % MOD
	elif s == 'C':
		abc = (abc + ab) % MOD
	elif s == '?':
		abc = (abc * 3 + ab) % MOD
		ab = (ab * 3 + a) % MOD
		a = (a * 3 + all_s) % MOD
		all_s = all_s * 3 % MOD
print(abc)


s = [1, 0, 0, 0]
for c in input():
	if c != '?':
		i = 'ABC'.find(c)
		s[i + 1] += s[i]
	else:
		s = [s[0] * 3, s[1] * 3 + s[0], s[2] * 3 + s[1], s[3] * 3 + s[2]]
	s = [i % (10 ** 9 + 7) for i in s]
print(s[3])


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


MOD = 10 ** 9 + 7
S = input()
N = len(S)
dp = [[0] * 4 for i in range(N + 1)]
dp[0][0] = 1
for i in range(N):
	dp[i + 1][0] = dp[i][0] if S[i] != '?' else dp[i][0] * 3 % MOD
	dp[i + 1][1] = dp[i][1] if S[i] != 'A' and S[i] != '?' else (dp[i][1] + dp[i][0]) % MOD if S[i] == 'A' else (dp[i][0] + dp[i][1] * 3) % MOD
	dp[i + 1][2] = dp[i][2] if S[i] != 'B' and S[i] != '?' else (dp[i][2] + dp[i][1]) % MOD if S[i] == 'B' else (dp[i][1] + dp[i][2] * 3) % MOD
	dp[i + 1][3] = dp[i][3] if S[i] != 'C' and S[i] != '?' else (dp[i][3] + dp[i][2]) % MOD if S[i] == 'C' else (dp[i][2] + dp[i][3] * 3) % MOD
print(dp[N][3])


m = 10 ** 9 + 7
n = 1
a = ab = abc = 0
for c in input():
	if c == 'A':
		a += n
	elif c == 'B':
		ab += a
	elif c == 'C':
		abc += ab
	else:
		(ta, tab) = (a, ab)
		a *= 3
		ab *= 3
		abc *= 3
		a += n
		ab += ta
		abc += tab
		n *= 3
	a %= m
	ab %= m
	abc %= m
	n %= m
print(abc)


S = input()
MOD = 10 ** 9 + 7
A = 0
AB = 0
ABC = 0
cnt = 1
for c in S:
	if c == 'A':
		A += cnt
		A %= MOD
	elif c == 'B':
		AB += A
		AB %= MOD
	elif c == 'C':
		ABC += AB
		ABC %= MOD
	else:
		nA = 3 * A + cnt
		nAB = 3 * AB + A
		nABC = 3 * ABC + AB
		cnt *= 3
		(A, AB, ABC) = (nA % MOD, nAB % MOD, nABC % MOD)
		cnt %= MOD
print(ABC)


s = input()
MOD = 10 ** 9 + 7
(a, ab, abc, q) = (0, 0, 0, 1)
for x in s:
	if x == 'A':
		a += q
		a %= MOD
	elif x == 'B':
		ab += a
		ab %= MOD
	elif x == 'C':
		abc += ab
		abc %= MOD
	else:
		abc = (abc * 3 + ab) % MOD
		ab = (ab * 3 + a) % MOD
		a = (a * 3 + q) % MOD
		q = q * 3 % MOD
print(abc % MOD)


s = input()
abc = 'ABCD'
n = len(s)
mod = 10 ** 9 + 7
dp = [[0] * 4 for i in range(n + 1)]
dp[n][3] = 1
for i in range(n - 1, -1, -1):
	for j in range(4):
		if s[i] == '?':
			if j == 3:
				dp[i][j] = 3 * dp[i + 1][j]
			else:
				dp[i][j] = 3 * dp[i + 1][j] + dp[i + 1][j + 1]
		elif s[i] == abc[j]:
			if j != 3:
				dp[i][j] = dp[i + 1][j] + dp[i + 1][j + 1]
			else:
				dp[i][j] = dp[i + 1][j]
		else:
			dp[i][j] = dp[i + 1][j]
		dp[i][j] %= mod
print(dp[0][0])


mod = 10 ** 9 + 7
s = list(input())
s = ['-'] + s
l = len(s)
dp = [[0 for j in range(4)] for i in range(l)]
dp[0][0] = 1
for i in range(1, l):
	for j in range(4):
		dp[i][j] = dp[i - 1][j]
		if s[i] == '?':
			dp[i][j] *= 3
		if j and (s[i] == '?' or 'ABC'[j - 1] == s[i]):
			dp[i][j] += dp[i - 1][j - 1]
		dp[i][j] %= mod
print(dp[-1][3])


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


def main():
	MOD = 10 ** 9 + 7
	s = input()
	n = len(s)
	dp = [[0] * 4 for _ in range(n + 1)]
	dp[0][0] = 1
	for (i, c) in enumerate(s, start=1):
		for j in range(4):
			dp[i][j] = dp[i - 1][j]
		if c == 'A':
			dp[i][1] += dp[i - 1][0]
		elif c == 'B':
			dp[i][2] += dp[i - 1][1]
		elif c == 'C':
			dp[i][3] += dp[i - 1][2]
		else:
			for j in range(1, 4):
				dp[i][j] += dp[i - 1][j - 1]
			for j in range(4):
				dp[i][j] += dp[i - 1][j] * 2
		for j in range(4):
			dp[i][j] %= MOD
	print(dp[n][3])

def __starting_point():
	main()
__starting_point()


S = input()
s = 'ABC'
N = len(S)
C = 10 ** 9 + 7
dp = [[0] * 4 for _ in range(N + 1)]
dp[N][3] = 1
for i in reversed(range(N)):
	for j in range(3):
		if i < j:
			continue
		dp[i][j] = ((1 + (S[i] == '?') * 2) * dp[i + 1][j] + (S[i] in {s[j], '?'}) * dp[i + 1][j + 1]) % C
	if i >= 3:
		dp[i][3] = (1 + (S[i] == '?') * 2) * dp[i + 1][3] % C
print(dp[0][0])


import sys
sr = lambda : sys.stdin.readline().rstrip()
ir = lambda : int(sr())
lr = lambda : list(map(int, sr().split()))
S = sr()[::-1]
MOD = 10 ** 9 + 7
answer = 0
dp = [0, 0, 1]
for i in range(len(S)):
	s = S[i]
	if s == 'A':
		answer += dp[1]
	elif s == 'B':
		dp[1] += dp[0]
	elif s == 'C':
		dp[0] += dp[2]
	elif s == '?':
		answer *= 3
		answer += dp[1]
		dp[1] *= 3
		dp[1] += dp[0]
		dp[0] *= 3
		dp[0] += dp[2]
		dp[2] *= 3
	answer %= MOD
	dp[0] %= MOD
	dp[1] %= MOD
	dp[2] %= MOD
print(answer)


MOD = 10 ** 9 + 7
s = input()
a = 0
ql = 0
c = s.count('C')
qr = s.count('?')
ans = 0
for si in s:
	if si == '?':
		qr -= 1
	if si in 'B?':
		ans = (ans + pow(3, ql + qr, MOD) * a * c + (pow(3, ql + qr - 1, MOD) * (ql * c + a * qr) if ql + qr - 1 >= 0 else 0) + (pow(3, ql + qr - 2, MOD) * ql * qr if ql + qr - 2 >= 0 else 0)) % MOD
	if si == '?':
		ql += 1
	elif si == 'A':
		a += 1
	elif si == 'C':
		c -= 1
print(ans)


s = str(input())
s = s[::-1]
c = 0
bc = 0
abc = 0
_ = 1
mod = 10 ** 9 + 7
for i in range(len(s)):
	if s[i] == '?':
		abc = (abc * 3 + bc) % mod
		bc = (bc * 3 + c) % mod
		c = (c * 3 + _) % mod
		_ = _ * 3 % mod
	if s[i] == 'A':
		abc = (abc + bc) % mod
	if s[i] == 'B':
		bc = (bc + c) % mod
	if s[i] == 'C':
		c = (c + _) % mod
print(abc)


MOD = 10 ** 9 + 7

def main():
	S = input()
	N = len(S)
	pre_hatena = S[:1].count('?')
	a = S[:1].count('A')
	post_hatena = S[2:].count('?')
	c = S[2:].count('C')
	ans = 0
	for i in range(1, N - 1):
		if S[i] == '?' or S[i] == 'B':
			pre_pow = pow(3, pre_hatena - 1, MOD)
			pre = pre_pow * 3 % MOD * a + pre_pow * pre_hatena
			post_pow = pow(3, post_hatena - 1, MOD)
			post = post_pow * 3 % MOD * c + post_pow * post_hatena
			ans += pre * post
			ans %= MOD
		if S[i] == '?':
			pre_hatena += 1
		if S[i] == 'A':
			a += 1
		if S[i + 1] == '?':
			post_hatena -= 1
		if S[i + 1] == 'C':
			c -= 1
	print(ans)

def __starting_point():
	main()
__starting_point()


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
		elif S[i] == '?':
			dp[j] = (3 * DP[j] + DP[j + 1]) % p
		elif S[i] == chr(65 + j):
			dp[j] = (DP[j] + DP[j + 1]) % p
		else:
			dp[j] = DP[j]
	DP = [x for x in dp]
print(DP[0] % p)


import numpy as np
MOD = 10 ** 9 + 7
S = input()
n = len(S)
dp = np.zeros((n + 1, 4), np.int64)
dp[0, 0] = 1
for (i, c) in enumerate(S):
	if c == 'A' or c == '?':
		dp[i + 1] += dp[i]
		dp[i + 1, 1] += dp[i, 0]
	if c == 'B' or c == '?':
		dp[i + 1] += dp[i]
		dp[i + 1, 2] += dp[i, 1]
	if c == 'C' or c == '?':
		dp[i + 1] += dp[i]
		dp[i + 1, 3] += dp[i, 2]
	dp[i + 1] %= MOD
print(dp[n, 3])


s = input().lower()
n = len(s)
dp_a = 0
dp_ab = 0
dp_abc = 0
hatena = 1
mod = 10 ** 9 + 7
for i in range(n):
	if s[i] == 'a':
		dp_a = (dp_a + hatena) % mod
	elif s[i] == 'b':
		dp_ab = (dp_a + dp_ab) % mod
	elif s[i] == 'c':
		dp_abc = (dp_ab + dp_abc) % mod
	else:
		dp_abc = (dp_ab + 3 * dp_abc) % mod
		dp_ab = (3 * dp_ab + dp_a) % mod
		dp_a = (3 * dp_a + hatena) % mod
		hatena = hatena * 3 % mod
print(dp_abc)


s = input()
m = 10 ** 9 + 7
a = [1, 0, 0, 0]
for ch in s:
	if ch == 'A':
		a[1] = (a[0] + a[1]) % m
	elif ch == 'B':
		a[2] = (a[1] + a[2]) % m
	elif ch == 'C':
		a[3] = (a[2] + a[3]) % m
	else:
		a[3] = (a[2] + 3 * a[3]) % m
		a[2] = (a[1] + 3 * a[2]) % m
		a[1] = (a[0] + 3 * a[1]) % m
		a[0] = 3 * a[0] % m
print(a[3])


s = input()
mod = pow(10, 9) + 7
dp = [0] * 4
dp[0] = 1
for si in s:
	if si == 'A':
		dp[1] += dp[0]
	elif si == 'B':
		dp[2] += dp[1]
	elif si == 'C':
		dp[3] += dp[2]
	else:
		dp[3] *= 3
		dp[3] += dp[2]
		dp[2] *= 3
		dp[2] += dp[1]
		dp[1] *= 3
		dp[1] += dp[0]
		dp[0] *= 3
	dp[3] %= mod
	dp[2] %= mod
	dp[1] %= mod
	dp[0] %= mod
print(dp[3])


S = input()
N = len(S)
(a, b, c, d) = (0, 0, 0, 1)
mod = 10 ** 9 + 7
for x in reversed(S):
	if x == '?':
		(a, b, c, d) = (3 * a + b, 3 * b + c, 3 * c + d, 3 * d)
	elif x == 'A':
		a += b
	elif x == 'B':
		b += c
	elif x == 'C':
		c += d
	a %= mod
	b %= mod
	c %= mod
	d %= mod
print(a)


S = input()
MOD = 10 ** 9 + 7
(dp, dp_a, dp_ab, dp_abc) = (1, 0, 0, 0)
for s in S:
	if s == 'A':
		dp_a += dp
	elif s == 'B':
		dp_ab += dp_a
	elif s == 'C':
		dp_abc += dp_ab
	else:
		(dp, dp_a, dp_ab, dp_abc) = (dp * 3, dp_a * 3 + dp, dp_ab * 3 + dp_a, dp_abc * 3 + dp_ab)
	dp %= MOD
	dp_a %= MOD
	dp_ab %= MOD
	dp_abc %= MOD
print(dp_abc)


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


s = input()
n = len(s)
p = 10 ** 9 + 7
dp = [[0 for j in range(4)] for i in range(n + 1)]
dp[0][0] = 1
for j in range(1, 4):
	dp[0][j] = 0
for i in range(1, n + 1):
	m = 3 if s[i - 1] == '?' else 1
	for j in range(4):
		dp[i][j] = dp[i - 1][j] * m % p
	if s[i - 1] == 'A' or s[i - 1] == '?':
		dp[i][1] = (dp[i][1] + dp[i - 1][0]) % p
	if s[i - 1] == 'B' or s[i - 1] == '?':
		dp[i][2] = (dp[i][2] + dp[i - 1][1]) % p
	if s[i - 1] == 'C' or s[i - 1] == '?':
		dp[i][3] = (dp[i][3] + dp[i - 1][2]) % p
print(dp[n][3])


from collections import Counter
s = list(input())
n = len(s)
c = Counter(s)
mod = 10 ** 9 + 7
left_a = 0
left_b = 0
left_c = 0
left_q = 0
right_a = c['A']
right_b = c['B']
right_c = c['C']
right_q = c['?']

def add_ans():
	lhs = left_a * pow(3, left_q, mod) + left_q * pow(3, left_q - 1, mod)
	rhs = right_c * pow(3, right_q, mod) + right_q * pow(3, right_q - 1, mod)
	return lhs * rhs % mod
ans = 0
for i in range(n):
	if s[i] == 'A':
		left_a += 1
	if s[i] == 'B':
		ans = (ans + add_ans()) % mod
	if s[i] == 'C':
		right_c -= 1
	if s[i] == '?':
		right_q -= 1
		ans = (ans + add_ans()) % mod
		left_q += 1
print(ans)


import sys
input = sys.stdin.readline
from itertools import accumulate
MOD = 10 ** 9 + 7
S = input()
n = len(S)
acc_A = [0] * n
acc_C = [0] * n
acc_Q_left = [0] * n
acc_Q_right = [0] * n
cnt = 0
for (i, s) in enumerate(S):
	if s == 'A':
		acc_A[i] = 1
	elif s == 'C':
		acc_C[i] = 1
	elif s == '?':
		acc_Q_left[i] = 1
		acc_Q_right[i] = 1
		cnt += 1
acc_A = list(accumulate(acc_A))
acc_C = list(accumulate(acc_C[::-1]))[::-1]
acc_Q_left = list(accumulate(acc_Q_left))
acc_Q_right = list(accumulate(acc_Q_right[::-1]))[::-1]
ans = 0
for (i, s) in enumerate(S):
	if i == 0 or i == n - 1:
		continue
	if s == 'B':
		ans += acc_A[i - 1] * acc_C[i + 1] * pow(3, cnt, MOD)
		if cnt >= 1:
			ans += acc_A[i - 1] * acc_Q_right[i + 1] * pow(3, cnt - 1, MOD)
			ans += acc_Q_left[i - 1] * acc_C[i + 1] * pow(3, cnt - 1, MOD)
		if cnt >= 2:
			ans += acc_Q_left[i - 1] * acc_Q_right[i + 1] * pow(3, cnt - 2, MOD)
	elif s == '?':
		ans += acc_A[i - 1] * acc_C[i + 1] * pow(3, cnt - 1, MOD)
		if cnt >= 2:
			ans += acc_A[i - 1] * acc_Q_right[i + 1] * pow(3, cnt - 2, MOD)
			ans += acc_Q_left[i - 1] * acc_C[i + 1] * pow(3, cnt - 2, MOD)
		if cnt >= 3:
			ans += acc_Q_left[i - 1] * acc_Q_right[i + 1] * pow(3, cnt - 3, MOD)
	ans %= MOD
print(ans)


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)


S = input()
N = len(S)
MOD = 10 ** 9 + 7
res = 0
dp = [[0] * 4 for _ in range(100001)]
for i in reversed(range(N + 1)):
	for j in reversed(range(4)):
		if i == N:
			dp[i][j] = int(j == 3)
		else:
			dp[i][j] = dp[i + 1][j] * (3 if S[i] == '?' else 1)
			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])


s = str(input())
mod = 10 ** 9 + 7
dp = [[0] * 4 for i in range(len(s) + 1)]
dp[0][0] = 1
for i in range(1, len(s) + 1):
	for j in range(4):
		if s[i - 1] == '?':
			dp[i][j] = dp[i - 1][j] * 3 % mod
		else:
			dp[i][j] = dp[i - 1][j] % mod
	if s[i - 1] == 'A':
		dp[i][1] += dp[i - 1][0] % mod
	elif s[i - 1] == 'B':
		dp[i][2] += dp[i - 1][1] % mod
	elif s[i - 1] == 'C':
		dp[i][3] += dp[i - 1][2] % mod
	else:
		dp[i][1] += dp[i - 1][0] % mod
		dp[i][2] += dp[i - 1][1] % mod
		dp[i][3] += dp[i - 1][2] % mod
print(dp[-1][-1] % mod)


S = list(str(input()))
MOD = 10 ** 9 + 7
a = 0
ab = 0
abc = 0
pat = 1
for s in S:
	if s == 'A':
		a = (a + pat) % MOD
	elif s == 'B':
		ab = (ab + a) % MOD
	elif s == 'C':
		abc = (abc + ab) % MOD
	else:
		tmpa = a
		tmpab = ab
		a = (3 * a + pat) % MOD
		ab = (3 * ab + tmpa) % MOD
		abc = (3 * abc + tmpab) % MOD
		pat = pat * 3 % MOD
print(abc)


s = input()
m = 1000000007
dp = [0] * 4
dp[0] = 1
for c in s:
	if c == 'A':
		dp[1] += dp[0]
	elif c == 'B':
		dp[2] += dp[1]
	elif c == 'C':
		dp[3] += dp[2]
	elif c == '?':
		dp = [dp[0] * 3 % m, (dp[0] + dp[1] * 3) % m, (dp[1] + dp[2] * 3) % m, (dp[2] + dp[3] * 3) % m]
print(dp[3] % m)


md = 10 ** 9 + 7
s = input()
dp = [[0] * 4 for _ in range(3)]
for c in s:
	if c == 'A':
		dp[0][0] = (dp[0][0] + 1) % md
	if c == 'B':
		for j in range(2):
			dp[1][j] = (dp[1][j] + dp[0][j]) % md
	if c == 'C':
		for j in range(3):
			dp[2][j] = (dp[2][j] + dp[1][j]) % md
	if c == '?':
		for j in range(3):
			dp[2][j + 1] = (dp[2][j + 1] + dp[1][j]) % md
		for j in range(2):
			dp[1][j + 1] = (dp[1][j + 1] + dp[0][j]) % md
		dp[0][1] = (dp[0][1] + 1) % md
ans = 0
q = s.count('?')
for j in range(4):
	if q - j < 0:
		break
	ans += dp[2][j] * pow(3, q - j, md)
	ans %= md
print(ans)


s = input()
mod = 10 ** 9 + 7
dpa = [[0, 0] for i in range(len(s) + 1)]
dpc = [[0, 0] for i in range(len(s) + 1)]
power3 = [1 for i in range(10 ** 5 + 100)]
for i in range(10 ** 5 + 3):
	power3[i + 1] = power3[i] * 3 % mod
for i in range(len(s)):
	if s[i] == 'A':
		dpa[i + 1][0] = (dpa[i][0] + power3[dpa[i][1]]) % mod
		dpa[i + 1][1] = dpa[i][1]
	elif s[i] == '?':
		dpa[i + 1][0] = (3 * dpa[i][0] + power3[dpa[i][1]]) % mod
		dpa[i + 1][1] = dpa[i][1] + 1
	else:
		dpa[i + 1] = dpa[i]
for i in range(len(s)):
	if s[len(s) - 1 - i] == 'C':
		dpc[i + 1][0] = (dpc[i][0] + power3[dpc[i][1]]) % mod
		dpc[i + 1][1] = dpc[i][1]
	elif s[len(s) - 1 - i] == '?':
		dpc[i + 1][0] = (3 * dpc[i][0] + power3[dpc[i][1]]) % mod
		dpc[i + 1][1] = dpc[i][1] + 1
	else:
		dpc[i + 1] = dpc[i]
ans = 0
for i in range(1, len(s) - 1):
	if s[i] == 'B' or s[i] == '?':
		ans += dpa[i][0] * dpc[len(s) - 1 - i][0]
		ans = ans % mod
print(ans)


import sys
input = sys.stdin.readline
MOD = 10 ** 9 + 7

def main():
	string = input().strip()
	n = len(string)
	dp = [[0, 0, 0, 0] for _ in range(n + 1)]
	dp[0][0] = 1
	for (i, s) in enumerate(string):
		if s == 'A':
			dp[i + 1][0] = dp[i][0]
			dp[i + 1][1] = dp[i][1] + dp[i][0]
			dp[i + 1][2] = dp[i][2]
			dp[i + 1][3] = dp[i][3]
		elif s == 'B':
			dp[i + 1][0] = dp[i][0]
			dp[i + 1][1] = dp[i][1]
			dp[i + 1][2] = dp[i][2] + dp[i][1]
			dp[i + 1][3] = dp[i][3]
		elif s == '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][3] = dp[i][3] + dp[i][2]
		else:
			dp[i + 1][0] = 3 * dp[i][0]
			dp[i + 1][1] = 3 * dp[i][1] + dp[i][0]
			dp[i + 1][2] = 3 * dp[i][2] + dp[i][1]
			dp[i + 1][3] = 3 * dp[i][3] + dp[i][2]
		for j in range(4):
			dp[i + 1][j] %= MOD
	print(dp[-1][-1] % MOD)
main()


t = 10 ** 9 + 7
s = [1, 0, 0, 0]
n = input()
for i in n:
	if i == '?':
		for j in range(3, 0, -1):
			s[j] *= 3
			s[j] += s[j - 1]
			s[j] %= t
		s[0] *= 3
		s[0] %= t
	else:
		j = '1ABC'.index(i)
		s[j] += s[j - 1]
		s[j] %= t
print(s[3])


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


mod = 1000000007
s = input()
ans = [0, 1, 0, 0, 0]
for c in s:
	if c == '?':
		for i in range(4, 0, -1):
			ans[i] *= 3
			ans[i] += ans[i - 1]
			ans[i] %= mod
	else:
		i = '00ABC'.index(c)
		ans[i] += ans[i - 1]
		ans[i] %= mod
print(ans[-1])


S = input()
mod = 10 ** 9 + 7
dic = {'': 1, 'A': 0, 'B': 0, 'C': 0}
for s in S:
	if s == 'A':
		dic[s] += dic['']
	elif s == 'B':
		dic[s] += dic['A']
	elif s == 'C':
		dic[s] += dic['B']
	elif s == '?':
		dic['C'] = dic['C'] * 3 + dic['B']
		dic['B'] = dic['B'] * 3 + dic['A']
		dic['A'] = dic['A'] * 3 + dic['']
		dic[''] *= 3
	dic[''] %= mod
	dic['A'] %= mod
	dic['B'] %= mod
	dic['C'] %= mod
print(dic['C'] % mod)


s = input()
n = len(s)
mod = 10 ** 9 + 7
dp = [[0] * 4 for _ in range(n + 1)]
dp[n][3] = 1
for i in reversed(list(range(n))):
	for j in reversed(list(range(4))):
		if j == 3:
			if s[i] == '?':
				m = 3
			else:
				m = 1
			dp[i][j] += m * dp[i + 1][j]
		else:
			if s[i] == '?':
				m1 = 3
			else:
				m1 = 1
			if j == 0:
				if s[i] == 'A' or s[i] == '?':
					m2 = 1
				else:
					m2 = 0
			elif j == 1:
				if s[i] == 'B' or s[i] == '?':
					m2 = 1
				else:
					m2 = 0
			elif s[i] == 'C' or s[i] == '?':
				m2 = 1
			else:
				m2 = 0
			dp[i][j] += m1 * dp[i + 1][j] + m2 * dp[i + 1][j + 1]
		dp[i][j] %= mod
print(dp[0][0] % mod)


def main():
	mod = 10 ** 9 + 7
	s = input()
	n = len(s)
	a_num = 0
	c_num = s.count('C')
	q_num = 0
	q_cnt = s.count('?')
	(pow3, pow2, pow1, pow0) = (0, 0, 0, 0)
	if q_cnt >= 3:
		pow3 = pow(3, q_cnt - 3, mod)
		pow2 = pow3 * 3 % mod
		pow1 = pow2 * 3 % mod
		pow0 = pow1 * 3 % mod
	elif q_cnt == 2:
		pow2 = 1
		pow1 = 3
		pow0 = 9
	elif q_cnt == 1:
		pow1 = 1
		pow0 = 3
	else:
		pow0 = 1
	ans = 0
	for x in s:
		if x == 'A':
			a_num += 1
		elif x == 'B':
			ans += pow0 * a_num * c_num
			ans += pow1 * (q_num * c_num + a_num * (q_cnt - q_num))
			ans += pow2 * q_num * (q_cnt - q_num)
			ans %= mod
		elif x == 'C':
			c_num -= 1
		else:
			ans += pow1 * a_num * c_num
			ans += pow2 * (q_num * c_num + a_num * (q_cnt - q_num - 1))
			ans += pow3 * q_num * (q_cnt - q_num - 1)
			ans %= mod
			q_num += 1
	print(ans)
main()


s = input()
l = len(s)
mod = 10 ** 9 + 7
dp = [[0, 0, 0, 0] for _ in range(l + 1)]
for i in range(l, -1, -1):
	for j in range(3, -1, -1):
		if i == l:
			if j == 3:
				dp[i][j] = 1
			else:
				dp[i][j] = 0
		else:
			if s[i] == '?':
				dp[i][j] = dp[i + 1][j] * 3
			else:
				dp[i][j] = dp[i + 1][j]
			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])


import sys
input = sys.stdin.readline
S = input().strip()
mod = 10 ** 9 + 7
a = 0
ab = 0
ans = 0
q = 1
for c in S:
	if c == 'A':
		a += q
	elif c == 'B':
		ab += a
	elif c == 'C':
		ans += ab
	elif c == '?':
		(a, ab, ans, q) = (a * 3 + q, ab * 3 + a, ans * 3 + ab, q * 3)
	a %= mod
	ab %= mod
	ans %= mod
	q %= mod
print(ans % mod)


S = input()
N = len(S)
mod = 10 ** 9 + 7
numofA = 0
numofAB = 0
numofABC = 0
numofquestion = 1
for i in range(N):
	if S[i] == '?':
		numofABC = (numofABC * 3 + numofAB) % mod
		numofAB = (numofAB * 3 + numofA) % mod
		numofA = (numofquestion + numofA * 3) % mod
		numofquestion = numofquestion * 3 % mod
	elif S[i] == 'C':
		numofABC = (numofAB + numofABC) % mod
	elif S[i] == 'B':
		numofAB = (numofAB + numofA) % mod
	else:
		numofA = (numofquestion + numofA) % mod
print(numofABC)


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)


import sys
S = list(input())
p = 10 ** 9 + 7
A = AB = ABC = 0
power = 1
for (i, Si) in enumerate(S):
	if Si == 'A':
		A = (A + 1 * power) % p
	elif Si == 'B':
		AB = (AB + A) % p
	elif Si == 'C':
		ABC = (ABC + AB) % p
	else:
		ABC = (3 * ABC + AB) % p
		AB = (3 * AB + A) % p
		A = (3 * A + 1 * power) % p
		power = power * 3 % p
print(ABC)


S = input()
a = 0
ab = 0
ans = 0
n = 1
m = 10 ** 9 + 7
for s in S:
	if s == 'A':
		a += n
	elif s == 'B':
		ab += a
	elif s == 'C':
		ans += ab
	else:
		ans += 2 * ans + ab
		ab += 2 * ab + a
		a += 2 * a + n
		n *= 3
		n %= m
	ans %= m
	ab %= m
	a %= m
print(ans)


import sys
readline = sys.stdin.readline
S = readline().rstrip()
DIV = 10 ** 9 + 7
dp = [[0] * 4 for i in range(len(S) + 1)]
dp[0][0] = 1
for i in range(len(S)):
	if S[i] == 'A' or S[i] == '?':
		dp[i + 1][0] += dp[i][0]
		dp[i + 1][1] += dp[i][1]
		dp[i + 1][2] += dp[i][2]
		dp[i + 1][3] += dp[i][3]
		dp[i + 1][1] += dp[i][0]
	if S[i] == 'B' or S[i] == '?':
		dp[i + 1][0] += dp[i][0]
		dp[i + 1][1] += dp[i][1]
		dp[i + 1][2] += dp[i][2]
		dp[i + 1][3] += dp[i][3]
		dp[i + 1][2] += dp[i][1]
	if S[i] == 'C' or S[i] == '?':
		dp[i + 1][0] += dp[i][0]
		dp[i + 1][1] += dp[i][1]
		dp[i + 1][2] += dp[i][2]
		dp[i + 1][3] += dp[i][3]
		dp[i + 1][3] += dp[i][2]
	for j in range(4):
		dp[i + 1][j] %= DIV
print(dp[len(S)][3])


s = str(input())
n = len(s)
mod = 10 ** 9 + 7
X = [[0] * 4 for _ in range(n + 1)]
for i in range(n):
	for j in range(4):
		X[i + 1][j] = X[i][j]
	if s[i] == 'A':
		X[i + 1][0] += 1
	elif s[i] == 'B':
		X[i + 1][1] += 1
	elif s[i] == 'C':
		X[i + 1][2] += 1
	else:
		X[i + 1][3] += 1
Y = [[0] * 4 for _ in range(n + 1)]
for i in reversed(list(range(n))):
	for j in range(4):
		Y[i][j] = Y[i + 1][j]
	if s[i] == 'A':
		Y[i][0] += 1
	elif s[i] == 'B':
		Y[i][1] += 1
	elif s[i] == 'C':
		Y[i][2] += 1
	else:
		Y[i][3] += 1
c = X[n][3]
ans = 0
for i in range(n):
	if s[i] == 'B':
		ans += X[i + 1][3] * Y[i][3] * pow(3, max(0, c - 2), mod)
		ans += X[i + 1][0] * Y[i][2] * pow(3, c, mod)
		ans += X[i + 1][3] * Y[i][2] * pow(3, max(0, X[i + 1][3] - 1 + Y[i][3]), mod)
		ans += X[i + 1][0] * Y[i][3] * pow(3, max(0, X[i + 1][3] + Y[i][3] - 1), mod)
		ans %= mod
	if s[i] == '?':
		ans += X[i][3] * Y[i + 1][3] * pow(3, max(0, c - 3), mod)
		ans += X[i + 1][0] * Y[i][2] * pow(3, max(0, c - 1), mod)
		ans += X[i][3] * Y[i][2] * pow(3, max(0, X[i][3] - 1 + Y[i + 1][3]), mod)
		ans += X[i + 1][0] * Y[i + 1][3] * pow(3, max(0, X[i][3] + Y[i + 1][3] - 1), mod)
		ans %= mod
		ans %= mod
print(ans)


S = input()
mod = 10 ** 9 + 7
(La, Lq, Rc, Rq) = (0, 0, S.count('C'), S.count('?'))
ans = 0
f = lambda x, y: pow(x, y, mod) if y >= 0 else 0
for s in S:
	Rc -= s == 'C'
	Rq -= s == '?'
	if s == 'B' or s == '?':
		ans += (La * f(3, Lq) + Lq * f(3, Lq - 1)) * (Rc * f(3, Rq) + Rq * f(3, Rq - 1))
		ans %= mod
	La += s == 'A'
	Lq += s == '?'
print(ans)


S = str(input())
N = len(S)
dp = [[0 for _ in range(4)] for _ in range(N + 1)]
dp[0][0] = 1
mod = 10 ** 9 + 7
for i in range(N):
	if S[i] == 'A':
		dp[i + 1][0] += dp[i][0] % mod
		dp[i + 1][1] += dp[i][1] % mod + dp[i][0] % mod
		dp[i + 1][2] += dp[i][2] % mod
		dp[i + 1][3] += dp[i][3] % mod
	if S[i] == 'B':
		dp[i + 1][0] += dp[i][0] % mod
		dp[i + 1][1] += dp[i][1] % mod
		dp[i + 1][2] += dp[i][2] % mod + dp[i][1] % mod
		dp[i + 1][3] += dp[i][3] % mod
	if S[i] == 'C':
		dp[i + 1][0] += dp[i][0] % mod
		dp[i + 1][1] += dp[i][1] % mod
		dp[i + 1][2] += dp[i][2] % mod
		dp[i + 1][3] += dp[i][3] % mod + dp[i][2] % mod
	if S[i] == '?':
		dp[i + 1][0] += 3 * dp[i][0] % mod
		dp[i + 1][1] += 3 * dp[i][1] % mod + dp[i][0] % mod
		dp[i + 1][2] += 3 * dp[i][2] % mod + dp[i][1] % mod
		dp[i + 1][3] += 3 * dp[i][3] % mod + dp[i][2] % mod
print(dp[N][3] % mod)


def main():
	S = input()
	mod = 10 ** 9 + 7
	A = AB = ABC = 0
	n = 1
	for i in S:
		if i == '?':
			ABC = ABC * 3 + AB
			AB = AB * 3 + A
			A = A * 3 + n
			n = n * 3 % mod
		if i == 'C':
			ABC = ABC + AB
		if i == 'B':
			AB = AB + A
		if i == 'A':
			A += n
	print(ABC % mod)
main()


S = input()
a = 0
b = 0
c = 0
p = 1
mod = 1000000000 + 7
for C in S:
	if C == '?':
		c = 3 * c + b
		b = 3 * b + a
		a = 3 * a + p
		p *= 3
	elif C == 'A':
		a += p
	elif C == 'B':
		b += a
	elif C == 'C':
		c += b
	a %= mod
	b %= mod
	c %= mod
	p %= mod
print(c)


from functools import reduce
M = 10 ** 9 + 7
S = input()
ans = reduce(lambda t, s: (t[0], t[1] + t[0], t[2], t[3]) if s == 'A' else (t[0], t[1], t[1] + t[2], t[3]) if s == 'B' else (t[0], t[1], t[2], t[2] + t[3]) if s == 'C' else (3 * t[0] % M, (3 * t[1] + t[0]) % M, (3 * t[2] + t[1]) % M, (3 * t[3] + t[2]) % M), S, (1, 0, 0, 0))[3] % M
print(ans)


s = input()
dp = [[0 for _ in range(4)] for _ in range(len(s))]
mod = 10 ** 9 + 7
power_3 = 1
for (idx, letter) in enumerate(s):
	dp[idx] = dp[idx - 1].copy()
	if letter == 'A':
		dp[idx][1] += power_3
	elif letter == 'B':
		dp[idx][2] += dp[idx - 1][1]
	elif letter == 'C':
		dp[idx][3] += dp[idx - 1][2]
	elif letter == '?':
		dp[idx][1] *= 3
		dp[idx][2] *= 3
		dp[idx][3] *= 3
		dp[idx][1] += power_3
		power_3 *= 3
		power_3 %= mod
		dp[idx][2] += dp[idx - 1][1]
		dp[idx][3] += dp[idx - 1][2]
		dp[idx][1] %= mod
		dp[idx][2] %= mod
		dp[idx][3] %= mod
print(dp[len(s) - 1][3] % mod)


mod = 1000000007
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])


def modinv(a, m):
	return pow(a, m - 2, m)
import copy
S = input()
N = len(S)
dp = [[[0, 0], [0, 0, 0], [0, 0, 0, 0]] for i in range(N + 1)]
mod = 10 ** 9 + 7
for i in range(N):
	dp[i + 1] = copy.deepcopy(dp[i])
	if S[i] == 'A':
		dp[i + 1][0][0] += 1
	elif S[i] == 'B':
		for j in range(2):
			dp[i + 1][1][j] = (dp[i + 1][1][j] + dp[i][0][j]) % mod
	elif S[i] == 'C':
		for j in range(3):
			dp[i + 1][2][j] = (dp[i + 1][2][j] + dp[i][1][j]) % mod
	else:
		dp[i + 1][0][1] += 1
		for j in range(2):
			dp[i + 1][1][j + 1] = (dp[i + 1][1][j + 1] + dp[i][0][j]) % mod
		for j in range(3):
			dp[i + 1][2][j + 1] = (dp[i + 1][2][j + 1] + dp[i][1][j]) % mod
Q = S.count('?')
inv3 = modinv(3, mod)
inv9 = inv3 * inv3 % mod
inv27 = inv9 * inv3 % mod
threeQ = pow(3, Q, mod)
ans = threeQ * (dp[N][2][0] + dp[N][2][1] * inv3 + dp[N][2][2] * inv9 + dp[N][2][3] * inv27) % mod
print(ans)


s = input()
mod = 10 ** 9 + 7
a = 0
ab = 0
abc = 0
q = 1
for i in s:
	if i == '?':
		abc *= 3
		abc += ab
		ab *= 3
		ab += a
		a *= 3
		a += q
		q *= 3
		q %= mod
	elif i == 'A':
		a += q
	elif i == 'B':
		ab += a
	else:
		abc += ab
	abc %= mod
	ab %= mod
	a %= mod
print(abc)


MOD = 10 ** 9 + 7
S = input()
N = len(S)
(Acum, Ccum, Qcum) = ([0] * (N + 1), [0] * (N + 1), [0] * (N + 1))
for i in range(N):
	Acum[i + 1] = Acum[i] + 1 if S[i] == 'A' else Acum[i]
	Ccum[i + 1] = Ccum[i] + 1 if S[i] == 'C' else Ccum[i]
	Qcum[i + 1] = Qcum[i] + 1 if S[i] == '?' else Qcum[i]
ans = 0
for i in range(N):
	if S[i] != 'B' and S[i] != '?':
		continue
	(a, c, l, r) = (Acum[i], Ccum[N] - Ccum[i + 1], Qcum[i], Qcum[N] - Qcum[i + 1])
	res = pow(3, l + r - 2, MOD) * (3 * a + l) % MOD * (3 * c + r) % MOD
	ans = (ans + res) % MOD
print(ans)


S = input()
MOD = 10 ** 9 + 7
dp = [1, 0, 0, 0]
for s in S:
	if s == 'A':
		dp[1] += dp[0]
	elif s == 'B':
		dp[2] += dp[1]
	elif s == 'C':
		dp[3] += dp[2]
	elif s == '?':
		dp[3] *= 3
		dp[3] += dp[2]
		dp[2] *= 3
		dp[2] += dp[1]
		dp[1] *= 3
		dp[1] += dp[0]
		dp[0] *= 3
	for i in range(4):
		dp[i] %= MOD
print(dp[3])


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


s = input()
n = len(s)
mod = 10 ** 9 + 7
qcnt = [[0, 0] for i in range(n)]
Acnt = [0] * n
Ccnt = [0] * n
q = 0
for i in range(n - 1):
	if s[i] == '?':
		q += 1
		qcnt[i + 1][0] += 1
	elif s[i] == 'A':
		Acnt[i + 1] += 1
	qcnt[i + 1][0] += qcnt[i][0]
	Acnt[i + 1] += Acnt[i]
	qcnt[i + 1][0] %= mod
	Acnt[i + 1] %= mod
if s[-1] == '?':
	q += 1
for i in range(n - 1, 0, -1):
	if s[i] == '?':
		qcnt[i - 1][1] += 1
	elif s[i] == 'C':
		Ccnt[i - 1] += 1
	qcnt[i - 1][1] += qcnt[i][1]
	Ccnt[i - 1] += Ccnt[i]
	qcnt[i - 1][1] %= mod
	Ccnt[i - 1] %= mod
ans = 0
for i in range(n):
	if s[i] == 'B' or s[i] == '?':
		if qcnt[i][0] + qcnt[i][1] - 2 < 0:
			val = -(qcnt[i][0] + qcnt[i][1] - 2)
			p = pow(3, val, mod)
			q = pow(p, mod - 2, mod)
			ans += q % mod * (3 * Acnt[i] + qcnt[i][0]) * (3 * Ccnt[i] + qcnt[i][1]) % mod
		else:
			ans += pow(3, qcnt[i][0] + qcnt[i][1] - 2, mod) % mod * (3 * Acnt[i] + qcnt[i][0]) * (3 * Ccnt[i] + qcnt[i][1]) % mod
		ans %= mod
print(ans % mod)


Mod = 10 ** 9 + 7
S = input()
N = len(S)
O = 1
A = [0] * N
AB = [0] * N
ABC = [0] * N
for i in range(N):
	A[i] = A[i - 1]
	AB[i] = AB[i - 1]
	ABC[i] = ABC[i - 1]
	if S[i] == 'A':
		A[i] += O
	if S[i] == 'B':
		AB[i] += A[i - 1]
	if S[i] == 'C':
		ABC[i] += AB[i - 1]
	if S[i] == '?':
		A[i] *= 3
		A[i] += O
		AB[i] *= 3
		AB[i] += A[i - 1]
		ABC[i] *= 3
		ABC[i] += AB[i - 1]
		O *= 3
	A[i] %= Mod
	AB[i] %= Mod
	ABC[i] %= Mod
	O %= Mod
print(ABC[-1])


S = input()
mod = 10 ** 9 + 7
(a, ab, abc, n) = (0, 0, 0, 1)
for s in S:
	if s == 'A':
		a += n
		a %= mod
	elif s == 'B':
		ab += a
		ab %= mod
	elif s == 'C':
		abc += ab
		abc %= mod
	else:
		(a, ab, abc, n) = (3 * a + n, 3 * ab + a, 3 * abc + ab, 3 * n)
		a %= mod
		ab %= mod
		abc %= mod
		n %= mod
print(abc)


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)


p = [1, 0, 0, 0]
m = 1000000000.0 + 7

def mod(x):
	return int(x % m)
for s in input():
	if s == 'A':
		p[1] = mod(p[0] + p[1])
	if s == 'B':
		p[2] = mod(p[1] + p[2])
	if s == 'C':
		p[3] = mod(p[2] + p[3])
	if s == '?':
		p[3] = mod(p[2] + p[3] * 3)
		p[2] = mod(p[1] + p[2] * 3)
		p[1] = mod(p[0] + p[1] * 3)
		p[0] = mod(p[0] * 3)
print(int(p[3] % m))


s = input()
dp = [[0] * (len(s) + 1) for _ in [0] * 4]
dp[0][0] = 1
mod = 10 ** 9 + 7
for (i, (c, n0, n1, n2, n3)) in enumerate(zip(s, dp[0], dp[1], dp[2], dp[3]), start=1):
	m = 3 if c == '?' else 1
	dp[0][i] = n0 * m % mod
	dp[1][i] = (n1 * m + n0 * (c == 'A' or c == '?')) % mod
	dp[2][i] = (n2 * m + n1 * (c == 'B' or c == '?')) % mod
	dp[3][i] = (n3 * m + n2 * (c == 'C' or c == '?')) % mod
print(dp[-1][-1])


s = input()
n = len(s)
p = 10 ** 9 + 7
q = s.count('?')
l_a = [0] * n
l_x = [0] * n
r_c = [0] * n
r_x = [0] * n
for i in range(1, n):
	l_a[i] = l_a[i - 1] + int(s[i - 1] == 'A')
	l_x[i] = l_x[i - 1] + int(s[i - 1] == '?')
	r_c[n - i - 1] = r_c[n - i] + int(s[n - i] == 'C')
	r_x[n - i - 1] = r_x[n - i] + int(s[n - i] == '?')
ans = 0
pow_q = []
for i in range(0, 4):
	pow_q.append(max(1, 3 ** (q - i) % p))
for i in range(n):
	if s[i] == 'B':
		ans += l_a[i] * r_c[i] % p * pow_q[0] % p
		ans += l_x[i] * r_c[i] % p * pow_q[1] % p
		ans += l_a[i] * r_x[i] % p * pow_q[1] % p
		ans += l_x[i] * r_x[i] % p * pow_q[2] % p
		ans %= p
	elif s[i] == '?':
		ans += l_a[i] * r_c[i] % p * pow_q[1] % p
		ans += l_x[i] * r_c[i] % p * pow_q[2] % p
		ans += l_a[i] * r_x[i] % p * pow_q[2] % p
		ans += l_x[i] * r_x[i] % p * pow_q[3] % p
		ans %= p
print(ans)


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


S = input()
N = len(S)
MOD = 1000000007
dp = [[0] * 4 for i in range(N + 1)]
for i in range(N, -1, -1):
	for j in range(3, -1, -1):
		if i == N:
			dp[i][j] = 1 if j == 3 else 0
		else:
			dp[i][j] = dp[i + 1][j] * (3 if S[i] == '?' else 1)
			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])


S = input()
MOD = 10 ** 9 + 7
dp = [0] * 3
pp = [0] * 3
nq = 0
for s in S:
	pp = dp
	dp = pp.copy()
	if s == 'A':
		dp[0] += pow(3, nq, MOD)
	elif s == 'B':
		dp[1] += pp[0]
	elif s == 'C':
		dp[2] += pp[1]
	else:
		dp[0] += pp[0] * 2 + pow(3, nq, MOD)
		dp[1] += pp[1] * 2 + pp[0]
		dp[2] += pp[2] * 2 + pp[1]
		nq += 1
	dp[0] %= MOD
	dp[1] %= MOD
	dp[2] %= MOD
print(dp[2])


S = input()
lis = [1, 0, 0, 0]
nlis = [1, 0, 0, 0]
for s in S:
	if s == '?':
		nlis[0] += lis[0] * 2
		nlis[1] += lis[1] * 2
		nlis[2] += lis[2] * 2
		nlis[3] += lis[3] * 2
	if s == 'A' or s == '?':
		nlis[1] += lis[0]
	if s == 'B' or s == '?':
		nlis[2] += lis[1]
	if s == 'C' or s == '?':
		nlis[3] += lis[2]
	lis = []
	for i in range(4):
		lis.append(nlis[i] % (10 ** 9 + 7))
print(lis[3] % (10 ** 9 + 7))


import sys
input = sys.stdin.readline
S = input().rstrip()
N = len(S)
mod = 10 ** 9 + 7
dp = [0, 0, 0]
k = 1
for i in range(N):
	if S[i] == 'A':
		dp[0] += k
	elif S[i] == 'B':
		dp[1] += dp[0]
	elif S[i] == 'C':
		dp[2] += dp[1]
	else:
		dp[2] = 3 * dp[2] + dp[1]
		dp[1] = 3 * dp[1] + dp[0]
		dp[0] = 3 * dp[0] + k
		k = k * 3 % mod
	dp[0] %= mod
	dp[1] %= mod
	dp[2] %= mod
print(dp[2])


box = [1, 0, 0, 0]
for c in input():
	if c == 'A':
		box[1] = box[0] + box[1]
	elif c == 'B':
		box[2] = box[1] + box[2]
	elif c == 'C':
		box[3] = box[2] + box[3]
	elif c == '?':
		box = [box[0] * 3, box[1] * 3 + box[0], box[2] * 3 + box[1], box[3] * 3 + box[2]]
	box = [i % (10 ** 9 + 7) for i in box]
print(box[3])


import sys
import math
from collections import deque
sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda : sys.stdin.readline().strip()
NI = lambda : int(input())
NMI = lambda : map(int, input().split())
NLI = lambda : list(NMI())
SI = lambda : input()

def make_grid(h, w, num):
	return [[int(num)] * w for _ in range(h)]

def main():
	S = SI()
	N = len(S)
	dp = make_grid(N + 1, 4, 0)
	dic = {'A': [0], 'B': [1], 'C': [2], '?': [0, 1, 2]}
	dp[0][0] = 1
	for (i, s) in enumerate(S):
		if s == '?':
			for j in range(4):
				if j in dic[s]:
					dp[i + 1][j + 1] += dp[i][j] % MOD
				dp[i + 1][j] += dp[i][j] * 3 % MOD
		else:
			for j in range(4):
				if j in dic[s]:
					dp[i + 1][j + 1] += dp[i][j] % MOD
				dp[i + 1][j] += dp[i][j] % MOD
	print(dp[N][3] % MOD)

def __starting_point():
	main()
__starting_point()


s = input()
a = 0
ab = 0
abc = 0
total = 1
mod = 10 ** 9 + 7
for i in range(len(s)):
	if s[i] == 'A':
		a += total
	elif s[i] == 'B':
		ab += a
	elif s[i] == 'C':
		abc += ab
	else:
		abc = 3 * abc + ab
		ab = 3 * ab + a
		a = 3 * a + total
		total *= 3
	a %= mod
	ab %= mod
	abc %= mod
	total %= mod
print(abc)


s = input()
n = len(s)
mod = 10 ** 9 + 7
dp = [[0] * 3 for _ in range(n)]
cnt = 1
for i in range(n):
	if s[i] == '?':
		if i > 0:
			dp[i][2] = dp[i - 1][1] + 3 * dp[i - 1][2]
			dp[i][2] %= mod
			dp[i][1] = dp[i - 1][0] + 3 * dp[i - 1][1]
			dp[i][1] %= mod
			dp[i][0] = 3 * dp[i - 1][0] + 1 * cnt
			dp[i][0] %= mod
		else:
			dp[i][0] = 1
		cnt *= 3
		cnt %= mod
	elif s[i] == 'C':
		if i > 0:
			dp[i][2] = dp[i - 1][1] + dp[i - 1][2]
			dp[i][2] %= mod
			dp[i][1] = dp[i - 1][1]
			dp[i][0] = dp[i - 1][0]
	elif s[i] == 'B':
		if i > 0:
			dp[i][2] = dp[i - 1][2]
			dp[i][1] = dp[i - 1][0] + dp[i - 1][1]
			dp[i][1] %= mod
			dp[i][0] = dp[i - 1][0]
	elif s[i] == 'A':
		if i > 0:
			dp[i][2] = dp[i - 1][2]
			dp[i][1] = dp[i - 1][1]
			dp[i][0] = dp[i - 1][0] + 1 * cnt
			dp[i][0] %= mod
		else:
			dp[0][0] = 1
print(dp[-1][2] % mod)


s = input()
mod = 1000000007
dp = [1, 0, 0, 0]
for c in s:
	newdp = [n for n in dp]
	if c == 'A':
		newdp[1] = (newdp[1] + dp[0]) % mod
	if c == 'B':
		newdp[2] = (newdp[2] + dp[1]) % mod
	if c == 'C':
		newdp[3] = (newdp[3] + dp[2]) % mod
	if c == '?':
		newdp[0] = newdp[0] * 3 % mod
		newdp[1] = (newdp[1] * 3 + dp[0]) % mod
		newdp[2] = (newdp[2] * 3 + dp[1]) % mod
		newdp[3] = (newdp[3] * 3 + dp[2]) % mod
	dp = newdp
print(dp[3])


S = input()
emp = 1
A = 0
AB = 0
ABC = 0
big = 10 ** 9 + 7
for a in S:
	if a == 'A':
		(emp, A, AB, ABC) = (emp, emp + A, AB, ABC)
	if a == 'B':
		(emp, A, AB, ABC) = (emp, A, A + AB, ABC)
	if a == 'C':
		(emp, A, AB, ABC) = (emp, A, AB, AB + ABC)
	if a == '?':
		(emp, A, AB, ABC) = (3 * emp % big, (emp + 3 * A) % big, (A + 3 * AB) % big, (AB + 3 * ABC) % big)
print(ABC % big)


S = input()
dp = [(-1, -1, -1, -1)] * (len(S) + 1)
dp[0] = (1, 0, 0, 0)
for i in range(len(S)):
	(w, x, y, z) = dp[i]
	if S[i] == 'A':
		x += w
	elif S[i] == 'B':
		y += x
	elif S[i] == 'C':
		z += y
	else:
		z = 3 * z + y
		y = 3 * y + x
		x = 3 * x + w
		w = 3 * w
	w = w % 1000000007
	x = x % 1000000007
	y = y % 1000000007
	z = z % 1000000007
	dp[i + 1] = (w, x, y, z)
res = dp[len(S)][3]
print(res)


N = input()
DP = [[0] * (len(N) + 1) for i in range(4)]
DP[0][0] = 1
mod = 10 ** 9 + 7
for i in range(len(N)):
	if N[i] == 'A':
		DP[0][i + 1] = DP[0][i] % mod
		DP[1][i + 1] = (DP[1][i] + DP[0][i]) % mod
		DP[2][i + 1] = DP[2][i] % mod
		DP[3][i + 1] = DP[3][i] % mod
	elif N[i] == 'B':
		DP[0][i + 1] = DP[0][i] % mod
		DP[1][i + 1] = DP[1][i] % mod
		DP[2][i + 1] = (DP[2][i] + DP[1][i]) % mod
		DP[3][i + 1] = DP[3][i] % mod
	elif N[i] == 'C':
		DP[0][i + 1] = DP[0][i] % mod
		DP[1][i + 1] = DP[1][i] % mod
		DP[2][i + 1] = DP[2][i] % mod
		DP[3][i + 1] = (DP[3][i] + DP[2][i]) % mod
	else:
		DP[3][i + 1] = (3 * DP[3][i] + DP[2][i]) % mod
		DP[0][i + 1] = DP[0][i] * 3 % mod
		DP[1][i + 1] = (DP[1][i] * 3 + DP[0][i]) % mod
		DP[2][i + 1] = (DP[2][i] * 3 + DP[1][i]) % mod
print(DP[3][-1] % mod)


D = [0, 0, 0, 1, 0]
for s in input():
	D = [(D[j] * ((s == '?') * 2 + 1) + D[j + 1] * (s in t + '?')) % (10 ** 9 + 7) for (j, t) in enumerate('CBA.')] + [0]
print(D[0])


s = input()
dp = [[0] * (len(s) + 1) for _ in range(4)]
dp[0][0] = 1
for (i, c) in enumerate(s):
	if c == 'A' or c == '?':
		dp[1][i + 1] = dp[0][i]
	if c == 'B' or c == '?':
		dp[2][i + 1] = dp[1][i]
	if c == 'C' or c == '?':
		dp[3][i + 1] = dp[2][i]
	for j in range(4):
		if c == '?':
			dp[j][i + 1] += dp[j][i] * 3
		else:
			dp[j][i + 1] += dp[j][i]
		dp[j][i + 1] %= 10 ** 9 + 7
print(dp[-1][-1])


def solve(s, MOD=int(1000000000.0 + 7)):
	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
		(k, a, ab, abc) = map(lambda x: x % MOD, [k, a, ab, abc])
	return abc % MOD
print(solve(input()))


MOD = 10 ** 9 + 7
dp = [0, 0]
ans = 0
t = 1
for c in input():
	ndp = dp.copy()
	if c in 'A':
		ndp[0] = (dp[0] + t) % MOD
	elif c in 'B':
		ndp[1] = (ndp[1] + dp[0]) % MOD
	elif c in 'C':
		ans = (ans + dp[1]) % MOD
	else:
		ndp[0] = (3 * dp[0] + t) % MOD
		ndp[1] = (3 * dp[1] + dp[0]) % MOD
		ans = (3 * ans + dp[1]) % MOD
		t = t * 3 % MOD
	dp = ndp
print(ans)


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


def inpl():
	return list(map(int, input().split()))
MOD = 10 ** 9 + 7
S = input()
(A, B, C) = (0, 0, 0)
q = 0
for (i, s) in enumerate(S, start=1):
	if s == 'A':
		A = (A + pow(3, q, MOD)) % MOD
	elif s == 'B':
		B = (B + A) % MOD
	elif s == 'C':
		C = (C + B) % MOD
	elif s == '?':
		(A, B, C) = ((3 * A + pow(3, q, MOD)) % MOD, (3 * B + A) % MOD, (3 * C + B) % MOD)
		q += 1
print(C)


from sys import stdin

def main():
	readline = stdin.readline
	s = readline().strip()
	mod = 10 ** 9 + 7
	n = len(s)
	dp = [[0] * 4 for _ in range(n + 1)]
	dp[0][0] = 1
	for i in range(1, n + 1):
		for j in range(4):
			if s[i - 1] != '?':
				dp[i][j] += dp[i - 1][j]
			else:
				dp[i][j] += dp[i - 1][j] * 3
		if s[i - 1] == 'A':
			dp[i][1] += dp[i - 1][0]
		elif s[i - 1] == 'B':
			dp[i][2] += dp[i - 1][1]
		elif s[i - 1] == 'C':
			dp[i][3] += dp[i - 1][2]
		elif s[i - 1] == '?':
			dp[i][1] += dp[i - 1][0]
			dp[i][2] += dp[i - 1][1]
			dp[i][3] += dp[i - 1][2]
		for j in range(4):
			dp[i][j] %= mod
	print(dp[n][3])

def __starting_point():
	main()
__starting_point()


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


s = input()
n_a = [0]
n_l = [0]
n_c = [0]
n_r = [0]
mod = 10 ** 9 + 7
n = len(s)
pow3 = [1]
for i in range(n):
	pow3.append(pow3[-1] * 3 % mod)
for i in range(n):
	if s[i] == 'A':
		n_a.append(n_a[-1] + 1)
	else:
		n_a.append(n_a[-1])
	if s[i] == '?':
		n_l.append(n_l[-1] + 1)
	else:
		n_l.append(n_l[-1])
	if s[-i - 1] == 'C':
		n_c.append(n_c[-1] + 1)
	else:
		n_c.append(n_c[-1])
	if s[-i - 1] == '?':
		n_r.append(n_r[-1] + 1)
	else:
		n_r.append(n_r[-1])
ans = 0
for i in range(1, n - 1):
	if s[i] in ['B', '?']:
		ans += n_a[i] * n_c[n - 1 - i] * pow3[n_l[i]] * pow3[n_r[n - 1 - i]] % mod
		ans %= mod
		ans += n_l[i] * n_c[n - 1 - i] * pow3[n_l[i] - 1] * pow3[n_r[n - 1 - i]] % mod
		ans %= mod
		ans += n_a[i] * n_r[n - 1 - i] * pow3[n_l[i]] * pow3[n_r[n - 1 - i] - 1] % mod
		ans %= mod
		ans += n_l[i] * n_r[n - 1 - i] * pow3[n_l[i] - 1] * pow3[n_r[n - 1 - i] - 1] % mod
		ans %= mod
print(ans)


mod = 10 ** 9 + 7
S = input()
dp = [[0] * 4 for i in range(len(S) + 1)]
dp[0][0] = 1
for i in range(len(S)):
	for j in range(4):
		if S[i] == '?':
			dp[i + 1][j] = dp[i][j] * 3 % mod
		else:
			dp[i + 1][j] = dp[i][j]
	if S[i] == 'A' or S[i] == '?':
		dp[i + 1][1] += dp[i][0]
	if S[i] == 'B' or S[i] == '?':
		dp[i + 1][2] += dp[i][1]
	if S[i] == 'C' or S[i] == '?':
		dp[i + 1][3] += dp[i][2]
print(dp[len(S)][3] % mod)


s = input()
n = len(s)
la = [0 for _ in range(n)]
rc = [0 for _ in range(n)]
lq = [0 for _ in range(n)]
rq = [0 for _ in range(n)]
for i in range(n - 1):
	if s[i] == 'A':
		la[i + 1] = 1
	if s[i] == '?':
		lq[i + 1] = 1
	if s[i + 1] == '?':
		rq[i] = 1
	if s[i + 1] == 'C':
		rc[i] = 1
for i in range(n - 1):
	la[i + 1] += la[i]
	lq[i + 1] += lq[i]
for i in range(n - 1, 0, -1):
	rc[i - 1] += rc[i]
	rq[i - 1] += rq[i]
ans = 0
mod = 10 ** 9 + 7
for i in range(n):
	if s[i] in ['B', '?']:
		l = la[i] * pow(3, lq[i], mod)
		if lq[i] > 0:
			l += lq[i] * pow(3, lq[i] - 1, mod)
			l %= mod
		r = rc[i] * pow(3, rq[i], mod)
		if rq[i] > 0:
			r += rq[i] * pow(3, rq[i] - 1, mod)
			r %= mod
		ans += l * r
		ans %= mod
print(ans)


S = input()
m = 10 ** 9 + 7
d = 'ABC'.index
dp = [0] * 4
dp[0] = 1
for c in S:
	if c == '?':
		dp = [3 * dp[0] % m, (3 * dp[1] + dp[0]) % m, (3 * dp[2] + dp[1]) % m, (3 * dp[3] + dp[2]) % m]
	else:
		i = d(c)
		dp[i + 1] += dp[i] % m
print(dp[3] % m)


S = input()
a = [1, 0, 0, 0]
for s in S:
	if s == 'A':
		a[1] += a[0]
	elif s == 'B':
		a[2] += a[1]
	elif s == 'C':
		a[3] += a[2]
	else:
		a = [3 * a[0]] + [3 * a[n + 1] + a[n] for n in range(3)]
	a = [a[n] % 1000000007 for n in range(4)]
print(a[3])


S = input()
N = len(S)
MOD = 10 ** 9 + 7
DP = [[1] * 4 for _ in range(N + 1)]
DP[N][3] = 1
DP[N][0] = 0
DP[N][1] = 0
DP[N][2] = 0
for i in range(N - 1, -1, -1):
	for j in range(3, -1, -1):
		DP[i][j] = DP[i + 1][j] * (3 if S[i] == '?' else 1)
		if j < 3:
			DP[i][j] += DP[i + 1][j + 1] * (1 if S[i] == 'ABC'[j] or S[i] == '?' else 0)
		DP[i][j] %= MOD
ans = DP[0][0]
print(ans)


MOD = 1000000007
s = input()
q = 1
a = 0
ab = 0
ans = 0
for c in s:
	if c == 'A':
		a += q
		a %= MOD
	elif c == 'B':
		ab += a
		ab %= MOD
	elif c == 'C':
		ans += ab
		ans %= MOD
	else:
		ans *= 3
		ans += ab
		ans %= MOD
		ab *= 3
		ab += a
		ab %= MOD
		a *= 3
		a += q
		a %= MOD
		q *= 3
		q %= MOD
print(ans)


s = input()
MOD = 10 ** 9 + 7
dp = [1, 0, 0, 0]
for x in s:
	(emp, a, b, c) = dp
	if x == 'A':
		dp[1] += emp
	if x == 'B':
		dp[2] += a
	if x == 'C':
		dp[3] += b
	if x == '?':
		dp = [v * 3 for v in dp]
		dp[1] += emp
		dp[2] += a
		dp[3] += b
	dp = [v % MOD for v in dp]
print(dp[3])


(e, a, b, c) = (1, 0, 0, 0)
p = 1000000007
for i in input():
	if i == 'A':
		a += e
	elif i == 'B':
		b += a
	elif i == 'C':
		c += b
	else:
		(e, a, b, c) = (3 * e % p, (e + 3 * a) % p, (a + 3 * b) % p, (b + 3 * c) % p)
print(c % 1000000007)


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
S = input()
ans = we_love_abc(S)
print(ans)


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]
			dp[i][3] %= 1000000000.0 + 7
		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]
			dp[i][j] %= 1000000000.0 + 7
print(int(dp[0][0]))


s = input()
n = len(s)
dp = [[0 for i in range(4)] for j in range(len(s) + 1)]
dp[0][0] = 1
string = ['A', 'B', 'C']
num = 10 ** 9 + 7
for i in range(n):
	for j in range(4):
		m = 0
		b = 1
		if '?' == s[i]:
			b = 3
		if j == 0:
			if '?' == s[i]:
				dp[i + 1][j] = dp[i][j] * 3 % num
			else:
				dp[i + 1][j] = dp[i][j] % num
			continue
		if s[i] == string[j - 1] or s[i] == '?':
			m = 1
		dp[i + 1][j] = (m * dp[i][j - 1] + b * dp[i][j]) % num
print(dp[-1][3])


MOD = 10 ** 9 + 7
S = input().rstrip()
A = 0
B = 0
C = 0
X = 1
for s in S:
	if s == '?':
		C = B + C * 3
		B = A + B * 3
		A = X + A * 3
		X *= 3
	else:
		if s == 'A':
			A += X
		if s == 'B':
			B += A
		if s == 'C':
			C += B
	X %= MOD
	A %= MOD
	B %= MOD
	C %= MOD
print(C)


S = input()
a = 0
ab = 0
abc = 0
all = 1
mod = 10 ** 9 + 7
for i in range(len(S)):
	if S[i] == 'A':
		a += all
	elif S[i] == 'B':
		ab += a
	elif S[i] == 'C':
		abc += ab
	elif S[i] == '?':
		abc = 3 * abc + ab
		ab = 3 * ab + a
		a = 3 * a + all
		all *= 3
	a %= mod
	ab %= mod
	abc %= mod
	all %= mod
print(abc)


S = input()
mod = 10 ** 9 + 7
N = len(S)
cA = 0
cAB = 0
cABC = 0
all = 1
for i in range(N):
	if S[i] == 'A':
		cA += all
	elif S[i] == 'B':
		cAB += cA
	elif S[i] == 'C':
		cABC += cAB
	else:
		cABC *= 3
		cABC += cAB
		cAB *= 3
		cAB += cA
		cA *= 3
		cA += all
		all *= 3
	cABC %= mod
	cAB %= mod
	cA %= mod
	all %= mod
print(cABC)


S = input()
MOD = 10 ** 9 + 7
dp = [[0, 0, 0] for i in range(len(S) + 1)]
base = 1
for (i, s) in enumerate(S, 1):
	dp[i][0] = dp[i - 1][0]
	dp[i][1] = dp[i - 1][1]
	dp[i][2] = dp[i - 1][2]
	if s == 'A':
		dp[i][0] += base
		dp[i][0] %= MOD
	elif s == 'B':
		dp[i][1] += dp[i - 1][0]
		dp[i][1] %= MOD
	elif s == 'C':
		dp[i][2] += dp[i - 1][1]
		dp[i][2] %= MOD
	else:
		dp[i][0] += 2 * dp[i - 1][0] + base
		dp[i][1] += 2 * dp[i - 1][1] + dp[i - 1][0]
		dp[i][2] += 2 * dp[i - 1][2] + dp[i - 1][1]
		dp[i][0] %= MOD
		dp[i][1] %= MOD
		dp[i][2] %= MOD
		base *= 3
		base %= MOD
print(dp[-1][2])


s = list(input())
mod = 1000000007
c = [1] + [0] * 3
for i in s:
	if i == 'A':
		c[1] = (c[1] + c[0]) % mod
	elif i == 'B':
		c[2] = (c[2] + c[1]) % mod
	elif i == 'C':
		c[3] = (c[3] + c[2]) % mod
	else:
		c[3] = (c[3] * 3 + c[2]) % mod
		c[2] = (c[2] * 3 + c[1]) % mod
		c[1] = (c[1] * 3 + c[0]) % mod
		c[0] = c[0] * 3 % mod
print(c[3])


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[num] += dp[num + 1] % mod
print(dp[0] % mod)


S = input()
ans = 0
MOD = 10 ** 9 + 7
la = 0
lp = 0
rc = 0
rp = 0
for c in S:
	if c == 'C':
		rc += 1
	if c == '?':
		rp += 1
for c in S:
	if c == 'C':
		rc -= 1
	if c == '?':
		rp -= 1
	if c == '?' or c == 'B':
		if lp == 0:
			l = la * pow(3, lp, MOD)
		else:
			l = la * pow(3, lp, MOD) + lp * pow(3, lp - 1, MOD)
		if rp == 0:
			r = rc * pow(3, rp, MOD)
		else:
			r = rc * pow(3, rp, MOD) + rp * pow(3, rp - 1, MOD)
		ans += l * r
		ans %= MOD
	if c == 'A':
		la += 1
	if c == '?':
		lp += 1
print(ans)


mod = 1000000007
S = input()
n = 1
a = 0
ab = 0
abc = 0
for s in S:
	if s in 'A':
		a += n
	if s in 'B':
		ab += a
	if s == 'C':
		abc += ab
	if s in '?':
		(n, a, ab, abc) = (3 * n, 3 * a + n, 3 * ab + a, 3 * abc + ab)
	n %= mod
	a %= mod
	ab %= mod
	abc %= mod
print(abc % mod)


s = input()
mod = 10 ** 9 + 7
(n, a, b, c) = (1, 0, 0, 0)
for i in s:
	if i == 'A':
		a += n
	if i == 'B':
		b += a
	if i == 'C':
		c += b
	if i == '?':
		(n, a, b, c) = (3 * n, 3 * a + n, 3 * b + a, 3 * c + b)
	n %= mod
	a %= mod
	b %= mod
	c %= mod
print(c)


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)


s = input()
dp = [[0 for _ in range(len(s) + 1)] for _ in range(4)]
dp[0][0] = 1
for i in range(0, 4):
	for j in range(1, len(s) + 1):
		if s[j - 1] == '?':
			dp[i][j] += dp[i][j - 1] * 3
		else:
			dp[i][j] += dp[i][j - 1]
		if 0 < i and (s[j - 1] == '?' or s[j - 1] == 'ABC'[i - 1]):
			dp[i][j] += dp[i - 1][j - 1]
		dp[i][j] %= 1000000007
print(dp[3][len(s)])


MOD = 10 ** 9 + 7

def main():
	s = input()
	dp = [[0] * 3 for _ in range(len(s) + 1)]
	tmp = 1
	for i in range(len(s)):
		c = s[i]
		if c == 'A':
			dp[i][0] += tmp
			dp[i][0] %= MOD
		elif c == 'B':
			dp[i][1] += dp[i][0]
			dp[i][1] %= MOD
		elif c == 'C':
			dp[i][2] += dp[i][1]
			dp[i][2] %= MOD
		else:
			pre = [v for v in dp[i]]
			dp[i] = [0, 0, 0]
			dp[i][0] += pre[0] + tmp
			dp[i][1] += pre[1]
			dp[i][2] += pre[2]
			dp[i][0] += pre[0]
			dp[i][1] += pre[0] + pre[1]
			dp[i][2] += pre[2]
			dp[i][0] += pre[0]
			dp[i][1] += pre[1]
			dp[i][2] += pre[1] + pre[2]
			tmp *= 3
			tmp %= MOD
			dp[i][0] %= MOD
			dp[i][1] %= MOD
			dp[i][2] %= MOD
		dp[i + 1][0] = dp[i][0]
		dp[i + 1][1] = dp[i][1]
		dp[i + 1][2] = dp[i][2]
	print(dp[len(s)][2] % MOD)

def __starting_point():
	main()
__starting_point()


def main():
	MOD = 10 ** 9 + 7
	S = input()
	N = len(S)
	CHARS = ['A', 'B', 'C']
	dp = [[0 for _ in range(4)] for _ in range(N + 1)]
	dp[N][3] = 1
	for i in range(N - 1, -1, -1):
		a = 3 if S[i] == '?' else 1
		dp[i][3] = a * dp[i + 1][3]
		dp[i][3] %= MOD
	for i in range(N - 1, -1, -1):
		a = 3 if S[i] == '?' else 1
		ch = S[i]
		for j in range(3):
			b = 1 if ch in ['?', CHARS[j]] else 0
			dp[i][j] = a * dp[i + 1][j] + b * dp[i + 1][j + 1]
			dp[i][j] %= MOD
	print(dp[0][0])

def __starting_point():
	main()
__starting_point()


MOD = pow(10, 9) + 7
s = input()
n = len(s)
dp = [[0 for _ in range(4)] for _ in range(n + 1)]
dp[0][0] = 1
for i in range(n):
	dp[i + 1][0] = dp[i][0]
	dp[i + 1][1] = dp[i][1]
	dp[i + 1][2] = dp[i][2]
	dp[i + 1][3] = dp[i][3]
	if s[i] == 'A':
		dp[i + 1][1] += dp[i][0]
	elif s[i] == 'B':
		dp[i + 1][2] += dp[i][1]
	elif s[i] == 'C':
		dp[i + 1][3] += dp[i][2]
	else:
		dp[i + 1][0] = dp[i][0] * 3
		dp[i + 1][1] = dp[i][1] * 3
		dp[i + 1][2] = dp[i][2] * 3
		dp[i + 1][3] = dp[i][3] * 3
		dp[i + 1][1] += dp[i][0]
		dp[i + 1][2] += dp[i][1]
		dp[i + 1][3] += dp[i][2]
	dp[i + 1][0] %= MOD
	dp[i + 1][1] %= MOD
	dp[i + 1][2] %= MOD
	dp[i + 1][3] %= MOD
print(dp[n][3])