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 SZ(x) (int)(x).size()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i, a, b) for (int i=a;i>=b;--i)

const int MX_N = 2e5+5;
const int MX_M = 2e5+5;
const int MOD = 1e9+7;

int N, M;
string S;

int dp[MX_N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

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

    bool same = true;
    FOR(i,0,M-1){
        same &= S[i] == S[0];
    }

    if (same) {
        // dp[i]: no of ways to color s.t. no 2 consec is B & i-th is R
        int ans = 0;
        dp[1] = 0; dp[2] = 1;   // 1st is B
        FOR(i,3,N){
            dp[i] = (dp[i-1] + dp[i-2]) % MOD;
        }
        ans = (ans + dp[N]) % MOD;           // Nth is R
        dp[1] = 1; dp[2] = 1;   // 1st is R
        FOR(i,3,N){
            dp[i] = (dp[i-1] + dp[i-2]) % MOD;
        }
        ans = (ans + (dp[N] + dp[N-1]) % MOD) % MOD; // Nth is R and B
        cout << ans;
        return 0;
    }

    if (N&1) {
        cout << 0;
        return 0;
    }

    int k = N, kp = N, cur = 0;
    FOR(i,0,M-1){
        if (S[i] != S[0]) {
            if (k == N) {
                if (cur&1) k = cur;
                else k = cur+1;
            } else if (cur&1) kp = min(kp,cur);
            cur = 0;
        } else ++cur;
    }

    int L = min({N-1,k,kp});
    N /= 2, L /= 2;

    //cout << "L is " << L << endl;

    dp[0] = 0; dp[1] = 1;
    int sum = 0;
    FOR(i,2,N){
        if (i-(L+2) >= 1) {
            sum = (sum - dp[i-(L+2)] + MOD) % MOD;
        }
        if (i-1 >= 1) {
            sum = (sum + dp[i-1]) % MOD;
        }
        dp[i] = sum;
    }

    int ans = 0;
    FOR(i,0,L){
        ans = (ans +  1LL * (i+1) * dp[N-i] % MOD) % MOD;
    }
    cout << ans * 2 % MOD;
}

