AT_abc104_d [ABC104D] We Love ABC
题目描述
字符串 $T$ 的 *ABC 数* 是满足以下所有条件的整数三元组 $(i,\ j,\ k)$ 的个数。
- $1\ \le \ i\
输入格式
输入为以下格式，通过标准输入给出。
> $S$
输出格式
请输出 $3^Q$ 种字符串所有 ABC 数之和对 $10^9 + 7$ 取模的结果。
说明/提示
### 限制条件
- $3\ \le\ |S|\ \le\ 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 翻译。