AT_arc110_e [ARC110E] Shorten ABC

有一个由 `A`、`B`、`C` 组成的长度为 $N$ 的字符串 $S$。 你可以对 $S$ 进行如下操作，操作次数可以为 $0$ 次或多次： - 选择一个 $i$（$1 \leq i \leq |S| - 1$），使得 $S_i \neq S_{i+1}$。将 $S_i$ 替换为一个与 $S_i$ 和 $S_{i+1}$ 都不同的字符（在 `A`、`B`、`C` 中），然后将 $S_{i+1}$ 从 $S$ 中删除。 请输出经过 $0$ 次或多次操作后，可能得到的 $S$ 的不同字符串的种类数，结果对 $10^9+7$ 取模。

输入通过标准输入给出，格式如下： > $N$\ > $S$

请输出经过 $0$ 次或多次操作后，可能得到的 $S$ 的不同字符串的种类数，结果对 $10^9+7$ 取模。

## 限制条件 - $1 \leq N \leq 10^6$ - $S$ 是由 `A`、`B`、`C` 组成的长度为 $N$ 的字符串 ## 样例解释 1 例如，可以按如下方式操作，得到字符串 $S$ 为 `ACB`。 - 首先选择 $i=2$，将 $S_2$ 替换为 `C`，并删除 $S_3$，此时 $S$ 变为 `ACAC`。 - 然后选择 $i=3$，将 $S_3$ 替换为 `B`，并删除 $S_4$，此时 $S$ 变为 `ACB`。 由 ChatGPT 4.1 翻译