Маленький Слоник

Маленький Слоник нашел на чердаке старую потрепанную черно-белую строку s.

Символы строки s пронумерованы слева направо от 1 до |s|, где |s| — длина строки. Обозначим i-тый символ строки si. Так как строка черно-белая, каждый символ строки это либо буква «B», либо буква «W». К сожалению, строка очень старая и некоторые символы повреждены. На их позициях стоит буква «X».

Маленький Слоник намерен восстановить строку и повесить ее себе на стену. Для этого нужно каждый символ «X» заменить на «B» или «W». Чтобы строка хорошо смотрелась на стене, нужно чтобы она была красивой. Маленький Слоник считает строку красивой, если у нее есть две непересекающиеся подстроки, заданной длины k, таких, что левая полностью состоит из символов «B», а правая полностью состоит из символов «W». Более формально, существует четыре целых числа a, b, c, d (1 ≤ a ≤ b < c ≤ d ≤ |s|; b - a + 1 = d - c + 1 = k) таких, что si = «B» (a ≤ i ≤ b) и sj = «W» (c ≤ j ≤ d).

Помогите Маленькому Слонику найти количество различных красивых строк, которые он может получить из строки s. Две строки считаются различными, если существует такая позиция, в которой символ в первой строке отличается от соответствующего символа второй строки. Если в строке нет символов «X» и она уже красивая — то ответ 1.

Так как ответ может быть довольно большим, выведите его остаток от деления на 1000000007 (109 + 7).

Входные данные
В первой строке через пробел заданы два целых числа n и k (1 ≤ k ≤ n ≤ 106). Во второй строке задана строка s. Строка s имеет длину n и состоит только из символов «W», «B» и «X».

Выходные данные
В единственной строке выведите целое число — ответ на задачу по модулю 1000000007 (109 + 7).

Миниатюры

 

0