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 <cmath>
#include <cstdio>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define MOD 1000000007
#define INF (1 << 29)
#define LINF (1LL << 60)
#define EPS (1e-10)
typedef long long Int;
typedef pair<Int, Int> P;

Int all(Int n) {  // no bb
  Int rr = 1, bb = 1, rb = 0, br = 0;
  for (int i = 1; i < n; i++) {
    Int nrr = (rr + rb) % MOD;
    Int nbb = br;
    Int nrb = rr;
    Int nbr = (bb + br) % MOD;
    rr = nrr;
    bb = nbb;
    rb = nrb;
    br = nbr;
  }
  return (rr + rb + br) % MOD;
}

Int tmp[216000];
Int rdp[216000];
Int dp[216000];
void calc(Int n, Int limit) {
  dp[0] = 1;
  rdp[0] = 1;
  for (int i = 1; i <= n + 1; i++) {
    dp[i] =
        (rdp[i - 1] - ((i - limit - 1) >= 0 ? rdp[i - limit - 1] : 0)) % MOD;
    if (dp[i] < 0) dp[i] += MOD;
    rdp[i] = (rdp[i - 1] + dp[i]) % MOD;
  }
}

Int solve(Int n, Int limit) {
  if (n % 2 == 1) return 0;
  if (limit % 2 != 1) exit(1);
  limit = (limit + 1) / 2;
  n /= 2;
  Int res = 0;
  calc(n + 10, limit);
  for (Int i = 1; i <= limit; i++) {
    if (n - i >= 0) res = (res + dp[n - i] * 2 * i) % MOD;
  }
  if (res < 0) exit(1);
  return res % MOD;
}

int main() {
  Int n, m;
  string str;
  vector<Int> vec;
  cin >> n >> m;
  cin >> str;
  bool allsame = true;
  for (int i = 0; i < m; i++) allsame &= (str[i] == str[0]);
  if (allsame) {
    cout << all(n) << endl;
    return 0;
  }
  for (int i = 0; i < m; i++) vec.push_back(str[i] == str[0]);
  // vec.push_back(0);
  Int l = 0;
  while (vec[l] == 1) l++;
  if (l % 2 == 0) l++;
  Int limit = l;
  l = 0;
  for (int i = 0; i < vec.size(); i++) {
    if (vec[i] == 1)
      l++;
    else {
      if (l % 2 == 1) limit = min(limit, l);
      l = 0;
    }
  }
  cout << solve(n, limit) << endl;
  return 0;
}