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>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x)//  cerr << #x << " = " << x << endl
using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const ld PI = 3.14159265359;

const ll MOD = (ll) 1e9 + 7;
const ll MAXN = (ll) 3e5 + 10;
const ll INF = (ll) 2242545357980376863;
const ld EPS = (ld) 1e-8;

vector<ll> A;
ll dp[MAXN], sm[MAXN];

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	ll n, m;
	cin >> n >> m;
	str s;
	cin >> s;
	
	ll cnt = 1;
	for(int i = 1; i < m; i++){
		if(s[i] == s[i - 1]) cnt ++;
		else {
			A.pb(cnt);
			cnt = 1;
		}
	}
	A.pb(cnt);
	if(A.size() == 1){
		//debug("S");
		dp[1] = 1;
		dp[2] = 0;
		sm[1] = 1;
		sm[2] = 1;
		for(int i = 3; i <= n; i++){
			dp[i] = sm[i - 2];
			sm[i] = (dp[i] + sm[i - 1]) % MOD;
		}
		ll ans = 1;
		for(int len = 1; len <= n - 1; len ++){
			ans += (len + 1ll) * dp[n - len];
			ans %= MOD;
		}
		cout << ans;
		return 0;
		/////
	}
	
	ll mx;
	
	if(A[0] % 2 == 0) mx = A[0] + 1;
	else mx = A[0];
	for(int i = 2; i + 1 < A.size(); i += 2){
		if(A[i] % 2 == 1) mx = min(mx, A[i]);
	}
	debug(mx);
	dp[0] = 0;
	dp[1] = 1;
	dp[3] = 1;
	for(int i = 5; i <= n; i++){
		dp[i] = dp[i - 2] + dp[i - 2];
		if(i >= mx + 3) dp[i] -= dp[i - mx - 3];
		dp[i] %= MOD;
	}
	//debug(dp[1]);
	//debug(dp[3]);
	ll ans = 0;
	for(ll len = 1; len <= min(n-1ll, mx); len += 2){
		ans += ((len + 1ll) * dp[n - len]);
		ans %= MOD;
	}
	cout << ((ans % MOD) + MOD)%MOD;
	
	return 0;
}


/*

                                 ____              ,----..               ,----..
   ,---,                       ,'  , `.           /   /   \             /   /   \
  '  .' \                   ,-+-,.' _ |          /   .     :           /   .     :
 /  ;    '.              ,-+-. ;   , ||         .   /   ;.  \         .   /   ;.  \
:  :       \            ,--.'|'   |  ;|        .   ;   /  ` ;        .   ;   /  ` ;
:  |   /\   \          |   |  ,', |  ':        ;   |  ; \ ; |        ;   |  ; \ ; |
|  :  ' ;.   :         |   | /  | |  ||        |   :  | ; | '        |   :  | ; | '
|  |  ;/  \   \        '   | :  | :  |,        .   |  ' ' ' :        .   |  ' ' ' :
'  :  | \  \ ,'        ;   . |  ; |--'         '   ;  \; /  |        '   ;  \; /  |
|  |  '  '--'          |   : |  | ,             \   \  ',  /          \   \  ',  /
|  :  :                |   : '  |/               ;   :    /            ;   :    /
|  | ,'                ;   | |`-'                 \   \ .'              \   \ .'
`--''                  |   ;/                      `---`                 `---`
                       '---'

*/

