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 int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

const int mod=1000000007;
int fact[1111111];
int inv[1111111];

int mpow(int n,int m){
	int ret=1;
	while(m){
		if(m&1)ret=ret*n%mod;
		n=n*n%mod;
		m>>=1;
	}
	return ret;
}

int binom(int n,int k){
	return fact[n]*inv[k]%mod*inv[n-k]%mod;
}

inline void add(int &a,int b){
	a+=b;
	if(a>=mod)a-=mod;
}

int N,M;
string S;

int dp[222222];
int sum[222222];

signed main(){
	fact[0]=1;
	for(int i=1;i<1111111;i++)fact[i]=fact[i-1]*i%mod;
	inv[1111111-1]=mpow(fact[1111111],mod-2);
	for(int i=1111111-2;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;


	cin>>N>>M;
	cin>>S;

	if(S[0]=='B'){
		rep(i,M){
			if(S[i]=='R')S[i]='B';
			else S[i]='R';
		}
	}

	while(S.size()&&S.back()=='R')S.pop_back();

	if(S.size()==0){
		int ans=0;
		int a=1,b=0;
		rep(i,N){
			int aa=(a+b)%mod;
			int bb=a;
			a=aa;b=bb;
		}
		add(ans,a);

		a=0;b=1;
		rep(i,N){
			int aa=(a+b)%mod;
			int bb=a;
			a=aa;b=bb;
		}
		add(ans,b);
		cout<<ans<<endl;
		return 0;
	}

	if(N%2){
		cout<<0<<endl;
		return 0;
	}

	int ma=1001001001;
	int cur=0;
	while(cur<S.size()){
		int nex=cur;
		while(nex<S.size()&&S[cur]==S[nex])nex++;
		if(S[cur]=='R'){
			int l=nex-cur;
			if(cur==0){
				if(l%2)chmin(ma,l);
				else chmin(ma,l+1);
			}
			else{
				if(l%2)chmin(ma,l);
			}
		}
		cur=nex;
	}

    ma=(ma+1)/2;
    N/=2;

    dp[0]=sum[0]=1;

    int ans=0;
    for(int i=1;i<=N;i++){
        dp[i]=sum[i-1];
        if(i>ma)dp[i]=(dp[i]-sum[i-ma-1]+mod)%mod;
        sum[i]=(sum[i-1]+dp[i])%mod;
    }

    for(int i=1;i<=ma;i++){
        add(ans,dp[N-i]*i%mod*2%mod);
    }
    cout<<ans<<endl;
	return 0;
}
