14179: 【原4179】计数

题目

题目描述

author: Sakiko 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4179

Description

侯不会正在学习一种古老的计数方式。在\((N,K)\) 计数系下，如果把每个数\(S\)看作字符串，则需要满足：
1. 包含\(N\)个字符，每个字符是′I′或者是′X′。
2. 相邻字符不相同的位置不超过\(K\)个。
3. \(S\)的字典序不大于它的反串\(S′\)。
一个数\(S\)的反串\(S′\)定义为把这个数从后往前写构成的数。
给出一个在\((N,K)\)计数系下的数\(S\)，求出它在计数系下的字典序排名。由于排名可能会很大，只需要输出它对\(10^9 + 7\)的模数。

Input Format

第一行一个整数\(T\)，表示数据组数；
每组数据的第一行包含两个整数\(N, K\)。
每组数据的第二行包含字符串\(S\)，保证它在\((N,K)\)计数系下。

Output Format

对于每组数据，输出一行，包含一个整数，代表这个数的排名对\(10^9+7\)的模数

Sample Input

2
3 2
XIX
6 4
IXIXXI

Sample Output

5
19

Data Range

对于20% 的数据，\(N ≤ 20\);
对于50% 的数据，\(N ≤ 60\);
对于100% 的数据，\(1 ≤ N ≤ 2000; 0 ≤ K < N\), \(T\)不超过\(5\).

Oops! 本题目还没有解答！

助教老师们编题的速度，已经超过了解题的速度！

OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。

如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！