给定一个字符串 $$$s$$$,由小写拉丁字母“a”、“b”和“c”以及问号“?”组成。
设字符串 $$$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$$$ $$$(3 \le n \le 200\,000)$$$ — $$$s$$$ 的长度。
输入的第二行包含长度为 $$$n$$$ 的字符串 $$$s$$$,由小写拉丁字母“a”、“b”和“c”以及问号“?”组成。
输出
如果将所有问号替换为字母“a”、“b”和“c”,则打印所有字符串中子序列“abc”的总数,模$$$10^{9} + 7$$$。
示例
输入 #1
6 ac?b?c
输出 #1
24
输入 #2
7 ???????
输出 #2
2835
输入 #3
9 cccbbbaaa
输出 #3
0
输入#4
5 a???c
输出#4
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”。