Різні підрядки

Limits: 3 sec., 512 MiB

У Зеника та Марічки є рядок \(s\), який складається із \(n\) маленький англійських букв a-z.

Сьогодні вони хочуть порахувати, скільки в ньому є різних підрядків, які складаються із не більше ніж \(k\) різних букв. Допоможіть їм знайти цю кількість.

Input

У першому рядку задано два цілих числа \(n\) та \(k\) — розмір рядка \(s\), а також максимальна кількість різних букв.

У другому рядку задано послідовність із \(n\) символів, кожен з яких є маленькою англійською буквою.

Output

У єдиному рядку виведіть одне ціле число — відповідь на задачу.

Constraints

\(1 \le n \le 5 \cdot 10^5\),

\(1 \le k \le 26\).

Samples

Input (stdin) сopy	Output (stdout) сopy
7 2 abacaba	9

Notes

У прикладі є 9 різних підрядків із не більше ніж 2-х букв: a, b, c, ab, ba, ac, ca, aba, aca.