← 返回题目列表

Codeforces · 1426/F

F. 子序列数

中文机器翻译题面 查看原题

给定一个字符串 $$$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”。