A - ABA and BAB Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

A, B からなる長さ N の文字列 S が与えられます．

あなたは以下の 2 種類の操作を好きな順序で 0 回以上繰り返すことができます．

  • S の中で ABA となっている (連続した) 部分を選び，それを A で置き換える．
  • S の中で BAB となっている (連続した) 部分を選び，それを B で置き換える．

操作後の S としてあり得る文字列の個数を 10^9+7 で割ったあまりを求めてください．

制約

  • 1 \leq N \leq 250000
  • S は A, B からなる長さ N の文字列

入力

入力は以下の形式で標準入力から与えられる．

N
S

出力

答えを出力せよ．

入力例 1

4
ABAB

出力例 1

2

操作後の S としてあり得るのは以下の 2 種類の文字列です．

  • ABAB: 0 回の操作を行うことでこの文字列を得ることができます．
  • AB: S=ABAB の 1 文字目から 3 文字目までが ABA となっています．これを A で置き換えると S=AB となります．

なお，S=ABAB の 2 文字目から 4 文字目までが BAB となっているので，これを B に置き換える操作も可能です． ただし，その結果得られる AB は重複して数えないことに注意してください．

入力例 2

1
A

出力例 2

1

操作を 1 度も行うことができません．

入力例 3

17
BBABABAABABAAAABA

出力例 3

18

入力例 4

100
ABAABAABABBABAABAABAABABBABBABBABBABBABBABBABBABBABBABBABBABBABBABAABABAABABBABBABABBABAABAABAABAABA

出力例 4

415919090

10^9+7 で割ったあまりを求めるのを忘れないようにしてください．

Score : 400 points

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 ABA in S and replace it with A.
  • Choose a (contiguous) substring BAB in S and replace it with B.

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 characters A and B.

Input

The input is given from Standard Input in the following format:

N
S

Output

Print the answer.

Sample Input 1

4
ABAB

Sample 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.

Sample Input 2

1
A

Sample Output 2

1

No operations can be performed.

Sample Input 3

17
BBABABAABABAAAABA

Sample Output 3

18

Sample Input 4

100
ABAABAABABBABAABAABAABABBABBABBABBABBABBABBABBABBABBABBABBABBABBABAABABAABABBABBABABBABAABAABAABAABA

Sample Output 4

415919090

Remember to take the result modulo 10^9+7.