{"problem":{"name":"Go around a Circle","description":{"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_","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc033_e"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   $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`.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $M$\n$S$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc033_e","tags":[],"sample_group":[["4 7\nRBRRBRR","2\n\nThe condition is satisfied only if the arcs are alternately painted red and blue, so the answer here is $2$."],["3 3\nBBB","4"],["12 10\nRRRRBRRRRB","78"]],"created_at":"2026-03-03 11:01:14"}}