Henry loves plastic palindromes. He loves plastic palindromes so much that he wants to find all of the plastic palindromes in a string. But since the string is too long, he is unable to do so. A palindrome is plastic if and only if it consists of the first $K$ lowercase characters in the Latin alphabet. As his friend, please give him a birthday surprise by counting the number of non-empty plastic palindromic substrings in the given string $S$.

A substring is obtained by deleting several (possibly, none) characters from the front of the string and several (possibly, none) characters from the back of the string.

Input

The first line of the input contains one string, $S$.
The second line of the input contains one integer, $K$.

Output

Output a single line, the number of non-empty plastic palindromic substrings in string $S$. $S$ contains lowercase characters only.

Constraints

In all cases, $1 \le |S| \le 10^6, 1 \le K \le26.$
Subtask 1 (30%): $|S| \le 100$
Subtask 2 (69%): $|S| \le 2000$
Subtask 3 (1%): No additional constraints