AT_abc104_d [ABC104D] We Love ABC

题目描述

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

• $1\ <=\ i\ <\ j\ <\ 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)$ 共 $3$ 个，因此 $T$ 的 ABC 数为 $3$。

给定一个字符串 $S$，其中每个字符都是 A、B、C 或 ? 之一。

设 $S$ 中 ? 的个数为 $Q$。将 $S$ 中的每个 ? 替换为 A、B 或 C 中的任意一个，可以得到 $3^Q$ 种不同的字符串。请计算这些字符串的 ABC 数之和。

由于这个和可能非常大，请输出其对 $10^9 + 7$ 取模的结果。

输入格式

输入为以下格式，通过标准输入给出。

$S$

输出格式

请输出 $3^Q$ 种字符串所有 ABC 数之和对 $10^9 + 7$ 取模的结果。

样例 1

输入

A??C

输出

8

样例 2

输入

ABCBC

输出

3

样例 3

输入

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

输出

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$，对 $10^9 + 7$ 取模后输出 $8$。

样例解释 2

当 $Q = 0$ 时，只需输出 $S$ 本身的 ABC 数对 $10^9 + 7$ 取模的结果。此字符串与题目描述中的例子相同，其 ABC 数为 $3$。

样例解释 3

在本例中，$3^Q$ 种字符串所有 ABC 数之和为 $2291979612924$，对 $10^9 + 7$ 取模后为 $979596887$，输出 $979596887$。

由 ChatGPT 4.1 翻译