E. Equivalent
time limit per test
1 second
memory limit per test
64 megabytes
input
standard input
output
standard output

Guga was bored, so he decided to read the dictionary and learned a new word:

  • Palindrome: a word, phrase, or sequence that reads the same backward as forward.

madam, hannah, x e redivider are examples of palindromes.

Analyzing some words, Guga realized the most of them weren't palindromes and decided to create a new category called K-Palindrome, defined as follows:

  • K-Palindrome: a word, phrase or sequence that, by substituting K letters, is equivalent to a palindrome.

For example, xyz is not a palindrome, but is a 1-Palindrome, because we can substitute the x with a z and obtain zyz. On the other hand, abcb is neither a palindrome nor a 1-Palindrome, but it is a 2-Palindrome, for we can substitute two letters and obtain a palindrome.

With this new definition, Guga was able to find many more words that satisfied it.

While researching on palindromes, Guga discovered the following problem: given a string S, how many continuous substrings of S are palindromes?

Intrigued, he decided to create an equivalent problem: given a string S and an integer K, how many continuous substrings of S are K-palindromes?

Guga thinks it's very easy to find a wrong answer to his problem with large strings, and want a computer program that solve it. Help Guga (:

Input

Each test case consists of two lines.

The first line contains a string S (1 ≤ |S| ≤ 3000) composed only of lowercase letters, the string in which Guga wants to find the K-Palindromes.

The second line contains an integer K (0 ≤ K ≤ |S| / 2), the number of letters that can be substituted in S.

Output

The output consists of a single line containing an integer X, the number of substrings of S that are K-palindromes.

Examples
Input
ovo
1
Output
6
Input
ovo
0
Output
4
Note

By definition:

  • Every K-Palindrome is also a K'-Palindrome, where K' > K.
  • Every palindrome is a 0-palindrome.