1426F · Number of Subsequences

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

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.