← 返回题目列表

AtCoder · arc180_a

A. ABA 和 BAB

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

给你一个字符串 S 长度 N 由字符组成 A 和 B.

您可以按任意顺序执行以下两种类型的操作零次或多次:

  • 选择一个(连续的)子字符串 ABA in S 并将其替换为 A.
  • 选择一个(连续的)子字符串 BAB in S 并将其替换为 B.

查找,取模 10^9+7,可能的字符串数量 S 执行操作后。

约束

  • 1 \leq N \leq 250000
  • S 是一个长度为 N 由字符组成 A 和 B.

输入

输入由标准输入按以下格式给出:

N
S

输出

打印答案。


示例输入 1

4
ABAB

示例输出 1

2

两个可能的字符串 S 之后的操作如下:

  • ABAB:该字符串可以通过零运算得到。
  • AB: 第 1 到第 3 个字符 S=ABAB 是 ABA。将它们替换为 A 结果 S=AB.

这里,第2个到第4个字符 S=ABAB 是 BAB,所以你也可以将它们替换为 B。但请注意,由此产生的 AB 不计算多次。


示例输入 2

1
A

示例输出 2

1

无法执行任何操作。


示例输入 3

17
BBABABAABABAAAABA

示例输出 3

18

示例输入 4

100
ABAABAABABBABAABAABAABABBABBABBABBABBABBABBABBABBABBABBABBABBABBABAABABAABABBABBABABBABAABAABAABAABA

示例输出 4

415919090

记住对结果取模 10^9+7.