[ARC180] A - ABA and BAB

A - ABA and BAB

Time Limit: 2 sec / Memory Limit: 1024 MB

分数: 400 分

题面

给定一个长度为 的字符串 ，由字符 A 和 B 构成。

可以按以下两种操作任意次数、任意顺序地执行：

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

在执行这些操作后，找到满足条件的字符串 的数量，对 取模后输出。

限制条件

• 是一个长度为 的字符串，由字符 A 和 B 构成。

---

输入

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

输出

输出答案。

---

输入样例 1

4
ABAB

输出样例 1

2

操作后得到的两个可能的字符串 分别如下：

• ABAB: 执行零次操作即可获得这个字符串。
• AB: 字符串 ABAB 的第 1 至 3 个字符为 ABA，将其替换为 A 可得到 AB。

同理，ABAB 的第 2 至 4 个字符为 BAB，也可以将其替换为 B。但需要注意，得到的 AB 不会重复计数。

---

输入样例 2

1
A

输出样例 2

1

不能进行任何操作。

---

输入样例 3

17
BBABABAABABAAAABA

输出样例 3

18

---

输入样例 4

100
ABAABAABABBABAABAABAABABBABBABBABBABBABBABBABBABBABBABBABBABBABBABAABABAABABBABBABABBABAABAABAABAABA

输出样例 4

415919090

需要记得对 取模。