暂无测试数据。

令字符串 $T$ 的长度为 $|T|$，我们这样定义它的 ABC 值 为满足以下要求的三元组 $(i,j,k)$ 的个数：

• $1\le i<j<k\le |T|$（假设字符串下标从 $1$ 开始）
• $T_i$ 为字符 A。
• $T_j$ 为字符 B。
• $T_k$ 为字符 C。

蒜头君的手上现在就有一个字符串 $T$，这个字符串里面不只有ABC三个字符，还有可能有?，而?可以被代替为ABC这三个字符中的任意一个。

令 $T$ 中总共有 $Q$ 个问号，那么实际上可以转化成 $3^Q$ 个串。你需要把这 $3^Q$ 个串的 ABC 值 的和 $sum$ 求出来，并对 $10^9+7$ 取模。

输入格式

字符串 $T$，长度不超过 $10^5$，由ABC?四种字符组成。

输出格式

一个值，$sum$ 对 $10^9+7$ 取模的结果。

ABCBC

3

A??C

8

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

979596887