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
// In the name of Allah. Ya ali!
#include<bits/stdc++.h>
#define double long double
typedef long long ll;
const ll MAX_N = 2e5+10;
const ll MOD = 1e9+7;
using namespace std;

ll dp[MAX_N];
ll sum[MAX_N];
int n,m;

ll solve(ll lim)
{
    if (n&1)
        return 0;
    dp[1] = 1;
    dp[3] = 1;
    sum[1] = 1;
    sum[3] = 2;
    for(int i = 5;i<=n+1;i+=2)
    {
        dp[i] = sum[i-2];
        if (i-2>lim)
            dp[i] = (dp[i]-sum[i-lim-3]+MOD)%MOD;
        sum[i] = (sum[i-2]+dp[i])%MOD;
    }
    ll ans = 0;
    ans = dp[n+1];
    for(ll i = 1;i<=lim;i+=2)
    {
        ans += (i*dp[n-i])%MOD;
        ans %= MOD;
    }
    return ans;
}

int main()
{
    cin >> n >> m;
    string s;
    cin >> s;
    if (s[0]=='B')
    {
        for(int i = 0;i<m;++i)
        {
            if (s[i]=='B')
                s[i] = 'R';
            else
                s[i] = 'B';
        }
    }
    bool ok = false;
    for(int i = 0;i<m;++i)
        ok |= (s[i]=='B');
    if (!ok)
    {
        dp[1] = 1;
        dp[3] = 1;
        sum[1] = 1;
        sum[2] = 1;
        sum[3] = 2;
        for(int i = 4;i<=n+1;++i)
        {
            dp[i] = sum[i-2];
            sum[i] = (sum[i-1]+dp[i])%MOD;
        }
        ll ans = dp[n+1]+1;
        for(ll i = 1;i<n;++i)
        {
            ans += (i*dp[n-i])%MOD;
            ans %= MOD;
        }
        cout << ans;
        return 0;
    }
    for(int i = m-1;i>=0;--i)
    {
        if (s[i]=='B')
        {
            m = i+1;
            break;
        }
    }
    vector<int> vc;
    int cnt = 0;
    for(int i = 0;i<m;++i)
    {
        if (s[i]=='B')
        {
            if (cnt)
                vc.push_back(cnt);
            cnt = 0;
        }
        else
            cnt++;
    }
    ok = false;
    for(auto x:vc)
        ok |= (x&1);
    if (!ok)
        return cout << solve(vc[0]+1),0;
    int mn = 1e9;
    if (vc[0]%2==0)
        mn = vc[0]+1;
    for(auto x:vc)
    {
        if (x&1)
            mn = min(mn,x);
    }
    cout << solve(mn);
    return 0;
}
