配点 : $400$ 点

問題文

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

• $1 \leq i < j < k \leq |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$ で割った余りを出力してください。

制約

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

入力

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

$S$

出力

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

A??C

8

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

ABCBC

3

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

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

979596887

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