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>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod=1000000007;
const int MAXN=200010, LOG=20;

int n, m, k=inf, u, v, x, y, t, a, b, ans;
int A[MAXN];
int dp[MAXN];
string S;

inline void fix(int &x){
	if (x>=mod) x-=mod;
	if (x<0) x+=mod;
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin>>n>>m>>S;
	for (int i=0; i<m; i++) if (S[i]=='R') S[i]='A'; // :(
	if (S[0]=='B'){
		for (int i=0; i<m; i++) S[i]='A'+'B'-S[i];
	}
	while (S.size()>1 && S.back()=='A') S.pop_back();
	m=S.size();
//	debug(S)
	if (m==1){
		dp[1]=1;
		for (int i=3; i<=n; i++){
			fix(dp[i]=dp[i-1]+dp[i-2]);
		}
		ans=n+1;
		for (int i=3; i<n; i++) ans=(ans + (n-i+1ll)*dp[i])%mod;
		fix(ans);
		cout<<ans<<"\n";
		
		return 0;
	}
	if (n&1) kill(0)
	for (int i=0, j=0; i<m; i=j){
		if (S[i]=='B') j++;
		else{
			while (S[j]=='A' && j<m) j++;
			if (i==0 || (j-i)%2==1) k=min(k, j-i);
		}
	}
//	debug(k)
	k>>=1;
	n>>=1;
//	debug2(n, k)
	dp[0]=1;
	dp[1]=1+(k>=1);
	for (int i=2; i<=n; i++){
		fix(dp[i]=2*dp[i-1]-(k>=i-1)+(k>=i));
		if (i>=k+2) fix(dp[i]-=dp[i-k-2]);
	}
//	debug(dp[1])
//	debug(dp[2])
//	debug(dp[3])
	
	for (int i=0; i+2<=n; i++) if (n-i-2<=k) ans=(ans + (n-i-1ll)*dp[i])%mod;
	if (n-1<=k) fix(ans+=n);
	fix(ans*=2);
	fix(ans);
	cout<<ans<<"\n";
	
	return 0;
}
/*
12 5
AAAAB

6 5
RRRRB

6 5
RRBRB


*/