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;
template<typename T>inline T read(){
	T f=0,x=0;char c=getchar();
	while(!isdigit(c)) f=c=='-',c=getchar();
	while(isdigit(c)) x=x*10+c-48,c=getchar();
	return f?-x:x;
}
namespace run{
	const int N=2e5+9,mod=1e9+7;
	inline int add(int x,int y){return x+y>=mod?x-mod+y:x+y;}
	inline int sub(int x,int y){return x>=y?x-y:x+mod-y;}
	inline int qpow(int x,int y){
		int ret=1;
		while(y){
			if(y&1) ret=1LL*x*ret%mod;
			x=1LL*x*x%mod,y>>=1;
		}
		return ret;
	}

	int n,m,f[N],sum[N];char s[N];
	int main(){
		n=read<int>(),m=read<int>(),scanf("%s",s+1);
		
		int peg=1;
		for(int i=2;i<=m;i++) if(s[1]!=s[i]) peg=0;
		if(peg){
			f[0]=1,f[1]=0,sum[0]=sum[1]=1;
			for(int i=2;i<=n;i++)
				f[i]=sum[i-2],sum[i]=add(sum[i-1],f[i]);
		//	for(int i=1;i<=n;i++) cout<<f[i]<<" ";cout<<endl;
			int ans=0;
			for(int i=2;i<=n;i++) ans=add(ans,1LL*f[n-i]*i%mod);
			printf("%d\n",add(ans,1));
			return 0;
		}
		int mx=0,i,t;
		for(i=1;i<=m;i++)
			if(s[i]!=s[1]){mx=i-1+(~(i-1)&1);break;}
		for(t=0;i<=m;i++)
			if(s[i]!=s[1]){
				if(t&1) mx=min(mx,t);
				t=0;
			}else t++;

		f[0]=1,f[1]=0,sum[0]=sum[1]=1;
		for(i=2;i<=n;i++){
			if(~i&1) f[i]=sub(sum[i-2],i-mx-2>=0?sum[i-mx-2]:0);
			sum[i]=sum[i-1];
			if(~i&1) sum[i]=add(sum[i],f[i]);
		}
	//	for(int i=1;i<=n;i++) cout<<f[i]<<" ";cout<<endl;
		int ans=0;
		for(int i=2;i<=mx+1;i++) if(~i&1) ans=add(ans,1LL*f[n-i]*i%mod);
		printf("%d\n",ans);
		return 0;
	}
}
int main(){
#ifdef my
	freopen(".in","r",stdin);
	freopen(".out","w",stdout);
#endif
	return run::main();
}