问题描述

考虑一个圆，其周长由$N$个点分成$N$个相等长度的弧，并且每个弧都被涂成红色或蓝色。当满足以下条件时，称这样的圆从每个点生成一个字符串$S$：

• 我们将在周长上的$N$个点中任意选择一个点，并在该点上放置一个棋子。
• 然后，我们将按顺时针或逆时针方向，将棋子移动到相邻的点上，重复执行以下移动$M$次。
• 在这里，无论我们最初选择哪个点，都可以通过适当地决定移动的方向，使棋子经过的第$i$个弧的颜色为$S_i$。

假设，如果$S_i$是R，表示红色；如果$S_i$是B，表示蓝色。需要注意的是，对于初始点的每个选择，移动的方向可以单独决定。

给定一个长度为$M$的由R和B组成的字符串$S$。在将周长分成$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$是R或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