题目描述

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

• $1 \leq i < j <k \leq |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$ 后输出。

输入

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

$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 后的结果）。

提示

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