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

Input is given from Standard Input in the following format:

```
$S$
```

Print the sum of the ABC numbers of all the $3^Q$ strings, modulo $10^9 + 7$.

-   $3 ≤ |S| ≤ 10^5$
-   Each character of $S$ is `A`, `B`, `C` or `?`.

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.

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.

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.