#P3457. Ring

    ID: 2657 传统题 1000ms 512MiB 尝试: 7 已通过: 3 难度: 8 上传者: 标签>CF2500提高+/省选-Burnside 引理补集计数KMP转移矩阵矩阵快速幂欧拉函数约数成对枚举试除法分解质因数模逆元

Ring

题目描述

SS 国的公主准备制作一串项链,镶有 nn 颗宝石,宝石有红蓝两种。

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

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

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

输入格式

第一行两个整数 n,kn,k ;

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

输出格式

一个数,表示不同的项链总数  mod 1000000007\bmod 1000000007。

3 2
RB
2

提示

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