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;

const int MOD = 1000000007;

int n, m;
string s;
int dp[212123];
int dpsum[212123];
bool nonmono;

// msize EVEN
void non(int msize) {
	assert(msize % 2 == 0);
	dp[0] = 1;
	dpsum[0] = 1;
	for (int i = 2; i <= n; i++) {
		dp[i] = dpsum[i-2];
		if (i-msize-2 >= 0) {
			dp[i] += MOD - dpsum[i-msize-2];
			dp[i] %= MOD;
		}
		dpsum[i] = (dp[i] + dpsum[i-2]) % MOD;
	}
	int ans = dp[n];
	for (int i = 1; i < n; i++) {
		// first colour must be i + 1 + evener
		int x = i + 1;
		if (x % 2 != 0) x++;
		// x now even
		if (x > msize) break;
		ans = (ans + dpsum[n-x]) % MOD;
		if (n-msize-2 >= 0) {
			ans += MOD - dpsum[n-msize-2];
			ans %= MOD;
		}
	}
	cout << ans << '\n';
}

void mono() {
	dp[0] = 1;
	dpsum[0] = 1;
	dpsum[1] = 1;
	for (int i = 2; i <= n; i++) {
		dp[i] = dpsum[i-2];
		dpsum[i] = (dpsum[i-1] + dp[i]) % MOD;
	}
	int ans = dp[n] + 1;
	for (int i = 0; i <= n-2; i++) {
		ans = (ans + dpsum[i]) % MOD;
	}
	cout << ans << '\n';
}

int main() {
	cin >> n >> m >> s;
	for (int i = 1; i < m; i++) {
		if (s[i] != s[0]) {
			nonmono = true;
			break;
		}
	}
	if (nonmono) {
		int msize = n;
		if (msize % 2 == 1) msize--;
		int fcur = -1;
		int cur = 0;
		for (int i = 0; i < m; i++) {
			if (s[i] == s[0]) cur++;
			else if (cur) {
				if (fcur == -1) fcur = cur;
				if (cur % 2 == 1) {
					cur++;
					msize = min(msize, cur);
				}
				cur = 0;
			}
		}
		fcur += 2;
		if (fcur % 2 == 1) fcur--;
		msize = min(fcur, msize);
		//cout << msize << '\n';
		non(msize);
	} else {
		mono();
	}
	return 0;
}

