题目描述

文字列 $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)$ の $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', 'B', 'C', '?'， 其中'?' 表示 'A', 'B', 'C' 中的任意一个，问在所有可能的 'A', 'B', 'C' 的字符串中，总共有多少长度为3的子序列是<'A', 'B', 'C'>。

答案对 $10 ^ 9 + 7$ 取模。

A??C

8

ABCBC

3

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

979596887

提示

制約

• $3\ <\ =\ |S|\ <\ =\ 10^5$
• $S$ のそれぞれの文字は A, B, C, ? のいずれかである。

Sample Explanation 1

この場合、$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$ を出力します。

Sample Explanation 2

$Q\ =\ 0$ のときは、$S$ 自体の ABC 数を $10^9\ +\ 7$ で割った余りを出力します。この文字列は問題文中で例として挙げたものと同じであり、その ABC 数は $3$ です。

Sample Explanation 3

この場合、$3^Q$ 通りの文字列すべての ABC 数の和は $2291979612924$ であり、これを $10^9\ +\ 7$ で割った余りである $979596887$ を出力します。