Number of Subsequences
Contest: Codeforces Round 674 (Div. 3)
Difficulty rating: 2000
Tags: combinatorics, dp, strings

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 format:
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 format:
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$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

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.

Example input:
6
ac?b?c

Example output:
24

Example input:
7
???????

Example output:
2835

Editorial:
There are several more or less complicated combinatorial solutions to this problem, but I will describe a dynamic programming one which, I think, is way easier to understand and to implement.
Suppose we have fixed the positions of a, b and c that compose the subsequence (let these positions be $$$p_a$$$, $$$p_b$$$ and $$$p_c$$$). How many strings contain the required subsequence on these positions? Obviously, if some of these characters is already not a question mark and does not match the expected character on that position, the number of strings containing the subsequence on that position is $$$0$$$. Otherwise, since we have fixed three characters, all question marks on other positions can be anything we want — so the number of such strings is $$$3^x$$$, where $$$x$$$ is the number of question marks on positions other than $$$p_a$$$, $$$p_b$$$ and $$$p_c$$$. It allows us to write an $$$O(n^3)$$$ solution by iterating on $$$p_a$$$, $$$p_b$$$ and $$$p_c$$$, and for every such triple, calculating the number of strings containing the required subsequence on those positions.
But that's too slow. Let's notice that, for every such subsequence, the number of strings containing it is $$$3^{k - qPos({p_a, p_b, p_c})}$$$, where $$$qPos({p_a, p_b, p_c})$$$ is the number of positions from $$${p_a, p_b, p_c}$$$ that contain a question mark. So, for each integer $$$i$$$ from $$$0$$$ to $$$3$$$, let's calculate the number of subsequences matching abc that contain exactly $$$i$$$ question marks — and that will allow us to solve the problem faster.
How can we calculate the required number of subsequences for every $$$i$$$? In my opinion, the simplest way is dynamic programming: let $$$dp_{i, j, k}$$$ be the number of subsequences of $$$s$$$ that end up in position $$$i$$$, match $$$j$$$ first characters of abc and contain $$$k$$$ question marks. The transitions in this dynamic programming are quadratic (since we have to iterate on the next/previous position from the subsequence), but can be sped up to linear if we rewrite $$$dp_{i, j, k}$$$ as the number of subsequences of $$$s$$$ that end up in position not later than $$$i$$$, match $$$j$$$ first characters of abc and contain $$$k$$$ question marks. Each transition is either to take the current character or to skip it, so they can be modeled in $$$O(1)$$$, and overall this dynamic programming solution works in $$$O(n)$$$.