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<stdio.h>
#include<vector>
#include<algorithm>
#include<string>
#include<iostream>
using namespace std;
#define SIZE 262144
typedef long long ll;
ll mod = 1000000007;
class BIT
{
public:
	ll bit[SIZE + 1];
	void add(int a, ll b)
	{
		a+=120000;
		for (;;)
		{
			bit[a] += b;
			bit[a] %= mod;
			a += a&-a;
			if (a > SIZE)return;
		}
	}
	ll get(int a)
	{
		a+=120000;
		ll ret = 0;
		for (;;)
		{
			ret += bit[a];
			a -= a&-a;
			if (a == 0)return ret%mod;
		}
	}
};
BIT bi;
ll dp[202020];
ll sub[2][202020][2];
int main()
{
	int num, len;
	scanf("%d%d", &num, &len);
	string s;
	cin >> s;
	if (s[0] == 'B')
	{
		for (int i = 0; i < s.size(); i++)s[i] = 'R' + 'B' - s[i];
	}
	int mini = 1000000000, cnt = 0;
	bool ff = false;
	for (int i = 0; i < s.size(); i++)
	{
		if (s[i] == 'R')cnt++;
		else
		{
			if (!ff)
			{
				if (cnt % 2 == 0)mini = min(mini, cnt + 1);
				else mini = min(mini, cnt);
				ff = true;
			}
			else if (cnt % 2 == 1)mini = min(mini, cnt);
			cnt = 0;
		}
	}
	if (!ff)
	{
		sub[0][0][0] = sub[1][0][1] = 1;
		for (int i = 0; i < 2; i++)
		{
			for (int j = 1; j < num; j++)
			{
				sub[i][j][0] = (sub[i][j - 1][0] + sub[i][j - 1][1]) % mod;
				sub[i][j][1] = sub[i][j - 1][0];
			}
		}
		ll r = sub[0][num - 1][0] + sub[0][num - 1][1] + sub[1][num - 1][0];
		printf("%lld\n", r%mod);
		return 0;
	}
	if (num % 2 == 1)
	{
		printf("0\n");
		return 0;
	}
	mini = (mini + 1) / 2;
	num /= 2;
	mini = min(mini, num);
	dp[0] = 1;
	bi.add(0, 1);
	for (int i = 1; i <= num; i++)
	{
		dp[i] = (bi.get(i - 1) - bi.get(i - mini - 1) + mod) % mod;
		bi.add(i, dp[i]);
		//printf("%d %lld\n", i, dp[i]);
	}
	ll r = 0;
	for (int i = 1; i <= mini; i++)r = (r + dp[num - i] * i * 2) % mod;
	printf("%lld\n", r);
}