Count Valid Splits

Split a lowercase string into two non-empty contiguous parts. The split is valid if the number of distinct characters that appear in both parts is strictly greater than m. Find the number of valid splits.

输入格式

The first line contains the string (length 1..100000), and the second line contains m (0..26).

输出格式

Output a single integer, the answer.

样例 1

输入：

abbcac
1

输出：

2

样例 2

输入：

a
0

输出：

0

样例 3

输入：

aaaa
0

输出：

3

样例说明

Example 1: splitting as ab|bcac and abbc|ac gives the intersections {a,b} and {a,c}, each with 2 characters, so the answer is 2. Example 2: the string cannot be split into two non-empty parts, so the answer is 0. Example 3: at all three split points both sides contain a, which exceeds the threshold 0, so the answer is 3.