子序列的数量

• 时间限制：1 秒
• 内存限制：256 MiB

题目描述

给定一个仅由小写字母 a、b、c 和问号 ? 组成的字符串 $s$。

设字符串中问号的数量为 $k$。你需要把每一个问号分别替换为 a、b 或 c，因此一共可以得到 $3^k$ 个只含 a、b、c 的字符串。

请统计所有这些字符串中，子序列 abc 的数量之和。答案可能很大，请对 $10^9+7$ 取模。

字符串 $t$ 的一个子序列，是指从 $t$ 中删除若干个字符（也可以不删除），且不改变剩余字符相对顺序后得到的字符串。不同的下标三元组视为不同的子序列。

输入格式

第一行输入一个整数 $n$，表示字符串长度。

第二行输入一个长度为 $n$ 的字符串 $s$，其中每个字符均为 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

数据范围

对于所有数据，$3\le n\le 200\,000$，且 $s$ 仅包含 a、b、c 和 ?。