题目描述

给定一个仅由小写拉丁字母 "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)$ 的子序列。

输入格式

第一行输入一个整数 $n$，表示 $s$ 的长度，$3 \leq n \leq 200\,000$。

第二行输入一个长度为 $n$ 的字符串 $s$，仅包含小写拉丁字母 "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" 子序列。

因此，总共有 $2 + 4 + 4 + 2 + 3 + 4 + 1 + 2 + 2 = 24$ 个 "abc" 子序列。