题目描述

有一个由 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

输入

5
ABAAC

输出

11

样例 2

输入

50
AACCCCBBBACCCCABABCCCCABACCACACACCACABABBBABABACCB

输出

256972022

说明/提示

限制条件

• $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 翻译