问题描述

给定一个的字符串$s$，仅包含$a$, $b$, $c$以及$?$。

你可以将$?$替换为$a$, $b$, $c$中任意一个字符。你需要将所有的$?$都替换掉，得到字符串$t$。假设$s$中有$k$个字符

$?$，那么就有$3^k$种可能的字符串$t$。

问子序列"abc"在所有可能的$t$中出现的次数之和。当然这个答案可能很大，你只用输出它对$10^9 + 7$取模后的结果。

输入格式

第一行一个正整数|$s$|，表示给定字符串的长度，第二行给出字符串s，仅包含$a$, $b$, $c$以及$?$。

输出格式

输出一个整数，表示答案。

样例

4
ab?c

5

abac:ab_c

abbc:ab_c a_bc

abcc:ab_c abc_

数据范围

• 对于所有测试数据：$0 ≤ k ≤ |s| ≤ 3 × 10^5$