Вам дана строка s, состоящая из строчных латинских букв. Некоторые из латинских букв являются хорошими, остальные — плохими.
Подстрокой s[l...r] (1 ≤ l ≤ r ≤ |s|) строки s = s1s2...s|s| (где |s| — длина строки s) называется строка slsl + 1...sr.
Подстроку s[l...r] назовем хорошей, если среди букв sl, sl + 1, ..., sr не более k являются плохими (смотрите пояснения к примерам для лучшего понимания).
Ваша задача — найти количество различных хороших подстрок данной строки s. Две подстроки s[x...y] и s[p...q] различны, если различно их содержимое, то есть s[x...y] ≠ s[p...q].
Выходные данные
Выведите единственное целое число — количество различных хороших подстрок строки s.
Примечание
В первом примере хорошими подстроками являются: «a», «ab», «b», «ba», «bab».
Во втором примере хорошими подстроками являются: «a», «aa», «ac», «b», «ba», «c», «ca», «cb».
Примеры
| № | Входные данные | Выходные данные |
|
1
|
ababab
01000000000000000000000000
1
|
5
|
|
2
|
acbacbacaa
00000000000000000000000000
2
|
8
|