描述

您将获得一个由小写拉丁字母"a","b"和"c"以及问号"?"组成的字符串 $s$ 。

设字符串 $s$ 中的问号数为 $k$ 。让我们用字母“a”、“b”和“c”之一替换每个问号。在这里，我们可以获得仅由字母“a”、“b”和“c”组成的所有 $3^k$ 可能的字符串。例如，如果 $s$="$ac?b?c$" 那么我们可以获得以下字符串： $[[ “acabac”， “acabbc”， “acabcc”， “acbbac”， “acbbbc”， “acbbcc”， “accbac”， “accbbc”， “accbcc” ]]$ 。

您的任务是计算所有生成的字符串中子序列“abc”的总数。由于答案可能非常大，因此请将其打印为模 $10^9+7$ 。

格式

输入

输入的第一行包含一个整数 $n$ $(3≤n≤200000)$，即 $s$ 的长度 。

输入的第二行包含长度为 $n$ 为小写的字符串 $s$ ，由小写拉丁字母"a","b"和"c"以及问号"?"组成。

输出

输出将所有问号替换为字母"a"或"b"或"c"得到的所有字符串中子序列“abc”的总数，模 $10^9+7$。

样例

6
ac?b?c

24