Home

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 ?.

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$.