Number of Subsequences

1000ms

262144K

Description:

You are given a string $$$s$$$ consisting of lowercase Latin letters "a", "b" and "c" and question marks "?".

Let the number of question marks in the string $$$s$$$ be $$$k$$$. Let's replace each question mark with one of the letters "a", "b" and "c". Here we can obtain all $$$3^{k}$$$ possible strings consisting only of letters "a", "b" and "c". For example, if $$$s = $$$"ac?b?c" then we can obtain the following strings: $$$[$$$"acabac", "acabbc", "acabcc", "acbbac", "acbbbc", "acbbcc", "accbac", "accbbc", "accbcc"$$$]$$$.

Your task is to count the total number of subsequences "abc" in all resulting strings. Since the answer can be very large, print it modulo $$$10^{9} + 7$$$.

A subsequence of the string $$$t$$$ is such a sequence that can be derived from the string $$$t$$$ after removing some (possibly, zero) number of letters without changing the order of remaining letters. For example, the string "baacbc" contains two subsequences "abc" — a subsequence consisting of letters at positions $$$(2, 5, 6)$$$ and a subsequence consisting of letters at positions $$$(3, 5, 6)$$$.

Input:

The first line of the input contains one integer $$$n$$$ $$$(3 \le n \le 200\,000)$$$ — the length of $$$s$$$.

The second line of the input contains the string $$$s$$$ of length $$$n$$$ consisting of lowercase Latin letters "a", "b" and "c" and question marks"?".

Output:

Print the total number of subsequences "abc" in all strings you can obtain if you replace all question marks with letters "a", "b" and "c", modulo $$$10^{9} + 7$$$.

Sample Input:

6
ac?b?c

Sample Output:

Sample Input:

7
???????

Sample Output:

Sample Input:

9
cccbbbaaa

Sample Output:

Sample Input:

5
a???c

Sample Output:

Note:

In the first example, we can obtain $$$9$$$ strings:

"acabac" — there are $$$2$$$ subsequences "abc",
"acabbc" — there are $$$4$$$ subsequences "abc",
"acabcc" — there are $$$4$$$ subsequences "abc",
"acbbac" — there are $$$2$$$ subsequences "abc",
"acbbbc" — there are $$$3$$$ subsequences "abc",
"acbbcc" — there are $$$4$$$ subsequences "abc",
"accbac" — there is $$$1$$$ subsequence "abc",
"accbbc" — there are $$$2$$$ subsequences "abc",
"accbcc" — there are $$$2$$$ subsequences "abc".

So, there are $$$2 + 4 + 4 + 2 + 3 + 4 + 1 + 2 + 2 = 24$$$ subsequences "abc" in total.

Informação

Provedor Codeforces

Código CF1426F