[AGC033E] Go around a Circle

有一个圆，圆弧被 $N$ 个点分成了等长的 $N$ 段，每段被染成了红色或蓝色。给定一个长为 $M$ 的只包含 $R$ 和 $B$ 的字符串 $S$，$R$ 代表红色，$B$ 代表蓝色。 求出有多少种给圆弧染色的方案，满足将棋子放在任意一个点上，都存在一种进行 $M$ 次操作的方案，每次操作选择将棋子顺时针或逆时针移动一段，使得第 $i$ 次经过的段的颜色为 $S_i$。 答案对 $10^9+7$ 取模。 如果两种方案旋转后相同，它们视作不同的方案。

[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 $ $ M $ $ S $

条件を満たすような各円弧の塗り方の個数を $ 10^9+7 $ で割ったあまりを出力せよ。

4 7
RBRRBRR

2

3 3
BBB

4

12 10
RRRRBRRRRB

78

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