AT_agc033_e [AGC033E] Go around a Circle

一个圆周被 $N$ 个点等分，每个点之间的圆弧被涂成红色或蓝色。我们说，这个圆可以从所有点出发生成一个由 `R` 和 `B` 组成、长度为 $M$ 的字符串 $S$，当且仅当满足以下条件： - 从圆周上的 $N$ 个点中任选一个点，将棋子放在该点上。 - 将棋子沿顺时针或逆时针方向移动到相邻的点，如此重复 $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$ 取模的结果。

### 限制条件 - $2 \leq N \leq 2 \times 10^5$ - $1 \leq M \leq 2 \times 10^5$ - $|S| = M$ - $S_i$ 是 `R` 或 `B` ### 样例解释 1 只有当红色和蓝色交替涂色时，才能满足条件。因此，这种情况下答案为 $2$。 由 ChatGPT 4.1 翻译