Score : 400 points
The ABC number of a string T is the number of triples of integers (i, j, k) that satisfy all of the following conditions:
A
(T_i is the i-th character of T from the beginning.)B
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.
A
, B
, C
or ?
.Input is given from Standard Input in the following format:
S
Print the sum of the ABC numbers of all the 3^Q strings, modulo 10^9 + 7.
A??C
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
: 0AABC
: 2AACC
: 0ABAC
: 1ABBC
: 2ABCC
: 2ACAC
: 0ACBC
: 1ACCC
: 0The 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.
ABCBC
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.
????C?????B??????A???????
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.