题目描述

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

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

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

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

输入格式

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

$N$ $S$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

4
ABAB

输出 #1

2

输入输出样例 #2

输入 #2

1
A

输出 #2

1

输入输出样例 #3

输入 #3

17
BBABABAABABAAAABA

输出 #3

18

输入输出样例 #4

输入 #4

100
ABAABAABABBABAABAABAABABBABBABBABBABBABBABBABBABBABBABBABBABBABBABAABABAABABBABBABABBABAABAABAABAABA

输出 #4

415919090

大样例

见选手目录下的 ABA/ABA.in 和 ABA/ABA.out。

说明/提示

限制条件

• $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$ 取模。