F. 子序列的数量
每次测试时间限制：$1$ 秒
内存限制：$256$ 兆字节

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

设字符串 $s$ 中问号的数量为 $k$。我们将每个问号替换为字母 "a"、"b" 或 "c" 中的一个。这样我们可以得到全部 $3^k$ 个仅由字母 "a"、"b"、"c" 组成的可能字符串。例如，若 $s = \texttt{"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)$ 的字母组成。

输入
第一行包含一个整数 $n$（$3 \le n \le 2 \cdot 10^5$）——字符串 $s$ 的长度。
第二行包含一个长度为 $n$ 的字符串 $s$，由小写拉丁字母 "a"、"b"、"c" 和问号 "?" 组成。

输出
输出将所有问号替换成字母 "a"、"b"、"c" 后，所有结果字符串中子序列 "abc" 的总数，对 $10^9 + 7$ 取模。

示例

输入

6
ac?b?c

输出

24

输入

7
???????

输出

2835

输入

9
cccbbbaaa

输出

0

输入

5
a???c

输出

46

说明
在第一个示例中，可以得到 $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$。