E - Go around a Circle Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 1500 点

問題文

円周が N 個の点によって N 等分され、それぞれが赤か青のいずれかで塗られているような円が、 R と B からなる長さ M の文字列 S をすべての点から生成するとは、以下の条件を満たすことを指します。

  • 円周上の N 個の点のうち 1 つを任意に選び、その点上に駒を置く。
  • 駒を時計回り、または反時計回りに隣合う点まで動かすことを M 回繰り返す。
  • このとき最初にどの点を選んだとしても、うまく動かす向きを定めることで、i 回目に駒が通る円弧の色が S_i であるようにできる。

ただし、S_i は R のとき赤を、B のとき青を指すものとします。 また駒を動かす向きは、最初に選ぶ点ごとに変えられることに注意してください。

実際に R と B からなる長さ M の文字列 S が与えられます。 円周が N 等分されている円の各円弧を赤または青のいずれかで塗る 2^N 通りの方法のうち、 S をすべての点から生成するような塗り方の個数を 10^9+7 で割ったあまりを求めてください。

ただし、回転して一致するような塗り方も区別して数えます。

制約

  • 2 ≦ N ≦ 2 \times 10^5
  • 1 ≦ M ≦ 2 \times 10^5
  • |S|=M
  • S_i は R または B

入力

入力は以下の形式で標準入力から与えられる。

N M
S

出力

条件を満たすような各円弧の塗り方の個数を 10^9+7 で割ったあまりを出力せよ。

入力例 1

4 7
RBRRBRR

出力例 1

2

赤と青が交互に塗られているときのみ条件を満たします。 なので、このケースの答えは 2 となります。

入力例 2

3 3
BBB

出力例 2

4

入力例 3

12 10
RRRRBRRRRB

出力例 3

78

Score : 1500 points

Problem Statement

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.

Sample Input 1

4 7
RBRRBRR

Sample Output 1

2

The condition is satisfied only if the arcs are alternately painted red and blue, so the answer here is 2.

Sample Input 2

3 3
BBB

Sample Output 2

4

Sample Input 3

12 10
RRRRBRRRRB

Sample Output 3

78