题目描述

$S$ 国的公主准备制作一串项链，镶有 $n$ 颗宝石，宝石有红蓝两种。

宝石的排列会给人带来不同的感觉，公主认为项链要有一个长度为 $k$ 的连续的排列 $a$，这串项链才算作漂亮。

项链显然可以旋转，但由于宝石并不对称，有正反两面，所以不能翻折。

这个艰巨的任务将要交给你的好友，好友想知道一共存在多少种这样的项链。

输入格式

第一行两个整数 $n,k$ ；

第二行输入一个长为 $k$ 的由 $\text{R}$ 和 $\text{B}$ 组成的字符串 $a$。

输出格式

一个数，表示不同的项链总数 $\bmod 1000000007$。

3 2
RB

2

提示

对于 $100\%$ 的数据 $1\leq n\leq 109,1\leq k\leq 30,k\leq n$。