题目描述

字符串 $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$ 中 ? 的出现次数。我们可以用 A、B 或 C 替换 $S$ 中的每个 ?，得到 $3^Q$ 个字符串。求所有这些字符串的 ABC 数之和。

由于这个和可能非常大，因此以 $10^9 + 7$ 为模打印这个和。

约束条件

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

输入

输入以以下格式从标准输入中给出：

$S$

输出

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

示例输入 1

A??C

示例输出 1

8

在这种情况下，$Q = 2$，通过将 $S$ 中的 ? 分别替换为 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$。

示例输入 2

ABCBC

示例输出 2

3

当 $Q = 0$ 时，我们打印 $S$ 本身的 ABC 数对 $10^9 + 7$ 取模的结果。该字符串与题目中的示例相同，其 ABC 数为 $3$。

示例输入 3

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

示例输出 3

979596887

在这种情况下，所有 $3^Q$ 个字符串的 ABC 数之和为 $2291979612924$，我们应该将这个数对 $10^9 + 7$ 取模得到 $979596887$。