下标三元组

对于字符串T，如果下标三元组(i,j,k)满足如下条件，则称(i,j,k)是“优质三元组”：

(1) 0 <= i < j < k < |T|, 其中|T|表示字符串T的长度。

(2) T[i] = 'A' 且 T[j]='B' 且 T[k] = 'C'。

显然，一个字符串可能有多个“优质三元组”。

给出字符串T，仅含4种类型的字符：'A', 'B', 'C', '?'。

对于每一个'?'，都可以替换成'A'或 'B'或 'C'之一。

显然，替换之后，总共可以得到3^y个不同的字符串，其中y是S当中'?'的数量。

输出3^y个不同的字符串，总共有多少个“优质三元组”？答案模(1e9+7)。

输入格式：

一个字符串T，仅含4种类型的字符：'A', 'B', 'C', '?'， 长度不超过1e5。

输出格式：

一个整数。

输入/输出例子1

输入：

A??C

输出：

8

样例解释

可以产生9个不同的字符串，下面是产生的9个不同字符串以及对应的“优质三元组”数量：

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