题目描述

给定一个由 A 和 B 组成、长度为 $N$ 的字符串 $S$。

你可以以任意顺序重复进行以下两种操作 $0$ 次或多次：

• 在 $S$ 中选择一个连续的子串 ABA，并将其替换为 A。
• 在 $S$ 中选择一个连续的子串 BAB，并将其替换为 B。

请你求出经过若干次操作后，可能得到的不同字符串的数量，并对 $10^9+7$ 取模。

输入格式

输入以以下格式从标准输入读入：

$N$ $S$

输出格式

请输出答案。

样例 1

输入

4
ABAB

输出

2

样例 2

输入

1
A

输出

1

样例 3

输入

17
BBABABAABABAAAABA

输出

18

样例 4

输入

100
ABAABAABABBABAABAABAABABBABBABBABBABBABBABBABBABBABBABBABBABBABBABAABABAABABBABBABABBABAABAABAABAABA

输出

415919090

说明/提示

限制条件

• $1 \leq N \leq 250000$
• $S$ 是由 A 和 B 组成的长度为 $N$ 的字符串。

样例解释 1

操作后可能得到以下 $2$ 种字符串：

• ABAB：不进行任何操作即可得到该字符串。
• AB：将 $S=$ABAB 的第 $1$ 到第 $3$ 个字符 ABA 替换为 A，得到 $S=$AB。另外，$S=$ABAB 的第 $2$ 到第 $4$ 个字符 BAB 也可以替换为 B，但结果得到的 AB 不要重复计数。

样例解释 2

无法进行任何操作。

样例解释 4

不要忘记对 $10^9+7$ 取模。

由 ChatGPT 4.1 翻译