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

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

第二行输入一行字符串，字符串仅包含大写字母（A到Z）。

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

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

合法的方案：
s[1,1] = E
s[1,2] = EA
s[1,3] = EAE
s[2,3] = AE
s[3,3] = E
s[6,6] = E