Consider a circle whose perimeter is divided by N points into N arcs of equal length, and each of the arcs is painted red or blue. Such a circle is said to generate a string S from every point when the following condition is satisfied:

* We will arbitrarily choose one of the N points on the perimeter and place a piece on it.
* Then, we will perform the following move M times: move the piece clockwise or counter-clockwise to an adjacent point.
* Here, whatever point we choose initially, it is always possible to move the piece so that the color of the i-th arc the piece goes along is S_i, by properly deciding the directions of the moves.



Assume that, if S_i is `R`, it represents red; if S_i is `B`, it represents blue. Note that the directions of the moves can be decided separately for each choice of the initial point.

You are given a string S of length M consisting of `R` and `B`. Out of the 2^N ways to paint each of the arcs red or blue in a circle whose perimeter is divided into N arcs of equal length, find the number of ways resulting in a circle that generates S from every point, modulo 10^9+7.

Note that the rotations of the same coloring are also distinguished.

Constraints

* 2 \leq N \leq 2 \times 10^5
* 1 \leq M \leq 2 \times 10^5
* |S|=M
* S_i is `R` or `B`.

Input

Input is given from Standard Input in the following format:


N M
S


Output

Print the number of ways to paint each of the arcs that satisfy the condition, modulo 10^9+7.

Examples

Input

4 7
RBRRBRR


Output

2


Input

3 3
BBB


Output

4


Input

12 10
RRRRBRRRRB


Output

78
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i, x, n) for (int i = x; i < (int)(n); ++i)

int const N = 200000, md = 1e9 + 7;
char s[N + 1];
int dp[N + 1], n, m;

inline void ad(int &x, int y) { if ((x += y) >= md)x -= md; }
inline void sb(int &x, int y) { if ((x -= y) <  0 )x += md; }
inline void out(int an) { printf("%d\n", an); exit(0); }

void sad(){
	dp[0] = 1;
	dp[1] = 1;
	f(i, 2, n + 1)ad(dp[i] = dp[i - 1], dp[i - 2]);
	int an = dp[n];
	ad(an, dp[n - 2]);
	out(an);
}

int main(){
	scanf("%d%d%s", &n, &m, s);
	int mx = md;
	bool im = false;
	f(i, 0, m){
		int j = i;
		while (j + 1 < m && s[j + 1] == s[i])++j;
		if (i == 0 && j + 1 == m)sad();
		im = !im;
		if (im && j + 1 != m){
			int ln = j - i + 1;
			if (ln & 1)mx = min(mx, ln);
			else if (i == 0)mx = min(mx, ln | 1);
		}
		i = j;
	}
	if (n & 1)out(0);
	n >>= 1;
	mx = mx + 1 >> 1;
	int l = 1, s = 0;
	f(i, 1, n + 1){
		if (i - l > mx)sb(s, dp[l++]);
		dp[i] = s;
		if (i <= mx)ad(dp[i], i << 1);
		ad(s, dp[i]);
	}
	out(dp[n]);
}