AT_agc033_e [AGC033E] Go around a Circle

[problemUrl]: https://atcoder.jp/contests/agc033/tasks/agc033_e 円周が $ N $ 個の点によって $ N $ 等分され、それぞれが赤か青のいずれかで塗られているような円が、 `R` と `B` からなる長さ $ M $ の文字列 $ S $ をすべての点から生成するとは、以下の条件を満たすことを指します。 - 円周上の $ N $ 個の点のうち $ 1 $ つを任意に選び、その点上に駒を置く。 - 駒を時計回り、または反時計回りに隣合う点まで動かすことを $ M $ 回繰り返す。 - このとき最初にどの点を選んだとしても、うまく動かす向きを定めることで、$ i $ 回目に駒が通る円弧の色が $ S_i $ であるようにできる。 ただし、$ S_i $ は `R` のとき赤を、`B` のとき青を指すものとします。 また駒を動かす向きは、最初に選ぶ点ごとに変えられることに注意してください。 実際に `R` と `B` からなる長さ $ M $ の文字列 $ S $ が与えられます。 円周が $ N $ 等分されている円の各円弧を赤または青のいずれかで塗る $ 2^N $ 通りの方法のうち、 $ S $ をすべての点から生成するような塗り方の個数を $ 10^9+7 $ で割ったあまりを求めてください。 ただし、回転して一致するような塗り方も区別して数えます。

N/A

N/A

### 制約 - $ 2\ ≦\ N\ ≦\ 2\ \times\ 10^5 $ - $ 1\ ≦\ M\ ≦\ 2\ \times\ 10^5 $ - $ |S|=M $ - $ S_i $ は `R` または `B` ### Sample Explanation 1 赤と青が交互に塗られているときのみ条件を満たします。 なので、このケースの答えは $ 2 $ となります。