← 返回题目列表

AtCoder · agc033_e

E. 绕一圈

中文机器翻译题面 查看原题

分数: 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 R or B.

输入

输入由标准输入按以下格式给出:

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