A string is fun if it contains each character at most ~K~ times. Given a string ~S~, how many substrings of the string are fun? A substring is a non-empty contiguous sequence of characters within a string.

Input Specification

The first line will contain the string ~S~ ~(1 \le |S| \le 10^5)~. The string will only consist of lowercase latin characters.

The second line will contain the integer ~K~ ~(1 \le K \le |S|)~.

Output Specification

Output the number of substrings that are considered fun.

Subtasks

Subtask 1 [10%]

~|S| \le 20~

Subtask 2 [20%]

~S~ will only contain the characters a and b.

Subtask 3 [70%]

No further constraints.

Sample Input 1 (Subtask 1)

abcabca
2

Sample Output 1

27

Sample Input 2 (Subtask 2)

aaaaaaaaaabbbbbbbbbba
2

Sample Output 2

45

Sample Input 3 (Subtask 3)

abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz
1

Sample Output 3

1027