Split Prefix Suffix

Split the whole string into two non-empty contiguous parts; the number of distinct letters that appear in both parts must be strictly greater than k. Find the number of valid split positions; this does not count repeated occurrences of shared characters.

输入格式

The string and k are given, separated by whitespace. Original bounds: a lowercase string of length 1..100000, and 0≤k≤26.

输出格式

Output a single integer, the answer.

样例 1

输入：

abbcac
1

输出：

2

样例 2

输入：

a
0

输出：

0

样例 3

输入：

aaaa
1

输出：

0

样例说明

The outputs of the three public examples are 2; 0; and 0, checked by independent enumeration or direct simulation.