我们爱 ABC

题目描述

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

• $1 \le i \lt j \lt k \le |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$。$S$ 中的每个字符都是 A、B、C、? 之一。

设 $S$ 中 ? 的个数为 $Q$。把 $S$ 中的每个 ? 分别替换为 A、B、C 之一,可以构造出 $3^Q$ 种字符串。请求出这些所有字符串的 ABC 数之和。

由于该和可能非常巨大,请输出该和除以 $10^9 + 7$ 的余数。

输入格式

输入从标准输入按以下格式给出。

$S$

输出格式

输出 $3^Q$ 种字符串所有 ABC 数之和除以 $10^9 + 7$ 的余数。

样例

A??C

8

这种情况下,$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$。

ABCBC

3

当 $Q = 0$ 时,输出 $S$ 本身的 ABC 数除以 $10^9 + 7$ 的余数。这个字符串与题目描述中作为例子举出的字符串相同,它的 ABC 数是 $3$。

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

979596887

这种情况下,$3^Q$ 种字符串所有 ABC 数之和是 $2291979612924$,输出它除以 $10^9 + 7$ 的余数,即 $979596887$。

数据范围

• $3 \le |S| \le 10^5$
• $S$ 中的每个字符都是 A、B、C、? 之一。