Skip to content

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了,可以的话,请您参考添加页面,与大家一起分享你的题解!