AT_arc180_a [ARC180A] ABA and BAB

[problemUrl]: https://atcoder.jp/contests/arc180/tasks/arc180_a `A`, `B` からなる長さ $ N $ の文字列 $ S $ が与えられます． あなたは以下の $ 2 $ 種類の操作を好きな順序で $ 0 $ 回以上繰り返すことができます． - $ S $ の中で `ABA` となっている (連続した) 部分を選び，それを `A` で置き換える． - $ S $ の中で `BAB` となっている (連続した) 部分を選び，それを `B` で置き換える． 操作後の $ S $ としてあり得る文字列の個数を $ 10^9+7 $ で割ったあまりを求めてください．

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

答えを出力せよ．

### 制約 - $ 1\ \leq\ N\ \leq\ 250000 $ - $ S $ は `A`, `B` からなる長さ $ N $ の文字列 ### Sample Explanation 1 操作後の $ S $ としてあり得るのは以下の $ 2 $ 種類の文字列です． - `ABAB`: $ 0 $ 回の操作を行うことでこの文字列を得ることができます． - `AB`: $ S= $`ABAB` の $ 1 $ 文字目から $ 3 $ 文字目までが `ABA` となっています．これを `A` で置き換えると $ S= $`AB` となります． なお，$ S= $`ABAB` の $ 2 $ 文字目から $ 4 $ 文字目までが `BAB` となっているので，これを `B` に置き換える操作も可能です． ただし，その結果得られる `AB` は重複して数えないことに注意してください． ### Sample Explanation 2 操作を $ 1 $ 度も行うことができません． ### Sample Explanation 4 $ 10^9+7 $ で割ったあまりを求めるのを忘れないようにしてください．