D - 我们喜欢 ABC

得分 : $400$ 分

问题描述

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

• $1 \le i < j < k \le |T|$（$|T|$ 是字符串 $T$ 的长度）
• $T_i =$ A（$T_i$ 表示字符串 $T$ 的第 $i$ 个字符）
• $T_j =$ B
• $T_k =$ C

例如，当 $T =$ ABCBC 时，满足条件的整数三元组 $(i, j, k)$ 的个数为 $3$，对应的三元组为：$(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$ 后输出。

约束

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

输入

输入为标准输入，具体格式如下：

$S$

输出

输出所有 $3^Q$ 个字符串的 ABC 数之和，结果模 $10^9 + 7$ 后输出。

A??C

8

对于这个样例，$Q = 2$，我们可以用 A、B 或者 C 分别替换 $S$ 中的每个 ?，这样可以得到 $3^Q = 9$ 个字符串。每个字符串的 ABC 数如下：

• AAAC 的 ABC 数为 $0$
• AABC 的 ABC 数为 $2$
• AACC 的 ABC 数为 $0$
• ABAC 的 ABC 数为 $1$
• ABBC 的 ABC 数为 $2$
• ABCC 的 ABC 数为 $2$
• ACAC 的 ABC 数为 $0$
• ACBC 的 ABC 数为 $1$
• ACCC 的 ABC 数为 $0$

这些字符串的 ABC 数之和为 $0 + 2 + 0 + 1 + 2 + 2 + 0 + 1 + 0 = 8$，所以我们输出 $8$（模 $10^9 + 7$ 后的结果）。

ABCBC

3

当 $Q = 0$ 时，我们输出 $S$ 本身的 ABC 数（模 $10^9 + 7$ 后的结果）。这个例子中的字符串和问题描述中给出的例子相同，其 ABC 数为 $3$。

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

979596887

对于这个样例，所有 $3^Q$ 个字符串的 ABC 数之和为 $2291979612924$，所以我们输出 $979596887$（模 $10^9 + 7$ 后的结果）。