分数: 1500 点
问题陈述
考虑一个周长除以的圆 N 指向 N 等长的弧线,每条弧线都涂成红色或蓝色。据说这样的圆 生成一个字符串 S 从每一点 当满足以下条件时:
- 我们将任意选择其中之一 N 指向周边并在其上放置一块。
- 然后,我们将执行以下动作 M 次:将棋子顺时针或逆时针移动到相邻点。
- 在这里,无论我们最初选择什么点,总是可以移动棋子,使得棋子的颜色 i该片段所经过的第弧是 S_i,通过正确决定移动的方向。
假设,如果 S_i is R,代表红色;如果 S_i is B,代表蓝色。
请注意,可以针对初始点的每个选择单独确定移动方向。
给你一个字符串 S 长度 M 组成 R 和 B。
出于 2^N 将周长分为以下的圆中的每个弧线涂成红色或蓝色的方法 N 等长的弧,求生成圆的方法数 S 从每个点取模 10^9+7.
注意,相同颜色的旋转也是有区别的。
约束
- 2 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- |S|=M
- S_i is
RorB.
输入
输入由标准输入按以下格式给出:
N M S
输出
打印满足条件的每个弧的绘制方式数,模数 10^9+7.
样本输入 1
4 7 RBRRBRR
示例输出 1
2
只有将圆弧交替涂成红色和蓝色才满足条件,所以这里的答案是 2.
示例输入 2
3 3 BBB
示例输出 2
4
示例输入 3
12 10 RRRRBRRRRB
示例输出 3
78