第五回日本最強プログラマー学生選手権-予選-（AtCoder Regular Contest 180）
翻译中…
Problem Statement
翻译中…
You are given a string $S$ of length $N$ consisting of characters A and B.
翻译中…
You can perform the following two types of operations zero or more times in any order:
翻译中…
- Choose a (contiguous) substring
ABAin$S$and replace it withA. - Choose a (contiguous) substring
BABin$S$and replace it withB.
翻译中…
Find, modulo $10^9+7$, the number of possible strings $S$ after performing the operations.
翻译中…
Constraints
翻译中…
$1 \leq N \leq 250000$$S$is a string of length$N$consisting of charactersAandB.
翻译中…
Input
翻译中…
The input is given from Standard Input in the following format:
翻译中…
N
S翻译中…
Output
翻译中…
Print the answer.
翻译中…
样例
Input #1
4
ABAB
Output #1
2
The two possible strings $S$ after the operations are as follows:
- `ABAB`: This string can be obtained by performing zero operations.
- `AB`: The 1st to 3rd characters of $S=$`ABAB` are `ABA`. Replacing them with `A` results in $S=$`AB`.
Here, the 2nd to 4th characters of $S=$`ABAB` are `BAB`, so you can also replace them with `B`. Note, however, that the resulting `AB` does not count multiple times.
Input #2
1
A
Output #2
1
No operations can be performed.
Input #3
17
BBABABAABABAAAABA
Output #3
18
Input #4
100
ABAABAABABBABAABAABAABABBABBABBABBABBABBABBABBABBABBABBABBABBABBABAABABAABABBABBABABBABAABAABAABAABA
Output #4
415919090
Remember to take the result modulo $10^9+7$.
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。