{"raw_statement":[{"iden":"problem statement","content":"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:\n\n*   We will arbitrarily choose one of the $N$ points on the perimeter and place a piece on it.\n*   Then, we will perform the following move $M$ times: move the piece clockwise or counter-clockwise to an adjacent point.\n*   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.\n\nAssume 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.\nYou 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$.\nNote that the rotations of the same coloring are also distinguished."},{"iden":"constraints","content":"*   $2 \\leq N \\leq 2 \\times 10^5$\n*   $1 \\leq M \\leq 2 \\times 10^5$\n*   $|S|=M$\n*   $S_i$ is `R` or `B`."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $M$\n$S$"},{"iden":"sample input 1","content":"4 7\nRBRRBRR"},{"iden":"sample output 1","content":"2\n\nThe condition is satisfied only if the arcs are alternately painted red and blue, so the answer here is $2$."},{"iden":"sample input 2","content":"3 3\nBBB"},{"iden":"sample output 2","content":"4"},{"iden":"sample input 3","content":"12 10\nRRRRBRRRRB"},{"iden":"sample output 3","content":"78"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}