题目描述

一个圆周被 $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$ 取模的结果。

样例 1

输入

4 7
RBRRBRR

输出

2

样例 2

输入

3 3
BBB

输出

4

样例 3

输入

12 10
RRRRBRRRRB

输出

78

说明/提示

限制条件

• $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 翻译