题目描述

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 \lt j \lt 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 mod $10^9 + 7$.

字符串 $T$ 的 _ABC 数是满足以下所有条件的整数 $(i, j, k)$ 三元组的个数：

• $1 ≤ i \lt j \lt k ≤ |T|$ （ $|T|$ 是 $T$ 的长度。）
• $T_i =$ A`（ $T_i$ 是 $T$ 从头开始的 $i$ 个字符。）
• $T_j =$ B
• $T_k =$ C

例如，当 $T =$ ABCBC`时，有三个整数三元组 $(i, j, k)$ 满足条件： $(1, 2, 3), (1, 2, 5), (1, 4, 5)$ .因此， $T$ 的 ABC 数是 $3$ 。

给你一个字符串 $S$ 。 $S$ 中的每个字符是 A、B、C 或 ?。

设 $Q$ 是 $S$ 中出现 ?的次数。我们可以用 A、B 或 C 替换 $S$ 中出现的每个 ?，从而组成 $3^Q$ 字符串。求所有这些字符串的 ABC 数字之和。

这个和可能会非常大，因此打印取模为 $10^9 + 7$ 的和。

输入格式

输入内容按以下格式标准输入：

$S$

输出格式

打印所有 $3^Q$ 字符串的 ABC 数字之和，模数为 $10^9 + 7$ 。

样例 #1

样例输入 #1

A??C

样例输出 #1

8

样例 #2

样例输入 #2

ABCBC

样例输出 #2

3

样例 #3

样例输入 #3

????C?????B??????A???????

样例输出 #3

979596887

说明

数据规模与约定

• $3 ≤ |S| ≤ 10^5$
• $S$ 的每个字符都是 A、B、C 或 ?。

样例 $1$ 解释

在这种情况下， $Q = 2$ ，我们可以通过用 A、B 或 C 替换每次出现的 ? 来组成 $3^Q = 9$ 字符串。每个字符串的 ABC 号码如下：

• AAAC`： $0$
• AABC： $2$
• AACC： $0$
• ABAC： $1$
• ABBC： $2$
• ABCC： $2$
• ACAC： $0$
• ACBC： $1$
• ACCC： $0$

其和为 $0 + 2 + 0 + 1 + 2 + 2 + 0 + 1 + 0 = 8$ ，因此我们打印 $8$ mod $10^9 + 7$ ，即 $8$ 。

样例 $2$ 解释

当 $Q = 0$ 时，我们打印 $S$ 本身的 ABC 数，模数为 $10^9 + 7$ 。该字符串与问题陈述中给出的示例字符串相同，其 ABC 编号为 $3$ 。

样例 $3$ 解释

在这种情况下，所有 $3^Q$ 字符串的 ABC 数字之和是 $2291979612924$ ，我们应该打印这个数字的模数 $10^9 + 7$ ，即 $979596887$ 。