问题2897--收集魔卡

2897: 收集魔卡

时间限制: 1 Sec  内存限制: 128 MB
提交: 143  解决: 72
[状态] [讨论版] [提交] [命题人:]
题目描述


小樱正在辛苦的收集魔卡,我们把每一个地点的魔卡简化到一条直线上,下标从1-n,小樱可以选择从某个地点开始往后连续的搜集(走到某格将代表拾取此处的魔卡),并且在某一地点停止而去战斗(走一格也可以),但是为了在战斗时拥有更多的选择,她想要至少搜集到k个正义的魔卡,同时要避免搜集到召唤恶灵的魔卡,现在小樱想要知道她一共可以有多少个搜集的方案。


输入


第一行输入两个正整数n(1 <= n <= 200000) k(1 <= k <= 15),

第二行输入一行字符串,字符串仅包含大写字母(AZ)。

E代表正义的魔卡,G代表召唤恶灵的魔卡。


输出

输出小樱的有效搜索的方案数。

样例输入 Copy
5 1
EAEGE
样例输出 Copy
6
提示
合法的方案:
s[1,1] = E
s[1,2] = EA
s[1,3] = EAE
s[2,3] = AE
s[3,3] = E
s[6,6] = E


来源/分类