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 <algorithm>
#include <iostream>
#include <string>

using namespace std;

#define MAX_N 200000
#define MAX_M 200000
#define MOD 1000000007

#define INF 1 << 29

int N, M;
string S;

long long dp[MAX_N + 2], rdp[MAX_N + 2];

int all_color_is_same()
{
    long long rr = 1, bb = 1, rb = 0, br = 0;

    for ( int i = 1; i < N; i++ )
    {
        long long nrr = ( rr + rb ) % MOD;
        long long nbb = br;
        long long nrb = rr;
        long long nbr = ( bb + br ) % MOD;

        rr = nrr;
        bb = nbb;
        rb = nrb;
        br = nbr;
    }

    return ( rr + rb + br ) % MOD;
}

/* S
の先頭の文字の最小連続回数を求める。ただし連続回数が偶数のものは無視する。
*/
int min_freq()
{
    int l = 0;
    while ( l < M && S[0] == S[l] ) l++;

    int ans = ( l & 1 ) ? l : l + 1;

    l = 0;
    for ( int i = 0; i < M; i++ )
    {
        if ( S[0] == S[i] )
            l++;
        else
        {
            if ( l & 1 ) ans = min( ans, l );
            l = 0;
        }
    }
    return ans;
    // int l = 0;
    // while ( S[0] == S[l] ) l++;
    // if ( l % 2 == 0 ) l++;
    // int limit = l;
    // l = 0;
    // for ( int i = 0; i < M; i++ )
    // {
    //     if ( S[i] == S[0] )
    //         l++;
    //     else
    //     {
    //         if ( l % 2 == 1 ) limit = min( limit, l );
    //         l = 0;
    //     }
    // }
    // return limit;
}

int solve()
{
    // 一色
    if ( S.find( "R" ) == string::npos || S.find( "B" ) == string::npos )
        return all_color_is_same();

    // N が奇数
    if ( N & 1 ) return 0;

    int L = min_freq();

    L = ( L + 1 ) >> 1;
    N >>= 1;

    dp[0] = rdp[0] = 1;
    for ( int i = 1; i <= N + 1; i++ )
    {
        dp[i] = rdp[i - 1];
        if ( i - L - 1 >= 0 ) dp[i] = ( dp[i] - rdp[i - L - 1] ) % MOD;
        if ( dp[i] < 0 ) dp[i] += MOD;
        rdp[i] = ( rdp[i - 1] + dp[i] ) % MOD;
    }

    long long res = 0;
    for ( int i = 1; i <= L; i++ )
        if ( N >= i ) res = ( res + dp[N - i] * 2 * i ) % MOD;

    return res % MOD;
}

int main( int argc, char **argv )
{
    cin >> N >> M;
    cin >> S;

    int ans = solve();

    cout << ans << endl;

    return 0;
}
