配点 : $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 \leq N \leq 2 \times 10^5$
• $1 \leq M \leq 2 \times 10^5$
• $|S|=M$
• $S_i$ は R または B

入力

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

$N$ $M$

$S$

出力

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

4 7
RBRRBRR

2

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

3 3
BBB

4

12 10
RRRRBRRRRB

78