题目描述

円周が $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$ で割ったあまりを求めてください。

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

输入格式

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

$N$ $M$ $S$

输出格式

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

题目大意

有一个圆，圆弧被 $N$ 个点分成了等长的 $N$ 段，每段被染成了红色或蓝色。给定一个长为 $M$ 的只包含 $R$ 和 $B$ 的字符串 $S$，$R$ 代表红色，$B$ 代表蓝色。

求出有多少种给圆弧染色的方案，满足将棋子放在任意一个点上，都存在一种进行 $M$ 次操作的方案，每次操作选择将棋子顺时针或逆时针移动一段，使得第 $i$ 次经过的段的颜色为 $S_i$。

答案对 $10^9+7$ 取模。

如果两种方案旋转后相同，它们视作不同的方案。

4 7
RBRRBRR

2

3 3
BBB

4

12 10
RRRRBRRRRB

78

提示

制約

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

Sample Explanation 1

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