[ABC104D] We Love ABC

给你一个字符串，只包含 'A', 'B', 'C', '?'， 其中'?' 表示 'A', 'B', 'C' 中的任意一个，问在所有可能的 'A', 'B', 'C' 的字符串中，总共有多少长度为3的子序列是<'A', 'B', 'C'>。 答案对 $10 ^ 9 + 7$ 取模。

[problemUrl]: https://atcoder.jp/contests/abc104/tasks/abc104_d 文字列 $ 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??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 $ を出力します。