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;

long long prime = 1000000007;

bool all_chars_equal(string s) {
    for (char c : s) {
        if (c != s[0]) {
            return false;
        }
    }
    return true;
}

vector<int> get_runs(string s) {
    vector<int> runs;
    int current_run = 0;
    for (char c : s) {
        if (c == s[0]) {
            ++current_run;
        } else if (current_run > 0) {
            runs.push_back(current_run);
            current_run = 0;
        }
    }
    return runs;
}
    
long long f(int n, int k) {
    vector<long long> pow_2(2 * k + 4);
    pow_2[0] = 1LL;
    for (int i = 1; i < 2 * k + 4; ++i) {
        pow_2[i] = pow_2[i - 1] * 2 % prime;
    }

    vector<long long> f1(max(n + 1, 2 * k + 4), 0);
    for (int i = 1; i <= k; ++i) {
        f1[i] = pow_2[i];
    }
    f1[k + 1] = (pow_2[k+1] - 1 + prime) % prime;
    for (int n1 = k + 2; n1 <= 2 * k + 3; ++n1) {
        f1[n1] = ((pow_2[n1] - 1 - n1 * pow_2[n1 - k - 2]) % prime + prime) % prime;
    }
    for (int n1 = 2 * k + 4; n1 <= n; ++n1) {
        f1[n1] = ((2 * f1[n1 - 1] - f1[n1 - k - 2]) % prime + prime) % prime;
    }
    return f1[n];
}

/*
f(n, k) = antal cirkler af længde n med højst k røde i streg (ingen andre begrænsninger)

f(n, k) = 2^n for n <= k
f(n, k) = 2^n - 1 for n = k+1
f(n, k) = 2^n - 1 - n * 2^{n-k-2} for k+2 <= n <= 2k+3
f(n, k) = 2f(n-1, k) - f(n-k-2, k) for n >= 2k + 4

*/

long long different_case(int n, int k) {
    return f(n / 2, (k - 1) / 2) * 2LL % prime;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    string s;
    cin >> n >> m;
    cin >> s;
    auto t0 = clock();
    if (all_chars_equal(s)) {
        cout << f(n, 1) << endl;  // OK since n >= 2
        cerr << "Time used: " << clock() - t0 << " ms" << endl;
        return 0;
    }
    if (n % 2 != 0) {
        cout << 0 << endl;
        return 0;
    }
    vector<int> runs = get_runs(s);
    int bound = runs[0] / 2 * 2 + 1;
    bound = min(bound, n - 1);
    for (int run : runs) {
        if (run % 2 == 1) {
            bound = min(bound, run);
        }
    }
    cout << different_case(n, bound) << endl;

    cerr << "Time used: " << clock() - t0 << " ms" << endl;
    return 0;
}
