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 pii pair<int,int>
#define mp make_pair
#define pb push_back
#define lg long long
#define db double
#define lb(x) ((x)&-(x))
#define ft first
#define sd second

#define HII cerr<<"HI"<<endl
#define LLLINE cerr<<"@@@@@@@@@@@@@@@@@@@@"<<endl

template <class _T_>
void read(_T_& d){
	d=0;int f=1;char c=getchar();
	for(;c<'0'||c>'9';c=getchar())if(c=='-')f*=-1;
	for(;c>='0'&&c<='9';c=getchar())d=d*10+c-'0';
	d*=f;
}

/************************************************/
#define Md 1000000007
#define MN 200005
int n,m;
char c[MN];
lg Pow(lg x,lg y){
	lg res=1;for(;y;y>>=1,x=x*x%Md)if(y&1)res=res*x%Md;return res;
}
int Fix(int x){
	if(x<0)return x+Md;
	if(x>=Md)return x-Md;
	return x;
}
int dp[MN],tmp[MN];
int miu[MN];
int main(){
	read(n);read(m);
	scanf("%s",c+1);
	miu[1]=1;
	for(int i=1;i<MN;++i){
		for(int j=i+i;j<MN;j+=i){
			miu[j]-=miu[i];
		}
	}
	char Hd=c[1];
	int cnt=0,mx;
	for(int i=1;i<=m;++i){
		if(c[i]==Hd)++cnt;
		else break;
	}
	if(cnt&1)mx=cnt;else mx=cnt+1;
	if((n&1)&&cnt!=m)return puts("0"),0;
	if(cnt==m){
		int res=0;
		tmp[0]=1;
		dp[0]=1;
		if(n>=2)res=n;
		for(int i=1;i<n-1;++i){
			dp[i]=(i>=2?tmp[i-2]:0);
			tmp[i]=Fix(tmp[i-1]+dp[i]);
			res=Fix(res+1ll*dp[i]*(n-i)%Md);
		}
		printf("%d",res+1);
		return 0;
	}
	int res=(cnt==m);
	cnt=0;
	for(int i=1;i<=m;++i){
		if(c[i]==Hd)++cnt;
		else{
			if(!cnt)continue;
			if(cnt&1)mx=min(mx,cnt);
			cnt=0;
		}
	}
	//for(int i=1;i<=5;++i)cerr<<miu[i]<<' ';cerr<<endl;
	tmp[0]=tmp[1]=1;
	dp[0]=1;
	mx+=2;
	if(n<mx)res+=n;
	for(int i=2;i<=n;i+=2){
		dp[i]=Fix(tmp[i-1]-(mx>i?0:tmp[i-mx]));
		tmp[i]=tmp[i+1]=Fix(tmp[i-1]+dp[i]);
		//cerr<<dp[i]<<' '<<i<<endl;
		if((n-i)%2==0&&n-i<mx)res=Fix(res+1ll*dp[i]*(n-i)%Md);
	}
	cout<<res;
	return 0;
}
