Counting Substrings with At Least k Distinct Characters

Given a string s and an integer k, your task is to compute the number of substrings of s that contain at least k distinct characters.

A substring is a contiguous sequence of characters in the string. This problem requires you to thoroughly check each possible substring to count those that satisfy the condition.

Note: If k is larger than the length of the string, the answer is 0.

The answer should be printed to standard output.

inputFormat

The input is given via standard input (stdin) and consists of two lines. The first line contains the string s, and the second line contains the integer k.

For example:

abcabc
3

outputFormat

Output a single integer on a line by standard output (stdout), which is the number of substrings that contain at least k distinct characters.

For example, given the sample input above, the correct output is 10.

## sample

abcabc
3

10