分数: 400 点
问题陈述
给你一个字符串 S 长度 N 由字符组成 A 和 B.
您可以按任意顺序执行以下两种类型的操作零次或多次:
- 选择一个(连续的)子字符串
ABAin S 并将其替换为A. - 选择一个(连续的)子字符串
BABin 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.