100 #ABC104D. [ABC104D] We Love ABC

[ABC104D] We Love ABC

题目描述

文字列 T T ABC 数 とは、以下の条件をすべて満たす整数の組 (i, j, k) (i,\ j,\ k) の個数です。

  • 1 < = i < j < k < = T 1\ <\ =\ i\ <\ j\ <\ k\ <\ =\ |T| T |T| T T の長さ)
  • Ti = T_i\ = ATi T_i T T の先頭から i i 番目の文字)
  • Tj = T_j\ = B
  • Tk = T_k\ = C

例えば、T = T\ = ABCBC のとき、条件をすべて満たす組 (i, j, k) (i,\ j,\ k) (1, 2, 3), (1, 2, 5), (1, 4, 5) (1,\ 2,\ 3),\ (1,\ 2,\ 5),\ (1,\ 4,\ 5) 3 3 個であるため、T T の ABC 数は 3 3 です。

文字列 S S が与えられます。S S のそれぞれの文字は A, B, C, ? のいずれかです。

S S に含まれる ? の個数を Q Q とします。S S に含まれる ? をそれぞれ A, B, C のいずれかに置き換えることで 3Q 3^Q 通りの文字列が作られます。これらの文字列すべての ABC 数の和を求めてください。

ただし、この和は非常に大きくなりうるため、和を 109 + 7 10^9\ +\ 7 で割った余りを出力してください。

输入格式

入力は以下の形式で標準入力から与えられる。

S S

输出格式

3Q 3^Q 通りの文字列すべての ABC 数の和を 109 + 7 10^9\ +\ 7 で割った余りを出力せよ。

题目大意

给你一个字符串,只包含 'A', 'B', 'C', '?', 其中'?' 表示 'A', 'B', 'C' 中的任意一个,问在所有可能的 'A', 'B', 'C' 的字符串中,总共有多少长度为3的子序列是<'A', 'B', 'C'>。

答案对 109+710 ^ 9 + 7 取模。

A??C
8
ABCBC
3
????C?????B??????A???????
979596887

提示

制約

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

Sample Explanation 1

この場合、Q = 2 Q\ =\ 2 であり、? をそれぞれ A, B, C のいずれかに置き換えることで 3Q = 9 3^Q\ =\ 9 通りの文字列が作られます。これらの文字列それぞれの ABC 数を以下に示します。 - AAAC: 0 0 - AABC: 2 2 - AACC: 0 0 - ABAC: 1 1 - ABBC: 2 2 - ABCC: 2 2 - ACAC: 0 0 - ACBC: 1 1 - ACCC: 0 0 これらの和は $ 0\ +\ 2\ +\ 0\ +\ 1\ +\ 2\ +\ 2\ +\ 0\ +\ 1\ +\ 0\ =\ 8 $ であり、8 8 109 + 7 10^9\ +\ 7 で割った余りである 8 8 を出力します。

Sample Explanation 2

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

Sample Explanation 3

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