CF1426F.Number of Subsequences

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)$.

给你一个由小写拉丁字母 "a"、"b" 和 "c" 以及问号 "?" 组成的字符串 $s$。

设字符串 $s$ 中问号的个数为 $k$。我们将每个问号替换成 "a"、"b" 或 "c" 中的一个字母，从而可以得到全部 $3^{k}$ 个仅由字母 "a"、"b" 和 "c" 构成的字符串。例如，若 $s = $"ac?b?c"$，则我们可以得到如下字符串：$[$"acabac", "acabbc", "acabcc", "acbbac", "acbbbc", "acbbcc", "accbac", "accbbc", "accbcc"$]$。

你的任务是计算所有这些结果字符串中子序列 "abc" 的总数。由于答案可能非常大，请将结果对 $10^{9} + 7$ 取模后输出。

字符串 $t$ 的一个子序列是指从 $t$ 中删除若干（可能为零）个字符后，剩余字符保持原有顺序所构成的序列。例如，字符串 "baacbc" 包含两个子序列 "abc"：一个由位置 $(2, 5, 6)$ 上的字符构成，另一个由位置 $(3, 5, 6)$ 上的字符构成。

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"?".

输入的第一行包含一个整数 $n$（$3 \le n \le 200\,000$）—— 字符串 $s$ 的长度。

输入的第二行包含一个长度为 $n$ 的字符串 $s$，由小写拉丁字母 "a"、"b"、"c" 和问号 "?" 组成。

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

打印在将所有问号替换为字母 “a”、“b” 和 “c” 后，所能得到的所有字符串中子序列 “abc” 的总个数，结果对 $10^{9} + 7$ 取模。

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.

在第一个例子中，我们可以得到 $9$ 个字符串：

• "acabac" — 包含 $2$ 个子序列 "abc"，
• "acabbc" — 包含 $4$ 个子序列 "abc"，
• "acabcc" — 包含 $4$ 个子序列 "abc"，
• "acbbac" — 包含 $2$ 个子序列 "abc"，
• "acbbbc" — 包含 $3$ 个子序列 "abc"，
• "acbbcc" — 包含 $4$ 个子序列 "abc"，
• "accbac" — 包含 $1$ 个子序列 "abc"，
• "accbbc" — 包含 $2$ 个子序列 "abc"，
• "accbcc" — 包含 $2$ 个子序列 "abc"。

因此，子序列 "abc" 的总数为 $2 + 4 + 4 + 2 + 3 + 4 + 1 + 2 + 2 = 24$。