题目描述

我们有一个长度为$N$的字符串$S$，由字符A、B和C组成。

可以对$S$进行以下操作零次或多次：

• 选择 $i$ $(1 \\leq i \\leq |S| - 1)$，满足 $S_i \\neq S_{i + 1}$。将 $S_i$ 替换为与 $S_i$ 和 $S_{i + 1}$ 均不同的字符（A、B 和 C 中的一个），并从 $S$ 中删除 $S_{i + 1}$。

找出在零次或多次操作后，$S$ 可以得到的不同字符串数量，并按模 $(10^9+7)$ 进行打印。

约束条件

• $1 \\leq N \\leq 10^6$
• $S$ 是由字符A、B和C组成的长度为 $N$ 的字符串。

输入

输入以以下格式从标准输入中给出：

$N$

$S$

输出

按模 $(10^9+7)$ 打印在零次或多次操作后，$S$ 可以得到的不同字符串数量。

示例输入1

5
ABAAC

示例输出1

11

例如，以下操作序列可以将 $S$ 变为 ACB：

• 首先选择 $i=2$。我们将 $S_2$ 替换为 C，并删除 $S_3$，将 $S$ 变为 ACAC。
• 然后选择 $i=3$。我们将 $S_3$ 替换为 B，并删除 $S_4$，将 $S$ 变为 ACB。

示例输入2

50
AACCCCBBBACCCCABABCCCCABACCACACACCACABABBBABABACCB

示例输出2

256972022