http://www.tsinsen.com/

清橙网格自动评测系统

>> 用户名或邮箱:   密码:       忘记密码   其他登录:
 
 
 
A1494. ring(高胜寒)
时间限制:3.0s   内存限制:256.0MB  
总提交次数:   AC次数:   平均分:
将本题分享到:
   
 
问题描述
  S国的公主准备制作一串项链,镶有n刻宝石,宝石有红蓝两种。宝石的排列会给人带来不同的感觉,公主认为项链要有一个长度为k的连续的排列a,这串项链才算作漂亮。项链显然可以旋转,但由于宝石并不对称,有正反两面,所以不能翻折。这个艰巨的任务将要交给你的好友,好友想知道一共存在多少种这样的项链。
输入描述
  第一行输入n,k如题意。
  第二行输入一个长为k的由’R’和’B’组成的字符串a。
输出描述
  一个数,表示不同的项链总数mod 1000000007。
样例输入
3 2
RB
样例输出
2
数据规模和约定
  20%的数据n,k<=10
  30%的数据n<=25,k<=5
  50%的数据n<=100
  60%的数据n<=1000
  100%的数据1<=n<=109,1<=k<=30且k<=n