A string is fun if it contains each character at most times. Given a string , how many substrings of the string are fun? A substring is a non-empty contiguous sequence of characters within a string.
The first line will contain the string . The string will only consist of lowercase latin characters.
The second line will contain the integer .
Output the number of substrings that are considered fun.
Subtask 1 [10%]
Subtask 2 [20%]
will only contain the characters
Subtask 3 [70%]
No further constraints.
Sample Input 1 (Subtask 1)
Sample Output 1
Sample Input 2 (Subtask 2)
Sample Output 2
Sample Input 3 (Subtask 3)
Sample Output 3