1496: 三兄弟睡觉

辟邪，四不相和天禄正在寻找一个睡觉的地方，天禄喜欢睡在有财宝的地方，四不相喜欢有云露的地方，辟邪喜欢有邪祟的地方。他们三个按照天禄在左，辟邪在右，四不相居中的方式排列。他们找到了一大块地方，用一个长度为 $n$ 的字符串 $s$ 表示， $s_i$ 表示位置 $i$ 的特点，'A'表示有财宝，'C' 表示有云露, 'M' 表示有邪祟，其它表示什么都没有。

由于三兄弟需要保证能够相互照应，因此他们之间的分隔距离不得超过$k$($对于一种方案(i, j, z), i \le j \le k$，  $ max(j-i,z-j) \le k$ )。

问他们有多少种选择方案？

每个测试样例第一行包含两个正整数$n$和$k$ ($1 \le n \le 2 \cdot 10^5, 0 \le k \le n$)。

每个测试样例第二行包含一个由大写字符组成的字符串$s$ 。

四不相三兽可以选择的方案数。

10 3
ACMAACCMMM

11

(1, 2, 3),(4, 6, 8),(4, 6, 9), (4, 7, 8), (4, 7, 9), (4, 7, 10), (5, 6, 8), (5, 6, 9), (5, 7, 8), (5, 7, 9), (5, 7, 10)