Distinct Palindromic Substrings

You are given a string S consisting of lowercase English letters and an integer K. Your task is to compute the number of distinct substrings of S of length exactly K that are palindromic.

A palindrome is a string that reads the same forward and backward. In this problem, you need to consider only those substrings of length K and count each palindromic substring only once even if it occurs multiple times.

Note: The formula for the problem can be written in \(\LaTeX\) as follows:

[ \text{result} = \left| { p \mid p = S[i:i+K], ; 0 \leq i \leq |S|-K \text{ and } p = p^R } \right| ]

where \(p^R\) is the reverse of the substring \(p\) and \(|S|\) denotes the length of string \(S\).

inputFormat

The input is given from STDIN and consists of two lines:

• The first line contains the string S.
• The second line contains the integer K.

It is guaranteed that \(1 \leq K \leq |S|\) and \(S\) consists only of lowercase English letters.

outputFormat

Output the number of distinct palindromic substrings of length exactly K to STDOUT.

## sample

abacaba
3

2

</p>