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 <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cctype>
 
#include <algorithm>
#include <tuple>
#include <random>
#include <bitset>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <vector>
#include <chrono>
#include <iostream>
#include <limits>
#include <numeric>
 
#define LOG(FMT...) fprintf(stderr, FMT)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
template <class T>
istream& operator>>(istream& is, vector<T>& v) {
  for (T& x : v)
    is >> x;
  return is;
}
 
template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  if (!v.empty()) {
    os << v.front();
    for (int i = 1; i < v.size(); ++i)
      os << ' ' << v[i];
  }
  return os;
}

const int N = 200010, P = 1000000007;

int n, m;
char s[N];

void add(int& x, int y) {
  if ((x += y) >= P)
    x -= P;
}

void sub(int& x, int y) {
  if ((x -= y) < 0)
    x += P;
}

int norm(int x) {
  return x >= P ? x - P : x;
}

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

  cin >> n >> m >> (s + 1);
  char a = s[1];
  if (count(s + 1, s + m + 1, a) == m) {
    static int dp[N][2][2];
    dp[1][0][0] = dp[1][1][1] = 1;
    for (int i = 2; i <= n; ++i)
      for (int j = 0; j < 2; ++j) {
        add(dp[i][j][0], dp[i - 1][j][0]);
        add(dp[i][j][0], dp[i - 1][j][1]);
        add(dp[i][j][1], dp[i - 1][j][0]);
      }
    int ans = norm(norm(dp[n][0][0] + dp[n][0][1]) + dp[n][1][0]);
    cout << ans << '\n';
    return 0;
  }
  int p = 1;
  while (s[p] == a) ++p;
  int len = p - 1;
  if (len % 2 == 0) ++len;
  int cur = 0;
  for (; p <= m; ++p)
    if (s[p] != a) {
      if (cur & 1)
        len = min(len, cur);
      cur = 0;
    } else
      ++cur;
  static int dp[N], sum[N];
  dp[1] = 1;
  for (int i = 2; i <= n; ++i) {
    sum[i - 1] = dp[i - 1];
    if (i - 3 >= 0)
      add(sum[i - 1], sum[i - 3]);
    dp[i] = sum[i - 2];
    if (i - len - 3 >= 0)
      sub(dp[i], sum[i - len - 3]);
  }
  int ans = 0;
  for (int i = 1; i <= n; ++i)
    if ((n - i) <= len && ((n - i) & 1))
      ans = (ans + dp[i] * (n - i + 1LL)) % P;
  cout << ans << '\n';

  return 0;
}
