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
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskE solver = new TaskE();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskE {
        static final long MODULO = (long) 1e9 + 7;

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int n = in.nextInt();
            int m = in.nextInt();
            String s = in.next();
            if (s.charAt(0) == 'B') {
                s = invert(s);
            }
            if (!s.contains("B")) {
                out.println(countSimple(n));
                return;
            }
            int minOdd = Integer.MAX_VALUE;
            int start = Integer.MAX_VALUE;
            int count = 0;
            for (int i = 0; i < s.length(); ++i) {
                if (s.charAt(i) == 'R') {
                    ++count;
                } else {
                    if (start == Integer.MAX_VALUE) start = count;
                    if (count % 2 != 0) {
                        minOdd = Math.min(minOdd, count);
                    }
                    count = 0;
                }
            }
            minOdd = Math.min(minOdd, start);
            out.println(countComplex(n, minOdd));
        }

        private long countComplex(int n, int minOdd) {
            if (n % 2 != 0) return 0;
            return 2 * countWithMaxRun(n / 2, minOdd / 2) % MODULO;
        }

        private long countWithMaxRun(int n, int maxRun) {
            long[] res = new long[n + 1];
            for (int i = 0; i <= maxRun && i + 1 <= n; ++i) {
                res[i + 1] = i + 1;
            }
            long s = 0;
            for (int i = 1; i <= n; ++i) {
                s += res[i - 1];
                if (i - maxRun - 2 >= 0) {
                    s -= res[i - maxRun - 2];
                }
                s %= MODULO;
                if (s < 0) s += MODULO;
                res[i] += s;
                res[i] %= MODULO;
            }
            return res[n];
        }

        private long countSimple(int n) {
            return countWithMaxRun(n, 1);
        }

        private String invert(String s) {
            char[] res = s.toCharArray();
            for (int i = 0; i < res.length; ++i) {
                res[i] ^= 'R' ^ 'B';
            }
            return new String(res);
        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}

