Ring
时间限制：30s 【提交】 空间限制：256MB
题目描述
S国的公主准备制作一串项链，镶有n刻宝石，宝石有红蓝两种。宝石的排列会给人带来不同的感觉，公主认为项链要有一个长度为k的连续的排列a，这串项链才算作漂亮。项链显然可以旋转，但由于宝石并不对称，有正反两面，所以不能翻折。这个艰巨的任务将要交给你的好友，好友想知道一共存在多少种这样的项链。
输入格式
第一行输入n，k如题意。
第二行输入一个长为k的由’R’和’B’组成的字符串a。
第二行输入一个长为k的由’R’和’B’组成的字符串a。
输出格式
一个数，表示不同的项链总数mod 1000000007。
样例输入
3 2 RB
样例输出
2
提示
100%的数据1<=n<=109，1<=k<=30且k<=n
题目来源
没有写明来源