Problem Statement

The ABC number of a string $T$ is the number of triples of integers $(i, j, k)$ that satisfy all of the following conditions:

• $1 ≤ i < j < k ≤ |T|$ ($|T|$ is the length of $T$.)
• $T_i =$ A ($T_i$ is the $i$-th character of $T$ from the beginning.)
• $T_j =$ B
• $T_k =$ C

For example, when $T =$ ABCBC, there are three triples of integers $(i, j, k)$ that satisfy the conditions: $(1, 2, 3), (1, 2, 5), (1, 4, 5)$. Thus, the ABC number of $T$ is $3$.

You are given a string $S$. Each character of $S$ is A, B, C or ?.

Let $Q$ be the number of occurrences of ? in $S$. We can make $3^Q$ strings by replacing each occurrence of ? in $S$ with A, B or C. Find the sum of the ABC numbers of all these strings.

This sum can be extremely large, so print the sum modulo $10^9 + 7$.

Constraints

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

Input

Input is given from Standard Input in the following format:

S

Output

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