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)$。因此，$T$ 的 ABC 数是 $3$。 给定一个字符串 $S$。$S$ 的每个字符都是 $A$, $B$, $C$ 或 $?$。 设 $Q$ 为 $S$ 中 $?$ 出现的次数。通过将 $S$ 中的每个 $?$ 替换为 $A$, $B$ 或 $C$，我们可以得到 $3^Q$ 个字符串。求所有这些字符串的 ABC 数之和。 这个和可能非常大，因此请对 $10^9 + 7$ 取模后输出。

输入格式

从标准输入给出，格式如下： $S$

输出格式

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

A??C

8

ABCBC

3

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

979596887

提示

$3 ≤ |S| ≤ 10^5$ $S$ 的每个字符都是 $A$, $B$, $C$ 或 $?$。在这个例子中，$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$ 对 $10^9 + 7$ 取模，即 $8$。
当 $Q = 0$ 时，输出的就是 $S$ 自身的 ABC 数对 $10^9 + 7$ 取模。该字符串与问题描述中的示例相同，其 ABC 数为 $3$。
在该情况下，所有字符串的 ABC 数之和为 $2291979612924$，对 $10^9 + 7$ 取模后应输出 $979596887$。

标签: AtCoder|abc104D

来源

AtCoder|abc104D