101043: [AtCoder]ABC104 D - We Love ABC

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $400$ points

Problem Statement

The ABC number of a string $T$ is the number of triples of integers $(i, j, k)$ that satisfy all of the following conditions:

  • $1 ≤ i < j < k ≤ |T|$ ($|T|$ is the length of $T$.)
  • $T_i =$ A ($T_i$ is the $i$-th character of $T$ from the beginning.)
  • $T_j =$ B
  • $T_k =$ C

For example, when $T =$ ABCBC, there are three triples of integers $(i, j, k)$ that satisfy the conditions: $(1, 2, 3), (1, 2, 5), (1, 4, 5)$. Thus, the ABC number of $T$ is $3$.

You are given a string $S$. Each character of $S$ is A, B, C or ?.

Let $Q$ be the number of occurrences of ? in $S$. We can make $3^Q$ strings by replacing each occurrence of ? in $S$ with A, B or C. Find the sum of the ABC numbers of all these strings.

This sum can be extremely large, so print the sum modulo $10^9 + 7$.

Constraints

  • $3 ≤ |S| ≤ 10^5$
  • Each character of $S$ is A, B, C or ?.

Input

Input is given from Standard Input in the following format:

$S$

Output

Print the sum of the ABC numbers of all the $3^Q$ strings, modulo $10^9 + 7$.


Sample Input 1

A??C

Sample Output 1

8

In this case, $Q = 2$, and we can make $3^Q = 9$ strings by by replacing each occurrence of ? with A, B or C. The ABC number of each of these strings is as follows:

  • AAAC: $0$
  • AABC: $2$
  • AACC: $0$
  • ABAC: $1$
  • ABBC: $2$
  • ABCC: $2$
  • ACAC: $0$
  • ACBC: $1$
  • ACCC: $0$

The sum of these is $0 + 2 + 0 + 1 + 2 + 2 + 0 + 1 + 0 = 8$, so we print $8$ modulo $10^9 + 7$, that is, $8$.


Sample Input 2

ABCBC

Sample Output 2

3

When $Q = 0$, we print the ABC number of $S$ itself, modulo $10^9 + 7$. This string is the same as the one given as an example in the problem statement, and its ABC number is $3$.


Sample Input 3

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

Sample Output 3

979596887

In this case, the sum of the ABC numbers of all the $3^Q$ strings is $2291979612924$, and we should print this number modulo $10^9 + 7$, that is, $979596887$.

Input

题意翻译

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

加入题单

上一题 下一题 算法标签: